Jak pobrać element z zestawu bez usuwania go?

Załóżmy, że:

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

Jak uzyskać wartość (dowolną wartość) sbez robienia s.pop()? Chcę pozostawić element w zestawie, dopóki nie będę pewien, że mogę go usunąć - czego mogę być pewien tylko po asynchronicznym wywołaniu do innego hosta.

Szybko i brudno:

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

Ale czy znasz lepszy sposób? Idealnie w stałym czasie.

Dwie opcje, które nie wymagają kopiowania całego zestawu:

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

Lub...

e = next(iter(s))

Ogólnie jednak zestawy nie obsługują indeksowania ani krojenia.

Najmniejszy kod to:

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

Oczywiście stworzyłoby to nową listę, która zawiera każdego członka zestawu, więc nie jest świetnie, jeśli twój zestaw jest bardzo duży.

Zastanawiałem się, jak te funkcje będą działać dla różnych zestawów, więc zrobiłem test porównawczy:

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

Ten wykres pokazuje wyraźnie, że niektóre podejścia ( RandomSample, SetUnpackingi ListIndex) zależy od wielkości zestawu i należy ich unikać w przypadku ogólnym (przynajmniej jeśli wydajność może być ważne). Jak już pokazują inne odpowiedzi, najszybszym sposobem jest ForLoop.

Jednak dopóki stosowane jest jedno ze stałych czasów, różnica wydajności będzie nieznaczna.

iteration_utilities(Uwaga: Jestem autorem) zawiera funkcję wygody dla tego przypadku użycia first:

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

Umieściłem go również w powyższym teście. Może konkurować z pozostałymi dwoma „szybkimi” rozwiązaniami, ale różnica nie jest duża.

tl; dr

for first_item in muh_set: breakpozostaje optymalnym podejściem w Pythonie 3.x. ^{Przeklnij cię, Guido.}

ty to zrób

Witaj w innym zestawie taktowania Python 3.x, ekstrapolowanym z wr. „S doskonałe Pythona 2.x-swoistych . W przeciwieństwie do równie pomocnej odpowiedzi AChampiona specyficznej dla Python 3.x , poniższe czasy również sugerują rozwiązania odstające od czasu - w tym:

• list(s)[0], Nowatorskie rozwiązanie oparte na sekwencji Johna .
• random.sample(s, 1), dF. eklektyczne rozwiązanie oparte na RNG .

Fragmenty kodu dla Wielkiej Radości

Włącz, nastrój, czas:

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

Szybko przestarzałe ponadczasowe czasy

Ujrzeć! Uporządkowane przez najszybsze do najwolniejszych fragmentów:

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

Osłony na twarz dla całej rodziny

Nic dziwnego, że ręczna iteracja pozostaje co najmniej dwa razy szybsza niż następne najszybsze rozwiązanie. Chociaż różnica zmniejszyła się od dni Bad Old Python 2.x (w których manualna iteracja była co najmniej cztery razy szybsza), rozczarowuje mnie fanatyka PEP 20 , że najbardziej szczegółowe rozwiązanie jest najlepsze. Przynajmniej przekształcenie zestawu w listę tylko w celu wyodrębnienia pierwszego elementu zestawu jest tak okropne, jak oczekiwano. Dzięki Guido, niech jego światło nadal nas prowadzi.

Co zaskakujące, rozwiązanie oparte na RNG jest absolutnie okropne. Konwersja list jest zła, ale random tak naprawdę wymaga okropnego sosu. Tyle o losowym Bogu liczb .

Chciałbym tylko, żeby amorficzni już odkryli set.get_first()dla nas metodę. Jeśli to czytasz, oni: „Proszę. Zrób coś”.

Aby podać wartości czasowe różnych podejść, rozważ poniższy kod. Get () jest moim niestandardowym dodatkiem do setobject.c Pythona, który jest tylko pop () bez usuwania elementu.

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

Dane wyjściowe to:

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

Oznacza to, że rozwiązanie for / break jest najszybsze (czasem szybsze niż niestandardowe rozwiązanie get ()).

Ponieważ chcesz elementu losowego, będzie to również działać:

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

Dokumentacja nie wspomina o wydajności random.sample. Z naprawdę szybkiego testu empirycznego z ogromną listą i ogromnym zestawem wydaje się, że jest to stały czas na listę, ale nie na zestaw. Również iteracja na zbiorze nie jest przypadkowa; kolejność jest niezdefiniowana, ale przewidywalna:

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

Jeśli losowość jest ważna i potrzebujesz kilku elementów w stałym czasie (duże zestawy), najpierw użyłbym random.samplei przekonwertował na listę:

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

Pozornie najbardziej kompaktowy (6 symboli), ale bardzo powolny sposób na uzyskanie zestawu elementów (możliwe dzięki PEP 3132 ):

e,*_=s

W Pythonie 3.5+ możesz także użyć tego 7-symbolowego wyrażenia (dzięki PEP 448 ):

[*s][0]

Obie opcje są około 1000 razy wolniejsze na mojej maszynie niż metoda for-loop.

Używam napisanej przeze mnie funkcji narzędziowej. Jego nazwa jest nieco myląca, ponieważ sugeruje, że może to być losowy przedmiot lub coś w tym rodzaju.

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

Obserwowanie @wr. post, otrzymuję podobne wyniki (dla 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()

Wynik:

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

Jednak przy zmianie zestawu podstawowego (np. Wywołanie do remove()) sprawy idą źle w przypadku iterowalnych przykładów ( 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()

Prowadzi do:

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

To, co zwykle robię dla małych kolekcji, to stworzenie takiej metody parsera / konwertera

def convertSetToList(setName):
return list(setName)

Następnie mogę skorzystać z nowej listy i uzyskać dostęp według numeru indeksu

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

Na liście znajdziesz wszystkie inne metody, z którymi możesz potrzebować pracować

Jak o s.copy().pop()? Nie mierzyłem czasu, ale powinno działać i jest proste. Działa najlepiej w przypadku małych zestawów, ponieważ kopiuje cały zestaw.

Inną opcją jest użycie słownika z wartościami, na których ci nie zależy. Na przykład,

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

Możesz traktować klucze jako zestaw, z wyjątkiem tego, że są tylko tablicą:

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

Efektem ubocznym tego wyboru jest to, że twój kod będzie wstecznie kompatybilny ze starszymi, wcześniejszymi setwersjami Pythona. Być może nie jest to najlepsza odpowiedź, ale to kolejna opcja.

Edycja: Możesz nawet zrobić coś takiego, aby ukryć fakt, że użyłeś dykta zamiast tablicy lub zestawu:

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