在Python中閱讀巨大文件

Question

我有一個包含5000萬行的384MB文本文件。每行包含2個空格分隔的整數：一個鍵和一個值。該文件按鍵排序。我需要一種有效的方式來查找Python中約200個鍵的列表的值。

我目前的做法包括在下面。它需要30秒。必須有更高效的Python foo才能將其降低到最多幾秒的合理效率。

# list contains a sorted list of the keys we need to lookup 
# there is a sentinel at the end of list to simplify the code 
# we use pointer to iterate through the list of keys 
for line in fin: 
    line = map(int, line.split()) 
    while line[0] == list[pointer].key: 
    list[pointer].value = line[1] 
    pointer += 1 
    while line[0] > list[pointer].key: 
    pointer += 1 
    if pointer >= len(list) - 1: 
    break # end of list; -1 is due to sentinel 

的編碼二進制搜索+求解（感謝kigurai！）：

entries = 24935502 # number of entries 
width = 18  # fixed width of an entry in the file padded with spaces 
        # at the end of each line 
for i, search in enumerate(list): # list contains the list of search keys 
    left, right = 0, entries-1 
    key = None 
    while key != search and left <= right: 
    mid = (left + right)/2 
    fin.seek(mid * width) 
    key, value = map(int, fin.readline().split()) 
    if search > key: 
     left = mid + 1 
    else: 
     right = mid - 1 
    if key != search: 
    value = None # for when search key is not found 
    search.result = value # store the result of the search 

Answer 1

如果您只需要5000萬行中的200行，那麼將它全部讀入內存是浪費。我會對搜索關鍵字列表進行排序，然後使用seek（）或類似的東西將二進制搜索應用到文件中。這樣你不會讀整個文件到內存，我認爲這應該加快速度。

Answer 2

我會使用內存馬平：http://docs.python.org/library/mmap.html。
這樣你就可以使用該文件，就像它存儲在內存中一樣，但操作系統決定從文件中實際讀取哪些頁面。

Answer 3

目前尚不清楚「list [pointer]」是什麼。不過，請考慮這一點。

from collections import defaultdict 
keyValues= defaultdict(list) 
targetKeys= # some list of keys 
for line in fin: 
    key, value = map(int, line.split()) 
    if key in targetKeys: 
     keyValues[key].append(value) 

Answer 4

一個可能的優化是使用file.readlines(..)中的sizehint選項做一點緩衝。這使您可以在內存中加載多行，總計大約爲sizehint字節。 S.Lotts答案

Answer 5

輕微優化：

from collections import defaultdict 
keyValues= defaultdict(list) 
targetKeys= # some list of keys as strings 
for line in fin: 
    key, value = line.split() 
    if key in targetKeys: 
     keyValues[key].append(value) 

由於我們使用的字典，而不是一個列表，該鍵不必須是數字。這將map（）操作和字符串保存爲每行的整數轉換。如果你想讓這些密鑰成爲數字，那麼只需要爲每個密鑰執行一次，而不是每個5000萬行，每次只進行一次轉換。

Answer 6

如果您對文件的格式有任何控制，則「排序和二進制搜索」響應是正確的。細節是，這隻適用於固定大小和偏移的記錄（嗯，我應該說它只適用於固定長度的記錄）。

使用固定長度的記錄，您可以輕鬆地尋找（）圍繞已排序的文件來查找您的密鑰。

Answer 7

你需要使用尋求（）

Answer 8

這裏是文本文件中的遞歸二進制搜索中的jEdit創建

import os, stat 

class IntegerKeyTextFile(object): 
    def __init__(self, filename): 
     self.filename = filename 
     self.f = open(self.filename, 'r') 
     self.getStatinfo() 

    def getStatinfo(self): 
     self.statinfo = os.stat(self.filename) 
     self.size = self.statinfo[stat.ST_SIZE] 

    def parse(self, line): 
     key, value = line.split() 
     k = int(key) 
     v = int(value) 
     return (k,v) 

    def __getitem__(self, key): 
     return self.findKey(key) 

    def findKey(self, keyToFind, startpoint=0, endpoint=None): 
     "Recursively search a text file" 

     if endpoint is None: 
      endpoint = self.size 

     currentpoint = (startpoint + endpoint) // 2 

     while True: 
      self.f.seek(currentpoint) 
      if currentpoint <> 0: 
       # may not start at a line break! Discard. 
       baddata = self.f.readline() 

      linestart = self.f.tell() 
      keyatpoint = self.f.readline() 

      if not keyatpoint: 
       # read returned empty - end of file 
       raise KeyError('key %d not found'%(keyToFind,)) 

      k,v = self.parse(keyatpoint) 

      if k == keyToFind: 
       print 'key found at ', linestart, ' with value ', v 
       return v 

      if endpoint == startpoint: 
        raise KeyError('key %d not found'%(keyToFind,)) 

      if k > keyToFind: 
       return self.findKey(keyToFind, startpoint, currentpoint) 
      else: 
       return self.findKey(keyToFind, currentpoint, endpoint) 

示例文本文件似乎工作來實現的二進制搜索：

>>> i = integertext.IntegerKeyTextFile('c:\\sampledata.txt') 
>>> i[1] 
key found at 0 with value 345 
345 

它肯定可以通過緩存找到的密鑰和使用緩存來確定未來的開始搜索點來改進。