112

Mam około 10 milionów wartości, które muszę umieścić w pewnym typie tabeli wyszukiwania, więc zastanawiałem się, który byłby bardziej wydajny lub z listy?Python: Lista kontra Dict dla tabeli wyszukiwania

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

if something in dict_of_stuff: 
    pass

if something in list_of_stuff: 
    pass

Moja myśl jest DICT będzie szybsze i bardziej efektywne.

Dzięki za pomoc.

EDIT 1
trochę więcej informacji na temat tego, co próbuję zrobić. Euler Problem 92. Przygotowuję tabelę sprawdzania, aby sprawdzić, czy obliczona wartość została już obliczona.

EDIT 2
Wydajność dla wzroku.

EDIT 3
Brak wartości assosiated z wartością ... więc zestaw być lepiej?

Źródło

2009-02-04 Nope

Wydajność pod względem tego, co? Wstawić? Wyszukiwanie? Zużycie pamięci? Czy sprawdzasz czystość wartości lub czy są z nią powiązane jakieś metadane? – truppo

Na marginesie, nie potrzebujesz 10 milionów list lub dykt dla tego konkretnego problemu, ale o wiele mniejszy. – sfotiadis

Co się stanie, jeśli tabela będzie krotką zamiast listy? Czy elementy krotki są zaszyfrowane, czy jest to tylko niezmienna lista? – RufusVS

154

łącze

Przeszukiwania listach O (n) wyszukiwań w słownikach amortyzuje O (1) w odniesieniu do liczby pozycji w struktura danych. Jeśli nie musisz kojarzyć wartości, użyj zestawów.

pamięci

Oba słowniki oraz zestawy wykorzystują mieszania i używają znacznie więcej niż tylko pamięć do przechowywania obiektów. Według A.M. Kuchling w Piękny kod, implementacja stara się zachować hash 2/3 pełne, więc możesz zmarnować trochę pamięci.

Jeśli nie dodasz nowych pozycji w locie (co zrobisz, na podstawie zaktualizowanego pytania), warto posortować listę i użyć wyszukiwania binarnego. Jest to O (log n) i prawdopodobnie będzie wolniejsze dla łańcuchów, niemożliwe dla obiektów, które nie mają naturalnej kolejności.

Źródło

2009-02-04 23:38:36

sortowanie listy to O (n log n) – SilentGhost

Tak, ale jest to operacja jednorazowa, jeśli zawartość nigdy się nie zmienia . Wyszukiwanie binarne to O (log n). –

OTOH, 10 milionów liczb całkowitych zajmie, co, 40 milionów bajtów? Jeśli wartość mieszania wynosi 2/3, to znaczy, że wynosi ona 60 milionów, i będzie nad głową (każdy wie, ile?), Ale całość powinna zmieścić się w kilkuset milionach pamięci. To mogło być problemem dziesięć lat temu, ale tak naprawdę nie jest teraz. –

jeśli dane są unikalne set() będzie najbardziej skuteczny, ale z drugiej - dict (który również wymaga wyjątkowość, oops :)

Źródło

2009-02-04 23:30:48 SilentGhost

Niezupełnie ... dane muszą być unikalne również dla dyktatu. – nosklo

Zdałem sobie sprawę, kiedy zobaczyłem, że moja odpowiedź została wysłana%) – SilentGhost

@SilentGhost, jeśli odpowiedź jest błędna, dlaczego jej nie usunąć? Szkoda, że nie udało się przegrać, ale tak się dzieje (cóż, _happened_) –

dict jest tabela hash, więc jest to naprawdę szybko, by znaleźć klawiatura. Tak więc między dyktowaniem a listą, dict będzie szybszy. Ale jeśli nie masz wartości do skojarzenia, lepiej jest użyć zestawu. Jest to tabela mieszająca, bez części "tabela".

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

Źródło

2009-02-04 23:31:41 nosklo

Chcesz dyktować.

W przypadku (nieposortowanych) list w Pythonie, operacja "w" wymaga czasu O (n) --- nie jest dobra, gdy masz dużą ilość danych. Z drugiej strony, dyktafon jest tablicą skrótów, więc możesz oczekiwać czasu wyszukiwania O (1).

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

pokrewne:

Python wiki: informacje na temat złożoności czasowej operacji kontenerowych Pythona.
SO Python operacji pojemnik czasu i pamięci złożoność

Źródło

2009-02-04 23:37:45 zweiterlinde

Nawet w przypadku posortowanych list "in" to O (n). –

Dla połączonej listy, tak --- ale "listy" w Pythonie to to, co większość ludzi nazwałaby wektorami, które zapewniają indeksowany dostęp w O (1) i operację znajdowania w O (log n), po posortowaniu. – zweiterlinde

Czy mówisz, że operator 'in' zastosowany do posortowanej listy działa lepiej niż po zastosowaniu do nieposortowanego (do wyszukiwania losowej wartości)?(Nie sądzę, czy są one implementowane wewnętrznie jako wektory lub jako węzły na liście połączonej). – martineau

W rzeczywistości nie trzeba przechowywać 10 milionów wartości w tabeli, więc nie jest to wielka sprawa w żaden sposób.

Wskazówka: pomyśl o tym, jak duży może być Twój wynik po wykonaniu pierwszej sumy operacji na kwadratach. Największy możliwy wynik będzie znacznie mniejszy niż 10 milionów ...

Źródło

2009-02-23 19:03:30 Kiv

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

Źródło

2009-02-23 19:24:39 recursive

zrobiłem kilka badań porównawczych i okazuje się, że jest szybszy niż dict zarówno liście i ustawić dla dużych zbiorów danych, systemem Pythona 2.7.3 na i7 CPU na Linux:

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

10 zwojów, najlepsze 3: 64,2 ms każdej pętli
python -mtimeit -s 'd=dict.fromkeys(range(10**7))' '5*10**6 in d'

10000000 pętle, najlepiej 3: 0.075 9 usec za pętlą
python -mtimeit -s 'from sets import Set; d=Set(range(10**7))' '5*10**6 in d'

1000000 pętle, najlepiej 3: 0,262 usec za pętlą

Jak widać, DICT jest znacznie szybciej niż liście i około 3 razy szybciej niż zestaw . W niektórych aplikacjach możesz jednak chcieć wybrać zestaw dla jego piękna. A jeśli zestawy danych są naprawdę małe (< 1000 elementów), listy działają całkiem nieźle.

Źródło

2012-06-28 09:16:06 EriF89

Czy nie powinno być dokładnie odwrotnie? Lista: 10 * 64.2 * 1000 = 642000 usec, dict: 10000000 * 0.0759 = 759000 usec i set: 1000000 * 0.262 = 262000 usec ... więc zestawy są najszybsze, a następnie lista i dyktatura jako ostatnia na twoim przykładzie. Czy może czegoś brakuje? – andzep

... ale pytanie do mnie tutaj brzmi: co właściwie mierzy ten czas? Nie czas dostępu dla danej listy, dyktowania lub ustawiania, ale o wiele więcej, czas i pętle do _twarcia_ listy, dyktowania, ustawiania i wreszcie do wyszukiwania i uzyskiwania dostępu do jednej wartości. Czy to w ogóle ma związek z pytaniem? ... Jest to interesujące ... – andzep

@andzep, mylisz się, opcja '-s' polega na skonfigurowaniu środowiska' timeit', tzn. Nie wlicza się do całkowitego czasu. Opcja '-s' jest uruchamiana tylko raz. Na Pythonie 3.3, otrzymuję następujące wyniki: gen (zakres) -> 0.229 usec, lista -> 157 msec, dict -> 0.0806 usec, set -> 0.0807 usec. Ustawienie i dyktowanie wydajności jest takie samo. Dict wymaga jednak nieco więcej czasu na zainicjowanie niż ustawienie (całkowity czas 13.580 s v. 11,803s) – sleblanc

Python: Lista kontra Dict dla tabeli wyszukiwania

Odpowiedz

łącze

pamięci

Powiązane problemy