在区间列表中快速查找

我有一个包含〜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

目前这些look ups需要很长时间。但是由于内存方面的考虑，我也不想生成一个包含开始和结束之间所有位置的更快的集合。

你有没有任何的指针如何创建一个快速启动，结束位置数据结构或更好的查找策略？

来源

2014-07-20 sargas

+11

考查[线段树]（https://en.wikipedia.org/wiki/Segment_tree）和[间隔树]（https://en.wikipedia.org/wiki/Interval_tree）。这是所谓[插入问题]的一个特例（http://www.cs.nthu.edu.tw/~wkhon/ds/ds10/tutorial/tutorial6.pdf） –

python bisect呢？它可以更快地产生效果 –

为什么不添加所有（开始，结束）元组，然后对结果列表进行排序？然后迭代排序列表以确定重叠（它们将彼此相邻）。或者你是否因为这种方法而受限于内存？ –

我的假设是范围不重叠，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()

来源

2015-06-12 20:20:43 Nanook

在区间列表中快速查找

回答

相关问题