统计列表中非唯一项的总数

Question

我正在寻找一种最省时的方法来计算Python大型列表中非唯一项的数量（大约100000项）

到目前为止，我采用的方法是：

original_list = [1, 4, 6, 2, 2, 1, 5, 3, 2]

duplicates_list = []
for item in original_list:
    if original_list.count(item) > 1:
        duplicates_list.append(item)

duplicates_count = len(duplicates_list)

print(duplicates_count)

# Should give the following answer:
5

目前，大约70-80K个项目的大型列表需要1-2分钟来执行计算。我想知道我们是否可以尽可能减少计算所需的时间（可能减少到3-10秒）

我真的很感谢你的帮助

Answer 1

计数器对象应该更快，因为在您的版本中，您正在对列表中的每个项目调用count()，所以每个问题调用100000次。这将对整个列表执行一次Count（），然后对计数器对象的迭代将仅对每个唯一值执行一次

original_list = [1, 4, 6, 2, 2, 1, 5, 3, 2]

from collections import Counter
count = Counter(original_list)

dupes = sum(v for k, v in count.items() if v > 1)

Answer 2

这利用了对Counter类中算术运算符的支持set和Counter都支持一些有用的操作：

>>> li = [1, 4, 6, 2, 2, 1, 5, 3, 2]
>>> s  = set(li)
>>>
>>> len(li) - len(s) + len(Counter(li) - Counter(s))
5
>>> 

len(li) - len(set(li))给出了重复项的数量，或者在我们取出set项之后剩下的列表项的数量

要获取与剩余列表中的项目相关的集合项目列表，请执行以下操作：

>>> list((Counter(li) - Counter(set(li))))
[1, 2]

要在删除set项后获取列表中剩余的重复项列表，请执行以下操作：

>>> list((Counter(li) - Counter(set(li))).elements())
[1, 2, 2]

如果列表有一个减法运算，那就是我们从列表中减去set后得到的结果

建议的优化

如果可能，使用此70-80K项列表的应用程序应该在填充列表时从一开始就递增地构建计数器。当需要时，它可以手头有它的列表、计数器或其他需要的结构，所以度量或其他类型的处理可以在后面的步骤中使用

基准

在没有特定顺序的情况下，下面是每个算法处理80K随机数列表所需的时间

>>> li     = [random.randint(0, 100) for _ in range(80 * 1000)]
>>> n_iter = 1000
>>>
>>> timeit.timeit("s = set(li); "
...               "len(li) - len(s) + len(Counter(li) - Counter(s))", 
...               globals=globals(), number=n_iter)
7.048838693
>>> 
>>> timeit.timeit("sum(v for k, v in Counter(li).items() if v > 1)", 
...               globals=globals(), number=n_iter)
5.787936814
>>>
>>> timeit.timeit(original_posters_script, globals=globals(), number=n_iter)
# Takes too much time to sit through. It's very slow. O(N^2)
>>> 

毫不奇怪，最快的算法是选定答案中的另一个计数器解