python - 使用哈希比较列表中的相似性？

Question

假设你有一个列表:

L1 = [milk, butter, bread, shampoo, dog food]

并且您想知道这个列表与另一个列表的相似程度

L2 = [milk, butter, shampoo, dog food, coffee]

即获取两个列表的并集:

Result = L1 U L2

结果是

[Milk, butter, dog food]

现在，我知道我可以遍历这些并找到并集。但是给定一个大小为 m 的列表和一个大小为 n 的列表。您将至少迭代 min(n, m) 次。给定 x 个列表，您有 x^min(n,m) 次迭代，这可能会变得很昂贵。

我在想哈希可能是一种方式，但我不确定。

但如果有一种方法可以将列表最小化为一个字符串并将其与另一个字符串进行比较。

也就是说 H(L1) U H(L2) 有 x% 的共同点？

请注意，我实际上不需要知道这些项目的共同点是什么。只是他们在两者之间分享了一个百分比。

Answer 1

如果您在两个列表中没有重复项，您可以改用集合，它在内部使用散列 -

>>> L1 = {'milk', 'butter', 'bread', 'shampoo', 'dog food'}
>>> L2 = {'milk', 'butter', 'shampoo', 'dog food', 'coffee'}
>>> L1 & L2
{'dog food', 'butter', 'shampoo', 'milk'}

如果您确实需要处理重复项，Python 有一个 collections.Counter 形式的多重集。 ，它的交集操作符合您的预期:

>>> from collections import Counter
>>> Counter(L1) & Counter(L2)
Counter({'butter': 1, 'milk': 1, 'shampoo': 1, 'dog food': 1})

要获得“x% in common”字符串，您需要将交集中的元素总数与开始时的元素数进行比较。集合以与列表相同的方式支持 len()，因此如果您没有重复项，则获取共同项的数量只是 len(L1 & L2)。取一个计数器的长度只会给你distinct元素的数量 - 当 L1 和 L2 是计数器时，要得到元素的数量以达到它们的重数，你可以这样做:

 common = L1 & L2
 num_in_common = sum(common.values())