8

我经常使用sorted和groupby查找可迭代项中的重复项。现在我发现它不可靠：

from itertools import groupby
data = 3 * ('x ',  (1,), u'x')
duplicates = [k for k, g in groupby(sorted(data)) if len(list(g)) > 1]
print duplicates
# [] printed - no duplicates found - like 9 unique values

上面的代码在 Python 2.x 中失败的原因在这里解释。

什么是查找重复项的可靠 Pythonic 方法？

我在 SO 上寻找类似的问题/答案。其中最好的是“在 Python 中，我如何获取一个列表并将其减少为重复项列表？ ”，但公认的解决方案不是 pythonic（它是程序多行... if ... add ... else ... add ... 返回结果）和其他解决方案不可靠（取决于“<”运算符的未实现传递性）或速度慢（O n*n）。

[编辑]关闭。接受的答案帮助我在下面更笼统的答案中总结了结论。

我喜欢使用内置类型来表示例如树结构。这就是为什么我现在害怕混合。

4

5 回答 5

11

注意：假设条目是可散列的

>>> from collections import Counter
>>> data = 3 * ('x ',  (1,), u'x')
>>> [k for k, c in Counter(data).iteritems() if c > 1]
[u'x', 'x ', (1,)]
于 2012-04-20T14:06:18.247 回答
1

结论：

  • 如果所有项目都是可散列的并且至少是 Python 2.7，那么最好的解决方案是上面的collections.Counter。
  • 如果某些项目不可散列或不存在 Python 2.7+，则groupby(sorted(..))在条件下解决方案非常好
    • 不结合 str 和 unicode 或
    • 不要使用名称按字母顺序排列在“str”和“unicode”之间的任何类型。（通常是“元组”或“类型”）
  • 如果数据是不可散列的并且是混合类型的，则不能使用上述任何内容，然后最好使用：
    • Counter(map(pickled.dumps, data))而不是Counter(data)最后解开它或
    • groupby(sorted(data, key=pickled.dumps))如果 unpickling 是不可取的或没有 python 2.7
  • 下面讨论的“天真的解决方案”可能比对大约少于 300 个的极少数项目进行酸洗更好。

其他问题中的所有其他解决方案目前都更糟。

笔记：

  • 看起来 Counter 类可以复制并粘贴到较低的 Python 版本。
  • 在整个数据中搜索每个项目的“简单解决方案”可用于非常少量的项目。它的优点是不需要散列数据并且不依赖于默认“<”运算符的传递性，但是对于超过 25 个可散列的项目来说，计数器更好，对于超过 300 个不可散列的“野生”项目来说，在腌制上的计数器更好项目。

我考虑过按类型对项目进行预排序或通过散列扩展它们以用于可散列项目，它目前有帮助，但它不是一个安全的解决方案，因为同样的问题会出现在“<”运算符的现场列表、元组等。

于 2012-04-21T10:16:53.160 回答
1

这个主题对我来说很有趣，所以我将上述解决方案与另一个线程中接受的解决方案进行了计时。

Counter 方法是这个线程非常优雅；但是，在这个线程中接受的答案在 Python 中，我如何获取一个列表并将其减少为重复列表？似乎快了大约 2 倍。

import random as rn
import timeit
from collections import Counter

a = [rn.randint(0,100000) for i in xrange(10000)]

def counter_way(x):
    return [k for k,v in Counter(x).iteritems() if v > 1]

def accepted_way(x): #accepted answer in the linked thread
    duplicates = set()
    found = set()
    for item in x:
        if item in found:
            duplicates.add(item)
        else:         
            found.add(item)
    return duplicates


t1 = timeit.timeit('counter_way(a)', 'from __main__ import counter_way, a', number = 100)
print "counter_way: ", t1
t2 = timeit.timeit('accepted_way(a)','from __main__ import accepted_way, a', number = 100)
print "accepted_way: ", t2

结果：

counter_way:  1.15775845813
accepted_way:  0.531060022992

我在不同的规格下尝试过这个，结果总是一样的。

于 2012-04-21T19:03:21.077 回答
0

但是，这两种解决方案都存在缺陷。原因是它合并了具有相同哈希值的值。因此，这取决于使用的值是否可能具有相同的哈希值。这并不是你想象的那么疯狂的评论（我之前也很惊讶），因为 Python 以特殊的方式散列了一些值。尝试：

from collections import Counter


def counter_way(x):
    return [k for k,v in Counter(x).iteritems() if v > 1]

def accepted_way(x): #accepted answer in the linked thread
    duplicates = set()
    found = set()
    for item in x:
        if item in found:
            duplicates.add(item)
        else:         
            found.add(item)
    return duplicates


a = ('x ',  (1,), u'x') * 2

print 'The values:', a
print 'Counter way duplicates:', counter_way(a)
print 'Accepted way duplicates:', accepted_way(a)
print '-' * 50

# Now the problematic values.
a = 2 * (0, 1, True, False, 0.0, 1.0)

print 'The values:', a
print 'Counter way duplicates:', counter_way(a)
print 'Accepted way duplicates:', accepted_way(a)

根据定义，1、1.0 和 True 具有相同的哈希值，0、0.0 和 False 也类似。它在我的控制台上打印以下内容（想想最后两行——所有值实际上应该是重复的）：

c:\tmp\___python\hynekcer\so10247815>python d.py
The values: ('x ', (1,), u'x', 'x ', (1,), u'x')
Counter way duplicates: [u'x', 'x ', (1,)]
Accepted way duplicates: set([u'x', 'x ', (1,)])
--------------------------------------------------
The values: (0, 1, True, False, 0.0, 1.0, 0, 1, True, False, 0.0, 1.0)
Counter way duplicates: [0, 1]
Accepted way duplicates: set([False, True])
于 2012-04-23T07:40:06.280 回答
0

只是因为我很好奇，这是在 0、False、0.0 等之间产生差异的解决方案。它基于对序列进行排序，同时my_cmp考虑到项目的类型。当然，与上述解决方案相比，它非常慢。这是因为排序。但是比较结果！

import sys
import timeit
from collections import Counter

def empty(x):
    return

def counter_way(x):
    return [k for k,v in Counter(x).iteritems() if v > 1]

def accepted_way(x): #accepted answer in the linked thread
    duplicates = set()
    found = set()
    for item in x:
        if item in found:
            duplicates.add(item)
        else:         
            found.add(item)
    return duplicates


def my_cmp(a, b):
    result = cmp(a, b)
    if result == 0:
        return cmp(id(type(a)), id(type(b)))
    return result    


def duplicates_via_sort_with_types(x, my_cmp=my_cmp):

    last = '*** the value that cannot be in the sequence by definition ***'
    duplicates = []
    added = False
    for e in sorted(x, cmp=my_cmp):
        if my_cmp(e, last) == 0:
            ##print 'equal:', repr(e), repr(last), added
            if not added:
                duplicates.append(e)
                ##print 'appended:', e
                added = True
        else:
            ##print 'different:', repr(e), repr(last), added
            last = e
            added = False
    return duplicates


a = [0, 1, True, 'a string', u'a string', False, 0.0, 1.0, 2, 2.0, 1000000, 1000000.0] * 1000

print 'Counter way duplicates:', counter_way(a)
print 'Accepted way duplicates:', accepted_way(a)
print 'Via enhanced sort:', duplicates_via_sort_with_types(a) 
print '-' * 50

# ... and the timing
t3 = timeit.timeit('empty(a)','from __main__ import empty, a', number = 100)
print "empty: ", t3
t1 = timeit.timeit('counter_way(a)', 'from __main__ import counter_way, a', number = 100)
print "counter_way: ", t1
t2 = timeit.timeit('accepted_way(a)','from __main__ import accepted_way, a', number = 100)
print "accepted_way: ", t2
t4 = timeit.timeit('duplicates_via_sort_with_types(a)','from __main__ import duplicates_via_sort_with_types, a', number = 100)
print "duplicates_via_sort_with_types: ", t4

它打印在我的控制台上：

c:\tmp\___python\hynekcer\so10247815>python e.py
Counter way duplicates: [0, 1, 2, 'a string', 1000000]
Accepted way duplicates: set([False, True, 2.0, u'a string', 1000000.0])
Via enhanced sort: [False, 0.0, 0, True, 1.0, 1, 2.0, 2, 1000000.0, 1000000, 'a string', u'a string']
--------------------------------------------------
empty:  2.11195471969e-05
counter_way:  0.76977053612
accepted_way:  0.496547434023
duplicates_via_sort_with_types:  11.2378848197
于 2012-04-24T07:52:44.730 回答