python - 使用巨大的列表优化循环

Question

我尝试编写一个高效的代码来处理巨大的列表。我正在比较几个与位置相关的列表。

理论列表:

Tx,Ty,Px,Py,Pz (Tx,Ty are locations and Px,Py,Pz are values of parameters associated with these locations)

真实列表:

Rx,Ry,px,py,pz 

len(Tx) = 215 000 and len(Rx) = 68 000 000

我做的第一件事是用理论上的 maxTx、maxTy、minTx 和 minTy 切割 Real 列表:

 r=[index for index, value in enumerate(Rx) if value<=maxTx and value>=minTx]
 for p in range (len(r)):
        rx.append(Rx[r[p]]) (same for Ry,px,py, pz)

然后我对 y 坐标执行相同的操作，因此我在准备比较的理论位置周围划定了一个正方形，现在 len(Rx) = 6 500 000

现在，我想让每个真实位置索引都满足特定条件:

       for i in range (len(set(Tx))):
       l=[index for index,value in enumerate(set(Rx)) if value<=Tx[i]+d  and value>=Tx[i]-d]
              for j in range (len(l)):
              rrx.append(Rx[l[j]]) (same for Ry,px,py,pz)

显然，这按预期工作，但是用 6500000 个 Rx 值检查每 215000 个 Tx 值需要很长时间。我想要的是符合我的条件的 Rx 值的索引，所以我只存储它。

然后我用较短列表的 y 个位置检查它..

我的最终条件是:

    for n in range (len(Rrrx)):
        if sqrt((Tx[i]-Rx[n])**2+(Ty[i]-Ry[n])**2)<=d:
            Sx.append(Rx[n])
            Sy.append(Ry[n])
            Dif.append(sqrt((Tx[i]-Rx[n])**2+(Ty[i]-Ry[n])**2)

首先，我刚刚检查了这个条件，但是用 68000000 个值检查每 215000 个值显然太长了，这就是为什么我在进行比较之前尝试将 Real 列表减少到最少的原因。

我希望这是可以理解的，你知道另一种更快的方法吗？感谢您的帮助

Answer 1

想象一个大小为 d/2 的网格。

根据 T 点所在的网格正方形将它们分成桶。您可以使用从网格正方形到点的 map 。

现在，对于每个 R 点，您只需要将它与 d 距离内的 9 个方格中的 T 点进行检查