如何在Python中高效地合并和删除重复列表？

Question

我想高效地在Python中合并和消除重复多个列表。每个 pd.Series 有 10 个列表，每个列表都有大约。 200k 个string 元素（它们不 具有相同的长度）。它们中的每一个都已被排序。列表有 ~90% 的重叠元素。我如何高效合并它们并删除重复数据？

我可以使用下面的代码来实现合并和排序，但是我们有更高效的方法吗？性能在这里很重要。 （由于开销，最好不使用 Cython）

targetList = list()
for l in lists:
  targetList += l
targetList = list(set(targetList))
targetList = targetList.sort()

我也知道我可以先线性合并所有列表（保序），然后用哈希集线性去重（实际上这两个步骤可以合并）。

但是，这样的列表合并没有内置函数，我担心我自己的代码（具有线性复杂性）可能会带来额外的开销，进而变得比具有简单系统内置函数的 NlogN 算法慢。我正在使用Python3.9

我知道这篇文章用于重复数据删除，但我的问题有很多功能，我认为还有优化的空间。

Answer 1

您可以尝试使用 heapq.merge 方法来合并排序的可迭代对象，然后应用线性重复数据删除步骤，从而实现高效的合并和重复数据删除。 有一个例子：

import heapq

# Assuming 'lists' is a list of sorted lists/pd.Series
merged = list(heapq.merge(*lists))

# Linear deduplication
deduplicated = [merged[0]] + [value for prev, value in zip(merged, merged[1:]) if prev != value]

heapq.merge 方法避免创建中间列表，为大型数据集提供良好的内存效率。总体时间复杂度为 O(N * log(k))，其中 N 是所有列表中的元素总数，k 是输入列表的数量