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

Terry Reedy tjreedy at udel.edu
Mon Sep 16 03:39:34 CEST 2013


On 9/15/2013 8:30 PM, Steven D'Aprano wrote:
> 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?

No, just the keys in one of the operands. That can be chosen to be the 
smaller of the two, making it O(min(M,N)). I believe that is what is 
happening above: the operands are switched when the first is smaller. I 
know there was a tracker issue that added this optimization.

-- 
Terry Jan Reedy



More information about the Python-ideas mailing list