アルゴリズムの速度

Question

私は、次の3つの機能のうち1ヶ月の日数を調べる最速の方法を見つけようとしていました。

def f1(): 
    t=time.time() 
    for month in range(1,13): 
     for year in range(10001): 
      leap_year=(year%4==0 and year%100!=0) or year%400==0 
      n=[29,31,28,31,30,31,30,31,31,30,31,30,31][month-2*leap_year*(month==2)] 
    return time.time()-t1 
def f2(): 
    t=time.time() 
    for month in range(1,13): 
     for year in range(10001): 
      leap_year=(year%4==0 and year%100!=0) or year%400==0 
      n=[31,28,31,30,31,30,31,31,30,31,30,31][month-1]+leap_year*(month==2) 
    return time.time()-t 
def f3(): 
    t=time.time() 
    for month in range(1,13): 
     for year in range(10001): 
      leap_year=(year%4==0 and year%100!=0) or year%400==0 
      n={1: 31, 2: 28, 3: 31, 4: 30, 5: 31, 6: 30, 7: 31, 8: 31, 9: 30, 10: 31, 11: 30, 12: 31}[month]+leap_year*(month==2) 
    return time.time()-t 
print(sum(f1() for i in range(100))) 
print(sum(f2() for i in range(100))) 
print(sum(f3() for i in range(100))) 

辞書のアルゴリズムが最も高速であると予想していました。しかし、私はこれを持っています：

3.7855005264282227 
3.625513792037964 
9.0009183883667 

明らかに、私は間違っていました。誰かがdictアルゴリズムのスピードが遅い理由を説明することはできますか？それは時間（O（1））を最小限に取るべきであり、リストアルゴリズムはO（n）を取るべきです。これは私が得た結果と矛盾します。私はプログラミングに非常に新しいです。ありがとう！

Answer 1

すべての繰り返しでリスト/辞書を作成しています。 これを一度しかビルドしないと、f3（）メソッドが最も速くなります。listとdictの両方のアクセス時間はO（1）です。

def f1(): 
    t=time.time() 
    m=[29,31,28,31,30,31,30,31,31,30,31,30,31] 
    for month in range(1,13): 
     for year in range(10001): 
      leap_year=(year%4==0 and year%100!=0) or year%400==0 
      n=m[month-2*leap_year*(month==2)] 
    return time.time()-t 
def f2(): 
    t=time.time() 
    m=[31,28,31,30,31,30,31,31,30,31,30,31] 
    for month in range(1,13): 
     for year in range(10001): 
      leap_year=(year%4==0 and year%100!=0) or year%400==0 
      n=m[month-1]+leap_year*(month==2) 
    return time.time()-t 



def f3(): 
    t=time.time() 
    m={1: 31, 2: 28, 3: 31, 4: 30, 5: 31, 6: 30, 7: 31, 8: 31, 9: 30, 10: 31, 11: 30, 12: 31} 
    for month in range(1,13): 
     for year in range(10001): 
      leap_year=(year%4==0 and year%100!=0) or year%400==0 
      n=m[month]+leap_year*(month==2) 
    return time.time()-t 


print(sum(f1() for i in range(100))) 
print(sum(f2() for i in range(100))) 
print(sum(f3() for i in range(100)))