Wie ein Element aus einem Satz abrufen, ohne sie zu entfernen?

https://stackoverflow.com/questions/59825

python
set

09-06-2019
|

Frage

Nehmen wir folgendes:

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

Wie bekomme ich einen Wert (beliebiger Wert) aus s ohne s.pop() zu tun? Ich mag den Artikel in der Menge verlassen, bis ich sicher bin ich es entfernen kann - etwas, das ich nur sicher auf einem anderen Host nach einem asynchronen Aufruf sein kann

Schnell und schmutzig:

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

Aber wissen Sie, einen besseren Weg? Im Idealfall in konstanter Zeit.

Lösung

Zwei Optionen, die erfordern nicht den ganzen Satz zu kopieren:

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

oder ...

e = next(iter(s))

Aber im allgemeinen Sätzen nicht unterstützen Indizierung oder Aufschneiden.

Andere Tipps

Am wenigsten Code wäre:

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

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

Um einige Timing Zahlen hinter den unterschiedlichen Ansätzen bieten, sollten Sie den folgenden Code ein. Die get () ist meine Gewohnheit neben Pythons setobject.c, wobei nur ein pop (), 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 lautet:

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

Das bedeutet, dass die für / Pause Lösung ist die schnellste (manchmal schneller als die benutzerdefinierte get () Lösung).

tl; dr

for first_item in muh_set: break bleibt der optimale Ansatz in Python 3.x ^{Verflucht seist du, Guido.}

y u tun dies

Willkommen zu einem weiteren Satz von Python 3.x Timings, hochgerechnet von wr. ist ausgezeichnet Python 2.x-spezifische Antwort . Im Gegensatz zu AChampion ist ebenso hilfreich Python 3.x-spezifische Antwort , die Timings unter auch Zeit Ausreißer oben vorgeschlagenen Lösungen - einschließlich:

list(s)[0], John 'Roman sequenzbasierte Lösung .
random.sample(s, 1), dF. ist eklektisch RNG-basierte Lösung .

Code-Snippets für Große Freude

Einschalten, tune in, Zeit:

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 Obsoleted Timeless Timings

Sehen Bestellen von schnellsten zum 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

Faceplants für die ganze Familie

Es überrascht nicht, manuelle Iteration bleibt mindestens doppelt so schnell als die nächste schnellste Lösung. Obwohl der Abstand von den schlechten alten Python 2.x Tage gesunken ist (in der manuellen Iteration mindestens viermal so schnell war), enttäuscht er die PEP 20 in mir Eiferer, dass die ausführliche Lösung die beste ist. Zumindest einen Satz in eine Liste Umwandlung nur das erste Element der Menge zu extrahieren, so schrecklich ist, wie erwartet. Danke Guido, kann sein Licht weiter zu uns führen.

Überraschenderweise ist die RNG-basierte Lösung ist absolut schrecklich. Liste Umwandlung schlecht, aber random wirklich nimmt die schrecklichen Sauce Kuchen. So viel zu den Random Number Gott .

Ich wünsche nur, die amorph Sie würden bereits eine set.get_first() Methode für uns aufzumöbeln. Wenn Sie dies lesen, Sie: „. Bitte etwas tun“

Da Sie ein zufälliges Element wollen, wird dies auch funktionieren:

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

Die Dokumentation scheint nicht die Leistung von random.sample zu erwähnen. Von einem wirklich schnellen empirischen Test mit einer riesigen Liste und einem riesigen Satz, so scheint es, konstante Zeit für eine Liste zu sein, aber nicht für den Satz. Auch Iteration über einen Satz ist nicht zufällig; die Reihenfolge ist nicht definiert, aber vorhersehbar:

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

Wenn Zufälligkeit ist wichtig, und Sie müssen eine Reihe von Elementen in konstanter Zeit (großer Mengen), würde ich random.sample verwenden und in eine Liste konvertieren zuerst:

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

Ich fragte mich, wie die Funktionen für verschiedene Sätze durchführen wird, so habe ich eine 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()

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

Doch solange eine der konstanten Zeit Ansätze, um die Leistungsdifferenz verwendet wird, vernachlässigbar.

iteration_utilities (Disclaimer: Ich bin der Autor) enthält ein Komfortfunktion für diesen anwendungs~~POS=TRUNC: first :

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

I enthalten sie auch in der Benchmark oben. Es kann mit den beiden anderen „schnellen“ Lösungen konkurrieren, aber der Unterschied ist nicht viel oder so.

Ich verwende eine Nutzenfunktion ich geschrieben habe. Sein Name ist etwas irreführend, weil es eine Art bedeutet, es könnte ein Zufallsgenerator oder etwas ähnliches sein.

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

Scheinbar die kompakteste (6 Symbole), obwohl sehr langsam Möglichkeit, einen Satz Element zu erhalten (möglich durch PEP 3132 ):

e,*_=s

Mit Python 3.5+ Sie können auch dieses 7-Symbol Ausdruck verwenden (dank PEP 448 ):

[*s][0]

Beide Optionen sind etwa 1000-mal langsamer auf meinem Rechner als die for-Schleife-Methode.

Nach @wr. Post, bekomme ich ä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

Wenn jedoch die zugrunde liegende Satz zu ändern (zum Beispiel remove() nennen) die Dinge schlecht für die iterable Beispiele (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()

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

Wie wäre es s.copy().pop()? Ich habe timed es nicht, aber es sollte funktionieren und es ist einfach. Es funktioniert am besten für kleine Mengen jedoch, wie es kopiert den ganzen Satz.

Eine weitere Option ist ein Wörterbuch mit Werten verwenden 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 Tasten als Set mit Ausnahme behandeln, dass sie nur ein Array:


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

Ein Nebeneffekt dieser Wahl ist, dass der Code rückwärts mit älteren, pre-set Versionen von Python kompatibel sein wird. Es ist vielleicht nicht die beste Antwort, aber es ist eine weitere Option.

Edit: Sie können sogar so etwas wie dies tun, um die Tatsache zu verbergen, dass Sie ein dict verwendet anstelle eines Arrays oder eingestellt:


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

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow