使用元组分隔集

在名为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

使用元组分隔集

回答

相关问题