[Python-Dev] non-mutating 'choose' to go with 'dict.popitem'? (original) (raw)

Tim Peters tim.one@home.com
Sun, 6 May 2001 14:15:57 -0400

[Greg Wilson]

Has anyone else found themselves wanting a method that chooses and returns a dictionary element at random,

Do you mean "random" or "arbitrary"? "random" means every dict entry is equally likely to be chosen; "arbitrary" means nothing is defined about the result (except that it is a dict entry). random is much more expensive to implement (under the covers it's a vector, but a vector with holes, so you can't just pick a slot at random then "slide over" to the first non-hole (else a given entry's chance of being selected would be proportional to the # of contiguous holes adjacent to it)).

without removing it (as popitem does)?

Note that, in the sense above, popitem() returns an arbitrary element.

Or is there some way to tell popitem to return a value without mutating the container?

No. Easy to write an efficient function that does, though:

def arb(dict): k, v = pair = dict.popitem() dict[k] = v # restore the entry return pair

Given the new dict iterators in 2.2, there's an easier fast way that doesn't mutate the dict even under the covers:

def arb(dict): if dict: return dict.iteritems().next() raise KeyError("arb passed an empty dict")

If neither, would this be useful, or is it DHG?

Do you have a particular algorithm, or class of algorithms, in mind for which it is useful? popitem's current behavior is most useful for me in the set algorithms I've used, usually in the form:

while working_set:
    x, dontcare = working_set.popitem()
    process(x)  # which may add more elts to working_set