[Python-ideas] Add dict.getkey() and set.get()

[David Mertz]

>
> On Sat, Sep 14, 2013 at 09:52:30AM -0700, David Mertz wrote:
> > def getexact(m, v):
> >     for x in m:
> >         if x==v: return x
> >     else:
> >         raise KeyError(v)
>
> This has the flaw that it is O(N) rather than O(1).


It's true, it is relatively inefficient.  But we also don't have a use case
where we actually need to do this enough that it matters.


> Now O(N) is tolerable if all you want to do is retrieve the canonical
> version of a single key. But if you want to do so for *all* of the keys
> in the dict, the naive way to do it ends up walking the dict for
> each key,


I thought the naive way to retrieve ALL the keys (in canonical form) was
'mydict.keys()'. :-)

I'm sure you can spin other variations on this.  Here's all the keys except
one, removed using a non-canonical equivalent value:

>>> {1:2, 3:4, 5:6, 7:8}.keys() - {Decimal(1.0)}
{3, 5, 7}

It's true though that I can't think of an efficient way to get the
canonical form of a key from a dictionary in O(1).  But also I think it is
rare enough not to worry, and TransformDict is a good specialization that
will do this in those unusual cases where we care.


> giving O(N**2) in total. Is there a non-naive way to speed
> this up? I haven't had breakfast yet so I can't think of one :-)
>
> My feeling here is that for ordinary dicts, needing to retrieve the
> canonical key is rare enough that they don't need a dedicated method to
> do so. But for the TransformDict suggested on the python-dev list, it
> will be a common need, and deserves an O(1) lookup method.
>
>
>
> --
> Steven
> _______________________________________________
> Python-ideas mailing list
> Python-ideas at python.org
> https://mail.python.org/mailman/listinfo/python-ideas
>



-- 
Keeping medicines from the bloodstreams of the sick; food
from the bellies of the hungry; books from the hands of the
uneducated; technology from the underdeveloped; and putting
advocates of freedom in prisons.  Intellectual property is
to the 21st century what the slave trade was to the 16th.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20130914/f376bedd/attachment-0001.html>