Python key in dict.keys() Wydajność dla dużych słowników

Question

Zastanawiam się, czy moglibyście mi dać jakąś radę, aby znacznie poprawić wydajność mojego kodu.

Mam zestaw pętli for, które sprawdzają, czy klucz znajduje się w słowniku, którego wartością jest lista, jeśli klucz istnieje, dołącza do listy, a jeśli nie, dodaje nową listę dla tego klucza

dict={} 
for value in value_list: 
    if value.key in dict.keys(): 
     temp_list = dict[value.key] 
     temp_list.append(value.val) 
     dict[value.key] = temp_list 
    else: 
     dict[value.key] = [value.val] 

teraz ten kod działa poprawnie, ale evenrually jako słownika zaczyna zapełniać value.key linii w dict.keys() staje się coraz bardziej uciążliwe.

Czy jest lepszy sposób to zrobić?

Dzięki,

Mike

Answer 1

Nie rób tego:

value.key in dict.keys() 

że - Python 2, le ast - tworzy listę zawierającą każdy klucz. To staje się coraz droższe, gdy słownik staje się większy i wykonuje wyszukiwanie O (n) na liście, aby znaleźć klucz, który pokonuje cel użycia dyktatury.

Zamiast tego po prostu zrobić:

value.key in dict 

który nie tworzy listę tymczasowy, i robi tablica mieszająca odnośnika do klucza, zamiast poszukiwania liniowego.

setdefault, jak wspomniano w innym miejscu, jest czystszy sposób, aby to zrobić, ale bardzo ważne jest, aby zrozumieć powyższe.

Answer 2

Korzystanie collections.defaultdict, to można uprościć do

d = collections.defaultdict(list) 
for value in value_list: 
    d[value.key].append(value.val) 

Answer 3

your_dict.setdefault(value.key, []).append(value.val) 

Answer 4

if value.key in dict.keys(): 

Jest bardzo kosztowne, ponieważ przechodzisz na listę kluczy, a następnie przeszukujesz listę. Wystarczy, że przy wymianie:

if value.key in dict: 

Gdyby skrócić wyszukiwanie do ~ log N (edit: Stoję poprawione przez Glenn, prawdopodobnie nawet szybciej, ponieważ słowniki Python użyć tabeli hash). Po prostu:

dict[key].append(value.val) 

Należy przyspieszyć trochę. Używanie tymczasowego nie jest wymagane i po prostu zjada kilka cykli procesora.

Jeśli możesz podać więcej szczegółów na temat tego, co próbujesz zrobić, ktoś może zaproponować lepszy algorytm.

Answer 5

Krok 1: przekształcamy kod używając temp_list w jedno wyrażenie (zakładam, że poza tym kodem nie jest potrzebne temp_list), używając metody dodawania zamiast metody append. Ponadto, nie musimy wyraźnie używać dict.keys(), jak wspomnieli inni (a tak naprawdę to marnuje ogromną ilość czasu).

for value in value_list: 
    if value.key in dict: 
     dict[value.key] = dict[value.key] + [value.val] 
    else: 
     dict[value.key] = [value.val] 

Krok 2: Przekształć przypisania w tę samą lokalizację, używając składni wyrażeń warunkowych.

for value in value_list: 
    dict[value.key] = dict[value.key] + [value.val] if value.key in dict else [value.val] 

Krok 3: Dołączanie lub poprzedzenie pustą listę nie ma wpływu na wartość z listy, tak że możemy wstawić, a następnie czynnik poza wspólną „dodatek” wartości.

for value in value_list: 
    dict[value.key] = (dict[value.key] if value.key in dict else []) + [value.val] 

Krok 4: Rozpoznawanie że DICT posiada wbudowane funkcjonalności do dostarczania „default” wartość, gdy klucz jest nieobecny:

for value in value_list: 
    dict[value.key] = dict.get(value.key, []) + [value.val] 

Krok 5: Zamiast się wartość, modyfikując go i ustawienie go z powrotem, możemy użyć .setdefault dać nam aktualną zawartość (lub ustawić je, jeśli jeszcze nie ma), a następnie wrócić do używania .append zmodyfikować listę:

for value in value_list: 
    dict.setdefault(value.key, []).append(value.val) 

(Chodzi mi o to, że mogłem tylko na to spojrzeć i zastanowić się przez chwilę, ale gdy zobaczyłem każdy krok, dokładniej, dokąd zmierzamy ...)