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

[Tim Peters]

[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