Performance: sets vs dicts.

[Paul Rubin]

aahz at pythoncraft.com (Aahz) writes:
> 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?

It's O(1) with reasonable input distributions but can be O(N) for
adverse distributions.  The docs should say something like that, and
include this link:

http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003/index.html