Path: csiph.com!usenet.pasdenom.info!aioe.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <5024392D.3010306@davea.name>
References: <930ab3d8-4ab9-446d-9970-ee811eb70a44@googlegroups.com> <F1B463BB-19A6-4DB1-99B3-929CCBFB5920@gmail.com> <50241F14.2060209@tim.thechases.com> <36EA3847-6713-4C12-B47B-9B5E10325F00@gmail.com> <502429C3.5000600@tim.thechases.com> <mailman.3120.1344548050.4697.python-list@python.org> <MsWUr.1183213$%k.489563@fx20.am4> <5024392D.3010306@davea.name>
From: Chris Kaynor <ckaynor@zindagigames.com>
Date: Thu, 9 Aug 2012 15:37:59 -0700
Subject: Re: save dictionary to a file without brackets.
To: python-list@python.org
Content-Type: text/plain; charset=ISO-8859-1
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.3131.1344551903.4697.python-list@python.org>
Lines: 48
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:26827

On Thu, Aug 9, 2012 at 3:26 PM, Dave Angel <d@davea.name> wrote:
> 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?

There are plenty of ways to make a pathological hash function that
will have that issue in CPython.

The very simple (and stupid):

class O(object):
    def __hash__(self):
        return 0
    def __eq__(self, other): # I am aware this is the default equals method.
        return self is other

Start adding those to a dictionary to get O(n) lookups.

Any case the hash return values modulus the dictionary hash table size
is constant will have similar results; powers of 2 are likely to
result in such behavior as well.

>
> --
>
> DaveA
>
> --
> http://mail.python.org/mailman/listinfo/python-list