高效的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落在范围30-40内Ranges.txt，因此对于范围30-40，我必须计算相关值的平均值（即平均值0.79和0.87），即0.82

我的最终输出文件应该是Ranges.txt，但所有数值的相关值的均值落入每个范围内。喜欢的东西：

Output.txt的

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

等。

希望得到关于如何在Python中有效编写的任何帮助和想法。

Answer 1

天真的做法是将Numbers.txt按照编号顺序读入某个结构，然后读取Ranges的每一行，使用二进制搜索来找到范围中的最小数字，并通过数字读取高于找到范围内的所有内容，以便可以生成相应的输出行。

我假设问题是你不能在内存中拥有所有的数字。

所以你可以分阶段地完成这个问题，每个阶段读取Numbers中的一部分，然后通过上面概述的过程，但是使用注释版本的范围，其中每行包括目前值的COUNT值已经产生了这个意思，并且会写出一个类似注释的版本。

显然，初始传球不会有注释版本的范围，而最终传球不会产生一个。

Answer 2

很明显，您需要从Numbers.txt中的每行运行Ranges.txt中的每一行。

您可以遍历Numbers.txt，并且对于每一行，遍历Ranges.txt。但是这将花费很长时间，读取整个Ranges.txt文件数百万次。

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

因此，你想要做的就是将Ranges.txt读入内存一次，并将其存储为一对ints的列表，而是将其存储为lansily，然后将它们逐个读入Numbers.txt，并遍历每个数字的列表。

这种事情总是出现。一般而言，您希望将更大的集合放入外部循环中，并尽可能使其变为惰性，而较小的集合进入内部循环，并进行预处理以使其尽可能快。但是如果更大的集合可以更有效地进行预处理（并且您有足够的内存来存储它！），请将其反转。

---

并且谈到预处理，您可以做比读入成对int列表更好的方法。如果您对Ranges.txt进行了排序，您可以找到距离最近的距离，然后只检查（18步），而不是详尽地检查每个距离（100000步）。

这对stdlib来说有点痛苦，因为在使用bisect时很容易发生错误的错误，但是有很多ActiveState配方可以使它更容易（包括一个linked from the official docs），更不用说了像blist或bintrees这样的第三方模块，这些模块为您提供了一个简单的面向对象接口的排序集合。

---

所以，像这样的伪代码：

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]。）

---

如果范围可以重叠，你需要一点更聪明，你必须要找到最接近的范围，而不去在开始时，与最接近的范围而不下到底会，以及两者之间的检查一切。但主要的诀窍与上一个版本完全相同。唯一的诀窍是保留两个范围副本，一个按起始值排序，另一个按照结束顺序排列，并且您需要将其中一个映射到另一个索引的映射，而不仅仅是一个普通列表。

Answer 3

它看起来像你的数据在这两个文件已经排序。如果不是，首先通过外部工具或使用Python对它们进行排序。

然后，您可以并行浏览这两个文件。您从Numbers.txt文件中读取一个数字，然后查看它是否在Ranges.txt文件的范围内，根据需要从该文件中读取许多行以回答该问题。然后从Numbers.txt中读取下一个数字，然后重复。这个想法类似于合并两个排序数组，并且应该运行在O(n+m)时间，n和m是文件的大小。如果您需要对文件进行排序，则运行时间为O(n lg(n) + m lg(m))。这里是一个快速的程序我写来实现这个：

import sys 
from collections import Counter 

class Gen(object): 
    __slots__ = ('rfp', 'nfp', 'mn', 'mx', 'num', 'd', 'n') 
    def __init__(self, ranges_filename, numbers_filename): 
     self.d = Counter() # sum of elements keyed by range 
     self.n = Counter() # number of elements keyed by range 

     self.rfp = open(ranges_filename) 
     self.nfp = open(numbers_filename) 
     # Read the first number and the first range values 
     self.num = float(self.nfp.next()) # Current number 
     self.mn, self.mx = [int(x) for x in self.rfp.next().split()] # Current range 

    def go(self): 
     while True: 
      if self.mx < self.num: 
       try: 
        self.mn, self.mx = [int(x) for x in self.rfp.next().split()] 
       except StopIteration: 
        break 
      else: 
       if self.mn <= self.num <= self.mx: 
        self.d[(self.mn, self.mx)] += self.num 
        self.n[(self.mn, self.mx)] += 1 
       try: 
        self.num = float(self.nfp.next()) 
       except StopIteration: 
        break 
     self.nfp.close() 
     self.rfp.close() 
     return self.d, self.n 

def run(ranges_filename, numbers_filename): 
    r = Gen(ranges_filename, numbers_filename) 
    d, n = r.go() 
    for mn, mx in sorted(d): 
     s, N = d[(mn, mx)], n[(mn, mx)] 
     if s: 
      av = s/N 
     else: 
      av = 0 
     sys.stdout.write('%d %d %.3f\n' % (mn, mx, av)) 

上的文件，在每个文件，上面运行的10,000,000号码在我的电脑上约1.5分钟不输出部分。