如何高效合并并去重Python中的多个已排序列表？

一、利用有序特性的线性时间归并去重 #

既然所有输入都是已排序的，直接用多路归并+在线去重是理论最优方案（时间复杂度O(N)，N为总元素数），内存开销也更可控。

实现思路 #

1. 用heapq.merge合并所有有序列表/Series（返回有序迭代器，无需一次性加载所有元素）
2. 遍历合并后的迭代器，跳过与前一个元素重复的值，完成去重

代码示例 #

import heapq
from typing import Iterable, List

def merge_deduplicate_sorted(lists: List[Iterable[str]]) -> List[str]:
    merged = heapq.merge(*lists)
    result = []
    prev = None
    for item in merged:
        if item != prev:
            result.append(item)
            prev = item
    return result

# 针对pd.Series的适配版本
import pandas as pd
def merge_deduplicate_sorted_series(series_list: List[pd.Series]) -> pd.Series:
    merged_iter = heapq.merge(*(s.iteritems() for s in series_list))
    result = []
    prev_key = None
    for key, val in merged_iter:
        if key != prev_key:
            result.append(val)
            prev_key = key
    return pd.Series(result)

优势：

• 线性时间复杂度，比先合并再用set（存在哈希计算开销）或内置排序（O(NlogN)）更高效
• 迭代式处理，内存占用远低于一次性加载所有元素到集合

二、Pandas内置优化方案 #

如果处理的是pd.Series，直接利用Pandas的C实现底层函数，性能会比纯Python代码更优：

方案1：concat + drop_duplicates（针对有序序列） #

因为输入已排序，合并后的Series也是有序的，drop_duplicates会利用有序特性做优化（无需全量哈希）：

def pandas_merge_deduplicate(series_list: List[pd.Series]) -> pd.Series:
    combined = pd.concat(series_list, ignore_index=True)
    return combined.drop_duplicates(keep='first')

方案2：利用Series.unique() #

对于已排序的Series，unique()方法会采用线性扫描去重，比无序序列的哈希去重更快：

def pandas_unique_merge(series_list: List[pd.Series]) -> pd.Series:
    combined = pd.concat(series_list, ignore_index=True)
    return pd.Series(combined.unique())

注意：Pandas的方法会一次性加载所有数据到内存，若内存紧张，优先选择归并迭代的方案。

三、哈希表快速去重方案（适合内存充足场景） #

如果内存足够容纳所有去重后的元素，直接用Python内置的set是最简单高效的方式，因为set的添加和查询都是O(1)平均时间，且底层是C实现：

def set_based_merge_deduplicate(lists: List[Iterable[str]]) -> List[str]:
    seen = set()
    result = []
    for lst in lists:
        for item in lst:
            if item not in seen:
                seen.add(item)
                result.append(item)
    # 若需要保持全局有序，最后执行排序（开销取决于去重后的元素量）
    result.sort()
    return result

对比：如果不需要保持全局有序，这个方法比归并更快；如果需要有序，最后排序的开销取决于去重后的元素量（若去重后仅约400k元素，排序开销极小）。

四、性能选型建议 #

1. 需要保持全局有序+内存有限：优先选择归并去重方案，线性时间+低内存占用
2. 处理pd.Series+内存充足：优先选择Pandas内置方案，底层C实现比纯Python快
3. 不需要有序+内存充足：优先选择set-based方案，代码最简单，性能最优

内容的提问来源于stack exchange，提问作者cat