Jak pobrać element z zestawu bez usuwania go?

427

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.

Daren Thomas
źródło
8
Czy ktoś wie, dlaczego Python nie ma jeszcze zaimplementowanej tej funkcji?
hlin117
Jaki jest przypadek użycia? Zestaw nie ma tej zdolności bez powodu. Powinieneś iterować przez to i wykonywać operacje powiązane z zestawem, takie jak unionetc, nie pobierając z niego elementów. Na przykład next(iter({3,2,1}))zawsze wraca, 1więc jeśli myślałeś, że zwróci losowy element - nie będzie. Więc może po prostu używasz niewłaściwej struktury danych? Jaki jest przypadek użycia?
user1685095
1
Powiązane: stackoverflow.com/questions/20625579/… (Wiem, to nie jest to samo pytanie, ale są tam wartościowe alternatywy i spostrzeżenia.)
John Y
@ hlin117 Ponieważ zestaw jest nieuporządkowaną kolekcją . Ponieważ nie oczekuje się żadnego zamówienia, nie ma sensu odzyskiwać elementu z danej pozycji - oczekuje się, że będzie losowy.
Jeyekomon,

Odpowiedzi:

545

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.

Blair Conrad
źródło
4
To odpowiada na moje pytanie. Niestety, nadal będę używać pop (), ponieważ iteracja wydaje się sortować elementy. Wolałbym je w losowej kolejności ...
Daren Thomas
9
Nie sądzę, aby iter () sortował elementy - kiedy tworzę set i pop (), dopóki nie będzie pusty, uzyskuję spójne (posortowane, w moim przykładzie) porządkowanie, i jest takie samo jak iterator - pop ( ) nie obiecuje losowego porządku, po prostu arbitralny, jak w „Nic nie obiecuję”.
Blair Conrad,
2
+1 iter(s).next()nie jest obrzydliwe, ale świetne. Całkowicie ogólne pobieranie dowolnych elementów z dowolnego obiektu iterowalnego. Twój wybór, jeśli chcesz zachować ostrożność, jeśli kolekcja jest pusta.
u0b34a0f6ae
8
next (iter (s)) jest również OK i wydaje mi się, że brzmi lepiej. Możesz także użyć wartownika, aby obsłużyć skrzynkę, gdy s jest pusty. Np. Next (iter (s), set ()).
ja
5
next(iter(your_list or []), None)obsłużyć Brak zestawów i puste zestawy
MrE
111

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.

Jan
źródło
96
next(iter(s))przekracza tylko list(s)[0]przez trzy znaki i jest inaczej dramatycznie lepszy zarówno w czasie i przestrzeni złożoności. Tak więc, chociaż twierdzenie o „najmniejszym kodzie” jest trywialnie prawdziwe, jest również trywialnie prawdziwe, że jest to najgorsze możliwe podejście. Nawet ręczne usunięcie, a następnie ponowne dodanie usuniętego elementu do oryginalnego zestawu jest lepsze niż „zbudowanie całego nowego kontenera tylko w celu wyodrębnienia pierwszego elementu”, co jest ewidentnie szalone. Bardziej mnie martwi fakt, że 38 Stackoverflowers faktycznie to poparło. Wiem tylko, że zobaczę to w kodzie produkcyjnym.
Cecil Curry
19
@augurar: Ponieważ wykonuje pracę w stosunkowo prosty sposób. A czasem to wszystko ma znaczenie w krótkim skrypcie.
tonysdg
4
@Vicrobot Tak, ale robi to, kopiując całą kolekcję i przekształcając operację O (1) w operację O (n). To okropne rozwiązanie, którego nikt nigdy nie powinien używać.
sierpień
9
Również jeśli dążysz do „najmniejszego kodu” (co jest głupie), min(s)używa nawet mniejszej liczby znaków, będąc jednocześnie tak strasznym i nieefektywnym jak to.
sierpień
5
+1 dla zwycięzcy kodu golfowego, który mam praktyczny kontrprzykład na to, że jestem „okropny i nieefektywny”: min(s)jest nieco szybszy niż next(iter(s))dla zestawów rozmiaru 1, i doszedłem do tej odpowiedzi, szczególnie szukając specjalnego przypadku wydobywania jedynego elementu z zestawów w rozmiarze 1.
lehiester
49

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

wprowadź opis zdjęcia tutaj

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.

MSeifert
źródło
43

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:

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ś”.

Cecil Curry
źródło
2
Myślę, że narzekanie na to, że next(iter(s)) jest dwa razy wolniejsze niż for x in s: breakw, CPythonjest trochę dziwne. Mam na myśli, że tak CPython. Będzie to około 50-100 razy (lub coś w tym rodzaju) wolniej niż C lub Haskell robiąc to samo (przez większość czasu, szczególnie w iteracji, bez eliminacji ogona i żadnych optymalizacji). Utrata niektórych mikrosekund nie robi żadnej różnicy. Nie sądzisz? Jest też PyPy
użytkownik1685095
39

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

wr.
źródło
Czy ktoś ma pojęcie, dlaczego iter (s) .next () jest o wiele wolniejszy niż inne możliwości, nawet wolniejszy niż s.add (s.pop ())? Dla mnie wygląda to na bardzo zły projekt iter () i next (), jeśli tak wyglądają czasy.
peschü
Cóż, dla tego wiersz tworzy nowy obiekt iteracyjny przy każdej iteracji.
Ryan,
3
@Ryan: Czy obiekt iteratora nie jest również utworzony pośrednio for x in s? „Tworzony jest iterator dla wyniku expression_list.”
musiphil
2
@musiphil To prawda; pierwotnie tęskniłem za „break” za 0,14, co jest naprawdę sprzeczne z intuicją. Chcę głęboko się w to zanurzyć, kiedy będę miał czas.
Ryan,
1
Wiem, że to jest stary, ale po dodaniu s.remove()do mieszanki tych iterprzykładów zarówno fori iteriść katastrofalnie źle.
AChampion
28

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
dF.
źródło
14
Jeśli chcesz tylko jednego elementu, losowy wybór jest bardziej sensowny.
Gregg Lind
list (s) .pop () zrobi, jeśli nie obchodzi cię, który element wziąć.
Evgeny
8
@Gregg: Nie możesz używać choice(), ponieważ Python spróbuje zaindeksować twój zestaw i to nie działa.
Kevin,
3
Chociaż jest to sprytne, jest to w rzeczywistości najwolniejsze rozwiązanie, jakie sugeruje rząd wielkości. Tak, to jest tak wolne. Nawet konwersja zestawu na listę w celu wyodrębnienia pierwszego elementu z tej listy jest szybsza. Dla niewierzących wśród nas ( ... cześć! ), Zobacz te wspaniałe czasy .
Cecil Curry
9

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.

Skovorodkin
źródło
1
Metoda pętli for (lub dokładniej metoda iteratora) ma złożoność czasową O (1), podczas gdy metody te są O (N). Są jednak zwięzłe . :)
ForeverWintr
6

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
Nacięcie
źródło
2
Możesz również przejść z następną (iter (iterowalną), Brak), aby zaoszczędzić atrament :)
1 ''
3

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
Mistrz
źródło
1

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ć

Josué Carvajal
źródło
dlaczego nie użyć listzamiast tworzenia metody konwertera?
Daren Thomas
-1

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.

Solomon Ucko
źródło
-6

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()
Pat Notz
źródło
3
To nie działa tak, jak masz nadzieję. W python 2 keys () jest operacją O (n), więc nie jesteś już stałym czasem, ale przynajmniej klawisze [0] zwrócą oczekiwaną wartość. W python 3 keys () to operacje O (1), więc tak! Jednak nie zwraca już obiektu listy, zwraca obiekt podobny do zestawu, którego nie można zindeksować, więc klucze [0] zwrócą błąd TypeError. stackoverflow.com/questions/39219065/…
sage88