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

Question

Nehmen Sie Folgendes an:

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

Wie erhalte ich einen Wert (irgendeinen Wert) aus der s ohne zu tun s.pop() ? Ich möchte das Element in der Menge belassen, bis ich sicher bin, dass ich es entfernen kann - etwas, das ich nur nach einem asynchronen Aufruf an einen anderen Host sicher sein kann.

Schnell und schmutzig:

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

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

Answer 1

Da Sie ein Zufallselement wünschen, funktioniert auch dies:

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

In der Dokumentation wird nicht erwähnt, dass die Leistung von random.sample . Ein schneller empirischer Test mit einer großen Liste und einer großen Menge hat ergeben, dass die Zeit für eine Liste konstant zu sein scheint, nicht aber 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 Folgendes verwenden random.sample und zunächst in eine Liste umwandeln:

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

Answer 2

Eine weitere Möglichkeit in Python 3:

next(iter(s))

o

s.__iter__().__next__()

Answer 3

Scheinbar ist die am kompaktesten (6 Symbole) obwohl sehr langsam Weg, um ein Set-Element zu erhalten (möglich gemacht durch PEP 3132 ):

e,*_=s

Mit Python 3.5+ können Sie auch diesen 7-Symbole-Ausdruck verwenden (dank der PEP 448 ):

[*s][0]

Beide Optionen sind auf meinem Rechner etwa 1000 Mal langsamer als die for-loop-Methode.

Answer 4

Ich verwende eine von mir geschriebene Hilfsfunktion. Ihr Name ist etwas irreführend, weil er irgendwie andeutet, dass es sich um ein zufälliges Element oder etwas Ähnliches handeln könnte.

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

Answer 5

Nach @wr. Beitrag, erhalte 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()

Sortie :

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 Menge geändert wird (z. B. durch Aufruf von remove() ) geht es bei den wiederholbaren Beispielen schlecht aus ( 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