使用哈希比较列表中的相似性?

2024-03-29 12:46:08 发布

您现在位置:Python中文网/ 问答频道 /正文

假设您有一个列表:

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)个迭代可以获得pricy。你知道吗

我在想哈希可能是一种方式,但我不确定。你知道吗

但是如果有办法将列表最小化为一个字符串,并将其与另一个字符串进行比较。你知道吗

也就是说H(L1)U H(L2)有x%的共同点?你知道吗

请注意,我实际上不需要知道这些项目的共同点是什么。只是他们之间有一个百分比。 提前谢谢。你知道吗


Tags: 字符串l1列表foodresultmincoffeedog
2条回答

如果两个列表中没有重复项,则可以使用集合,集合在内部使用哈希-

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

如果需要处理重复项,Python有一个^{}形式的multiset,它的交集操作执行您期望的操作:

>>> 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())

这正是集合的工作原理。将列表转换为集合,然后可以使用并集/交集

S1 = set(L1)
S2 = set(L2)
result = S1.intersection(S2)

但这并不能维持秩序。你知道吗

相关问题 更多 >