2sum性能改進

Question

該文件包含100萬個正整數和負整數（可能有一些重複！）。這是整數的數組，其中第i行指定數組的第i個條目。

任務是計算區間[-10000,10000]（含）內的目標值數t，使輸入文件中有不同數x，y滿足x + y = t。

數字的答案是0-2的整數20001.

#ans = 427 
data, count, n = set(map(int, open('2sum.txt').read().splitlines())), 0, 1000003 

def two_sum(): 
    global count 

    H = [] 
    for i in range(n): 
     H.append(set()) 

    for x in data: 
     insert(H, x) 

    for t in range(-10000, 10000 + 1): 
     for x in data: 
      if t - x != x and lookup(H, t - x): 
       count += 1 

    print(count) 

def insert(H, x): 
    H[hashfunc(x)].add(x) 

def lookup(H, x): 
    if x in H[hashfunc(x)]: 
     return True 
    return False 

def hashfunc(x): 
    return (x >> 10) % n 

if __name__ == '__main__': 
    two_sum() 

以上代碼之間

是WAYY太慢。

編輯：我編輯代碼按照Willem Van Onsem的說法使用類似[set()] * n的語法初始化H，這是錯誤的。代碼仍然很慢，但我現在知道更多現在哈哈。

Answer 1

我不能運行你的代碼，但我建議你使用配置文件來判斷性能。 我認爲所有的問題發生在

for t in range(-10000, 10000 + 1): 
    for x in data: 
     if t - x != x and lookup(H, t - x): 
      count += 1 

這是一個O（N * N）的操作。

也許你應該嘗試hashtable解決方案。