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

429

Supposons ce qui suit:

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

Comment puis-je obtenir une valeur (n'importe quelle valeur) ssans le faire s.pop()? Je veux laisser l'élément dans l'ensemble jusqu'à ce que je sois sûr de pouvoir le supprimer - quelque chose 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.

Daren Thomas
la source
8
Quelqu'un sait pourquoi python n'a pas déjà cette fonction implémentée?
hlin117
Quel est le cas d'utilisation? Set n'a pas cette capacité pour une raison. Vous êtes censé le parcourir et effectuer des opérations liées à un ensemble comme unionetc sans en retirer des éléments. Par exemple, next(iter({3,2,1}))renvoie toujours 1donc si vous pensiez que cela retournerait un élément aléatoire - ce ne serait pas. Alors peut-être utilisez-vous simplement la mauvaise structure de données? Quel est le cas d'utilisation?
user1685095
1
Connexe: stackoverflow.com/questions/20625579/… (Je sais, ce n'est pas la même question, mais il y a des alternatives et des idées intéressantes là-bas.)
John Y
@ hlin117 Parce que set est une collection non ordonnée . Puisqu'aucun ordre n'est attendu, cela n'a aucun sens de récupérer un élément à une position donnée - il devrait être aléatoire.
Jeyekomon

Réponses:

548

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

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.

Blair Conrad
la source
4
Cela répond à ma question. Hélas, je suppose que j'utiliserai toujours pop (), car l'itération semble trier les éléments. Je les préférerais dans un ordre aléatoire ...
Daren Thomas
9
Je ne pense pas que l'iter () trie les éléments - lorsque je crée un ensemble et pop () jusqu'à ce qu'il soit vide, j'obtiens un ordre cohérent (trié, dans mon exemple), et c'est la même chose que l'itérateur - pop ( ) ne promet pas un ordre aléatoire, juste arbitraire, comme dans "Je ne promets rien".
Blair Conrad,
2
+1 iter(s).next()n'est pas grossier mais super. Complètement général pour prendre un élément arbitraire de tout objet itérable. Votre choix si vous voulez être prudent si la collection est vide.
u0b34a0f6ae
8
suivant (iter (s)) est également OK et j'ai tendance à penser qu'il se lit mieux. En outre, vous pouvez utiliser une sentinelle pour gérer le cas lorsque s est vide. Par exemple next (iter (s), set ()).
ja
5
next(iter(your_list or []), None)pour gérer les ensembles Aucun et les ensembles vides
MrE
112

Le moins de code serait:

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

Évidemment, cela créerait une nouvelle liste qui contient chaque membre de l'ensemble, donc pas génial si votre ensemble est très grand.

John
la source
97
next(iter(s))ne dépasse que list(s)[0]de trois caractères et est par ailleurs considérablement supérieur en termes de complexité temporelle et spatiale. Ainsi, alors que la revendication du "moindre code" est trivialement vraie, il est également trivialement vrai que c'est la pire approche possible. Même supprimer manuellement puis rajouter l'élément supprimé à l'ensemble d'origine est supérieur à «construire un tout nouveau conteneur juste pour extraire le premier élément», ce qui est manifestement fou. Ce qui me préoccupe le plus, c'est que 38 Stackoverflowers ont voté en faveur de cela. Je sais juste que je verrai cela dans le code de production.
Cecil Curry
19
@augurar: Parce que cela fait le travail d'une manière relativement simple. Et parfois, c'est tout ce qui compte dans un script rapide.
tonysdg
4
@Vicrobot Oui, mais il le fait en copiant la collection entière et en transformant une opération O (1) en une opération O (n). C'est une terrible solution que personne ne devrait jamais utiliser.
augurar
9
De plus, si vous visez simplement le "moins de code" (ce qui est stupide), utilisez min(s)encore moins de caractères tout en étant aussi terrible et inefficace que cela.
augurar
5
+1 pour le gagnant de golf de code, que j'ai un contre-exemple pratique pour être "terrible et inefficace": min(s)est légèrement plus rapide que next(iter(s))pour les ensembles de taille 1, et je suis venu à cette réponse en recherchant spécifiquement un cas spécial en extrayant le seul élément des ensembles de taille 1.
lehiester
52

Je me demandais comment les fonctions fonctionneraient pour différents ensembles, alors j'ai fait un test de performance:

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()

entrez la description de l'image ici

Ce graphique montre clairement que certaines approches ( RandomSample, SetUnpackinget ListIndex) dépendent de la taille de l'ensemble et doivent être évitées dans le cas général (au moins si les performances peuvent être importantes). Comme l'ont déjà montré les autres réponses, le moyen le plus rapide est ForLoop.

Cependant, tant qu'une des approches à temps constant est utilisée, la différence de performances sera négligeable.


iteration_utilities(Avertissement: 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 l'indice de référence ci-dessus. Il peut rivaliser avec les deux autres solutions «rapides», mais la différence n'est pas grande dans les deux cas.

MSeifert
la source
43

tl; dr

for first_item in muh_set: breakreste 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é à partir de wr. est une excellente réponse spécifique à Python 2.x . Contrairement à AChampion réponse spécifique à Python 3.x tout aussi utile d' , les délais ci-dessous temporisent également les solutions aberrantes suggérées ci-dessus - y compris:

Extraits de code pour Great Joy

Allumez, syntonisez, 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()

Timings intemporels rapidement obsolètes

Voir! Ordonné par 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

Plantes faciales pour toute la famille

Sans surprise, l' itération manuelle reste au moins deux fois plus rapide que la solution la plus rapide suivante. Bien que l'écart ait diminué depuis les jours Bad Old Python 2.x (au cours desquels l'itération manuelle était au moins quatre fois plus rapide), il déçoit en moi le fanatique PEP 20 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 de nous guider.

Étonnamment, la solution basée sur RNG est absolument horrible. La conversion de liste est mauvaise, mais prend random vraiment le gâteau de sauce horrible. Voilà pour le Dieu du nombre aléatoire .

Je souhaite juste aux amorphes qu'ils auraient PEP une set.get_first()méthode pour nous déjà. Si vous lisez ceci, ils: "S'il vous plaît. Faites quelque chose."

Cecil Curry
la source
2
Je pense que ce plaignant next(iter(s)) est deux fois plus lent que for x in s: breakdans CPythonest un peu étrange. Je veux dire que oui CPython. Ce sera environ 50-100 fois (ou quelque chose comme ça) plus lent que C ou Haskell faisant la même chose (pour la plupart du temps, surtout en itération, pas d'élimination des appels de queue et aucune optimisation que ce soit). La perte de quelques microsecondes ne fait pas vraiment de différence. Tu ne crois pas? Et il y a aussi PyPy
user1685095
39

Pour fournir des chiffres de synchronisation derrière les différentes approches, considérez 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()

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 la solution for / break est la plus rapide (parfois plus rapide que la solution get () personnalisée).

wr.
la source
Quelqu'un at-il une idée pourquoi iter (s) .next () est tellement plus lent que les autres possibilités, encore plus lent que s.add (s.pop ())? Pour moi, cela ressemble à une très mauvaise conception de iter () et next () si les horaires ressemblent à ça.
peschü
Eh bien pour celui-ci, cette ligne crée un nouvel objet iter à chaque itération.
Ryan
3
@Ryan: Un objet itérateur n'est-il pas créé implicitement for x in saussi? "Un itérateur est créé pour le résultat de la expression_list."
musiphil
2
@musiphil C'est vrai; à l'origine, j'ai manqué le "break" étant à 0,14, c'est vraiment contre-intuitif. Je veux approfondir cela quand j'aurai le temps.
Ryan
1
Je sais que c'est vieux, mais quand on ajoute s.remove()au mélange les iterexemples à la fois foret que iterça va terriblement mal.
AChampion du
28

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. À partir d'un test empirique très rapide avec une liste énorme et un ensemble énorme, il semble qu'il soit temps 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.sampleet convertirais d'abord en liste:

>>> lst = list(s) # once, O(len(s))?
...
>>> e = random.sample(lst, 1)[0] # constant time
dF.
la source
14
Si vous voulez juste un élément, random.choice est plus sensé.
Gregg Lind
list (s) .pop () fera l'affaire si vous ne vous souciez pas de l'élément à prendre.
Evgeny
8
@Gregg: Vous ne pouvez pas utiliser choice(), car Python essaiera d'indexer votre ensemble et cela ne fonctionne pas.
Kevin
3
Bien qu'intelligent, c'est en fait la solution la plus lente à ce jour suggérée par un ordre de grandeur. Oui, c'est si lent. Même la conversion de l'ensemble en liste juste pour extraire le premier élément de cette liste est plus rapide. Pour les non-croyants parmi nous ( ... salut! ), Voir ces horaires fabuleux .
Cecil Curry
9

Apparemment le moyen le plus compact (6 symboles) mais très lent pour obtenir un élément set (rendu possible par PEP 3132 ):

e,*_=s

Avec Python 3.5+, vous pouvez également utiliser cette expression à 7 symboles (grâce à PEP 448 ):

[*s][0]

Les deux options sont environ 1000 fois plus lentes sur ma machine que la méthode for-loop.

skovorodkin
la source
1
La méthode de la boucle for (ou plus précisément la méthode itérateur) a une complexité temporelle O (1), tandis que ces méthodes sont O (N). Ils sont cependant concis . :)
ForeverWintr
6

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
pseudo
la source
2
Vous pouvez également utiliser le suivant (iter (itérable), Aucun) pour économiser de l'encre :)
1 ''
3

Après @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()

Production:

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 du changement de l'ensemble sous-jacent (par exemple l'appel à remove()), les choses vont 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
Un champion
la source
1

Ce que je fais habituellement pour les petites collections, c'est de créer une sorte de méthode analyseur / convertisseur comme celle-ci

def convertSetToList(setName):
return list(setName)

Ensuite, je peux utiliser la nouvelle liste et accéder par numéro d'index

userFields = convertSetToList(user)
name = request.json[userFields[0]]

En tant que liste, vous aurez toutes les autres méthodes avec lesquelles vous devrez peut-être travailler

Josué Carvajal
la source
pourquoi ne pas simplement utiliser listau lieu de créer une méthode de conversion?
Daren Thomas
-1

Et alors 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 entier.

Solomon Ucko
la source
-6

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 anciennes setversions antérieures de Python. Ce n'est peut-être pas la meilleure réponse, mais c'est une autre option.

Edit: Vous pouvez même faire quelque chose comme ça pour cacher 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()
Pat Notz
la source
3
Cela ne fonctionne pas comme vous l'espérez. En python 2, keys () est une opération O (n), donc vous n'êtes plus à temps constant, mais au moins keys [0] renverra la valeur attendue. En python 3, les touches () sont des opérations O (1), alors oui! Cependant, il ne retourne plus un objet liste, il retourne un objet de type ensemble qui ne peut pas être indexé, donc les touches [0] lèveraient TypeError. stackoverflow.com/questions/39219065/…
sage88