python - 在间隔列表中快速查找

Question

我有一个包含 ~280.000 个元素的开始和结束位置列表。总共覆盖了大约 73.000.000 个位置。

出于性能原因，我已经将它们分成字典中的部分(通过子集因子)，字典又包含一个元组列表(开始，结束)。

最后我得到一个位置列表，我想测试它们是否位于由开始和结束跨越的区域中。

posit = (start,end)
dict[subset].append(posit)

for position in dict[subset]:
    if posit[0] < varpos < posit[1]:
    # do some stuff here 

目前，这些查找需要很长时间。但出于内存方面的考虑，我也不想生成包含开始和停止之间所有位置的更快的集合。

对于如何创建快速开始、结束位置数据结构或更好的查找策略，您有什么建议吗？

Answer 1

我的假设是范围不重叠，并且 280000 个范围对象不会定期更改。我的第一直觉是使用排序的列表列表而不是字典对象列表。然后我将导入位置列表并将它们传递给“findRange”方法。

为了测试我的实现，我生成了一个包含 280000 个列表的排序列表。然后将1000个随机'possiblePositionMatches'传入findRange进行匹配。

此实现对 100 个“possiblePositionMatches”花费了 7.260579 秒，对 1000 个“possiblePositionMatches”花费了 71.96268 秒。

import random
import time

values = list()
for a in range(0,73000000,250) :
    values.append([a, a+200])

possiblePositionMatches = list()
count = 1000
while count:
    count = count - 1
    possiblePositionMatches.append(random.randint(0,73000000))

matches = []

def findRange(value) :
    for x in range(len(values)) :
        if (value >= values[x][0]) and (value < values[x][1]) :
            matches.append([value, values[x]])

def main():
    t1 = time.process_time()
    for y in possiblePositionMatches: 
        findRange(y)
    print (matches)
    t2 = time.process_time() - t1
    print("Total Time: {0} seconds".format(t2))

main()