Zestawy Python vs. Listy

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?

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.

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

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}

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.

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.

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.

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.

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

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