高效的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分鐘不輸出部分。