使用元組分隔集

在名爲mixed_sets的元組列表中，存在三個獨立集。每個集合都包含具有相交值的元組。一組中的元組不會與另一組中的元組相交。使用元組分隔集

我想出了以下代碼來整理集合。我發現當涉及到元組時，python集的功能是有限的。如果集合交集操作可以查看每個元組索引而不是停在封閉元組對象上，那將會很好。

下面的代碼：

mixed_sets= [(1,15),(2,22),(2,23),(3,13),(3,15), 
       (3,17),(4,22),(4,23),(5,15),(5,17), 
       (6,21),(6,22),(6,23),(7,15),(8,12), 
       (8,15),(9,19),(9,20),(10,19),(10,20), 
       (11,14),(11,16),(11,18),(11,19)] 

def sort_sets(a_set): 
    idx= 0 
    idx2=0 
    while len(mixed_sets) > idx and len(a_set) > idx2: 
     if a_set[idx2][0] == mixed_sets[idx][0] or a_set[idx2][1] == mixed_sets[idx][1]: 
      a_set.append(mixed_sets[idx]) 
      mixed_sets.pop(idx) 
      idx=0 

     else: 
      idx+=1 
      if idx == len(mixed_sets): 
       idx2+=1 
       idx=0 
    a_set.pop(0) #remove first item; duplicate 
    print a_set, 'a returned set'    
    return a_set 

sorted_sets=[] 
for new_set in mixed_sets: 
    sorted_sets.append(sort_sets([new_set])) 

print mixed_sets #Now empty. 

OUTPUT: 
[(1, 15), (3, 15), (5, 15), (7, 15), (8, 15), (3, 13), (3, 17), (5, 17), (8, 12)] a returned set 
[(2, 22), (2, 23), (4, 23), (6, 23), (4, 22), (6, 22), (6, 21)] a returned set 
[(9, 19), (10, 19), (10, 20), (11, 19), (9, 20), (11, 14), (11, 16), (11, 18)] a returned set

現在，這看起來並不像完成這個任務的最Python的方式。這段代碼適用於大型元組列表（大約2E6），如果不需要檢查已經排序的元組，我覺得程序運行速度會更快。因此我使用pop（）來縮小mixed_sets列表。我發現使用pop（）使列表解析，循環或任何迭代器有問題，所以我使用while循環代替。

它確實有效，但是執行此任務時沒有使用while循環和idx和idx2計數器嗎？

來源

2012-08-09 Naaaysmith

請參閱[此問題]（http://stackoverflow.com/questions/9110837/python-simple-list-merging-based-on-intersections）多種解決方案的一個變種這個問題。 – DSM 2012-08-09 21:50:58

也許你可以通過首先計算mixed_sets中所有元組中所有第一個元素的集合和一組所有第二個元素來提高速度。然後在迭代中，您可以檢查第一個或第二個元素是否位於其中一個集合中，並使用二分搜索找到正確的完整元組。其實你需要多套，你可以使用字典來模擬。

喜歡的東西[目前未測試]：

from collections import defaultdict 
# define the mixed_sets list. 
mixed_sets.sort() 
first_els = defaultdict(int) 
secon_els = defaultdict(int) 

for first,second in mixed_sets: 
    first_els[first] += 1 
    second_els[second] += 1 


def sort_sets(a_set): 
    index= 0 
    while mixed_sets and len(a_set) > index: 
     first, second = a_set[index] 
     if first in first_els or second in second_els: 
      if first in first_els: 
       element = find_tuple(mixed_sets, first, index=0) 
       first_els[first] -= 1 
       if first_els[first] <= 0: 
        del first_els[first] 
      else: 
       element = find_tuple(mixed_sets, second, index=1) 
       second_els[second] -= 1 
       if second_els[second] <= 0: 
        del second_els[second] 

      a_set.append(element) 
      mixed_sets.remove(element) 
     index += 1 
    a_set.pop(0) #remove first item; duplicate 
    print a_set, 'a returned set'    
    return a_set

其中「find_tuple（mixed_sets，首先，索引= 0,1）」返回屬於具有「第一」給定索引處mixed_sets元組。

也許你將不得不復制mixed_sets，並按第一個元素對另一個副本進行排序，對第二個元素進行排序。

或者，也許你可以再次玩字典。添加到「first_els」和「second_els」中的值也是元組的排序列表。

我不知道表演會如何擴展，但我認爲如果數據的數量在200萬的數量級上，您不應該擔心太多。

來源

2012-08-16 19:43:05 Bakuriu

使用元組分隔集

回答

相關問題