2sumのパフォーマンス向上

Question

ファイルには正と負の両方の100万の整数が含まれています（いくつかの繰り返しがあります）。これは整数の配列で、ファイルのi番目の行は配列のi番目のエントリを指定します。

入力ファイルにx + y = tを満たす別個の番号x、yが存在するように、区間[-10000,10000]（両端を含む）内のターゲット値tの数を計算することです。 WAYY遅すぎるコードの上

#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() 

0〜20001

数値答えは整数です。

EDIT：[set()] * nのような構文を使用してHを初期化するWillem Van Onsemの発言に従ってコードを編集しましたが、これは間違っています。コードはまだ遅いですが、私はもっと笑を知っています。

Answer 1

私はあなたのコードを実行することはできませんが、パフォーマンスを判断するためにプロファイルを使用することをお勧めします。 は、私はそれがO（N * N）操作です

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

にすべての問題が起こると思います。

おそらく、ハッシュテーブルソリューションを試す必要があります。