在區間列表中快速查找

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

在區間列表中快速查找

回答

相關問題