Słownik Pythona kontra lista, która jest szybsza?

Question

Zakodowałem problem Eulera i wpadłem w wątpliwość, która wywołała moją ciekawość. Mam dwa fragmenty kodu. Jednym z nich jest lista innych słowników używających.

Używanie list:

n=100000 
num=[] 
suma=0 
for i in range(n,1,-1): 
    tmp=tuple(set([n for n in factors(i)])) 
    if len(tmp) != 2: continue 
    if tmp not in num: 
     num.append(tmp) 
      suma+=i 

wykorzystujące słowniki:

n=100000 
num={} 
suma=0 
for i in range(n,1,-1): 
    tmp=tuple(set([n for n in factors(i)])) 
    if len(tmp) != 2: continue 
    if tmp not in num: 
     num[tmp]=i 
     suma+=i 

Obawiam się tylko o wydajność. Dlaczego drugi przykład użycia słowników działa niesamowicie szybko, szybciej niż pierwszy przykład z listami. przykład ze słownikami działa prawie trzydzieści razy szybciej!

Przetestowałem te 2 kody za pomocą n = 1000000, a pierwszy kod uruchomiono w 1032 sekundy, a drugi w 3,3 sekundy "amazin"!

Answer 1

Na liście kod if tmp not in num: to O (n) , natomiast O (lgn) w dyktafonie .

Edytuj: Dict jest oparty na haszowaniu, więc jest znacznie szybszy niż wyszukiwanie listy liniowej. Dzięki @ user2357112 za to.

Answer 2

Jestem prawie pewien, że "magiczny sos" za pomocą słownika polega na tym, że słownik składa się z par klucz-> wartość.

Na liście macie do czynienia z tablicami, co oznacza, że ​​pętla for musi wystartować z indeksu 0 wewnątrz listy, aby przechodzić przez każdy rekord.

słownika prostu musi znaleźć kluczykowy> parę wartości w pytaniu na pierwszym „go-round” i odesłać go, stąd prędkość ...

zasadzie, badania do członkostwa w zestawie klucz -> pary wartości są o wiele szybsze niż wyszukiwanie całej listy dla wartości. im większa twoja lista, tym wolniej będzie ... ale to nie zawsze tak jest, są scenariusze, w których lista będzie szybsza ... ale wierzę, że to może być odpowiedź, którą szukasz

Answer 3

W języku Python, średni czas złożoności wyszukiwania klucza słownikowego to O (1), ponieważ są one zaimplementowane jako tablice skrótów. Złożoność czasowa wyszukiwania na liście to średnio O (n). W kodzie robi to różnicę w linii if tmp not in num:, ponieważ w przypadku listy Python musi przeszukać całą listę, aby wykryć członkostwo, podczas gdy w przypadku dyktatury nie wyklucza absolutnie najgorszego przypadku.

Aby uzyskać więcej informacji, sprawdź numer TimeComplexity.

Answer 4

Jeśli chodzi o prędkość, nie powinno stwarzać żadnych list:

n = 100000 
factors = ((frozenset(factors(i)), i) for i in range(2, n+1)) 
num = {k:v for k,v in factors if len(k)==2} 
suma = sum(num.values())