Comment récupérer un élément d’un ensemble sans le supprimer ?
https://stackoverflow.com/questions/59825
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Supposons ce qui suit :
>>> s = set([1, 2, 3])
Comment puis-je obtenir une valeur (n'importe quelle valeur) de s sans faire s.pop()?Je souhaite laisser l'élément dans l'ensemble jusqu'à ce que je sois sûr de pouvoir le supprimer - ce dont je ne peux être sûr qu'après un appel asynchrone vers un autre hôte.
Rapide et sale:
>>> elem = s.pop()
>>> s.add(elem)
Mais connaissez-vous un meilleur moyen ?Idéalement en temps constant.
La solution
Deux options qui ne nécessitent pas de copier l'ensemble :
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.
Autres conseils
Le moins de code serait :
>>> s = set([1, 2, 3])
>>> list(s)[0]
1
Évidemment, cela créerait une nouvelle liste contenant chaque membre de l'ensemble, donc ce n'est pas génial si votre ensemble est très grand.
Pour fournir quelques chiffres de timing derrière les différentes approches, considérons le code suivant.Le get() est mon ajout personnalisé au setobject.c de Python, étant juste un pop() sans supprimer 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()
Le résultat 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/pause La solution est la plus rapide (parfois plus rapide que la solution personnalisée get()).
tl;dr
for first_item in muh_set: break reste l'approche optimale dans Python 3.x. Je te maudis, Guido.
tu fais ça
Bienvenue dans un autre ensemble de timings Python 3.x, extrapolés à partir de wr.c'est excellent Réponse spécifique à Python 2.x.Contrairement à Un championc'est tout aussi utile Réponse spécifique à Python 3.x, les horaires ci-dessous aussi solutions pour les valeurs aberrantes dans le temps suggérées ci-dessus, notamment :
list(s)[0], Johnle roman solution basée sur la séquence.random.sample(s, 1), dF.c'est éclectique Solution basée sur RNG.
Des extraits de code pour une grande joie
Allumez, connectez-vous, chronométrez :
from timeit import Timer
stats = [
"for i in range(1000): \n\tfor x in s: \n\t\tbreak",
"for i in range(1000): next(iter(s))",
"for i in range(1000): s.add(s.pop())",
"for i in range(1000): list(s)[0]",
"for i in range(1000): random.sample(s, 1)",
]
for stat in stats:
t = Timer(stat, setup="import random\ns=set(range(100))")
try:
print("Time for %s:\t %f"%(stat, t.timeit(number=1000)))
except:
t.print_exc()
Des timings intemporels rapidement obsolètes
Voir! Classés des extraits les plus rapides aux plus lents :
$ ./test_get.py
Time for for i in range(1000):
for x in s:
break: 0.249871
Time for for i in range(1000): next(iter(s)): 0.526266
Time for for i in range(1000): s.add(s.pop()): 0.658832
Time for for i in range(1000): list(s)[0]: 4.117106
Time for for i in range(1000): random.sample(s, 1): 21.851104
Des plantes faciales pour toute la famille
Sans surprise, l'itération manuelle reste au moins deux fois plus rapide comme la prochaine solution la plus rapide.Bien que l'écart ait diminué depuis l'époque de Bad Old Python 2.x (au cours de laquelle l'itération manuelle était au moins quatre fois plus rapide), il déçoit le PPE 20 fanatique en moi, je pense que la solution la plus verbeuse est la meilleure.Au moins convertir un ensemble en liste juste pour extraire le premier élément de l'ensemble est aussi horrible que prévu. Merci Guido, que sa lumière continue à nous guider.
Étonnamment, le La solution basée sur RNG est absolument horrible. La conversion de liste est mauvaise, mais random vraiment prend le gâteau à la sauce horrible.Voilà pour le Dieu des nombres aléatoires.
Je souhaite juste que les amorphes s'énervent set.get_first() méthode pour nous déjà.Si vous lisez ceci, ils :"S'il te plaît.Faire quelque chose."
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 liste énorme et un ensemble énorme, 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 convertissez-le d'abord en liste :
>>> lst = list(s) # once, O(len(s))?
...
>>> e = random.sample(lst, 1)[0] # constant time
Je me demandais comment les fonctions fonctionneraient pour différents ensembles, j'ai donc fait un benchmark :
from random import sample
def ForLoop(s):
for e in s:
break
return e
def IterNext(s):
return next(iter(s))
def ListIndex(s):
return list(s)[0]
def PopAdd(s):
e = s.pop()
s.add(e)
return e
def RandomSample(s):
return sample(s, 1)
def SetUnpacking(s):
e, *_ = s
return e
from simple_benchmark import benchmark
b = benchmark([ForLoop, IterNext, ListIndex, PopAdd, RandomSample, SetUnpacking],
{2**i: set(range(2**i)) for i in range(1, 20)},
argument_name='set size',
function_aliases={first: 'First'})
b.plot()
Ce graphique montre clairement que certaines approches (RandomSample, SetUnpacking et ListIndex) dépendent de la taille de l'ensemble et doivent être évités dans le cas général (du moins si les performances pourrait être important).Comme déjà montré par les autres réponses, le moyen le plus rapide est ForLoop.
Cependant, tant que l'une des approches à temps constant est utilisée, la différence de performances sera négligeable.
iteration_utilities (Clause de non-responsabilité:Je suis l'auteur) contient une fonction pratique pour ce cas d'utilisation : first:
>>> from iteration_utilities import first
>>> first({1,2,3,4})
1
Je l'ai également inclus dans le benchmark ci-dessus.Elle peut rivaliser avec les deux autres solutions « rapides », mais la différence n’est pas grande dans les deux cas.
J'utilise une fonction utilitaire que j'ai écrite.Son nom est quelque peu trompeur car il implique en quelque sorte qu'il pourrait s'agir d'un élément aléatoire ou quelque chose comme ça.
def anyitem(iterable):
try:
return iter(iterable).next()
except StopIteration:
return None
Apparemment le le plus compact (6 symboles) cependant très lent moyen d'obtenir un élément d'ensemble (rendu possible par PEP 3132):
e,*_=s
Avec Python 3.5+ vous pouvez également utiliser cette expression à 7 symboles (grâce à PPE 448):
[*s][0]
Les deux options sont environ 1 000 fois plus lentes sur ma machine que la méthode de la boucle for.
Suite à @wr.post, j'obtiens des résultats similaires (pour Python3.5)
from timeit import *
stats = ["for i in range(1000): next(iter(s))",
"for i in range(1000): \n\tfor x in s: \n\t\tbreak",
"for i in range(1000): s.add(s.pop())"]
for stat in stats:
t = Timer(stat, setup="s=set(range(100000))")
try:
print("Time for %s:\t %f"%(stat, t.timeit(number=1000)))
except:
t.print_exc()
Sortir:
Time for for i in range(1000): next(iter(s)): 0.205888
Time for for i in range(1000):
for x in s:
break: 0.083397
Time for for i in range(1000): s.add(s.pop()): 0.226570
Cependant, lors de la modification de l'ensemble sous-jacent (par ex.appeler pour remove()) les choses se passent mal pour les exemples itérables (for, iter):
from timeit import *
stats = ["while s:\n\ta = next(iter(s))\n\ts.remove(a)",
"while s:\n\tfor x in s: break\n\ts.remove(x)",
"while s:\n\tx=s.pop()\n\ts.add(x)\n\ts.remove(x)"]
for stat in stats:
t = Timer(stat, setup="s=set(range(100000))")
try:
print("Time for %s:\t %f"%(stat, t.timeit(number=1000)))
except:
t.print_exc()
Résulte en:
Time for while s:
a = next(iter(s))
s.remove(a): 2.938494
Time for while s:
for x in s: break
s.remove(x): 2.728367
Time for while s:
x=s.pop()
s.add(x)
s.remove(x): 0.030272
Que diriez-vous s.copy().pop()?Je ne l'ai pas chronométré, mais ça devrait marcher et c'est simple.Cependant, cela fonctionne mieux pour les petits ensembles, car il copie l’ensemble de l’ensemble.
Une autre option consiste à utiliser un dictionnaire avec des valeurs qui ne vous intéressent pas.Par exemple.,
poor_man_set = {}
poor_man_set[1] = None
poor_man_set[2] = None
poor_man_set[3] = None
...
Vous pouvez traiter les clés comme un ensemble, sauf qu'elles ne sont qu'un tableau :
keys = poor_man_set.keys()
print "Some key = %s" % keys[0]
Un effet secondaire de ce choix est que votre code sera rétrocompatible avec les versions antérieures et antérieures.set versions de Python.Ce n'est peut-être pas la meilleure réponse, mais c'est une autre option.
Modifier:Vous pouvez même faire quelque chose comme ceci pour masquer le fait que vous avez utilisé un dict au lieu d'un tableau ou d'un ensemble :
poor_man_set = {}
poor_man_set[1] = None
poor_man_set[2] = None
poor_man_set[3] = None
poor_man_set = poor_man_set.keys()
