我有两个 2D 列表，有 1000 万个 + 条目。List1充满了范围(例如[100, 25]的意思是范围从100开始，跨度为25，或100到125)，List2充满了情节点。我必须计算每个点适合多少个范围。
由于我要处理如此大量的数据，因此我从二进制搜索函数开始，以便更轻松地搜索起点，而不是逐个循环浏览整个列表。除了我修改了搜索以从我的情节点上方返回最接近的索引List1，因为情节点不能保证是List1中的一个元素。
我最终在List2和List1中的每个情节点之间做了比较，从我从二叉搜索中获得的索引开始，向下移动List1直到情点不再在一个范围内。虽然这有效，但这非常耗时且效率低下。
def findRange(List1, List2):
for plot in List2:
count = 0
startIndex = binarySearch(List1, plot)
while plot <= List1[startIndex - 1][0] + 250:
if List1[startIndex][0] < plot[0] < List1[startIndex][0] + List1[startIndex][1]:
count += 1
startIndex -= 1
plot[1] = count
return List2
我在while循环中有... + 250，因为范围距离可以是从0到250的任何地方，所以我用它来确定进一步的索引是否可能包含该点。
我已经研究了将List1转换为字典，其中键是总和的距离，值是找到的重复次数。我认为通过摆脱重复范围，我可以减少一些开销。不过，我找不到以这种方式获得正确解决方案的方法。
有什么建议可以指导我更好地优化我的算法吗？我只能使用标准库。
编辑：
List1 = [
[1233, 120],
[1233, 80],
[1490, 50],
[1789, 220],
[1800, 250]
]
List2 = [
[1300, 0],
[1450, 0],
[1490, 0],
[2000, 0]
]
我应该用情节点落入多少范围的数量来更新List2中的零。所以输出将是这样的：
List2 = [
[1300, 2], # this point can be found in List1[0] and List1[1] because 1300 is between 1233-1353 and 1233-1313
[1450, 0], # this plot can be found in none of ranges
[1490, 1], # this plot can be found in List1[2]
[2000, 2] # this plot can be found in List1[2] and List1[3]
]
如您所见，计数索引在List2从 0 更新到包含该点的范围数。
版本 1 (二叉搜索)
您最好在List2中搜索List1的元素，而不是相反。假设两个列表都已排序，您将始终缩小搜索空间。此外，您将避免在假设范围大小上限时必须执行的潜在浪费操作。
作为旁注，二叉搜索是在 python 的bisect模块中实现的。我建议同时使用bisect_left(用于范围开始)和bisect_right用于范围结束。
from bisect import bisect_left, bisect_right
start = 0
for rnge in List1:
start = bisect_left(List2, [rnge[0], 0], start)
end = bisect_right(List2, [rnge[0] + rnge[1] - 1, 0], start)
for plot_index in range(start, end):
List2[plot_index][1] += 1
示例的结果是
>>> List2
[[1300, 2], [1450, 0], [1490, 1], [2000, 2]]
版本 2(单程线性搜索)
话虽如此，我想到了更好的解决方案。您可以同时对两个列表进行一次传递中执行整个操作。有两个想法可以实现这一目标。
首先，考虑如果有两个可以查看的迭代器，会发生什么情况。您可以随时检查哪个更大，哪个更小，并递增适当的一个，直到另一个的头部更大或更小。
其次，您可以使用 List1，将每个范围的开始和结束转换为索引，并对所有这些索引进行排序。但是，您仍然必须跟踪哪些索引表示进入范围，哪些索引表示退出范围。实际上，您可以想象，输入范围会增加应分配给其中遇到的所有绘图的数字，而退出范围会减少该数字。
让我们首先使用第二个想法转换List1。它将成为对列表，其中第一个元素是索引，第二个元素是 +1 或 -1，具体取决于索引是开始还是结束：
actions = []
for rnge in List1:
actions.append([rnge[0], +1])
actions.append([rnge[0] + rnge[1], -1])
actions.sort()
现在你可以沿着两个列表(action和List2)步进，保持从action开始的增量的运行总和。如果List2中的元素的键比action中的元素小，则将当前增量分配给List2中的元素并继续。如果action中的键较小或相等，则通过更新增量(即进入或退出范围)来处理它：
end = (List2[-1] + 1, 0) # Key to ensure that increment stops changing once actions runs out
it = iter(actions)
key, inc = next(it, end)
increment = 0
for plot in List2: # Keep plot as a list, since it needs to be incremented
while key <= plot[0]:
increment += inc
key, inc = next(it, end)
plot[1] += increment
虽然此方法有两个部分，但请注意，它只沿List1进行两次线性走List2进行一次走。不涉及实际搜索，仅涉及比较。调用next(it, end)确保无论如何List2所有内容都得到完全处理，因为一旦actions用完，就不会递增iterator。
和以前一样，结果是
>>> List2
[[1300, 2], [1450, 0], [1490, 1], [2000, 2]]