尋找重疊的/一個巨大的名單亞羣的另一大名單

我寫了一個Python模塊通過檢查列表中的重疊的項目/與另一個列表項相交，以找到一個列表的子集相交。我模塊的主要部分看起來是這樣的：尋找重疊的/一個巨大的名單亞羣的另一大名單

from collections import defaultdict

有總的overalllist 1865390個項目（項目是數組）

overalllist = [(8361474, 8363645), (8363182, 8363758), …, (14634342, 14634440)]

有在MYLIST共有608348項

mylist = [(8362677, 8363216), (8414202, 8414313), …, (14634354, 14634397)]

查找列表的子集

def mysubsets(list1, list2):      
    sublist = [(x, y) for x, y in list1 if x <= list2[1] and y >= list2[0]]     
    return sublist

對於上面給出我的示例列表，MYLIST的第一項，（8362677，8363216），重疊與前兩個項overalllist的，[（8361474，8363645），（8363182，8363758）]。因此，對於（8362677,8363216），整體列表的子集是[（8361474,8363645），（8363182,8363758）]，...

初始化將填充項目的空字典作爲鍵和子集從overalllist通過在MYLIST每個項目值

mydict = defaultdict(list)

循環並找到overalllist子集，並把它們放到mydict

for item in mylist: 
    sublist = mysubsets(overalllist, item) 
    mydict.update({item:sublist})

輸出看起來是這樣的

>>> mydict 
defaultdict(<type 'list'>, {(14634354, 14634397): [(14634342, 14634440)], …, (8362677, 8363216): [(8361474, 8363645), (8363182, 8363758)]})

我的劇本作品，但極其緩慢（它跑了大約18小時）。我檢查使用CPROFILE的執行時間，發現mysubsets（）花了大量的時間：

ncalls tottime percall cumtime percall文件名：LINENO（功能）
608348 1732.827 0.003 1732.827 0.003 mymodule.py:383(mysubsets ）

我不知道是否有任何最快速，高效的方式來實現我的目標。謝謝。

來源

2016-01-19 lisa

所以在每個列表中你有一系列的時間間隔，對吧？我們可以假設每個列表中的間隔在它們之間沒有重疊嗎？ –

列表是否已分類？ – tglaria

@tglaria：我排序了兩個列表。 – lisa

假設在每個列表中的間隔有themsevles之間沒有重疊，第一排序每個列表中，然後從開始到結束遍歷這兩個列表，在線性時間內，下面的這個僞代碼：

i1 = 0 
i2 = 0 
while i1<len(list1) && i2<len(list2): 
    if list1[i1] is to the left of list2[i2]: 
    i1 += 1 
    elif list2[i2] is to the left of list1[i1]: 
    i2 += 1 
    else // list1[i1] overlaps list2[i2] 
    find all intervals from list2[i2:] that overlap with the interval list1[i1] 
    i1 += 1

來源

2016-01-19 14:55:42

根據描述，列表中有重疊。 – tglaria

很酷。祝你好運，麗莎。如果您在我的算法中發現錯誤，請告訴我，我會更正它。可能對其他人有用。 –

我檢查了我的列表，它們之間有一些重疊在每個列表中。對於那個很抱歉。 – lisa

def mysubsets(list1, list2): 
    len_l2 = len(list2) 
    idx = 0 
    sublist = [] 
    for x,y in list1: 
     if x<=list2[idx][0]: 
      if y>=list2[idx][1]: 
       sublist.append((x,y)) 
     else: 
      idx+=1 
      if idx>=len_l2: 
       break 
    return sublist

來源

2016-01-19 14:57:44 tglaria

比你的幫助，我會嘗試你的代碼，並讓你知道結果。 – lisa

這不適用於重疊部分（在'overalllist'中） – tglaria

我在我的列表的子集中做了一個快速測試，腳本仍然運行得非常慢 – lisa

你可以嘗試另一種方法是分而治之的一個，這不承擔相互排斥的時間間隔：

修正了一些值X.

Take list1, divide it to three lists: left1, mid1, right1. 
    left1 contains all intervals that are left of x. 
    right1 contains all intervals that are right of x. 
    mid1 contains all intervals that contain x

值X應該被選擇爲使得它大致放入LEFT1的項目，而另一半在RIGHT1的一半。

Do the same for list2. Divide it to three lists: left2, mid2, right2.

現在我們知道，LEFT1與RIGHT2 而LEFT2沒有重疊與RIGHT1沒有重疊

Now, recursively find all overlaps between (left1+mid1) and (left2+mid2) 
and all overlaps between (right1+mid1) and (right2+mid2)

的遞歸終止條件應該是其中一個列表的大小低於一些門檻。

這不是一個最優算法，這裏也有重疊，會發現一次以上。但出於實際目的應該足夠快。

來源

2016-01-19 15:44:26

謝謝阿迪萊文。你的代碼是用Python還是其他語言編寫的？我需要一個Python代碼片段並將其插入到我的Python模塊中。 – lisa

我剛寫了一些僞代碼 - 不是Python :-) –

尋找重疊的/一個巨大的名單亞羣的另一大名單

回答

相關問題