Come leggere un file a ritroso per trovare sottostringa efficiente

Question

Ho un file di log enorme in questo tipo di struttura:

"timestamp": { "identificatore": valore}

"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}, 

voglio estrarre il contenuto dopo un dato timestamp come (!):

std::ifstream * myfunc(uint32_t timestamp) 

esempio:

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

Il file di log è troppo lungo per conservarlo in memoria. Il codice verrà eseguito su dispositivi embedded con risorse limitate (80 Mhz, ~ 10kB di memoria libera), quindi sto cercando alcune idee per una soluzione efficace.

Il file di registro potrebbe avere voci di 500k + e nel 99% del tempo il timestamp sarà nelle ultime 100 righe, quindi partire dall'inizio del file e verificare che ogni riga per il timestamp giusto sarebbe molto inefficiente.

Quindi suppongo che sto cercando una soluzione per leggere il file all'indietro, riga per riga. Non ho davvero una soluzione su come farlo in modo efficiente senza caricare grandi blocchi in memoria.

Ho provato a leggere in blocchi di 200 byte a partire dall'EOF, ma ho dovuto affrontare il problema, che il blocco tagliava in due il timestamp in molti casi. Ho provato a rilevarlo e selezionare nuovamente alcuni byte se necessario, ma ho avuto la sensazione che ci debba essere una soluzione smarte.

Answer 1

Bene, ho trovato questo tipo di interessante così ho messo a punto una prova di concetto per l'idea binary-search.

Questo è mal testato e probabilmente un po 'bacato, ma sembra funzionare fino ad ora e dimostra l'idea di dividi e impara. Controlli nel mezzo del file e, a seconda se sei troppo alto o troppo basso, dividi i dati in due e cerchi la metà pertinente. Lo fai in modo ricorsivo finché non ti avvicini abbastanza.

#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"; 
} 

uscita:

"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

Se le prestazioni non sono un problema, è possibile leggere l'intero file riga per riga fino a raggiungere l'ora richiesta, quindi avviare il dump. Non c'è motivo di leggere l'intero file in memoria. Se le prestazioni sono un problema, cerca metà del file, controlla il timestamp, quindi dividi nuovamente per due in modo ricerca binaria.

Answer 3

Dato che ci si trova su un dispositivo incorporato in cui è probabile che non sia disponibile mmap(), suppongo che l'unico approccio praticabile sia quello di utilizzare un buffer che si riempie con una parte del file, per poterne esaminare il contenuto di un blocco in un tempo. Notare che sarà necessario sovrapporre le finestre del buffer per evitare di perdere una linea tagliata a metà dall'inizio del buffer. Dovrai cercare la prima nuova riga all'inizio di un blocco e scartarla con qualsiasi cosa prima di poter iniziare a esaminare il blocco per i timestamp. Scartare la linea parziale all'inizio del buffer aiuta anche ad allineare la fine di quella stessa linea con la fine del buffer quando si carica il blocco precedente nel buffer.

La gestione di righe incomplete all'inizio del buffer rende questo approccio molto brutto e soggetto a errori. Questo è il motivo per cui suggerirei di usare mmap() se disponibile, ti permetterebbe semplicemente di ignorare questi problemi.