python - 在Python中从大文件中选择部分记录的更有效方法

Question

我想根据给定的 ID 从大文件(列表列表，10M+ 行)中过滤记录。

selected_id = list()            # 70k+ elements

for line in in_fp:              # input file: 10M+ lines
    id = line.split()[0]        # id (str type), such as '10000872820081804' 

    if id in selected_id:
        out_fp.write(line)

上面的代码比较耗时。我想到了一个主意。将 selected_id 存储为 dict 而不是 list。

还有更好的解决方案吗？

Answer 1

您遇到了一些问题，但只有第一个确实很糟糕:

1. (到目前为止，所有可能的最大成本)检查列表中的成员资格是O(n)；对于 70K 元素的 list 来说，这是一项大量的工作。将其设为set/frozenset，查找通常是O(1)，从而节省数千次比较。如果类型不可散列，您可以对 selected_list 进行预排序，并使用 bisect 模块在 O(log n ) 时间，对于如此大的列表，仍然可以获得多个数量级的加速。
2. 如果你的行很大，并且有好几行空白，那么在所有点上分割会浪费时间；您可以指定 maxsplit 仅拆分足以获取 ID
3. 如果 ID 始终为整数值，那么可能值得花时间让 selected_id 存储 int 而不是 str 并在读取时转换，以便查找比较运行得更快一些(这需要测试)。这可能不会产生重大影响，因此我将在示例中省略它。

结合所有建议:

selected_id = frozenset(... Your original list of 70k+ str elements ...)

for line in in_fp:               # input file: 10M+ lines
    id, _ = line.split(None, 1)  # id (str type), such as '10000872820081804' 

    if id in selected_id:
        out_fp.write(line)

您甚至可以将 for 循环转换为带有生成器表达式的单个调用(尽管它有点过于紧凑)，这会将更多工作推送到 CPython 中的 C 层，从而减少 Python 字节码执行开销:

out_fp.writelines(x for x in in_fp if x.split(None, 1)[0] in selected_id)