Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #93055 > unrolled thread

Re: Looking up a dictionary _key_ by key?

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Looking up a dictionary _key_ by key? Chris Angelico <rosuav@gmail.com> - 2015-06-24 11:02 +1000
    Re: Looking up a dictionary _key_ by key? Paul Rubin <no.email@nospam.invalid> - 2015-06-23 18:06 -0700
      Re: Looking up a dictionary _key_ by key? Ian Kelly <ian.g.kelly@gmail.com> - 2015-06-24 00:50 -0600
        Re: Looking up a dictionary _key_ by key? Marko Rauhamaa <marko@pacujo.net> - 2015-06-24 09:55 +0300
      Re: Looking up a dictionary _key_ by key? Laura Creighton <lac@openend.se> - 2015-07-05 08:25 +0200

#93055 — Re: Looking up a dictionary _key_ by key?

On Wed, Jun 24, 2015 at 10:47 AM, Dan Stromberg <drsalists@gmail.com> wrote:
> 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.

ChrisA

[toc] | [next] | [standalone]

#93057

Chris Angelico <rosuav@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.

[toc] | [prev] | [next] | [standalone]

#93065

On Tue, Jun 23, 2015 at 7:06 PM, Paul Rubin <no.email@nospam.invalid> wrote:
> Chris Angelico <rosuav@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.

I don't think that it's fundamentally broken. A simple example would
be the int 3, vs. the float 3, vs. the Decimal 3. All of them compare
equal to one another, but they are distinct values, and sometimes it
might be useful to be able to determine which one is actually a key in
the dict.

[toc] | [prev] | [next] | [standalone]

#93066

Ian Kelly <ian.g.kelly@gmail.com>:

> I don't think that it's fundamentally broken. A simple example would
> be the int 3, vs. the float 3, vs. the Decimal 3. All of them compare
> equal to one another, but they are distinct values, and sometimes it
> might be useful to be able to determine which one is actually a key in
> the dict.

One possibility is to enter the key on the value side as well:

    d[key] = (key, value)

    ...

    canonical_key, value = d[key]


Marko

[toc] | [prev] | [next] | [standalone]

#93503

In a message of Tue, 23 Jun 2015 18:06:45 -0700, Paul Rubin writes:
>Chris Angelico <rosuav@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.
>-- 
>https://mail.python.org/mailman/listinfo/python-list

This just showed up in my mailbox:

     Subject: [ANN] pyskiplist-1.0.0
     From:    Geert Jansen <geertj@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
https://github.com/geertj/pyskiplist
It's also available on PyPI.

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

Laura

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web