[Python-ideas] set.add() return value

[Adam Olsen]

On Thu, Feb 12, 2009 at 8:36 PM, Ralf W. Grosse-Kunstleve
<rwgk at yahoo.com> wrote:
> Of course, the memory cache does have an influence here, but
> your claim is also at odds with anything I could find in the
> literature. A dictionary or set has to do some kind of search to
> find a key or element. Dictionary and set lookups have O(log N)
> runtime complexity, where N is the size of the dict or set at
> the time of the lookup.

The literature you found was assuming a binary tree implementation,
which is O(log n).  Python's dict and set use a hash table, which is
O(1).  The performance effect you found was because of the CPU's
cache.

Besides, you really should use more than 2 samples if you want to show
an O(log n) performance curve.


-- 
Adam Olsen, aka Rhamphoryncus