Comment récupérer un élément d'un ensemble sans le supprimer ?

Question

Supposons ce qui suit :

>>> s = set([1, 2, 3])

Comment obtenir une valeur (n'importe quelle valeur) à partir de s sans faire s.pop() ? Je veux laisser l'élément dans l'ensemble jusqu'à ce que je sois sûr de pouvoir le retirer - ce dont je ne peux être sûr qu'après un appel asynchrone à un autre hôte.

Rapide et sale :

>>> elem = s.pop()
>>> s.add(elem)

Mais connaissez-vous un meilleur moyen ? Idéalement en temps constant.

Answer 1

Deux options qui ne nécessitent pas de copier l'ensemble du jeu :

for e in s:
    break
# e is now an element from s

Ou...

e = next(iter(s))

Mais en général, les ensembles ne prennent pas en charge l'indexation ou le découpage en tranches.

Answer 2

Le code le plus faible serait :

>>> s = set([1, 2, 3])
>>> list(s)[0]
1

Évidemment, cela créerait une nouvelle liste contenant chaque membre de l'ensemble, ce qui n'est pas idéal si votre ensemble est très grand.

Answer 3

Pour donner quelques chiffres sur le timing des différentes approches, considérons le code suivant. Le get() est mon ajout personnalisé au setobject.c de Python, étant juste un pop() sans enlever l'élément.

from timeit import *

stats = ["for i in xrange(1000): iter(s).next()   ",
         "for i in xrange(1000): \n\tfor x in s: \n\t\tbreak",
         "for i in xrange(1000): s.add(s.pop())   ",
         "for i in xrange(1000): s.get()          "]

for stat in stats:
    t = Timer(stat, setup="s=set(range(100))")
    try:
        print "Time for %s:\t %f"%(stat, t.timeit(number=1000))
    except:
        t.print_exc()

La sortie est :

$ ./test_get.py
Time for for i in xrange(1000): iter(s).next()   :       0.433080
Time for for i in xrange(1000):
        for x in s:
                break:   0.148695
Time for for i in xrange(1000): s.add(s.pop())   :       0.317418
Time for for i in xrange(1000): s.get()          :       0.146673

Cela signifie que le pour/briser est la solution la plus rapide (parfois plus rapide que la solution personnalisée get()).

Answer 4

Puisque vous voulez un élément aléatoire, cela fonctionnera également :

>>> import random
>>> s = set([1,2,3])
>>> random.sample(s, 1)
[2]

La documentation ne semble pas mentionner les performances de random.sample . D'après un test empirique très rapide avec une énorme liste et un énorme ensemble, il semble que le temps soit constant pour une liste mais pas pour l'ensemble. De plus, l'itération sur un ensemble n'est pas aléatoire ; l'ordre est indéfini mais prévisible :

>>> list(set(range(10))) == range(10)
True 

Si le caractère aléatoire est important et que vous avez besoin d'un tas d'éléments en temps constant (grands ensembles), j'utiliserais random.sample et convertir en liste d'abord :

>>> lst = list(s) # once, O(len(s))?
...
>>> e = random.sample(lst, 1)[0] # constant time

Answer 5

J'utilise une fonction utilitaire que j'ai écrite. Son nom est quelque peu trompeur car il laisse entendre qu'il pourrait s'agir d'un élément aléatoire ou quelque chose du genre.

def anyitem(iterable):
    try:
        return iter(iterable).next()
    except StopIteration:
        return None