2010-06-06 20 views
9

Digamos que rutinariamente tengo que trabajar con archivos con un número desconocido, pero grande de líneas. Cada línea contiene un conjunto de enteros (espacio, coma, punto y coma, o algún carácter no numérico es el delimitador) en el intervalo cerrado [0, R], donde R puede ser arbitrariamente grande. El número de enteros en cada línea puede ser variable. Muchas veces obtengo el mismo número de enteros en cada línea, pero ocasionalmente tengo líneas con conjuntos desiguales de números.Mover a una posición arbitraria en un archivo en Python

Supongamos que quiero ir a la línea Nth en el archivo y recuperar el número Kth en esa línea (y asumir que las entradas N y K son válidas --- es decir, no me preocupan las malas entradas). ¿Cómo hago esto de manera eficiente en Python 3.1.2 para Windows?

No quiero atravesar el archivo línea por línea.

Intenté usar mmap, pero mientras hurgaba en SO, aprendí que probablemente esa no sea la mejor solución en una compilación de 32 bits debido al límite de 4 GB. Y, a decir verdad, no podría entender cómo mover las N líneas de mi posición actual. Si puedo al menos simplemente "saltar" a la línea Nth, entonces puedo usar .split() y tomar el entero Kth de esa manera.

El matiz aquí es que no solo necesito tomar una línea del archivo. Necesitaré tomar varias líneas: no necesariamente están todas juntas, el orden en que las obtengo importa, y el orden no siempre se basa en alguna función determinista.

¿Alguna idea? Espero que esto sea suficiente información.

Gracias!

+0

estaría feliz si hubiera una solución para el caso cuando tengo el mismo número de enteros en cada uno en el archivo. –

Respuesta

16

pitón de seek va a un byte desplazamiento en un archivo, no a una línea offset, simplemente porque eso es los sistemas operativos modernos camino y sus sistemas de ficheros de trabajo - el OS/FS simplemente no registrar o recordar "offsets de línea" de cualquier manera, y no hay forma de que Python (o cualquier otro idioma) los adivine mágicamente. Cualquier operación que pretenda "ir a una línea" inevitablemente tendrá que "recorrer el archivo" (debajo de las coberturas) para hacer la asociación entre los números de línea y las compensaciones de bytes.

Si está de acuerdo con eso y lo quiere ocultar de su vista, la solución es el módulo de biblioteca estándar linecache - pero el rendimiento no será mejor que el del código que podría escribir usted mismo.

Si tiene que leer desde el mismo archivo de gran tamaño en múltiples ocasiones, una gran optimización sería correr vez en ese archivo grande de un script que se acumula y guarda en el disco el número de línea - a - Byte correspondencia offset (técnicamente un archivo auxiliar de "índice"); luego, todas las ejecuciones sucesivas (hasta que el archivo grande cambie) podrían usar muy rápidamente el archivo de índice para navegar con un rendimiento muy alto a través del archivo grande. ¿Es este tu caso de uso ...?

Editar: ya que aparentemente esto puede aplicarse - aquí está la idea general (sin pruebas cuidadosas, comprobación de errores u optimización ;-).Para hacer el índice, utilice makeindex.py, de la siguiente manera:

import array 
import sys 

BLOCKSIZE = 1024 * 1024 

def reader(f): 
    blockstart = 0 
    while True: 
    block = f.read(BLOCKSIZE) 
    if not block: break 
    inblock = 0 
    while True: 
     nextnl = block.find(b'\n', inblock) 
     if nextnl < 0: 
     blockstart += len(block) 
     break 
     yield nextnl + blockstart 
     inblock = nextnl + 1 

def doindex(fn): 
    with open(fn, 'rb') as f: 
    # result format: x[0] is tot # of lines, 
    # x[N] is byte offset of END of line N (1+) 
    result = array.array('L', [0]) 
    result.extend(reader(f)) 
    result[0] = len(result) - 1 
    return result 

def main(): 
    for fn in sys.argv[1:]: 
    index = doindex(fn) 
    with open(fn + '.indx', 'wb') as p: 
     print('File', fn, 'has', index[0], 'lines') 
     index.tofile(p) 

main() 

y después de usarlo, por ejemplo, la siguiente useindex.py:

import array 
import sys 

def readline(n, f, findex): 
    f.seek(findex[n] + 1) 
    bytes = f.read(findex[n+1] - findex[n]) 
    return bytes.decode('utf8') 

def main(): 
    fn = sys.argv[1] 
    with open(fn + '.indx', 'rb') as f: 
    findex = array.array('l') 
    findex.fromfile(f, 1) 
    findex.fromfile(f, findex[0]) 
    findex[0] = -1 
    with open(fn, 'rb') as f: 
    for n in sys.argv[2:]: 
     print(n, repr(readline(int(n), f, findex))) 

main() 

He aquí un ejemplo (en mi portátil lenta):

$ time py3 makeindex.py kjv10.txt 
File kjv10.txt has 100117 lines 

real 0m0.235s 
user 0m0.184s 
sys 0m0.035s 
$ time py3 useindex.py kjv10.txt 12345 98765 33448 
12345 '\r\n' 
98765 '2:6 But this thou hast, that thou hatest the deeds of the\r\n' 
33448 'the priest appointed officers over the house of the LORD.\r\n' 

real 0m0.049s 
user 0m0.028s 
sys 0m0.020s 
$ 

El archivo de ejemplo es un archivo de texto plano de la Biblia king James':

$ wc kjv10.txt 
100117 823156 4445260 kjv10.txt 

100K líneas, 4.4 MB, como puede ver; esto toma alrededor de un cuarto de segundo para indexar y 50 milisegundos para leer e imprimir tres líneas aleatorias (sin duda, esto puede acelerarse enormemente con una optimización más cuidadosa y una máquina mejor). El índice en la memoria (y también en el disco) toma 4 bytes por línea del archivo de texto que se indexa, y el rendimiento debe escalar de una manera perfectamente lineal, así que si tuviera alrededor de 100 millones de líneas, 4.4 GB, esperaría alrededor de 4-5 minutos para construir el índice, un minuto para extraer e imprimir tres líneas arbitrarias (y los 400 MB de RAM tomados para el índice no deberían ser inconvenientes ni siquiera para una máquina pequeña; incluso mi pequeña laptop lenta tiene 2GB después de todo ;-).

También puede ver que (por velocidad y conveniencia) trato el archivo como binario (y supongo que la codificación utf8 - funciona con cualquier subconjunto como ASCII, por supuesto, por ejemplo, que el archivo de texto KJ es ASCII) y no molesta colapsar \r\n en un solo carácter si eso es lo que el archivo tiene como terminador de línea (es bastante trivial hacer eso después de leyendo cada línea si quieres).

+0

su solución de optimización es agradable. me gusta. +1. Todavía tengo que atravesar el archivo auxiliar de índice, ¿verdad? pero, por supuesto, eso es mejor que tener que atravesar mi archivo original. linecache parece cargar todo el archivo en la memoria RAM y no siempre tendré ese lujo. –

+1

@B Rivera, el "archivo auxiliar de índice" debe ser lo suficientemente pequeño como para mantenerse en la RAM incluso para un archivo de texto de varios millones de líneas. Permítanme esbozar una solución simplista para mostrar lo que tengo en mente (pronto voy a editar mi respuesta para mostrar eso). –

+0

sabes qué, entiendo lo que dices. use linecache en el archivo auxiliar de índice. eso es ciertamente razonable. –

4

El problema es que debido a que sus líneas no son de longitud fija, debe prestar atención a los marcadores de línea para realizar su búsqueda, y eso se convierte efectivamente en "atravesar el archivo línea por línea". Por lo tanto, cualquier enfoque viable seguirá atravesando el archivo, es simplemente una cuestión de lo que puede atravesarlo más rápido.

+0

supongamos que aflojo el requisito sobre líneas de longitud desigual. por longitud ¿te refieres al número real de caracteres o al número de enteros? los archivos más estructurados que obtendré son aquellos con el mismo número de enteros separados por algún delimitador en cada línea, pero no necesariamente tendrán el mismo número de caracteres. ¿Eso hace posible hacer lo que necesito? –

+0

@BRivera, el problema es el número de bytes por línea: cómo esos bytes en una línea se dividen entre enteros o cualquier otra cosa es irrelevante. –

+2

Suponiendo que son archivos de texto (y suponiendo que el archivo está codificado en una codificación de caracteres de número fijo de bytes, como ASCII simple), "igual longitud" significa la misma cantidad de caracteres. La razón por la que hace la diferencia es porque si usted sabe que las líneas son de longitud fija * character *, también sabrá que las líneas son de longitud fija * byte * y, por lo tanto, puede usar 'file.seek (longitud de línea) (linenum-1)) 'para mover al byte que comienza una línea dada. Pero esto solo funciona si 'linelength' es el mismo para todas las líneas. De lo contrario, ese cálculo es imposible. – Amber

0

Otra solución, si el archivo potencialmente va a cambiar mucho, es ir por completo a una base de datos adecuada. El motor de base de datos creará y mantendrá los índices por usted para que pueda hacer búsquedas/consultas muy rápidas.

Esto puede ser una exageración.

Cuestiones relacionadas