Mam około 10 milionów wartości, które muszę umieścić w jakiejś tabeli wyszukiwania, więc zastanawiałem się, która byłaby bardziej wydajna lista lub dyktowania ?

Wiem, że możesz zrobić coś takiego dla obu:

if something in dict_of_stuff:
    pass

i

if something in list_of_stuff:
    pass

Myślę, że dyktando będzie szybsze i wydajniejsze.

Dzięki za pomoc.

EDYCJA 1
Trochę więcej informacji o tym, co próbuję zrobić. Kłębuszek 92 . Robię przeglądową tabelę, aby sprawdzić, czy obliczona wartość została już obliczona.

EDYCJA 2
Wydajność wyszukiwania.

EDYCJA 3
Nie ma wartości powiązanych z wartością ... czy zestaw byłby lepszy?

Prędkość

Odnośniki na listach to O (n), wyszukiwania w słownikach są amortyzowane O (1) w odniesieniu do liczby pozycji w strukturze danych. Jeśli nie musisz kojarzyć wartości, użyj zestawów.

Pamięć

Zarówno słowniki, jak i zestawy używają mieszania i zużywają znacznie więcej pamięci niż tylko do przechowywania obiektów. Według AM Kuchlinga w Beautiful Code implementacja stara się zachować 2/3 wartości skrótu, więc możesz stracić trochę pamięci.

Jeśli nie dodajesz nowych wpisów w locie (co robisz na podstawie zaktualizowanego pytania), warto posortować listę i użyć wyszukiwania binarnego. To jest O (log n) i prawdopodobnie będzie wolniejsze dla łańcuchów, niemożliwe dla obiektów, które nie mają naturalnego uporządkowania.

Dykt to tablica mieszająca, więc znalezienie kluczy jest naprawdę szybkie. Więc między dict i list, dict byłby szybszy. Ale jeśli nie masz wartości do skojarzenia, jeszcze lepiej jest użyć zestawu. Jest to tablica mieszająca bez części „tabela”.

EDYCJA: w przypadku nowego pytania TAK, zestaw byłby lepszy. Po prostu utwórz 2 zestawy, jeden dla sekwencji zakończonych na 1, a drugi dla sekwencji zakończonych na 89. Z powodzeniem rozwiązałem ten problem używając zestawów.

set()jest dokładnie tym, czego chcesz. O (1) wyszukiwania i mniejsze niż dict.

Przeprowadziłem trochę testów porównawczych i okazuje się, że dict jest szybszy niż lista i zestaw dla dużych zestawów danych, uruchamiając Pythona 2.7.3 na procesorze i7 w systemie Linux:

• python -mtimeit -s 'd=range(10**7)' '5*10**6 in d'

  10 pętli, najlepiej 3: 64,2 ms na pętlę

• python -mtimeit -s 'd=dict.fromkeys(range(10**7))' '5*10**6 in d'

  10000000 pętli, najlepiej 3: 0,0759 usek na pętlę

• python -mtimeit -s 'from sets import Set; d=Set(range(10**7))' '5*10**6 in d'

  1000000 pętli, najlepiej 3: 0,262 usek na pętlę

Jak widać, dict jest znacznie szybszy niż list i około 3 razy szybszy niż set. Jednak w niektórych aplikacjach nadal możesz chcieć wybrać zestaw ze względu na jego piękno. A jeśli zbiory danych są naprawdę małe (<1000 elementów), listy działają całkiem dobrze.

Chcesz dyktanda.

W przypadku (nieposortowanych) list w Pythonie operacja „in” wymaga czasu O (n) - nie jest dobra, gdy masz dużą ilość danych. Z drugiej strony dykt jest tablicą mieszającą, więc możesz spodziewać się czasu wyszukiwania O (1).

Jak zauważyli inni, możesz zamiast tego wybrać zestaw (specjalny typ dyktowania), jeśli masz tylko klucze, a nie pary klucz / wartość.

Związane z:

• Wiki Pythona : informacje o złożoności czasowej operacji kontenerowych w języku Python.
• System operacyjny: czas operacji kontenera Pythona i złożoność pamięci

jeśli dane są unikalne, set () będzie najbardziej wydajne, ale z dwóch - dict (co również wymaga unikalności, ups :)

Jako nowy zestaw testów do pokazania, @ EriF89 wciąż ma rację po tych wszystkich latach:

$ python -m timeit -s "l={k:k for k in xrange(5000)}"    "[i for i in xrange(10000) if i in l]"
1000 loops, best of 3: 1.84 msec per loop
$ python -m timeit -s "l=[k for k in xrange(5000)]"    "[i for i in xrange(10000) if i in l]"
10 loops, best of 3: 573 msec per loop
$ python -m timeit -s "l=tuple([k for k in xrange(5000)])"    "[i for i in xrange(10000) if i in l]"
10 loops, best of 3: 587 msec per loop
$ python -m timeit -s "l=set([k for k in xrange(5000)])"    "[i for i in xrange(10000) if i in l]"
1000 loops, best of 3: 1.88 msec per loop

Tutaj również porównujemy a tuple, o których wiadomo, że są szybsze niż lists(i zużywają mniej pamięci) w niektórych przypadkach użycia. W przypadku tabeli przeglądowej rozszerzenietuple nie wypadło lepiej.

Zarówno dictiset spisały się bardzo dobrze. Daje to interesującą kwestię związaną z odpowiedzią @SilentGhost na temat unikalności: jeśli OP ma 10M wartości w zestawie danych i nie wiadomo, czy są w nich duplikaty, warto byłoby równolegle zachować zestaw / dyktando jego elementów z rzeczywistym zbiorem danych i testowaniem istnienia w tym zbiorze / dyktandzie. Możliwe, że 10M punktów danych ma tylko 10 unikalnych wartości, co oznacza znacznie mniejszą przestrzeń do wyszukiwania!

Błąd SilentGhost dotyczący dykt jest w rzeczywistości naświetlony, ponieważ można użyć dyktu do skorelowania zduplikowanych danych (w wartościach) w nie powielony zestaw (klucze), a tym samym zachować jeden obiekt danych do przechowywania wszystkich danych, a jednocześnie być szybki jak tabela przeglądowa. Na przykład kluczem dict może być szukana wartość, a wartością może być lista indeksów na wyimaginowanej liście, na której ta wartość wystąpiła.

Na przykład, jeśli lista danych źródłowych do przeszukania była l=[1,2,3,1,2,1,4], można ją zoptymalizować zarówno pod kątem wyszukiwania, jak i pamięci, zastępując ją tym dyktowaniem:

>>> from collections import defaultdict
>>> d = defaultdict(list)
>>> l=[1,2,3,1,2,1,4]
>>> for i, e in enumerate(l):
...     d[e].append(i)
>>> d
defaultdict(<class 'list'>, {1: [0, 3, 5], 2: [1, 4], 3: [2], 4: [6]})

Z tym dyktando można wiedzieć:

1. Jeśli wartość znajdowała się w oryginalnym zbiorze danych (tj. 2 in dZwraca True)
2. Gdzie wartość była w oryginalnym zbiorze danych (czyli d[2]wraca lista indeksów, gdzie dane zostały znalezione w oryginalnej listy danych: [1, 4])

W rzeczywistości nie musisz przechowywać 10 milionów wartości w tabeli, więc i tak nie jest to wielka sprawa.

Wskazówka: zastanów się, jak duży może być Twój wynik po wykonaniu pierwszej operacji sumy kwadratów. Największy możliwy wynik będzie znacznie mniejszy niż 10 milionów ...