Python jest "kluczem do dyktowania" innym/szybszym niż "key in dict.keys()"

Question

Intuicyjnie myślę, że key in dict jest szybszy niż key in dict.keys(), ponieważ .keys() tworzy listę kluczy. To pytanie ma potwierdzić, czy to prawda.

Zastanawiasz się, czy key in dict wewnętrznie tworzy/używa listy, aby sprawdzić, czy klucz jest obecny?

Czy jedna metoda jest szybsza od drugiej?

Answer 1

Krótka odpowiedź:

• W python 2: Twoje założenie jest poprawne: dict.keys() spowalnia.
• W Pythonie 3: Twój założenie nie jest prawidłowe: in dict.keys() zachowuje się jak jak in dict

Detale dla Py2 i py3 śledzić poniżej.

Python 2.7 odpowiedź:

Twoje założenie jest poprawne, z następujących powodów:

• dict.keys() wymaga dodatkowego wywołania funkcji (stos overhead).
• dict.keys() zwraca listę, która zawiera wszystkie klucze w pamięci (w przeciwieństwie do leniwego obiektu generatora). Dlatego musi przydzielić pamięć.
• key in dict może używać wewnętrznego obiektu, który jest indeksowanym odnośnikiem. key in dict.keys() jest przeszukiwanie liniowe w postaci listy

stworzyłem mały skrypt benckmark pokazać mój punkt:

#! /usr/bin/python2.7 

import datetime as dt 
import random 

dict_size = 1000000 
num_iterations = 100 

d = {i: i for i in xrange(dict_size)} 

def f(): 
    k = random.randint(0,dict_size-1) 
    return (k in d) 

def g(): 
    k = random.randint(0,dict_size-1) 
    return (k in d.keys()) 

def test(func): 
    t = dt.datetime.utcnow() 
    for i in xrange(num_iterations): 
     func() 
    print "%s --> %1.6f s" % (func, (dt.datetime.utcnow()-t).total_seconds()) 

test(f) 
test(g) 

Output (Python 2.7.6 Ubuntu 14.04):

<function f at 0x7ff2e0126d70> --> 0.000598 s 
<function g at 0x7ff2e0126de8> --> 5.191553 s 

I testowany również z numerami iteracji i zamienionymi rozmiarami dyktowanymi (dyktuje tylko 100 pozycji, iteracje 1M).

<function f at 0x7f94cb5e6d70> --> 3.614162 s 
<function g at 0x7f94cb5e6de8> --> 7.007922 s 

Tutaj wyniki są znacznie bliżej siebie.

Różnica w wydajności naprawdę rośnie wraz z rozmiarem dyktatury.

Python 3 odpowiedź:

I dostosowany skrypt dla Pythona 3:

• xrange nie ma, zamiast używać range.(Nie w wydajności krytycznych wewnętrznej pętli funkcji testowej tak ograniczony wpływ na wydajność)
• mechanicznych klamry z print
• linii zmienia shabang do #!/usr/bin/python3

i przebadano pytona 3.4.3 na tym samym maszyna.

• dict_size = 1000000; num_iterations = 100

  f -> 0.000590 s G -> 0,000565 y

• dict_size = 100; num_iterations = 1000000

  f -> 4.525487 s G -> 4,837232 y

Więc pytona 3, różnica wyników nie ma.