On 08/09/2012 06:03 PM, Andrew Cooper wrote:
> On 09/08/2012 22:34, Roman Vashkevich wrote:
>> Actually, they are different.
>> Put a dict.{iter}items() in an O(k^N) algorithm and make it a hundred
>> thousand entries, and you will feel the difference.
>> Dict uses hashing to get a value from the dict and this is why it's O(1).
>>
> Sligtly off topic, but looking up a value in a dictionary is actually
> O(n) for all other entries in the dict which suffer a hash collision
> with the searched entry.
>
> True, a sensible choice of hash function will reduce n to 1 in common
> cases, but it becomes an important consideration for larger datasets.
>
> ~Andrew
I'm glad you're wrong for CPython's dictionaries. The only time the
lookup would degenerate to O[n] would be if the hash table had only one
slot. CPython sensibly increases the hash table size when it becomes
too small for efficiency.
Where have you seen dictionaries so poorly implemented?
--
DaveA
--
http://mail.python.org/mailman/listinfo/python-list
