Zestawy Python vs. Listy

187

Która struktura danych w Pythonie jest bardziej wydajna / szybsza? Zakładając, że kolejność nie jest dla mnie ważna, a mimo to sprawdzałbym duplikaty, czy zestaw Python jest wolniejszy niż lista Python?

Mantas Vidutis
źródło

Odpowiedzi:

231

To zależy od tego, co zamierzasz z tym zrobić.

Zestawy są znacznie szybsze, jeśli chodzi o ustalenie, czy obiekt jest obecny w zestawie (jak w x in s), ale są wolniejsze niż listy, jeśli chodzi o iterację ich zawartości.

Możesz użyć modułu timeit, aby zobaczyć, który jest szybszy w twojej sytuacji.

Michael Aaron Safyan
źródło
4
Jeśli chodzi o twój punkt: „Zestawy są znacznie szybsze”, jaka jest podstawowa implementacja, która sprawia, że ​​jest szybszy?
przeeksponowanie
Języki skryptowe lubią ukrywać podstawowe implementacje, ale ta pozorna prostota nie zawsze jest dobrą rzeczą, potrzebujesz pewnej świadomości „struktury danych” podczas projektowania oprogramowania.
Christophe Roussy
4
Zestaw nie jest znacznie wolniejszy niż lista podczas iteracji.
omerfarukdogan
39
Zestawy i listy mają liniową iterację czasu. Powiedzenie, że jedno jest „wolniejsze” niż drugie, jest mylące i dezorientuje nowych programistów, którzy czytają tę odpowiedź.
habnabit
@ habnabit, jeśli mówisz, że oba mają liniową iterację czasu. Czy to oznacza, że ​​mają ten sam czas iteracji? Jaka jest zatem różnica?
Mohammed Noureldin
153

Listy są nieco szybsze niż zestawy, gdy chcesz po prostu iterować po wartościach.

Zestawy są jednak znacznie szybsze niż listy, jeśli chcesz sprawdzić, czy element jest w nim zawarty. Mogą jednak zawierać tylko unikalne przedmioty.

Okazuje się, że krotki działają prawie dokładnie tak samo jak listy, z wyjątkiem ich niezmienności.

Iteracja

>>> def iter_test(iterable):
...     for i in iterable:
...         pass
...
>>> from timeit import timeit
>>> timeit(
...     "iter_test(iterable)",
...     setup="from __main__ import iter_test; iterable = set(range(10000))",
...     number=100000)
12.666952133178711
>>> timeit(
...     "iter_test(iterable)",
...     setup="from __main__ import iter_test; iterable = list(range(10000))",
...     number=100000)
9.917098999023438
>>> timeit(
...     "iter_test(iterable)",
...     setup="from __main__ import iter_test; iterable = tuple(range(10000))",
...     number=100000)
9.865639209747314

Sprawdź, czy obiekt jest obecny

>>> def in_test(iterable):
...     for i in range(1000):
...         if i in iterable:
...             pass
...
>>> from timeit import timeit
>>> timeit(
...     "in_test(iterable)",
...     setup="from __main__ import in_test; iterable = set(range(1000))",
...     number=10000)
0.5591847896575928
>>> timeit(
...     "in_test(iterable)",
...     setup="from __main__ import in_test; iterable = list(range(1000))",
...     number=10000)
50.18339991569519
>>> timeit(
...     "in_test(iterable)",
...     setup="from __main__ import in_test; iterable = tuple(range(1000))",
...     number=10000)
51.597304821014404
Ellis Percival
źródło
6
Odkryłem, że (zestaw inicjujący -> 5.5300979614257812) (lista inicjująca -> 1.8846848011016846) (krotka inicjująca -> 1.8730108737945557) Przedmioty o wielkości 10.000 na moim czterordzeniowym rdzeniu Intel Core i5 z 12 GB pamięci RAM. Należy to również wziąć pod uwagę.
ThePracticalOne
4
Zaktualizowałem kod, aby usunąć teraz tworzenie obiektu. Faza konfiguracji pętli timeit jest wywoływana tylko raz ( docs.python.org/2/library/timeit.html#timeit.Timer.timeit ).
Ellis Percival
7

Wydajność listy:

>>> import timeit
>>> timeit.timeit(stmt='10**6 in a', setup='a = range(10**6)', number=100000)
0.008128150348026608

Ustaw wydajność:

>>> timeit.timeit(stmt='10**6 in a', setup='a = set(range(10**6))', number=100000)
0.005674857488571661

Możesz rozważyć stosowanie Tuple, ponieważ są one podobne do list, ale nie można ich modyfikować. Zajmują nieco mniej pamięci i są szybciej dostępne. Nie są tak elastyczne, ale są bardziej wydajne niż listy. Zwykle służą jako klucze słownikowe.

Zbiory są również strukturami sekwencji, ale z dwiema różnicami od list i krotek. Chociaż zestawy mają kolejność, kolejność ta jest dowolna i nie podlega kontroli programisty. Druga różnica polega na tym, że elementy zestawu muszą być unikalne.

setzgodnie z definicją. [ python | wiki ].

>>> x = set([1, 1, 2, 2, 3, 3])
>>> x
{1, 2, 3}
użytkownik2601995
źródło
4
Po pierwsze, należy zaktualizować do setwbudowanego łącza typu ( docs.python.org/2/library/stdtypes.html#set ), a nie przestarzałej setsbiblioteki. Po drugie, „Zestawy są również strukturami sekwencji”, przeczytaj następujące informacje z wbudowanego łącza typu: „Będąc kolekcją nieuporządkowaną, zestawy nie rejestrują pozycji elementu ani kolejności wstawiania. W związku z tym zestawy nie obsługują indeksowania, dzielenia ani innych zachowanie podobne do sekwencji ”.
Seaux
7
rangenie jest list. rangeto specjalna klasa z niestandardową __contains__metodą magiczną.
Ryne Wang
@RyneWang to prawda, ale tylko w przypadku Python3. W zakresie Python2 zwraca normalną listę (dlatego istnieją takie okropne rzeczy jak xrange)
Manoel Vilela,
7

Setwygrywa dzięki prawie natychmiastowym czekom „zawiera”: https://en.wikipedia.org/wiki/Hash_table

Implementacja listy : zwykle tablica, niski poziom blisko metalu, dobry do iteracji i losowy dostęp według indeksu elementów.

Implementacja zestawu : https://en.wikipedia.org/wiki/Hash_table , nie iteruje się na liście, ale znajduje element, obliczając skrót z klucza, więc zależy to od natury kluczowych elementów i skrótu funkcjonować. Podobne do tego, co jest używane do dyktowania. Podejrzewam, że listmoże być szybszy, jeśli masz bardzo mało elementów (<5), im większy element, tym lepsza setwydajność przy sprawdzaniu zawartości. Jest również szybki do dodawania i usuwania elementów. Pamiętaj też, że zbudowanie zestawu ma swój koszt!

UWAGA : Jeśli listjest już posortowane, wyszukiwanie listmoże być dość szybkie, ale w zwykłych przypadkach a setjest szybsze i prostsze w przypadku sprawdzania zawartości.

Christophe Roussy
źródło
8
Blisko do metalu? Co to w ogóle oznacza w kontekście Pythona? Jak lista jest bliżej metalu niż zestawu?
roganjosh
@roganjosh, python nadal działa na komputerze, a niektóre implementacje, takie jak lista jako „tablica”, są bliższe temu, co sprzęt jest dobry: stackoverflow.com/questions/176011/... , ale zawsze zależy to od tego, co chcesz osiągnąć, to dobrze jest wiedzieć trochę o implementacjach, a nie tylko abstrakcjach.
Christophe Roussy
2

tl; dr

Struktury danych (DS) są ważne, ponieważ służą do wykonywania operacji na danych, co w zasadzie implikuje: weź trochę danych wejściowych , przetworz je i zwróć dane wyjściowe .

Niektóre struktury danych są bardziej przydatne niż inne w niektórych szczególnych przypadkach. Dlatego niesprawiedliwe jest pytanie, które (DS) jest bardziej wydajne / szybkie. To jak pytanie, które narzędzie jest bardziej wydajne między nożem a widelcem. Mam na myśli, że wszystko zależy od sytuacji.

Listy

Lista jest zmienną sekwencją , zwykle używaną do przechowywania kolekcji jednorodnych przedmiotów .

Zestawy

Ustawiony obiekt to nieuporządkowana kolekcja różnych obiektów możliwych do skrótu . Jest powszechnie używany do testowania członkostwa, usuwania duplikatów z sekwencji i obliczania operacji matematycznych, takich jak przecięcie, połączenie, różnica i różnica symetryczna.

Stosowanie

Z niektórych odpowiedzi jasno wynika, że ​​lista jest znacznie szybsza niż zestaw podczas iteracji po wartościach. Z drugiej strony zestaw jest szybszy niż lista podczas sprawdzania, czy element jest w nim zawarty. Dlatego jedyną rzeczą, którą możesz powiedzieć, jest to, że lista jest lepsza niż zestaw dla niektórych konkretnych operacji i na odwrót.

lmiguelvargasf
źródło
2

Byłem zainteresowany wynikami podczas sprawdzania za pomocą CPython, czy wartość jest jedną z niewielkiej liczby literałów. setwygrywa Pythonie 3 vs tuple, listi or:

from timeit import timeit

def in_test1():
  for i in range(1000):
    if i in (314, 628):
      pass

def in_test2():
  for i in range(1000):
    if i in [314, 628]:
      pass

def in_test3():
  for i in range(1000):
    if i in {314, 628}:
      pass

def in_test4():
  for i in range(1000):
    if i == 314 or i == 628:
      pass

print("tuple")
print(timeit("in_test1()", setup="from __main__ import in_test1", number=100000))
print("list")
print(timeit("in_test2()", setup="from __main__ import in_test2", number=100000))
print("set")
print(timeit("in_test3()", setup="from __main__ import in_test3", number=100000))
print("or")
print(timeit("in_test4()", setup="from __main__ import in_test4", number=100000))

Wynik:

tuple
4.735646052286029
list
4.7308746771886945
set
3.5755991376936436
or
4.687681658193469

Dla 3 do 5 literałów setnadal wygrywa z szerokim marginesem i orstaje się najwolniejszy.

W Pythonie 2 setjest zawsze najwolniejszy. orjest najszybszy dla 2 do 3 literałów tuplei listjest szybszy z 4 lub więcej literałami. Nie mogłem odróżnić prędkość tuplevs list.

Gdy wartości do testowania były buforowane w zmiennej globalnej poza funkcją, zamiast tworzyć literał w pętli, setwygrywało za każdym razem, nawet w Pythonie 2.

Te wyniki dotyczą 64-bitowego CPython na Core i7.

Pedro Gimeno
źródło
0

Poleciłbym implementację Set, w której przypadek użycia ogranicza się do odwoływania się lub wyszukiwania istnienia, oraz implementację Tuple, w której przypadek użycia wymaga wykonania iteracji. Lista jest implementacją niskiego poziomu i wymaga znacznego obciążenia pamięci.


źródło
1
Rzeczywiście, właściwe rozróżnienie między tym, kiedy używać zestawów, a kiedy używać Tuple, ma naprawdę ogromne znaczenie. Nie martwiłbym się związanymi z tym kosztami pamięci i śladami, chyba że piszę skrypt API niższego poziomu.
0
from datetime import datetime
listA = range(10000000)
setA = set(listA)
tupA = tuple(listA)
#Source Code

def calc(data, type):
start = datetime.now()
if data in type:
print ""
end = datetime.now()
print end-start

calc(9999, listA)
calc(9999, tupA)
calc(9999, setA)

Wyjście po porównaniu 10 iteracji dla wszystkich 3: Porównanie

Harshal SG
źródło
0

Zestawy są szybsze, ponadto dostajesz więcej funkcji dzięki zestawom, na przykład powiedzmy, że masz dwa zestawy:

set1 = {"Harry Potter", "James Bond", "Iron Man"}
set2 = {"Captain America", "Black Widow", "Hulk", "Harry Potter", "James Bond"}

Możemy łatwo połączyć dwa zestawy:

set3 = set1.union(set2)

Dowiedz się, co jest wspólne w obu:

set3 = set1.intersection(set2)

Dowiedz się, co różni się w obu:

set3 = set1.difference(set2)

I wiele więcej! Wypróbuj je, są fajne! Co więcej, jeśli musisz pracować nad różnymi wartościami z 2 list lub wspólnymi wartościami z 2 list, wolę przekonwertować twoje listy na zestawy, a wielu programistów robi to w ten sposób. Mam nadzieję, że to ci pomoże :-)

Shakhyar Gogoi
źródło