<分区>
我希望比较大约 1000 个不同大小的列表。每个列表可能有数千个项目。我想比较每对列表，因此可能进行大约 500000 次比较。每次比较都包括计算较大列表中存在的较小列表的数量(如果大小相同，则选择任一列表)。最终我想使用这些计数对列表进行聚类。我希望能够对两种类型的数据执行此操作:
有没有一种在 python 中执行此操作的有效方法？我看过 LShash 和其他与聚类相关的算法，但它们似乎需要相同长度的列表。 TIA。
尝试阐明我的目标的示例:
列表 A:汽车、挖掘、狗、the。
列表 B:鱼、狗。
(在任何列表中都没有重复。虽然我认为它们可能相当容易，但未排序。列表的大小各不相同。)
结果:2，因为“dog”和“the”都在两个列表中。
实际上，每个列表的长度可能有数千个，并且有大约 1000 个这样的列表，每个列表都必须相互比较。
继续这个例子:
列表 C:dog、the、a、fish、fry。
结果: AB:2 空调:2 公元前:3
最佳答案
没有什么是超快的，那里有很多数据(首先是 50 万个结果)，但以下内容应该符合您在现代硬件上的时间和空间预算。
如果可能，首先按长度对列表进行排序，从最长到最短。 (我不是说对每个列表进行排序；列表中元素的顺序无关紧要。我的意思是，对列表集合进行排序，以便您可以首先处理最长的列表。)这样做的唯一目的是允许相似性度量存储在半对角矩阵而不是全矩阵中，这样可以节省一半的矩阵空间。因此，如果您在开始之前不知道列表的长度，那不是危机；这只是意味着您需要更多空间。
注意 1: 重要的是，只要列表中没有重复元素，您提出的指标是完全对称的。没有重复元素，指标就是 |A⋂B|。 ，无论是否A或 B更长，所以当你计算 A 的交集的大小时和 B您可以为 (A,B) 填写相似度矩阵和 (B,A) .)
注意 2: 当我重新阅读算法的描述时，我似乎感到困惑，所以当它指的是一个时，我将“列表”一词更改为“列表”千个输入列表，“列表”表示普通的 Python 列表。因为列表不能是 Python 字典中的键，假设 列表 是作为列表实现的，所以有必要以某种方式用一个可以使用的标识符来标识每个 列表作为 key 。我希望这很清楚。
我们需要两个辅助结构:一个是(半对角线)结果矩阵，由成对的list 标识符键控，我们将其初始化为全 0。另一个是由唯一数据元素键控的字典，映射到 list 标识符列表。
然后，依次获取每个列表，对于该列表中的每个元素，我们执行以下操作:
如果该元素尚未出现在字典中，则添加它，映射到由当前列表标识符组成的单个元素列表。
如果字典中存在该元素，但相应 ID 列表中的最后一个元素是当前 ID，则我们找到了重复元素。由于我们不希望出现重复元素，因此请忽略它或发出错误消息。
否则，我们之前已经见过该元素，并且我们有一个标识符列表，列表 元素出现在其中。对于每个这样的标识符，增加当前标识符和列表中标识符之间的相似性计数。 (请注意，如果我们按长度倒序扫描列表，则列表中的所有标识符都对应于至少与当前列表<一样长的列表/em>，这就是我们首先对 列表 进行排序的原因。)最后，将当前标识符附加到列表的末尾，以便下次找到该数据元素时，当前的list 将出现。
就是这样。空间要求是O(N<sup>2</sup> + M)其中 N是列表和M的数量是所有列表的总大小。时间要求本质上是 O(M<sup>2</sup>)在最坏的情况下——即每个 list 都只有一个元素并且它们都是相同的元素。 (更准确地说，它是每个唯一元素的频率的平方和。)
关于python - 有效的不同大小的列表比较，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26550430/