Leer archivo enorme en Python

Question

Tengo un archivo de texto de 384MB con 50 millones de líneas. Cada línea contiene 2 enteros separados por espacios: una clave y un valor. El archivo está ordenado por clave. Necesito una forma eficiente de buscar los valores de una lista de aproximadamente 200 claves en Python.

Mi enfoque actual se incluye a continuación. Tarda 30 segundos. Debe haber un Foo de Python más eficiente para llevar esto a una eficiencia razonable de un par de segundos como máximo.

# 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 

Coded búsqueda binaria + buscar una solución (gracias 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

Si solo necesita 200 de 50 millones de líneas, leer todo eso en la memoria es un desperdicio. Ordenaría la lista de claves de búsqueda y luego aplicaría la búsqueda binaria al archivo usando seek() o algo similar. De esta forma, no leería todo el archivo en la memoria, lo que creo que debería acelerar las cosas.

Answer 2

me gustaría utilizar la memoria-Maping: http://docs.python.org/library/mmap.html.
De esta forma puede usar el archivo como si estuviera almacenado en la memoria, pero el sistema operativo decide qué páginas deberían leerse realmente del archivo.

Answer 3

No está claro de qué se trata la "lista [puntero]". Considera esto, sin embargo.

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

Una posible optimización es hacer un poco de almacenamiento en búfer utilizando la opción sizehint en file.readlines(..). Esto le permite cargar varias líneas en la memoria por un total de aproximadamente sizehint bytes.

Answer 5

optimización leve de respuesta 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) 

Puesto que estamos utilizando un diccionario en lugar de una lista, las claves no tienen que ser números. Esto guarda la operación map() y una conversión de cadena a entero para cada línea. Si desea que las claves sean números, realice la conversión al final, cuando solo tenga que hacerlo una vez para cada clave, en lugar de hacerlo para cada una de 50 millones de líneas.

Answer 6

Si tiene control sobre el formato del archivo, las respuestas de "ordenar y buscar binaria" son correctas. El detalle es que esto solo funciona con registros de tamaño fijo y desplazamiento (bueno, debería decir que solo funciona fácilmente con registros de longitud fija).

Con registros de longitud fija, puede buscar fácilmente() alrededor del archivo ordenado para encontrar sus claves.

Answer 7

es necesario implementar búsqueda binaria utilizando seek()

Answer 8

Aquí es una búsqueda binaria recursiva en el archivo de texto

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) 

Un archivo de texto de ejemplo creada en jEdit parece funcionar:

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

Definitivamente podría mejorarse almacenando en caché las claves encontradas y utilizando la memoria caché para determinar los puntos de búsqueda de inicio futuros.