python - 处理两个大文件的高效 Python 方法？

Question

我正在研究一个问题，我必须找出一个数字是否在某个范围内。但是，由于我正在处理的文件有数十万行，所以问题很复杂。

下面我尽量用通俗易懂的语言来解释这个问题。

这里是我的输入文件的简要描述:

文件 Ranges.txt 有一些范围，其最小值和最大值用制表符分隔。

10 20
30 40
60 70

这可能有大约 10,000,000 行带有范围的行。

注意:范围从不重叠。

文件 Numbers.txt 包含一个数字列表以及与每个数字关联的一些值。

12 0.34
22 0.14
34 0.79
37 0.87

等等。同样，有成千上万行带有数字及其相关值的行。

我想做的是从 Numbers.txt 中取出每个数字，并检查它是否在 Ranges.txt 中的任何范围内。

对于范围内的所有此类数字，我必须得到它们相关值的平均值(即每个范围的平均值)。

例如。在上面的例子中 Numbers.txt 中，有两个数字 34 和 37 在 Ranges.txt 中落在 30-40 范围内，所以对于 30-40 范围我必须计算 34 和 37 的相关值的平均值。(即 0.79 和 0.87 的平均值)，即 0.82

我的最终输出文件应该是 Ranges.txt，但包含落在每个范围内的所有数字的相关值的平均值。像这样的东西:

输出.txt

10 20 <mean>
30 40 0.82
60 70 <mean>

等等。

对于如何用 Python 有效地编写它的任何帮助和想法，我们将不胜感激。

Answer 1

显然，您需要针对 Ranges.txt 中的每一行运行 Numbers.txt 中的每一行。

您可以只遍历 Numbers.txt，然后对每一行遍历 Ranges.txt。但这需要很长时间，需要读取整个 Ranges.txt 文件数百万次。

您可以将它们都读入内存，但这会占用大量存储空间，这意味着在您完成对这两个文件的读取和预处理之前，您将无法进行任何处理。

因此，您要做的是将 Ranges.txt 读入内存一次并将其存储为例如整数对的列表，但懒惰地读取 Numbers.txt，遍历每个数字的列表。

这种事情经常出现。一般来说，你希望较大的集合进入外循环，并使其尽可能惰性，而较小的集合进入内循环，并进行预处理以使其尽可能快。但是，如果可以更有效地预处理更大的集合(并且您有足够的内存来存储它!)，则相反。

---

说到预处理，您可以做的比仅仅读入成对的整数列表要好得多。如果您对 Ranges.txt 进行排序，您可以找到最近的范围，而无需通过平分然后检查(18 步)，而不是详尽地检查每个范围(100000 步)。

这对标准库来说有点麻烦，因为在使用 bisect 时很容易出现差一错误。 ，但是有很多 ActiveState 方法可以让它更容易(包括一个 linked from the official docs )，更不用说像 blist 这样的第三方模块了。或 bintrees在简单的 OO 界面中为您提供排序的集合。

---

所以，像这样的伪代码:

with open('ranges.txt') as f:
    ranges = sorted([map(int, line.split()) for line in f])
range_values = {}
with open('numbers.txt') as f:
    rows = (map(int, line.split()) for line in f)
    for number, value in rows:
        use the sorted ranges to find the appropriate range (if any)
        range_values.setdefault(range, []).append(value)
with open('output.txt') as f:
    for r, values in range_values.items():
        mean = sum(values) / len(values)
        f.write('{} {} {}\n'.format(r[0], r[1], mean))

---

顺便说一下，如果解析比在每一行调用 split 更复杂，我建议使用 csv 模块……但是它看起来这在这里不会成为问题。

---

如果您不能将 Ranges.txt 放入内存，但可以将 Numbers.txt 放入内存怎么办？那么，您可以对其进行排序，然后遍历 Ranges.txt，找到排序数字中的所有匹配项，然后写出该范围的结果。

这有点复杂，因为你必须 bisect_left 和 bisect_right 并迭代它们之间的所有内容。但这是它变得更难的唯一方式。 (在这里，第三方类会提供更多帮助。例如，使用 bintrees.FastRBTree 作为您的排序集合，它只是 sorted_number_tree[low:high]。 )

---

如果范围可以重叠，您需要更聪明一些 — 您必须找到最接近的范围而不越过起点，找到最近的范围而不越过终点，并检查两者之间的所有内容。但是这里的主要技巧与上一个版本使用的技巧完全相同。唯一的另一个技巧是保留两份范围副本，一份按起始值排序，一份按末尾排序，并且您需要将其中一份映射到另一份中的索引，而不仅仅是一个普通列表。