如何从 python 中的 defaultdict(int) 中删除重复值？

Question

我有一个字典，它由如下唯一的键值对组成：

    edu_bg={1: 1, 2: 2, 3: 1, 4: 1, 5: 2, 6: 2}

我想根据以上数据创建一个字典，以便将相似的记录（具有相似的值）分组如下：

   {(1, 3): 1, (5, 6): 1, (1, 4): 1, (2, 6): 1,(2, 5): 1, (3, 4): 1})

我尝试使用以下代码实现上述输出：

    myedu = defaultdict(int)
    for k,v in edu_bg.iteritems():
        for K,V in edu_bg.iteritems():
          if K == k and V == v:
              pass
          if K != k and V == v:
              myedu[(k,K)] += 1
          else:
              pass

然而却导致重复记录如下：

         defaultdict(<type 'int'>, {(1, 3): 1, (5, 6): 1, (4, 1): 1, (3, 1): 1, (5, 2): 1, (1, 4): 1, (2, 6): 1, (4, 3): 1, (6, 2): 1, (2, 5): 1, (3, 4): 1, (6, 5): 1})

我想删除这些重复值。对此问题的任何建议表示赞赏。

Answer 1

您正在将每个键与所有其他键（包括它们自己）进行比较。这些导致 n**2 检查，包括您不想考虑的两种情况：键与自身比较和键比较两次。您已经正确传递了键相等的情况。您可以传递键 k 小于键 K 的情况，这将忽略本应重复的一半检查。

from collections import defaultdict

edu_bg = {1:1, 2:2, 3:1, 4:1, 5:2, 6:2}
myedu = defaultdict(int)
for k,v in edu_bg.iteritems():
    for K,V in edu_bg.iteritems():
        if K == k and V == v:
            pass
        if K > k and V == v:
            myedu[(k,K)] += 1
        else:
            pass
print myedu

理想情况下，您会限制 for 循环，这样密钥被同等或两次计算的情况就永远不会发生。您可以通过以下方式进行操作：

edu_bg = {1:1, 2:2, 3:1, 4:1, 5:2, 6:2}
myedu = defaultdict(int)
keys = edu_bg.keys()
for i in xrange(len(keys)):
    for j in xrange(i+1, len(keys)):
        k = keys[i]
        K = keys[j]
        if edu_bg[k] == edu_bg[K]:
            myedu[(k,K)] += 1         

print myedu

Answer 2

不是迭代每对的笛卡尔积，这将迭代恰好 n^2 个元素，您可以迭代每个可能的组合，这将迭代 n(n-1)/2 个元素。虽然 Big Oh 复杂度相同，但常数因子将显着降低：

>>> from collections import defaultdict
>>> from itertools import combinations
>>> myedu = defaultdict(int)
>>> edu_bg={1: 1, 2: 2, 3: 1, 4: 1, 5: 2, 6: 2}
>>> for k1,k2 in combinations(edu_bg,2):
...   if edu_bg[k1] == edu_bg[k2]:
...     myedu[(k1,k2)] += 1
... 
>>> myedu
defaultdict(<class 'int'>, {(2, 6): 1, (1, 3): 1, (5, 6): 1, (2, 5): 1, (3, 4): 1, (1, 4): 1})
>>>

不过我要重申一下，这听起来像是 XY problem...

Answer 3

反转映射并获取按值划分的键组的组合。

>>> edu_bg={1: 1, 2: 2, 3: 1, 4: 1, 5: 2, 6: 2}
>>> def invert(d):
...     i={}
...     for k,v in d.iteritems():
...             i.setdefault(v,[]).append(k)
...     return i
... 
>>> invert(edu_bg)
{1: [1, 3, 4], 2: [2, 5, 6]}

然后为每个子列表计算 combinations(sublist, 2):

>>> [comb for sublist in {1: [1, 3, 4], 2: [2, 5, 6]}.values() for comb in combinations(sublist, 2)]
[(1, 3), (1, 4), (3, 4), (2, 5), (2, 6), (5, 6)]

所有计数将始终为 1，因为每个组合只生成一次。因此，我们可以简单地生成请求的输出：

>>> dict.fromkeys([(1, 3), (1, 4), (3, 4), (2, 5), (2, 6), (5, 6)], 1)
{(2, 6): 1, (5, 6): 1, (1, 4): 1, (1, 3): 1, (2, 5): 1, (3, 4): 1}

每一步合并

>>> dict.fromkeys([comb for sublist in invert(edu_bg).values() for comb in combinations(sublist, 2)],1)
{(2, 6): 1, (5, 6): 1, (1, 4): 1, (1, 3): 1, (2, 5): 1, (3, 4): 1}

这比迭代产品或组合和过滤的成本要低得多。这也会生成所有没有重复的输出。

如何从 python 中的 defaultdict(int) 中删除重复值？

How to remove duplicate values from defaultdict(int) in python?

python

duplicates

defaultdict