python - 用 Python 读取大文件

Question

我有一个 384MB 的文本文件，有 5000 万行。每行包含 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

score 11 · Accepted Answer

如果你只需要 5000 万行中的 200 行，那么将它们全部读入内存是一种浪费。我会对搜索键列表进行排序，然后使用 seek() 或类似的东西对文件应用二进制搜索。这样你就不会将整个文件读入内存，我认为这应该加快速度。

score 7 · Accepted Answer

S.Lotts 答案的轻微优化：

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 万行中的每一行执行一次。

score 4 · Accepted Answer

目前尚不清楚“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 )

score 3 · Accepted Answer

我会使用内存映射：http: //docs.python.org/library/mmap.html。
通过这种方式，您可以像存储在内存中一样使用该文件，但操作系统会决定应该从文件中实际读取哪些页面。

score 3 · Accepted Answer

这是对文本文件的递归二进制搜索

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)

在 jEdit 中创建的示例文本文件似乎可以工作：

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

它肯定可以通过缓存找到的键并使用缓存来确定未来的起始搜索点来改进。

score 2 · Accepted Answer

如果您对文件的格式有任何控制权，则“排序和二进制搜索”响应是正确的。细节是这只适用于固定大小和偏移量的记录（好吧，我应该说它只适用于固定长度的记录）。

使用固定长度的记录，您可以轻松地在已排序的文件周围 seek() 以找到您的密钥。

score 0 · Accepted Answer

一种可能的优化是使用file.readlines(..)sizehint中的选项进行一些缓冲。这允许您在内存中加载多行，总计约为字节。sizehint

score 0 · Accepted Answer

0

您需要使用 seek() 实现二进制搜索

于 2009-04-13T15:56:12.913 回答

python - 用 Python 读取大文件

8 回答 8

Related

Reference