3

在名为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() 来缩小混合集列表。我发现使用 pop() 会使列表推导、for 循环或任何迭代器出现问题，因此我使用了 while 循环。

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

4

1 回答 1

0

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

类似[当前未测试]：

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

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

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

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

于 2012-08-16T19:43:05.157 回答