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

[Steven D'Aprano]

On Sun, Sep 15, 2013 at 09:02:33PM +0100, Oscar Benjamin wrote:

> I don't know whether this is relying on undefined behaviour but the
> following is O(1) and seems to work:
> 
> >>> def canonical_key(d, k):
> ...     k, = {k} & d.keys()
> ...     return k
> ...

I'm pretty sure that (1) it relies on implementation-specific behaviour, 
and (2) it's O(N), not O(1).

The implementation-specific part is whether & takes the key from the 
left-hand or right-hand operand when the keys are equal. For example, in 
Python 3.3:

py> {1} & {1.0}
{1.0}
py> {1} & {1.0, 2.0}
{1}

And surely it's O(N) -- to be precise, O(M+N) -- because & has to walk 
all the keys in both operands? I suppose technically & could special 
case "one of the operands has length 1" and optimize it, but that too 
would be an implementation detail.



-- 
Steven