python - 在没有设置的情况下更快地获得两个列表的差异

Question

我正在尝试比较两个列表并获取新元素，包括冗余元素。例如，结果:

l1 = [1,2,3,3,4]
l2 = [3,3,3,4,4,5,6]

是:

l2 - l1 = [3,4,5,6]

你可以很容易地理解我不能用set来做，因为

set(l1) = (1,2,3,4)
set(l2) = (3,4,5,6)

结果将是:(5,6)

我不想用

这样的迭代来做

[i for i in l1 if i not in l2 ]

因为它太慢了(参见 Get difference between two lists 的基准测试)

有谁知道如何在没有迭代的情况下做到这一点并保留冗余元素或迭代方法是唯一的方法？

谢谢!

解决方案的基准测试:

我对两个给定的解决方案进行了基准测试，结果如下:

import random
init1 = list(range(10000))
init2 = [i*random.randint(1,50) for i in range(10000)]

# Put both solution in function, diff1 = remove method, diff2 = Counter method 

import time
tic1 = time.clock()
print(diff1(init2,init1))
toc1 = time.clock()
tic2 = time.clock()
print(diff2(init2,init1))
toc2 = time.clock()
print(toc1-tic1)
print(toc2-tic2)

结果是:

2.756271607145601   for diff1
0.028116911506909315    for diff2

Answer 1

您正在寻找 multisets ，这正是 collections.Counter用于:

>>> from collections import Counter
>>> list((Counter(l2) - Counter(l1)).elements())
[3, 4, 5, 6]