Python生成器函数求两文件公共行：优化方法与diff源码查询

我正在阅读Steven和Dusty所著的《Python Object-oriented programming》一书，目前学到第10章迭代器设计模式，章末练习要求编写生成器函数/表达式找出两个文件的公共行，先给出我的两种朴素实现：

原始生成器函数 #

import os

old = os.path.normpath('E:/testing/old.txt')
new = os.path.normpath('E:/testing/new.txt')
res = []

def func(source):
    for line in source.readlines():
        yield line

方法1：嵌套循环比对 #

with open(old, "r") as f:
    for line in func(f):
        with open(new, "r") as _f:
            for _line in func(_f):
                if line == _line:
                    res.append(line)

方法2：结合filter的实现 #

with open(old, "r") as f:
    for line in func(f):
        with open(new, "r") as _f:
            res.extend(filter(lambda a: line == a, func(_f)))

已知处理两个含n和m个元素的字符串列表时，可通过O(n)时间、O(m)空间复杂度找到公共字符串，现针对以下两个问题展开解答：

1. 更具Python风格的重构方式 #

原始实现存在两个核心问题：一是自定义的func生成器完全冗余（文件对象本身就是可迭代的，直接遍历即可）；二是每次循环都重复打开第二个文件，时间复杂度高达O(n*m)，效率极低。

重构后的Pythonic实现 #

方式1：利用集合+生成器（平衡时间与空间）

优先读取较小的文件存入集合（利用集合O(1)的查找效率），再遍历另一个文件筛选公共行，同时用生成器延迟返回结果，避免占用过多内存：

from pathlib import Path

old_path = Path("E:/testing/old.txt")
new_path = Path("E:/testing/new.txt")

def find_common_lines(file1: Path, file2: Path):
    # 先读取较小文件到集合，减少空间占用
    file1_size = file1.stat().st_size
    file2_size = file2.stat().st_size
    small_file, large_file = (file1, file2) if file1_size <= file2_size else (file2, file1)
    
    with open(small_file, "r") as f:
        small_lines = set(f)
    
    with open(large_file, "r") as f:
        for line in f:
            if line in small_lines:
                yield line

# 使用示例：遍历生成器获取结果
for line in find_common_lines(old_path, new_path):
    print(line.strip())

方式2：生成器表达式（极简写法）

如果不需要封装成函数，也可以用一行生成器表达式实现：

with open(old_path, "r") as f1, open(new_path, "r") as f2:
    lines_set = set(f1)
    common_lines = (line for line in f2 if line in lines_set)

重构后的代码符合Python风格的核心点：

• 用pathlib替代os.path处理路径，更直观易用
• 直接利用文件对象的可迭代性，省去冗余的自定义生成器
• 用集合优化查找效率，避免嵌套循环的低效操作
• 用生成器延迟生成结果，节省内存空间

2. 时间复杂度更优的实现方法 #

原始方法的时间复杂度是O(n*m)，而上述集合方法已经达到O(n+m)的理论最优时间复杂度（必须遍历两个文件至少一次）。但如果文件过大，无法将整个文件的行存入内存，可采用排序+双指针的方法，将空间复杂度降至O(1)（不考虑排序临时文件的空间）：

排序+双指针实现（适合超大文件） #

import tempfile
from pathlib import Path

def sort_file(input_path: Path, output_path: Path):
    # 读取文件内容并排序后写入临时文件
    with open(input_path, "r") as f:
        sorted_lines = sorted(f)
    with open(output_path, "w") as f:
        f.writelines(sorted_lines)

def find_common_lines_large_files(file1: Path, file2: Path):
    # 创建临时文件存储排序后的内容
    with tempfile.NamedTemporaryFile(mode="w+", delete=False) as tmp1, \
         tempfile.NamedTemporaryFile(mode="w+", delete=False) as tmp2:
        tmp1_path = Path(tmp1.name)
        tmp2_path = Path(tmp2.name)
    
    try:
        # 对两个文件分别排序
        sort_file(file1, tmp1_path)
        sort_file(file2, tmp2_path)
        
        # 双指针遍历排序后的文件找公共行
        with open(tmp1_path, "r") as f1, open(tmp2_path, "r") as f2:
            line1 = f1.readline()
            line2 = f2.readline()
            while line1 and line2:
                if line1 == line2:
                    yield line1
                    line1 = f1.readline()
                    line2 = f2.readline()
                elif line1 < line2:
                    line1 = f1.readline()
                else:
                    line2 = f2.readline()
    finally:
        # 清理临时文件
        tmp1_path.unlink()
        tmp2_path.unlink()

该方法的时间复杂度为O(n logn + m logm)（主要来自排序操作），空间复杂度为O(1)（仅存储当前遍历的行），适合处理内存无法容纳的超大文件。

Linux diff与git-diff的源码相关 #

• Linux diff命令属于GNU diffutils项目，源码托管在GNU Savannah平台的diffutils仓库中。
• git-diff是Git工具的核心组件之一，其实现代码主要位于Git源码仓库的diff.c、diff.h等相关文件中。

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