查找两个列表公共元素大数据量报错是否需要用yield解决

原有代码问题分析 #

你当前的实现存在两个核心问题，这才是大数据量下报错的根本原因，和是否使用yield没有直接关系：

• 时间复杂度过高：element in B的查找操作、B.remove(element)的删除操作时间复杂度都是O(M)，整体时间复杂度为O(N*M)，数据量达到万级以上就会出现严重的性能问题甚至超时崩溃。
• 存在副作用：代码直接修改传入的参数B，如果你后续还需要使用原始的B数组，会发现数据已经被篡改，属于隐形逻辑bug。

优化实现方案 #

最优解法是基于哈希表统计元素出现频次，整体时间复杂度降为O(N+M)，空间复杂度为O(min(N,M))，可以轻松应对大数据量场景：

from collections import Counter

def solve(A, B):
    # 优先统计长度更短的数组的元素频次，最大程度节省内存
    if len(A) > len(B):
        A, B = B, A
    freq = Counter(A)
    result = []
    for num in B:
        if freq.get(num, 0) > 0:
            result.append(num)
            freq[num] -= 1
    return result

关于yield的使用说明 #

只有当你的结果集本身非常大、不需要一次性拿到全部公共元素、可以逐个处理结果的时候，才需要用yield生成器进一步降低内存占用，实现示例如下：

from collections import Counter

def solve_generator(A, B):
    if len(A) > len(B):
        A, B = B, A
    freq = Counter(A)
    for num in B:
        if freq.get(num, 0) > 0:
            yield num
            freq[num] -= 1

# 生成器使用方式：迭代获取每个公共元素，不会一次性加载所有结果到内存
# for item in solve_generator(A, B):
#     逐个处理公共元素

测试用例验证 #

上述代码可以通过你给出的两个测试用例：

• 用例1输入：A = [1, 2, 2, 1]，B = [2, 3, 1, 2]，输出结果为[1, 2, 2]，符合预期
• 用例2输入：A = [2, 1, 4, 10]，B = [3, 6, 2, 10, 10]，输出结果为[2, 10]，符合预期

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