如何对含重复值的两个已排序列表实现归并连接

核心问题说明 #

常规双指针归并连接仅适用于连接键为单值、无重复的场景，遇到重复键或单条目携带多连接键时，单步比较推进指针的逻辑会跳过同键匹配段，导致结果缺失。该场景不需要重构现有数据结构，只需要在标准归并逻辑上补充两个规则即可：

• 当双指针定位到相等的连接键时，先一次性收集两侧所有同键的连续条目段，完成段内所有匹配后再推进指针
• 针对list_1单条目携带多连接键的特性，增加指针回退逻辑，避免跨键条目被漏匹配

可直接运行的实现代码 #

def merge_join(list1, list2):
    result = []
    ptr1 = 0  # list1遍历指针
    ptr2 = 0  # list2遍历指针
    len1, len2 = len(list1), len(list2)

    while ptr1 < len1 and ptr2 < len2:
        # 收集list2侧所有和当前键相同的连续段，处理list2重复键场景
        current_l2_key = list2[ptr2][0]
        l2_same_key_end = ptr2
        while l2_same_key_end < len2 and list2[l2_same_key_end][0] == current_l2_key:
            l2_same_key_end += 1
        # 提取当前键对应的关联值，同键多值可按需合并，示例场景下同键唯一直接取首个即可
        match_values = list2[ptr2][1]

        # 遍历list1侧所有可能携带当前连接键的条目
        temp_ptr = ptr1
        while temp_ptr < len1:
            l1_id, l1_keys = list1[temp_ptr]
            # list1按键列表升序排列，若当前条目最小键大于匹配键，后续条目均无匹配可能，跳出
            key_min = min(l1_keys)
            if key_min > current_l2_key:
                break
            # 键命中则加入结果集
            if current_l2_key in l1_keys:
                result.append((l1_id, match_values.copy()))
            temp_ptr += 1

        # 移动list2指针到下一个不同键的位置
        ptr2 = l2_same_key_end

        # 回退list1指针到首个可能匹配下一个键的位置，避免携带多键的条目被漏匹配
        if ptr2 < len2:
            next_l2_key = list2[ptr2][0]
            while ptr1 > 0:
                prev_l1_keys = list1[ptr1 - 1][1]
                if max(prev_l1_keys) >= next_l2_key:
                    ptr1 -= 1
                else:
                    break
        ptr1 = temp_ptr
    return result

# 测试用例
if __name__ == "__main__":
    list_1 = [(288645, [300]),
            (249594, [300, 305]),
            (288647, [300, 310]),
            (249587, [300])]

    list_2 = [(290, [786020, 601157, 827251]),
            (300, [814888, 829081, 365044]),
            (305, [781169, 826323]),
            (310, [819361, 639450])]
    
    print(merge_join(list_1, list_2))

上述代码会输出全量匹配结果，包含300、305、310三个键的所有匹配项，你给出的临时结果仅为300键对应的部分匹配内容。

性能优化建议 #

• 如果list_1中每个条目的键列表本身是升序排列的，可以将代码中min(l1_keys)、max(l1_keys)直接替换为l1_keys[0]、l1_keys[-1]，省去重复求最值的开销
• 如果数据量较小、内存充足，可直接将list_2转为{key: values}格式的字典做哈希连接，时间复杂度更低；如果数据量过大无法全量加载到内存，上述归并逻辑仅需常数级额外内存，更适合外存排序后的大表连接
• 你给出的list_2排序代码存在笔误，赋值对象错写为list_1，实际运行需修正为list_2 = sorted(list_2_dict.items(), key=lambda item: item[0])，避免覆盖原list_1数据

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