간격 목록의 빠른 찾아보기

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()