python - 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

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万行ごとではなく、キーごとに1回だけ変換する必要がある場合に、最後に変換を行います。

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。
この方法では、ファイルをメモリに保存されているかのように使用できますが、ファイルから実際に読み取るページは OS によって決定されます。

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

0

seek() を使用してバイナリ検索を実装する必要があります

于 2009-04-13T15:56:12.913 に答える

score 0 · Accepted Answer

考えられる最適化の 1 つは、 file.readlines(..)sizehintのオプションを使用して少しバッファリングすることです。これにより、合計で約バイトになる複数の行をメモリにロードできます。sizehint

python - Python での巨大なファイルの読み取り

8 に答える 8

Related

Reference