txt - leer una linea especifica de un archivo en c++

Cómo leer un archivo al revés para encontrar subcadenas eficientemente

Question

Tengo un archivo de registro enorme en este tipo de estructura:

"timestamp": {"identifier": value}

"1463403600":{"AA":74.42},
"1463403601":{"AA":29.55},
"1463403603":{"AA":24.78},
"1463403604":{"AA":8.46},
"1463403605":{"AA":44.84},
"1463403607":{"AA":87.05},
"1463403608":{"AA":54.81},
"1463403609":{"AA":93.1},
"1463403611":{"AA":77.64},
"1463403612":{"AA":33.39},
"1463403613":{"AA":69.2},

Quiero extraer el contenido después de (!) Una marca de tiempo determinada como:

std::ifstream * myfunc( uint32_t timestamp) 

ejemplo:

myfunc(1463403611);
/* returns
"1463403611":{"AA":77.64},
"1463403612":{"AA":33.39},
"1463403613":{"AA":69.2},
*/

El archivo de registro es largo, demasiado largo para mantenerlo en la memoria. El código se ejecutará en dispositivos integrados con recursos limitados (80Mhz, ~ 10kB de memoria libre), por lo que estoy buscando algunas ideas para una solución efectiva.

El archivo de registro puede tener más de 500k entradas y, en el 99% del tiempo, la marca de tiempo estará en las últimas 100 líneas, por lo que comenzar desde el principio del archivo y verificar que cada línea tenga la marca de tiempo correcta sería muy ineficaz.

Así que supongo que estoy buscando una solución para leer el archivo al revés, línea por línea. Realmente no tengo una solución para hacer eso eficiente sin cargar grandes trozos en la memoria.

Intenté leer en partes de 200 bytes a partir del EOF, pero me enfrenté con el problema, que la parte corta la marca de tiempo en la mitad en muchos casos. Traté de detectar eso y volver a seleccionar algunos bytes si fuera necesario, pero tuve la sensación de que debía haber una solución inteligente.

Answer 1

Bueno, encontré este tipo de interesante, así que encontré una prueba de concepto para la idea de binary-search .

Esto está mal probado y probablemente tiene un poco de buggy, pero parece funcionar hasta ahora y demuestra la idea de dividir y conquistar. Usted verifica en la mitad del archivo y, dependiendo de si está en un nivel alto o demasiado bajo, divide los datos en dos y busca la mitad relevante. Lo haces recursivamente hasta que te acerques lo suficiente.

#include <ctime>
#include <cmath>
#include <cstdlib>
#include <string>
#include <fstream>
#include <iostream>

// Don''t use this, its just to show how many reads
// are being done to find the record.
int global_counter;

std::streampos find_stamp(std::istream& is, long stamp, std::streampos pos, std::streampos end)
{
    ++global_counter;

    if(pos == 0) // can''t divide zero
        return 0;

    std::string s;
    long found_stamp;

    // extract nearest timestamp after pos
    is.seekg(pos);
    if(!(std::getline(std::getline(is, s, '',''), s, ''"'') >> found_stamp))
        return end;

    // if its too big check first half of this region
    if(found_stamp > stamp)
        return find_stamp(is, stamp, pos / 2, pos);

    // if its not within 10 timestamp seconds check end half of this region
    if(stamp - found_stamp > 10)
        return find_stamp(is, stamp, (pos + end) / 2, end);

    // read record by record (prolly more efficient than skipping)
    pos = is.tellg();
    while(std::getline(std::getline(is, s, '',''), s, ''"'') >> found_stamp)
    {
        if(found_stamp > stamp)
            return pos;
        pos = is.tellg();
    }
    return end;
}

void print_after(const std::string& filename, long stamp)
{
    // open at end of file (to get length)
    std::ifstream ifs(filename, std::ios::ate);

    std::streampos end = ifs.tellg();
    auto pos = end / 2; // start checking in middle

    // find position before required record
    // (may be in the middle of a record)
    if((pos = find_stamp(ifs, stamp, pos, end)) != end)
    {
        ifs.seekg(pos);

        std::string line;
        std::getline(ifs, line, '',''); // skip to next whole record

        // print out all following recors
        while(std::getline(ifs, line, '',''))
            std::cout << line;
    }
}

inline
std::string leading_zeros(int n, int zeros = 2)
{
    std::string s;
    for(int z = std::pow(10, zeros - 1); z; z /= 10)
        s += (n < z ? "0":"");
    return s + std::to_string(n);
}

int main()
{
    std::srand(std::time(0));

    // generate some test data
    std::ofstream ofs("test.txt");

    for(int i = 0; i < 1000; ++i)
    {
        ofs << ''"'' << leading_zeros(i, 10) << ''"'';
        ofs << ":{/"AA/":" << (std::rand() % 100);
        ofs << ''.'' << (std::rand() % 100) << "},/n";
    }

    ofs.close();

    global_counter = 0;
    print_after("test.txt", 993);

    std::cout << "find checked " << global_counter << " places in the file/n";
}

Salida:

"0000000994":{"AA":80.6}
"0000000995":{"AA":11.90}
"0000000996":{"AA":16.43}
"0000000997":{"AA":53.11}
"0000000998":{"AA":68.43}
"0000000999":{"AA":79.77}
find checked 6 places in the file

Answer 2

Dado que se encuentra en un dispositivo integrado donde mmap() probablemente no esté disponible, creo que el único método viable es utilizar un búfer que rellene con una parte del archivo, para poder examinar su contenido de una en una. Tenga en cuenta que tendrá que superponer las ventanas de su búfer para evitar perder una línea que se corta a la mitad al comienzo del búfer. Deberá buscar la primera nueva línea al comienzo de un fragmento y descartarlo con cualquier cosa antes de que pueda comenzar a examinar el fragmento para las marcas de tiempo. Descartar la línea parcial al principio del búfer también ayuda a alinear el final de esa misma línea con el final del búfer cuando carga la parte anterior en su búfer.

El manejo de líneas incompletas al comienzo del búfer hace que este enfoque sea muy feo y propenso a errores. Esta es la razón por la que sugeriría usar mmap() si está disponible, le permitiría simplemente ignorar estos problemas.

Answer 3

Si el rendimiento no es un problema, puede leer la línea completa del archivo por línea hasta llegar al tiempo solicitado y luego iniciar el volcado. No hay razón para leer todo el archivo en la memoria. Si el rendimiento es un problema, busque la mitad del archivo, verifique la marca de tiempo, luego divida por dos nuevamente en una búsqueda binaria.