2sum性能改进

该文件包含100万个正整数和负整数（可能有一些重复！）。这是整数的数组，其中第i行指定数组的第i个条目。2sum性能改进

任务是计算区间[-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，这是错误的。代码仍然很慢，但我现在知道更多现在哈哈。

来源

2017-04-14 Pranjal Verma

但你的'[set（）] * n'确实不*创建* n *个不同的集合：它会生成一个包含对同一集合的引用的列表。 –

@WillemVanOnsem omg我刚刚测试过，你是对的！我不知道。这是为什么发生？我通常初始化像[None] * n这样的列表，所以我天真地认为[set（）] * n也可以工作！ –

你不能摆脱查找功能吗？你只需要t -x数据。那么你也不需要H。 – Elan

我不能运行你的代码，但我建议你使用配置文件来判断性能。我认为所有的问题发生在

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解决方案。

来源

2017-04-14 09:10:09 obgnaw

这**实际上是** hashtable解决方案。如你所说，这个双重for循环实际上并不是“O（n^2）”。因为这里的n等于1百万，而不是20002。因此，双for循环更像是'20002 * n'，这又是'O（n）'。但是我会同意，在这个运行时中，常量20002真的非常糟糕。这实际上是我要求的修复。 –

然后您可以尝试将百万转化为20002，并记录时间，使用[PROFILE]（https://docs.python.org/2/library/profile.html）@PranjalVerma – obgnaw

2sum性能改进

回答

相关问题