Python中高效合并两个近同超长已排序列表的方法

我们有两个各含2000万+元素的已排序列表，两者大部分元素相同，仅少数元素不同，需要合并去重并得到有序结果。之前尝试的基于集合的方法（转集合后排序、集合求并后排序等）耗时约50分钟，效率极低。

问题根源 #

基于集合的方法需要先将所有元素存入哈希表构建集合，再对去重后的元素排序。这两步的时间复杂度分别为O(n+m)和O(k log k)（k为去重后的元素数量），对于2000万级别的数据，排序步骤开销极大，同时集合的哈希表构建也会占用大量内存，导致整体效率低下。

最优解决方案：双指针法 #

利用两个列表已排序的特性，使用双指针遍历一次即可完成合并去重，结果直接有序，无需额外排序步骤，时间复杂度仅为O(n+m)，内存开销远低于集合方法。

代码实现

def merge_sorted_unique(list1, list2):
    merged = []
    i = j = 0
    len1, len2 = len(list1), len(list2)
    
    while i < len1 and j < len2:
        if list1[i] < list2[j]:
            merged.append(list1[i])
            i += 1
        elif list1[i] > list2[j]:
            merged.append(list2[j])
            j += 1
        else:
            # 元素相同仅保留一个，同时移动两个指针避免重复
            merged.append(list1[i])
            i += 1
            j += 1
    
    # 追加剩余未遍历的元素（剩余元素自身有序且大于结果中所有元素）
    merged.extend(list1[i:])
    merged.extend(list2[j:])
    
    return merged

# 调用示例
combined = merge_sorted_unique(list_1, list_2)

逻辑说明

1. 初始化双指针i和j，分别指向两个列表的起始位置
2. 循环比较指针指向的元素：
   • 取较小的元素加入结果，移动对应指针
   • 元素相同时仅加入一次，同时移动两个指针
3. 循环结束后，将任意列表中剩余的元素追加到结果中

内存优化（针对超大规模数据） #

如果内存压力较大，可改为生成器版本，按需生成元素，避免一次性存储整个合并列表：

def merge_sorted_unique_gen(list1, list2):
    i = j = 0
    len1, len2 = len(list1), len(list2)
    
    while i < len1 and j < len2:
        if list1[i] < list2[j]:
            yield list1[i]
            i += 1
        elif list1[i] > list2[j]:
            yield list2[j]
            j += 1
        else:
            yield list1[i]
            i += 1
            j += 1
    
    # 生成剩余元素
    yield from list1[i:]
    yield from list2[j:]

# 调用示例，如需列表可转换：
combined = list(merge_sorted_unique_gen(list_1, list_2))

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