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

[Steven D'Aprano]

On Sat, 24 Oct 2009 08:12:26 pm Martin (gzlist) wrote:

> On 24/10/2009, Nick Coghlan <ncoghlan at gmail.com> wrote:
> > Ben Finney wrote:
> >> Which then raises the question “what part of the set does it
> >> get?”, which the function signature does nothing to answer. I'm
> >> proposing that a no-parameters ‘set.get’ is needlessly confusing
> >> to think about.
> >
> > The fact that set.get() is just set.pop() without removing the
> > result from the set seems perfectly straightforward.
>
> There's a different proposed meaning for `set.get` that's been
> discussed on python-dev before:
>
> <http://mail.python.org/pipermail/python-dev/2009-April/088128.html>

That thread has an example of a use-case for extracting an item from a 
set, given the item itself: interning.

The current Python idiom for interning is to use a dict:

# store the canonical version
_cache[item] = item

# retrieve the interned version
item = _cache[item]

It has been argued that such interning is better done by sets rather 
than dicts, since this will save a pointer per item (plus any 
additional overhead dicts may have over that of sets). If this argument 
is accepted, then we want a fast, efficient operation to perform this:

def get(self, item):
    """Return an element of the set equal to item.
    Useful for retrieving the canonical version of an element 
    and for interning.
    """
    for x in self:
        if x == item:
            return x
    raise ValueError('item not in set')


The above is O(N); ideally it should be O(1).

Normally we don't care about identity, only equality, so if x and item 
above are equal we are indifferent about which one we use. But 
interning is a real example of a use-case where we do care about 
identity. Arguably it is inefficient and wasteful to use a dict for 
interning when sets could be just as fast while using less memory.

The other proposed semantics for set.get() are to retrieve an arbitrary 
element. It must be arbitrary, because elements in a set are unordered 
and unkeyed. This gives us the semantics of pop() without removing the 
element:

def get(self):
    """Return an arbitrary element of the set without removing it."""
    for x in self:
        return x
    raise ValueError("empty set")

This is a frequent request, but I still don't know what the use-case is.

If you'll excuse me stating the obvious, both of these can easily be 
written as helper-functions. The main arguments for making them methods 
are:

(1) The first one is needlessly O(N) when it could be O(1).

(2) The second one is apparently a common need (although I personally 
have never needed it), forcing people to re-invent the wheel, sometimes 
incorrectly or inefficiently, e.g.:

def get(aset):
    for element in aset:
        pass
    return element



-- 
Steven D'Aprano