die Laufzeitdifferenz der Liste vs dict Verständnis

Question

Ich war für meinen Test zu studieren und ist eher zufällig auf diesem:

Die Frage ist: Welcher Algorithmus ist die schnellste , das ist die langsamste.

def f1(): 
    a = [] 
    for j in range(100000): 
     a.append(j*j) 

    for j in range(100000): 
     if 99999*j == a[j]: 
      print("yes") 
def f2(): 
    a = [] 
    for j in range(100000): 
     a.append(j*j) 

    for j in range(100000): 
     if 99999*j in a: 
      print("yes") 
def f3(): 
    d = {} 
    for j in range(100000): 
     d[j] = j*j 

    for j in range(100000): 
     if 99999*j in d: 
      print("yes") 

Ich verstand f2 die ist langsamste weil zu überprüfen, ob ein Element in einer Liste ist, dass Sie alle Mitglieder der Liste laufen.

Was würde schneller laufen? Boolescher Ausdruck: (99999 * j == a [j]) oder (99999 * j in d, wobei d ein Wörterbuch ist und Hash verwendet) und warum? Ich dachte, Hash macht alles O (1), also sollten sie gleich sein.

Vielen Dank.

Answer 1

jetzt ohne Bearbeitung in Fall 3 Sie nur nach Schlüsseln nicht Werte suchen und vielleicht ist dies ein Fehler. bu, wenn Sie es wie bearbeiten

def f3(): 
    d = {} 
    for j in range(100000): 
     d[j] = j*j 
    for j in range(100000): 
     if d[j] == 99999*j: 
      print("yes") 

dann funktionieren auch 1 schneller

sein