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

[Steven D'Aprano]

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 really quite 
unfortunate to have dicts and sets able to access keys in (almost) 
constant time, but not be able to communicate that key back to the 
caller except by walking the entire dict/set.

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, 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