时间戳

首页 > 解决方案 > 更快地查找哪些列表共享元素

python - 更快地查找哪些列表共享元素

问题描述

我有一个形状为 (142000, 1) 的熊猫数据框，其中有一列名为关键字，其中每个单元格都包含一个关键字列表。

我想检查哪些行至少有一个相等的关键字。

for i in combinations(list(range(len(df.index))), 2):
    if set(df['keywords'][i[0]]) & set(df['keywords'][i[1]]):
        do_something() # this runs reasonably fast, no problem here

设置的东西如下set([1,2,3]) & set([3,4,5]) = {3}：所以实际上只是检查列表是否共享任何项目。

问题在于暴力破解它，因为我们总共有 142000!/[(142000 - 2)!2!] 次迭代。

有一个更好的方法吗？

标签： pythonpandas

解决方案

创建一个从关键字到该关键字出现的所有索引的索引（我对 Pandas 不太熟悉，因此您可能需要修复一些问题）：

keyword_index = defaultdict(set)
for i, keywords in enumerate(df['keywords']):
    for keyword in keywords:
        keyword_index[keyword].add(i)

然后遍历索引并对出现在多个索引处的所有关键字做一些事情：

for keyword, indices in keyword_index.items():
    if len(indices) >= 2:
        do_something()

您必须决定如何处理出现在两行以上的关键字。如果你想分别处理每个组合，它仍然是原始代码中最坏的情况 O(n^2) 。

推荐阅读