programas - manual de c++ basico

La forma más rápida de encontrar el número de líneas en un texto(C++)

Question

Necesito leer la cantidad de líneas en un archivo antes de realizar algunas operaciones en ese archivo. Cuando intento leer el archivo e incrementar la variable line_count en cada iteración hasta llegar a eof. No fue tan rápido en mi caso. Utilicé tanto ifstream como fgets. Ambos fueron lentos. ¿Existe una forma pirata de hacer esto, que también es utilizada por, por ejemplo, BSD, kernel de Linux o db berkeley (puede ser mediante el uso de operaciones bitwise).

Como dije antes, hay millones de líneas en ese archivo y cada vez se hace más grande, cada línea tiene alrededor de 40 o 50 caracteres. Estoy usando Linux.

Nota: Estoy seguro de que habrá personas que podrían decir que usan un idiota de DB. Pero brevemente en mi caso no puedo usar un db.

Answer 1

Hay una diferencia entre contar líneas y contar separadores de líneas. Algunos errores comunes a tener en cuenta si obtener un recuento de líneas exacto es importante:

1. ¿Cuál es la codificación del archivo? Las soluciones de byte a byte funcionarán para ASCII y UTF-8, pero tenga cuidado si tiene UTF-16 o alguna codificación multibyte que no garantiza que un byte con el valor de un salto de línea codifique necesariamente un salto de línea.

2. Muchos archivos de texto no tienen un separador de línea al final de la última línea. Así que si tu archivo dice "Hello, World!" , podría terminar con un conteo de 0 en lugar de 1. En lugar de solo contar los separadores de línea, necesitará una máquina de estados simple para realizar un seguimiento.

3. Algunos archivos muy oscuros usan Unicode U+2028 LINE SEPARATOR (o incluso U+2029 PARAGRAPH SEPARATOR ) como separadores de línea en lugar del retorno de carro y / o avance de línea más común. También es posible que desee tener cuidado con U+0085 NEXT LINE (NEL) .

4. Tendrá que considerar si desea contar algunos otros caracteres de control como interruptores de línea. Por ejemplo, ¿debería considerarse una U+000C FORM FEED o U+000B LINE TABULATION (también conocida como pestaña vertical) yendo a una nueva línea?

5. Los archivos de texto de versiones anteriores de Mac OS (antes de OS X) utilizan retornos de carro ( U+000D ) en lugar de U+000D de línea ( U+000A ) para separar las líneas. Si está leyendo los bytes sin procesar en un búfer (por ejemplo, con su flujo en modo binario) y los está escaneando, obtendrá un conteo de 0 en estos archivos. No puede contar los retornos de carro y los avances de línea, porque los archivos de PC generalmente terminan una línea con ambos. Una vez más, necesitará una máquina de estado simple. (Alternativamente, puede leer el archivo en modo de texto en lugar de en modo binario. Las interfaces de texto normalizarán los separadores de línea a ''/n'' para los archivos que cumplan con la convención utilizada en su plataforma. Si está leyendo archivos de otras plataformas, volverá al modo binario con una máquina de estados.)

6. Si alguna vez tiene una línea muy larga en el archivo, el método getline() puede generar una excepción que haga que su simple contador de línea falle en una pequeña cantidad de archivos. (Esto es particularmente cierto si está leyendo un archivo Mac antiguo en una plataforma que no es Mac, lo que hace que getline() vea el archivo completo como una línea gigantesca.) Al leer fragmentos en un búfer de tamaño fijo y usar una máquina de estados , puedes hacerlo a prueba de balas.

El código en la respuesta aceptada sufre de la mayoría de estas trampas. Hazlo bien antes de que lo hagas rápido.

Answer 2

La única forma de encontrar el recuento de líneas es leer el archivo completo y contar el número de caracteres de fin de línea. La forma más rápida en que Tom puede hacer esto es, probablemente, leer todo el archivo en un búfer grande con una sola operación de lectura y luego recorrer el búfer contando los caracteres ''/ n''.

Como su tamaño de archivo actual parece ser de unos 60Mb, esta no es una opción atractiva. Puede obtener algo de la velocidad si no lee el archivo completo, sino que lo lee en trozos. Por ejemplo, del tamaño de 1Mb. También dice que una base de datos está fuera de discusión, pero realmente parece ser la mejor solución a largo plazo.

Edición: acabo de encontrar un pequeño punto de referencia en esto y el uso del enfoque de búfer (tamaño del búfer 1024K) parece ser un poco más rápido que leer una línea a la vez con getline () Aquí está el código: mis pruebas se realizaron con g ++ utilizando el nivel de optimización -O2:

#include <iostream>
#include <fstream>
#include <vector>
#include <ctime>
using namespace std;

unsigned int FileRead( istream & is, vector <char> & buff ) {
    is.read( &buff[0], buff.size() );
    return is.gcount();
}

unsigned int CountLines( const vector <char> & buff, int sz ) {
    int newlines = 0;
    const char * p = &buff[0];
    for ( int i = 0; i < sz; i++ ) {
        if ( p[i] == ''/n'' ) {
            newlines++;
        }
    }
    return newlines;
}

int main( int argc, char * argv[] ) {
    time_t now = time(0);
    if ( argc == 1  ) {
        cout << "lines/n";
        ifstream ifs( "lines.dat" );
        int n = 0;
        string s;
        while( getline( ifs, s ) ) {
            n++;
        }
        cout << n << endl;
    }
    else {
        cout << "buffer/n";
        const int SZ = 1024 * 1024;
        std::vector <char> buff( SZ );
        ifstream ifs( "lines.dat" );
        int n = 0;
        while( int cc = FileRead( ifs, buff ) ) {
            n += CountLines( buff, cc );
        }
        cout << n << endl;
    }
    cout << time(0) - now << endl;
}

Answer 3

Lo que lleva tiempo es cargar más de 40 MB en la memoria. La forma más rápida de hacerlo es mapearlo en memoria o cargarlo de una vez en un búfer grande. Una vez que lo tiene en la memoria, de una forma u otra, un bucle que atraviesa los datos en busca de caracteres /n es casi instantáneo, sin importar cómo se implemente.

Entonces, realmente, el truco más importante es cargar el archivo en la memoria lo más rápido posible. Y la forma más rápida de hacerlo es hacerlo como una sola operación.

De lo contrario, pueden existir muchos trucos para acelerar el algoritmo. Si solo se agregan líneas, nunca se modifican ni se eliminan, y si está leyendo el archivo repetidamente, puede almacenar en caché las líneas leídas anteriormente, y la próxima vez que tenga que leer el archivo, solo lea las líneas recién agregadas.

O tal vez puede mantener un archivo de índice separado que muestre la ubicación de los caracteres ''/ n'' conocidos, para que esas partes del archivo se puedan omitir.

La lectura de grandes cantidades de datos desde el disco duro es lenta. No hay manera de evitar eso.

Answer 4

No es lento debido a su algoritmo, es lento porque las operaciones de IO son lentas. Supongo que está utilizando un algoritmo O (n) simple que simplemente está recorriendo el archivo de forma secuencial. En ese caso, no existe un algoritmo más rápido que pueda optimizar su programa.

Sin embargo , dije que no hay un algoritmo más rápido, pero hay un mecanismo más rápido que se llama "Archivo de memoria asignado". Hay algunos inconvenientes para los archivos asignados y puede que no sea apropiado para su caso, por lo que tendrá que leerlo. y averigua por ti mismo.

Los archivos asignados en memoria no le permitirán implementar un algoritmo mejor que O (n), pero puede reducir el tiempo de acceso a IO.

Answer 5

No use cadenas de caracteres C ++ y getline (o fgets de C), solo punteros en bruto de estilo C y bloqueos de lectura en trozos de tamaño de página o mmap del archivo.

Luego escanee el bloque con el tamaño de palabra nativo de su sistema (es decir, uint32_t o uint64_t ) utilizando uno de los algoritmos mágicos "Operaciones SIMD dentro de un registro (SWAR)" para probar los bytes dentro de la palabra. Un ejemplo está here ; el bucle con el 0x0a0a0a0a0a0a0a0aLL en él busca los saltos de línea. (ese código llega a alrededor de 5 ciclos por byte de entrada que coincide con una expresión regular en cada línea de un archivo)

Si el archivo solo tiene unas decenas o un centenar de megabytes, y sigue creciendo (es decir, algo se está escribiendo), entonces es muy probable que Linux lo tenga almacenado en la memoria caché, por lo que no estará limitado el E / S del disco. , pero el ancho de banda de memoria limitado.

Si solo se agrega el archivo, también puede recordar el número de líneas y la longitud anterior, y comenzar desde allí.

Se ha señalado que podría usar mmap con los algoritmos C ++ stl y crear un functor para pasar a std :: foreach. Le sugerí que no debería hacerlo porque no puede hacerlo de esa manera, pero no hay ninguna ventaja en escribir el código adicional para hacerlo. O puede usar el iterador mmapped de boost, que lo maneja todo por usted; pero para el problema, el código al que me vinculé fue escrito porque esto era mucho, mucho más lento, y la pregunta era sobre la velocidad, no sobre el estilo.

Answer 6

Recuerda que todos los fstreams están en búfer. Así que, en efecto, en realidad se leen en porciones para que no tenga que recrear esta funcionalidad. Así que todo lo que necesitas hacer es escanear el búfer. No uses getline (), ya que esto te obligará a dimensionar una cadena. Así que solo usaría STL std :: count y transmitiré los iteradores.

#include <iostream>
#include <fstream>
#include <iterator>
#include <algorithm>


struct TestEOL
{
    bool operator()(char c)
    {
        last    = c;
        return last == ''/n'';
    }
    char    last;
};

int main()
{
    std::fstream  file("Plop.txt");

    TestEOL       test;
    std::size_t   count   = std::count_if(std::istreambuf_iterator<char>(file),
                                          std::istreambuf_iterator<char>(),
                                          test);

    if (test.last != ''/n'')  // If the last character checked is not ''/n''
    {                       // then the last line in the file has not been 
        ++count;            // counted. So increement the count so we count
    }                       // the last line even if it is not ''/n'' terminated.
}

Answer 7

Solo puede obtener una respuesta definitiva al escanear todo el archivo en busca de caracteres de nueva línea. No hay manera de evitar eso.

Sin embargo, hay un par de posibilidades que puede considerar.

1 / Si está utilizando un bucle simplista, leer un carácter a la vez para verificar si hay nuevas líneas, no. A pesar de que la E / S puede estar almacenada en búfer, las llamadas a funciones en sí mismas son costosas en el tiempo.

Una mejor opción es leer grandes fragmentos del archivo (por ejemplo, 5M) en la memoria con una sola operación de E / S, y luego procesarlos. Es probable que no tenga que preocuparse demasiado por las instrucciones de ensamblaje especiales, ya que la biblioteca de tiempo de ejecución de C se optimizará de todos modos; un simple strchr() debería hacerlo.

2 / Si está diciendo que la longitud general de la línea es de unos 40-50 caracteres y no necesita un recuento de líneas exacto , simplemente tome el tamaño del archivo y divídalo por 45 (o el promedio que considere conveniente usar).

3 / Si esto es algo así como un archivo de registro y no tiene que guardarlo en un archivo (puede que sea necesario volver a trabajar en otras partes del sistema), considere dividir el archivo periódicamente.

Por ejemplo, cuando llegue a 5M, muévalo (por ejemplo, x.log ) a un nombre de archivo con fecha (por ejemplo, x_20090101_1022.log ) y x_20090101_1022.log cuántas líneas hay en ese punto (almacenándolo en x_20090101_1022.count , entonces inicie un nuevo archivo de registro x.log . Las características de los archivos de registro significan que esta sección con fecha que se creó nunca cambiará, por lo que nunca tendrá que volver a calcular el número de líneas.

Para procesar el "archivo" de registro, solo debe cat x_*.log través de algún conducto de proceso en lugar de cat x.log . Para obtener el recuento de líneas del "archivo", haga un wc -l en el x.log actual (relativamente rápido) y añádalo a la suma de todos los valores en los archivos de x_*.count .

Answer 8

Usted escribió que sigue siendo cada vez más grande. Esto suena como si fuera un archivo de registro o algo similar donde se agregan nuevas líneas pero las líneas existentes no se cambian. Si este es el caso, podría intentar un enfoque incremental .

Analizar hasta el final del archivo. Recuerde el recuento de líneas y el desplazamiento de EOF. Cuando el archivo crezca hasta el desplazamiento, fseek EOF y actualice el recuento de líneas y el desplazamiento.