Leyendo archivo enorme en Python

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 Python foo más eficiente para reducir 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 

Búsqueda binaria codificada + solución de búsqueda (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  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 

Si solo necesita 200 de 50 millones de líneas, entonces leer todo 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 utilizando seek () o algo similar. De esta manera no leerías todo el archivo en la memoria, lo que creo que debería acelerar las cosas.

Optimización ligera de respuesta de 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 ) 

Ya que estamos usando 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 por cada clave, en lugar de cada una de 50 millones de líneas.

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 ) 

Yo usaría el mapeo de memoria: http://docs.python.org/library/mmap.html .
De esta manera, puede usar el archivo como si estuviera almacenado en la memoria, pero el sistema operativo decide qué páginas deben leerse realmente desde el archivo.

Aquí está 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 creado 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 el caché para determinar los puntos de búsqueda de inicio futuros.

Si tiene algún control sobre el formato del archivo, las respuestas de “clasificación y búsqueda binaria” son correctas. El detalle es que esto solo funciona con registros de tamaño y desplazamiento fijos (bueno, debo 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.

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

Es necesario implementar la búsqueda binaria utilizando seek ()