Wie kann man ein Element aus einer Menge abrufen, ohne es zu entfernen?

426

Angenommen, Folgendes:

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

Wie bekomme ich einen Wert (irgendeinen Wert) heraus, sohne es zu tun s.pop()? Ich möchte das Element im Set belassen, bis ich sicher bin, dass ich es entfernen kann - etwas, dessen ich mir erst nach einem asynchronen Aufruf eines anderen Hosts sicher sein kann.

Schnell und dreckig:

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

Aber kennen Sie einen besseren Weg? Idealerweise in konstanter Zeit.

Daren Thomas
quelle
8
Weiß jemand, warum Python diese Funktion noch nicht implementiert hat?
hlin117
Was ist der Anwendungsfall? Set hat diese Fähigkeit aus einem bestimmten Grund nicht. Sie sollten es durchlaufen und satzbezogene Operationen wie unionusw. ausführen, ohne Elemente daraus zu entnehmen . Zum Beispiel wird next(iter({3,2,1}))immer zurückgegeben 1, wenn Sie dachten, dass dies ein zufälliges Element zurückgeben würde - würde dies nicht der Fall sein. Vielleicht verwenden Sie nur die falsche Datenstruktur? Was ist der Anwendungsfall?
Benutzer1685095
1
Siehe auch : stackoverflow.com/questions/20625579/… (Ich weiß, es ist nicht die gleiche Frage, aber es gibt dort lohnende Alternativen und Erkenntnisse.)
John Y
@ hlin117 Da set eine ungeordnete Sammlung ist . Da keine Reihenfolge erwartet wird, ist es nicht sinnvoll, ein Element an einer bestimmten Position abzurufen - es wird erwartet, dass es zufällig ist.
Jeyekomon

Antworten:

543

Zwei Optionen, bei denen nicht das gesamte Set kopiert werden muss:

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

Oder...

e = next(iter(s))

Im Allgemeinen unterstützen Sets jedoch keine Indizierung oder Aufteilung.

Blair Conrad
quelle
4
Dies beantwortet meine Frage. Leider werde ich immer noch pop () verwenden, da die Iteration die Elemente zu sortieren scheint. Ich würde sie in zufälliger Reihenfolge bevorzugen ...
Daren Thomas
9
Ich glaube nicht, dass iter () die Elemente sortiert. Wenn ich ein Set und pop () erstelle, bis es leer ist, erhalte ich eine konsistente (in meinem Beispiel sortierte) Reihenfolge und es ist dasselbe wie beim iterator - pop () ) verspricht keine zufällige Reihenfolge, nur willkürlich, wie in "Ich verspreche nichts".
Blair Conrad
2
+1 iter(s).next()ist nicht brutto, aber großartig. Ganz allgemein, um ein beliebiges Element von einem iterierbaren Objekt zu übernehmen. Ihre Wahl, wenn Sie vorsichtig sein möchten, wenn die Sammlung leer ist.
u0b34a0f6ae
8
next (iter (s)) ist ebenfalls in Ordnung und ich denke eher, dass es besser liest. Sie können auch einen Sentinel verwenden, um den Fall zu behandeln, wenn s leer ist. ZB next (iter (s), set ()).
Ja
5
next(iter(your_list or []), None)Keine Sätze und leere Sätze zu handhaben
MrE
109

Der kleinste Code wäre:

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

Offensichtlich würde dies eine neue Liste erstellen, die jedes Mitglied des Satzes enthält, also nicht großartig, wenn Ihr Satz sehr groß ist.

John
quelle
94
next(iter(s))nur überschreitet list(s)[0]durch drei Zeichen und ist ansonsten dramatisch überlegen in Zeit und Raum Komplexität. Während die Behauptung des "kleinsten Codes" trivial wahr ist, ist es auch trivial wahr, dass dies der schlechteste mögliche Ansatz ist. Selbst das manuelle Entfernen und anschließende Hinzufügen des entfernten Elements zum ursprünglichen Satz ist besser als "einen ganz neuen Container zu erstellen, nur um das erste Element zu extrahieren", was offensichtlich verrückt ist. Was mich mehr beschäftigt ist, dass 38 Stackoverflowers dies tatsächlich positiv bewertet haben. Ich weiß nur, dass ich das im Produktionscode sehen werde.
Cecil Curry
19
@augurar: Weil es die Arbeit auf relativ einfache Weise erledigt. Und manchmal ist das alles, was in einem kurzen Skript zählt.
Tonysdg
4
@Vicrobot Ja, aber dies geschieht, indem die gesamte Sammlung kopiert und eine O (1) -Operation in eine O (n) -Operation umgewandelt wird. Dies ist eine schreckliche Lösung, die niemand jemals verwenden sollte.
Augurar
9
Auch wenn Sie nur "am wenigsten Code" anstreben (was dumm ist), min(s)werden noch weniger Zeichen verwendet, während Sie genauso schrecklich und ineffizient sind.
Augurar
5
+1 für den Code-Golf-Gewinner, für den ich ein praktisches Gegenbeispiel für "schrecklich und ineffizient" habe: min(s)ist etwas schneller als next(iter(s))für Sätze der Größe 1, und ich bin zu dieser Antwort gekommen, um speziell das Sonderelement aus Sätzen zu extrahieren von Größe 1.
Lehiester
48

Ich habe mich gefragt, wie die Funktionen für verschiedene Sets funktionieren, also habe ich einen Benchmark durchgeführt:

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

Geben Sie hier die Bildbeschreibung ein

Dieses Diagramm zeigt deutlich, dass einige Ansätze ( RandomSample, SetUnpackingund ListIndex) von der Größe des Satzes abhängen und im allgemeinen Fall vermieden werden sollten (zumindest wenn die Leistung wichtig sein könnte ). Wie bereits in den anderen Antworten gezeigt, ist der schnellste Weg ForLoop.

Solange jedoch einer der Ansätze mit konstanter Zeit verwendet wird, ist der Leistungsunterschied vernachlässigbar.


iteration_utilities(Disclaimer: Ich bin der Autor) eine Komfortfunktion für diesen Anwendungsfall: first:

>>> from iteration_utilities import first
>>> first({1,2,3,4})
1

Ich habe es auch in den obigen Benchmark aufgenommen. Es kann mit den anderen beiden "schnellen" Lösungen konkurrieren, aber der Unterschied ist in keiner Weise groß.

MSeifert
quelle
43

tl; dr

for first_item in muh_set: breakbleibt der optimale Ansatz in Python 3.x. Verfluche dich, Guido.

Du machst das

Willkommen zu einem weiteren Satz von Python 3.x-Timings, extrapoliert aus wr. 's ausgezeichnete Python 2.x-spezifische Antwort . Im Gegensatz zu AChampions ebenso hilfreicher Python 3.x-spezifischer Antwort werden in den folgenden Zeitabläufen auch die oben vorgeschlagenen Zeitausreißerlösungen aufgeführt - einschließlich:

Code-Schnipsel für große Freude

Einschalten, einschalten, zeitlich festlegen:

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

Schnell veraltete zeitlose Timings

Erblicken! Sortiert nach schnellsten bis langsamsten Schnipsel:

$ ./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

Gesichtspflanzen für die ganze Familie

Es überrascht nicht, dass die manuelle Iteration mindestens doppelt so schnell bleibt wie die nächstschnellste Lösung. Obwohl sich die Lücke seit den Tagen von Bad Old Python 2.x verringert hat (in denen die manuelle Iteration mindestens viermal so schnell war), enttäuscht es den PEP 20- Fanatiker in mir, dass die ausführlichste Lösung die beste ist. Zumindest das Konvertieren eines Sets in eine Liste, um nur das erste Element des Sets zu extrahieren, ist so schrecklich wie erwartet. Danke Guido, möge sein Licht uns weiterhin führen.

Überraschenderweise ist die RNG-basierte Lösung absolut schrecklich. Listenkonvertierung ist schlecht, nimmt aber random wirklich den schrecklichen Saucen-Kuchen. Soviel zum Zufallszahlengott .

Ich wünschte nur, die Amorphen würden set.get_first()bereits eine Methode für uns entwickeln. Wenn Sie dies lesen, sagen sie: "Bitte. Tun Sie etwas."

Cecil Curry
quelle
2
Ich finde es seltsam, sich darüber zu beschweren, dass next(iter(s)) das zweimal langsamer ist als for x in s: breakin CPython. Ich meine das ist CPython. Es wird ungefähr 50-100 Mal (oder so ähnlich) langsamer sein als C oder Haskell, die das Gleiche tun (die meiste Zeit, insbesondere bei Iterationen, keine Eliminierung von Tail Calls und keinerlei Optimierungen). Das Verlieren einiger Mikrosekunden macht keinen wirklichen Unterschied. Denkst du nicht? Und es gibt auch PyPy
user1685095
39

Beachten Sie den folgenden Code, um einige Zeitangaben für die verschiedenen Ansätze bereitzustellen. Das get () ist meine benutzerdefinierte Ergänzung zu Pythons setobject.c, da es nur ein pop () ist, ohne das Element zu entfernen.

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

Die Ausgabe ist:

$ ./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

Dies bedeutet, dass die for / break- Lösung die schnellste ist (manchmal schneller als die benutzerdefinierte get () -Lösung).

wr.
quelle
Hat jemand eine Idee, warum iter (s) .next () so viel langsamer ist als die anderen Möglichkeiten, sogar langsamer als s.add (s.pop ())? Für mich fühlt es sich nach einem sehr schlechten Design von iter () und next () an, wenn die Timings so aussehen.
Peschü
Zum einen erstellt diese Zeile bei jeder Iteration ein neues Iterationsobjekt.
Ryan
3
@ Ryan: Wird nicht auch implizit ein Iteratorobjekt erstellt for x in s? "Für das Ergebnis der wird ein Iterator erstellt expression_list."
Musiphil
2
@musiphil Das ist wahr; ursprünglich habe ich die "Pause" bei 0,14 verpasst, das ist wirklich kontraintuitiv. Ich möchte tief in dieses Thema eintauchen, wenn ich Zeit habe.
Ryan
1
Ich weiß , das alt ist, aber beim Hinzufügen s.remove()in die die mischen iterBeispiele beide forund itergehen katastrophal schlecht.
AChampion
28

Da Sie ein zufälliges Element möchten, funktioniert dies auch:

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

Die Dokumentation scheint die Leistung von nicht zu erwähnen random.sample. Nach einem wirklich schnellen empirischen Test mit einer riesigen Liste und einer riesigen Menge scheint es eine konstante Zeit für eine Liste zu sein, aber nicht für die Menge. Außerdem ist die Iteration über eine Menge nicht zufällig. Die Reihenfolge ist undefiniert, aber vorhersehbar:

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

Wenn Zufälligkeit wichtig ist und Sie eine Reihe von Elementen in konstanter Zeit benötigen (große Mengen), würde ich diese zuerst verwenden random.sampleund in eine Liste konvertieren:

>>> lst = list(s) # once, O(len(s))?
...
>>> e = random.sample(lst, 1)[0] # constant time
dF.
quelle
14
Wenn Sie nur ein Element möchten, ist random.choice sinnvoller.
Gregg Lind
list (s) .pop () reicht aus, wenn es Ihnen egal ist, welches Element Sie verwenden möchten.
Evgeny
8
@ Gregg: Sie können nicht verwenden choice(), da Python versucht, Ihren Satz zu indizieren, und das funktioniert nicht.
Kevin
3
Dies ist zwar klug, aber tatsächlich die langsamste Lösung, die bisher um eine Größenordnung vorgeschlagen wurde. Ja, es ist so langsam. Selbst das Konvertieren des Sets in eine Liste, um nur das erste Element dieser Liste zu extrahieren, ist schneller. Für die Ungläubigen unter uns ( ... hi! ) Sehen Sie diese fabelhaften Zeiten .
Cecil Curry
9

Scheinbar der kompakteste (6 Symbole), wenn auch sehr langsame Weg, um ein gesetztes Element zu erhalten (ermöglicht durch PEP 3132 ):

e,*_=s

Mit Python 3.5+ können Sie auch diesen Ausdruck mit 7 Symbolen verwenden (dank PEP 448 ):

[*s][0]

Beide Optionen sind auf meinem Computer ungefähr 1000-mal langsamer als die For-Loop-Methode.

Skovorodkin
quelle
1
Die for-Schleifenmethode (oder genauer die Iteratormethode) hat eine zeitliche Komplexität von O (1), während diese Methoden O (N) sind. Sie sind jedoch prägnant . :)
ForeverWintr
6

Ich benutze eine Dienstprogrammfunktion, die ich geschrieben habe. Sein Name ist etwas irreführend, weil er impliziert, dass es sich um einen zufälligen Gegenstand oder ähnliches handelt.

def anyitem(iterable):
    try:
        return iter(iterable).next()
    except StopIteration:
        return None
Nick
quelle
2
Sie können auch mit next (iter (iterable), None) fortfahren, um Tinte zu sparen :)
1 ''
3

Nach @wr. Post, ich bekomme ähnliche Ergebnisse (für 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()

Ausgabe:

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

Beim Ändern der zugrunde liegenden Menge (z. B. Aufruf von remove()) laufen die iterierbaren Beispiele ( for, iter) jedoch schlecht :

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

Ergebnisse in:

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
Ein Champion
quelle
1

Was ich normalerweise für kleine Sammlungen mache, ist eine Art Parser / Konverter-Methode wie diese zu erstellen

def convertSetToList(setName):
return list(setName)

Dann kann ich die neue Liste verwenden und über die Indexnummer zugreifen

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

Als Liste haben Sie alle anderen Methoden, mit denen Sie möglicherweise arbeiten müssen

Josué Carvajal
quelle
Warum nicht einfach verwenden, listanstatt eine Konvertermethode zu erstellen?
Daren Thomas
-1

Wie wäre es s.copy().pop()? Ich habe es nicht geplant, aber es sollte funktionieren und es ist einfach. Es funktioniert jedoch am besten für kleine Sets, da es das gesamte Set kopiert.

Solomon Ucko
quelle
-6

Eine andere Möglichkeit besteht darin, ein Wörterbuch mit Werten zu verwenden, die Sie nicht interessieren. Z.B,


poor_man_set = {}
poor_man_set[1] = None
poor_man_set[2] = None
poor_man_set[3] = None
...

Sie können die Schlüssel als Satz behandeln, außer dass sie nur ein Array sind:


keys = poor_man_set.keys()
print "Some key = %s" % keys[0]

Ein Nebeneffekt dieser Auswahl ist, dass Ihr Code mit älteren Vorversionen setvon Python abwärtskompatibel ist . Es ist vielleicht nicht die beste Antwort, aber es ist eine andere Option.

Bearbeiten: Sie können sogar so etwas tun, um die Tatsache zu verbergen, dass Sie ein Diktat anstelle eines Arrays oder Sets verwendet haben:


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
quelle
3
Dies funktioniert nicht so, wie Sie es sich erhoffen. In Python 2 ist keys () eine O (n) -Operation, sodass Sie keine konstante Zeit mehr haben, aber mindestens keys [0] den erwarteten Wert zurückgeben. In Python 3 ist keys () eine O (1) -Operation, also yay! Es wird jedoch kein Listenobjekt mehr zurückgegeben, sondern ein satzähnliches Objekt, das nicht indiziert werden kann, sodass die Schlüssel [0] TypeError auslösen würden. stackoverflow.com/questions/39219065/…
sage88