Performance: sets vs dicts.

[Raymond Hettinger]

On Aug 30, 6:03 am, a... at pythoncraft.com (Aahz) wrote:
> That reminds me: one co-worker (who really should have known better ;-)
> had the impression that sets were O(N) rather than O(1).  Although
> writing that off as a brain-fart seems appropriate, it's also the case
> that the docs don't really make that clear, it's implied from requiring
> elements to be hashable.  Do you agree that there should be a comment?

There probably ought to be a HOWTO or FAQ entry on algorithmic
complexity
that covers classes and functions where the algorithms are
interesting.
That will concentrate the knowledge in one place where performance is
a
main theme and where the various alternatives can be compared and
contrasted.

I think most users of sets rarely read the docs for sets.  The few
lines
in the tutorial are enough so that most folks "just get it" and don't
read
more detail unless they attempting something exotic.   Our docs have
gotten
somewhat voluminous, so it's unlikely that adding that particular
needle to the haystack would have cured your colleague's "brain-fart"
unless he had been focused on a single document talking about the
performance
characteristics of various data structures.


Raymond

Raymond