python - 使用元组分离集合

Question

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

现在这看起来不像是执行此任务的最 pythonic 方式。这段代码适用于大型元组列表(大约 2E6)，我觉得如果程序不必检查已经排序的元组，它会运行得更快。因此我使用 pop() 来缩小 mixed_sets 列表。我发现使用 pop() 会导致列表理解、for 循环或任何迭代器出现问题，因此我改用 while 循环。

它确实有效，但是是否有更 pythonic 的方式来执行此任务，而不使用 while 循环和 idx 和 idx2 计数器？

Answer 1

您可能可以通过首先计算混合集元组中所有第一个元素的集合和所有第二个元素的集合来提高速度。然后在您的迭代中，您可以检查第一个或第二个元素是否在其中一个集合中，并使用二进制搜索找到正确的完整元组。 实际上你需要多集，你可以使用字典来模拟。

类似[目前未测试]:

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, first, index=0,1)”返回属于 mixed_sets 的元组，该元组在给定索引处具有“first”。

可能您还必须复制 mixed_sets 并按第一个元素排序一个副本，另一个按第二个元素排序。

或者也许您可以再次使用字典。添加到“first_els”和“second_els”中的值也是一个排序的元组列表。

我不知道性能会如何扩展，但我认为如果数据在 200 万左右，您就不必担心太多。