Looking up a dictionary _key_ by key?

Laura Creighton lac at openend.se
Sun Jul 5 08:25:38 CEST 2015

In a message of Tue, 23 Jun 2015 18:06:45 -0700, Paul Rubin writes:
>Chris Angelico <rosuav at gmail.com> writes:
>>> Would I have to do an O(n) search to find my key?
>> Iterate over it - it's an iterable view in Py3 - and compare.
>I think the question was whether the O(n) search could be avoided, not
>how to do it.  I don't see a way to avoid it.  There is fundamental
>brokenness in having unequal objects compare as equal, and the breakage
>messes up the dictionary when those objects are used as keys.
>Solution is to either fix the object equality test, or wrap them in
>something (maybe a tuple containing the objects and the distinguishing
>fields that are missing from the original object's equality method) that
>treats unequal objects as unequal.

This just showed up in my mailbox:

     Subject: [ANN] pyskiplist-1.0.0
     From:    Geert Jansen <geertj at gmail.com>

     PySkipList is a fast, pure Python implementation of an indexable
     skiplist. It implements a SkipList data structure that provides an
     always sorted, list-like data structure for (key, value) pairs.

... more details including timing.  For the full text see
It's also available on PyPI.

Looks to me as if he's fixed the 0(n) problem ....


More information about the Python-list mailing list