Python的間隔interesction

Question

我的問題如下：

具有間隔的列表文件：

1 5 
2 8 
9 12 
20 30 

和一系列

0 200 

我想這樣做這樣的交集將在給定範圍內報告我的間隔之間的位置[開始結束]。

例如：

8 9 
12 20 
30 200 

除了任何想法如何咬這，也將是不錯的閱讀優化的一些想法，因爲一如既往輸入文件都將是巨大的。

Answer 1

該解決方案的工作原理是間隔按起始點排序，不需要創建與總範圍一樣大的列表。

代碼

with open("0.txt") as f: 
    t=[x.rstrip("\n").split("\t") for x in f.readlines()] 
    intervals=[(int(x[0]),int(x[1])) for x in t] 

def find_ints(intervals, mn, mx): 
    next_start = mn 
    for x in intervals: 
     if next_start < x[0]: 
      yield next_start,x[0] 
      next_start = x[1] 
     elif next_start < x[1]: 
      next_start = x[1] 
    if next_start < mx: 
     yield next_start, mx 

print list(find_ints(intervals, 0, 200)) 

輸出：

（在你給的例子的情況下）

[(0, 1), (8, 9), (12, 20), (30, 200)] 

Answer 2

粗糙算法：

1. 創建布爾值的陣列，全部設置爲假seen = [False]*200
2. 遍歷輸入文件，對於每一個線start end設置seen[start] .. seen[end]是True
3. 一旦完成，那麼你可以輕鬆地走數組來找到未使用的時間間隔。

在最佳化的方面，如果輸入的範圍列表上開始數進行排序，那麼你就可以跟蹤最高看到數並用它來過濾範圍，因爲它們處理 - 例如像

for (start,end) in input: 
    if end<=lowest_unseen: 
    next 
    if start<lowest_unseen: 
    start=lowest_unseen 
    ... 

它（忽略原始排序的成本）應該使整個事情爲O（n） - 你去通過陣列一次標籤看到/看不見的，一旦輸出unseens。

似乎我感覺很好。這裏是（未優化）的代碼，假設你的輸入文件被稱爲input

seen = [False]*200 
file = open('input','r') 
rows = file.readlines() 
for row in rows: 
    (start,end) = row.split(' ') 
    print "%s %s" % (start,end) 
    for x in range(int(start)-1, int(end)-1): 
    seen[x] = True 

print seen[0:10] 

in_unseen_block=False 
start=1 
for x in range(1,200): 
    val=seen[x-1] 
    if val and not in_unseen_block: 
    continue 
    if not val and in_unseen_block: 
    continue 
    # Must be at a change point. 
    if val: 
    # we have reached the end of the block 
    print "%s %s" % (start,x) 
    in_unseen_block = False 
    else: 
    # start of new block 
    start = x 
    in_unseen_block = True 
# Handle end block 
if in_unseen_block: 
    print "%s %s" % (start, 200) 

我要離開的優化作爲一個練習留給讀者。

Answer 3

如果每次輸入間隔打開或關閉時都做一個註釋，您可以將opens和closes的鍵合併成一個有序集合，然後就可以完成所需的操作基本上可以這樣認爲，「好吧，讓我們假設每一對相鄰的數字形成一個間隔，然後我可以把所有的邏輯作爲離散塊集中在這些間隔上。」

myRange = range(201) 
intervals = [(1,5), (2,8), (9,12), (20,30)] 
opens = {} 
closes = {} 

def open(index): 
    if index not in opens: 
     opens[index] = 0 
    opens[index] += 1 

def close(index): 
    if index not in closes: 
     closes[index] = 0 
    closes[index] += 1 

for start, end in intervals: 
    if end > start: # Making sure to exclude empty intervals, which can be problematic later 
     open(start) 
     close(end) 

# Sort all the interval-endpoints that we really need to look at 
oset = {0:None, 200:None} 
for k in opens.keys(): 
    oset[k] = None 
for k in closes.keys(): 
    oset[k] = None 
relevant_indices = sorted(oset.keys()) 

# Find the clear ranges 
state = 0 
results = [] 
for i in range(len(relevant_indices) - 1): 
    start = relevant_indices[i] 
    end = relevant_indices[i+1] 

    start_state = state 
    if start in opens: 
     start_state += opens[start] 
    if start in closes: 
     start_state -= closes[start] 

    end_state = start_state 
    if end in opens: 
     end_state += opens[end] 
    if end in closes: 
     end_state -= closes[end] 
    state = end_state 

    if start_state == 0: 
     result_start = start 
     result_end = end 
     results.append((result_start, result_end)) 

for start, end in results: 
    print(str(start) + " " + str(end)) 

此輸出：

0 1 
8 9 
12 20 
30 200 

的間隔不需要進行排序。