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

[Andrew Barnert]

On Sep 15, 2013, at 18:39, Terry Reedy <tjreedy at udel.edu> wrote:

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

But it doesn't happen for dict_keys, because that ends up calling intersection_update on a copy of the left operand, which means it always walks the right operand (in this case the dict_keys itself), instead of calling set_intersection, as it would on two sets.

At any rate, whenever this does what's desired, it does a linear walk of all keys in the dict; conversely, any variant that only walks the single key in {k} ends up returning {k} instead of what you were looking for.