Procesando archivos de texto enormes

StackOverflow https://stackoverflow.com/questions/1625299

  •  06-07-2019
  •  | 
  •  

Pregunta

Problema:Tengo un enorme archivo de texto sin procesar (supongo 3GIG), necesito pasar por cada palabra en el archivo y descubrir que una palabra aparece cuántas veces en el archivo.

Mi solución propuesta:Divida el archivo enorme en varios archivos y cada archivo dividido tendrá palabras ordenadas.Por ejemplo, todas las palabras que comienzan con "a"se almacenará en un"_a.dic" archivo.Así, en ningún momento excederemos de 26 archivos.

El problema en este enfoque es,

Puedo usar transmisiones para leer el archivo, pero quería usar subprocesos para leer ciertas partes del archivo.Por ejemplo, lea de 0 a 1024 bytes con un subproceso separado (al menos tenga de 4 a 8 subprocesos según el número.de procesadores existen en la caja).¿Es esto posible o estoy soñando?

¿Algún enfoque mejor?

Nota:Debería ser una solución pura basada en C++ o C.No se permiten bases de datos, etc.

¿Fue útil?

Solución

Debe mirar ' La práctica de la programación ' de Kernighan y Pike, y específicamente el capítulo 3.

En C ++, use un mapa basado en las cadenas y un conteo (std::map<string,size_t>, IIRC). Lea el archivo (una vez; es demasiado grande para leerlo más de una vez), divídalo en palabras a medida que avanza (para una definición de 'palabra') e incremente el recuento en la entrada del mapa para cada palabra que encuentre.

En C, deberá crear el mapa usted mismo. (O encuentre el & Quot; C Interfaces e implementaciones & Quot de David Hanson ;.)

O puede usar Perl, Python o Awk (todos los cuales tienen matrices asociativas, equivalentes a un mapa).

Otros consejos

No creo que usar varios hilos que leen partes del archivo en paralelo vaya a ayudar mucho. Esperaría que esta aplicación esté vinculada al ancho de banda y la latencia de su disco duro, no al conteo real de palabras. Tal versión de subprocesos múltiples podría funcionar peor porque & Quot; cuasi-random & Quot; el acceso a archivos suele ser más lento que " archivo lineal " acceso.

En caso de que la CPU esté realmente ocupada en una versión de subproceso único, puede haber una posible aceleración. Un hilo podría leer los datos en grandes fragmentos y ponerlos en una cola de capacidad limitada. Un montón de otros hilos de trabajo podrían operar cada uno en su propio trozo y contar las palabras. Después de que los subprocesos de trabajo de conteo terminaron, debe fusionar los contadores de palabras.

Primero: decida la estructura de datos para guardar las palabras.

La elección obvia es el mapa. Pero quizás un Trie le sirva mejor. En cada nodo, guarda el recuento de la palabra. 0 significa que es solo una parte de una palabra. Puede insertar en el trie usando una secuencia y leyendo su archivo basado en caracteres.

Segundo: ¿subprocesos múltiples sí o no? Este no es fácil de responder. Según el tamaño, la estructura de datos crece y la forma en que se paraleliza la respuesta puede diferir.

  1. Singlethreaded: directo y fácil de implementar.
  2. Multiproceso con múltiples hilos de lectura y una estructura de datos. Luego debe sincronizar el acceso a la estructura de datos. En un Trie, solo necesita bloquear el nodo en el que se encuentra realmente, para que múltiples lectores puedan acceder a la estructura de datos sin mucha interferencia. Un árbol de equilibrio automático puede ser diferente, especialmente cuando se reequilibra.
  3. Multiproceso con múltiples hilos de lectura, cada uno con su propia estructura de datos. Cada hilo construye su propia estructura de datos mientras lee una parte del archivo. Una vez finalizado cada uno, los resultados deben combinarse (lo que debería ser fácil).

Una cosa en la que debe pensar es que debe encontrar un límite de palabras para que comience cada subproceso, pero eso no debería plantear un gran problema (por ejemplo, cada subproceso camina desde su inicio hasta el primer límite de palabra y comienza allí, en el terminar cada hilo termina la palabra en la que está trabajando).

Si bien puedes usar un segundo hilo para analizar los datos después de leerlos, probablemente no ganarás mucho al hacerlo.Intentar utilizar más de un hilo para leer los datos seguramente perjudicará la velocidad en lugar de mejorarla.Usar múltiples subprocesos para procesar los datos no tiene sentido: el procesamiento será muchas veces más rápido que la lectura, por lo que incluso con un solo subproceso adicional, el límite será la velocidad del disco.

Una forma (posible) de ganar una velocidad significativa es evitar los iostreams habituales; aunque algunos son casi tan rápidos como usar C FILE*, no conozco nada que sea realmente más rápido y algunos son sustancialmente más lentos.Si está ejecutando esto en un sistema (p. ej.Windows) que tiene un modelo de E/S que es notablemente diferente al de C, puedes ganar mucho más con un poco de cuidado.

El problema es bastante simple:el archivo que estás leyendo es (potencialmente) más grande que el espacio de caché que tienes disponible, pero no ganarás nada con el almacenamiento en caché, porque no volverás a leer fragmentos del archivo nuevamente (al menos si haces cosas sesudamente).Como tal, desea indicarle al sistema que omita cualquier almacenamiento en caché y que simplemente transfiera los datos lo más directamente posible desde la unidad de disco a su memoria, donde podrá procesarlos.En un sistema tipo Unix, eso probablemente sea open() y read() (y no te hará ganar mucho).En Windows, eso es CreateFile y ReadFile, pasando el FILE_FLAG_NO_BUFFERING bandera a CreateFile - y probablemente duplicará aproximadamente tu velocidad si lo haces bien.

También recibió algunas respuestas que recomiendan realizar el procesamiento utilizando varias construcciones paralelas.Creo que están fundamentalmente equivocados.A menos que haga algo terriblemente estúpido, el tiempo para contar las palabras en el archivo será solo unos pocos milisegundos más de lo que se necesita para simplemente leer el archivo.

La estructura que usaría sería tener dos buffers de, digamos, un megabyte cada uno.Leer datos en un búfer.Entregue ese búfer a su hilo de conteo para contar las palabras en ese búfer.Mientras eso sucede, lea los datos en el segundo búfer.Cuando haya terminado, básicamente intercambie los buffers y continúe.Hay un poco de procesamiento adicional que necesitarás hacer al intercambiar buffers para tratar con una palabra que puede cruzar el límite de un buffer al siguiente, pero es bastante trivial (básicamente, si el buffer no termina en blanco espacio, todavía estás en una palabra cuando comienzas a operar en el siguiente búfer de datos).

Siempre que esté seguro de que solo se usará en una máquina multiprocesador (multinúcleo), usar subprocesos reales está bien.Si existe la posibilidad de que esto se pueda hacer alguna vez en una máquina de un solo núcleo, sería mejor usar un solo subproceso con E/S superpuestas.

Como otros han indicado, el cuello de botella será la E / S del disco. Por lo tanto, le sugiero que use E / S superpuestas. Esto básicamente invierte la lógica del programa. En lugar de la codificación de su código para determinar cuándo hacer E / S, simplemente le dice al sistema operativo que llame a su código cada vez que haya terminado un poco de E / S. Si usa puertos de finalización de E / S , incluso puede decirle al Sistema operativo para utilizar varios subprocesos para procesar los fragmentos de archivo.

solución basada en c?

Creo que Perl nació para este propósito exacto.

La secuencia

solo tiene un cursor. Si accede a la transmisión con más de un hilo a la vez, no estará seguro de leer donde desee. La lectura se realiza desde la posición del cursor.

Lo que haría es tener solo un hilo (quizás el principal) que lea la secuencia y envíe bytes de lectura a otros hilos.

Por ejemplo:

  • El hilo #i está listo y pide al hilo principal que le dé la siguiente parte,
  • El hilo principal lee los siguientes 1Mb y los proporciona al hilo 1,
  • El hilo #i lee los 1Mb y cuenta las palabras como quieras,
  • El hilo #i termina su trabajo y vuelve a pedir los próximos 1Mb.

De esta manera, puede separar la lectura de la secuencia del análisis de la secuencia.

Lo que estás buscando es RegEx. Este hilo de Stackoverflow en motores c ++ regex debería ayudar:

C ++: ¿qué biblioteca de expresiones regulares debo usar?

Primero, estoy bastante seguro de que C / C ++ no es la mejor manera de manejar esto. Idealmente, también usarías algún mapa / reducción para el paralelismo.

Pero, asumiendo sus limitaciones, esto es lo que haría.

1) Divida el archivo de texto en fragmentos más pequeños. No tiene que hacer esto por la primera letra de la palabra. Solo divídalos en, digamos, fragmentos de 5000 palabras. En pseudocódigo, harías algo como esto:

index = 0

numwords = 0

mysplitfile = archivo abierto (index-split.txt)

while (archivo grande > > word) 

mysplitfile << word

numwords ++

if (numwords > 5000)

    mysplitfile.close()

    index++

    mysplitfile = openfile(index-split.txt)

2) Use una estructura de datos de mapas compartidos y pthreads para generar nuevos hilos para leer cada uno de los subarchivos. Nuevamente, pseudocódigo:

maplock = create_pthread_lock ()

sharedmap = std :: map ()

para cada archivo index-split.txt: 

spawn-new-thread(myfunction, filename, sharedmap, lock)

dump_map (sharedmap)

anular myfunction (nombre de archivo, mapa compartido) {

localmap = std::map<string, size_t>();

file = openfile(filename)

while (file >> word)

    if !localmap.contains(word)
         localmap[word] = 0

    localmap[word]++

acquire(lock)
for key,value in localmap
    if !sharedmap.contains(key)
         sharedmap[key] = 0

    sharedmap[key] += value
release(lock)

}

Perdón por la sintaxis. He estado escribiendo mucho python últimamente.

No es C, y es un poco FEO, pero solo tardó 2 minutos en sonar:

perl -lane '$h{$_}++ for @F; END{for $w (sort {$h{$b}<=>$h{$a} || $a cmp $b} keys %h) {print "$h{$w}\t$w"}}' file > freq

Recorre cada línea con -n
Divide cada línea en @F palabras con -a
Cada $_ hash de incrementos de palabras %h
Una vez el END de file Ha sido alcanzado,
sort el hash por la frecuencia $h{$b}<=>$h{$a}
Si dos frecuencias son idénticas, ordene alfabéticamente $a cmp $b
imprimir la frecuencia $h{$w} y la palabra $w
Redirigir los resultados al archivo 'freq'

Ejecuté este código en un archivo de texto de 3,3 GB con 580.000.000 de palabras.
Perl 5.22 se completó en 173 segundos.

Mi archivo de entrada ya tenía la puntuación eliminada y las mayúsculas convertidas a minúsculas, usando este fragmento de código:
perl -pe "s/[^a-zA-Z \t\n']/ /g; tr/A-Z/a-z/" file_raw > file
(duración de 144 segundos)

El script de conteo de palabras también podría escribirse en awk:
awk '{for (i=1; i<=NF; i++){h[$i]++}} END{for (w in h){printf("%s\t%s\n", h[w], w)}}' file | sort -rn > freq

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top