[Python-Dev] Retrieve an arbitrary element from a set withoutremoving it

[Guido van Rossum]

On Tue, Nov 3, 2009 at 2:46 PM, Steven D'Aprano <steve at pearwood.info> wrote:
> On Tue, 3 Nov 2009 09:19:38 am Greg Ewing wrote:
>> Cameron Simpson wrote:
>> > Personally, I'm for the iteration spec in a lot of ways.
>> >
>> > Firstly, a .get()/.pick() that always returns the same element
>> > feels horrible. Is there anyone here who _likes_ it?
>>
>> It doesn't sound very useful to me. However, an iterating
>> version of it doesn't sound any more useful. What would it
>> gain you? Why not just iterate over the set? Or make a
>> copy and repeatedly pop() it?
>
> Since I was the person who decided that "arbitrary" meant "give a
> different result each time", I should answer that.
>
> My intention was not that people should use repeated calls to pick() for
> iteration. I described that as an abuse of the method. But I can
> imagine scenarios where the caller calls set.pick() sequentially:
>
> def pick_two_cards(hand):
>    assert isinstance(hand, (set, frozenset))
>    assert len(hand) == 5
>    return (hand.pick(), hand.pick())
>
>
> As I said in a reply to Raymond, optimization was not my primary
> concern, but as a fundamental set operation[1] pick() should be
> efficient. It may be called on a set with millions of items, not just
> small sets. Copying to another set, or to a list, will be O(N) and
> potentially slow -- at the very least, it is wasteful to copy millions
> of elements in order to access one.
>
> I don't know how expensive it is to create a set iterator, but (my
> reasoning went) surely we can do better? The set already has access to
> its own elements, it just needs to return one of them. pop() also knows
> how to retrieve an arbitrary element. pick() is just like pop(), except
> without removal.
>
>
>> I completely fail to see a use case for this.
>
> Nevertheless, people keep requesting it, so obviously they have a use
> for it. None of the standard solutions are obvious or easily
> discoverable, and in my experience the usual solution people come up
> with is to pop() an element, then add() it back in, but of course
> that's not just inelegant but it fails on frozensets.
>
>
>
> [1] Obviously there is disagreement on whether or not pick() is a
> fundamental operation or not. As Raymond points out, it is uncommon in
> other languages. But Wikipedia lists it as fundamental, and it is not
> just Python users who ask for it:
>
> http://stackoverflow.com/questions/124671/picking-a-random-element-from-a-set

You're obviously talking about a *random* element. This is a separate
use case (though I agree many people don't know the difference).

Picking a random element can be done in O(1) only if the data
structure supports access by index, which Python's hash tables don't.

-- 
--Guido van Rossum (python.org/~guido)