在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 

它肯定可以通过缓存找到的密钥和使用缓存来确定未来的开始搜索点来改进。