Как прочитать файл задом наперед, чтобы эффективно найти подстроку

У меня огромный лог-файл в такой структуре:

«отметка времени»: {«идентификатор»: значение}

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

Я хочу извлечь содержимое после (!) Заданной отметки времени, например:

std::ifstream * myfunc( uint32_t timestamp)

пример:

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

Файл журнала длинный — слишком длинный, чтобы хранить его в памяти. Код будет работать на встроенных устройствах с ограниченными ресурсами (80 МГц, ~ 10 КБ свободной памяти), поэтому я ищу некоторые идеи для эффективного решения.

Файл журнала может содержать более 500 тыс. Записей, и в 99% случаев метка времени будет находиться в последних 100 строках, поэтому начинать с начала файла и проверять каждую строку на правильность метки времени будет очень неэффективно.

Поэтому я думаю, что я ищу решение для чтения файла в обратном порядке, строка за строкой.
У меня действительно нет решения, как сделать это эффективно, не загружая большие куски в память.

Я пытался читать частями по 200 байт, начиная с EOF, но столкнулся с проблемой, состоящей в том, что во многих случаях блок сокращал временную метку пополам. Я попытался обнаружить это и повторно выбрать несколько байтов, если это необходимо, но у меня возникло ощущение, что должно быть разумное решение.

27

Решение

Ну, я нашел этот вид интересным, поэтому я нашел подтверждение концепции двоично-поиск идея.

Это плохо протестировано и, возможно, немного ошибочно, но, похоже, работает до сих пор и демонстрирует идею «разделяй и властвуй». Вы проверяете середину файла и, в зависимости от того, слишком высокий или низкий уровень, делите данные на две части и ищите соответствующую половину. Вы делаете это рекурсивно, пока не подойдете достаточно близко.

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

Выход:

"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
21

Другие решения

Поскольку вы находитесь на встроенном устройстве, где mmap() скорее всего, недоступен, я думаю, что единственный жизнеспособный подход — это использовать буфер, который вы заполняете частью файла, чтобы иметь возможность проверять его содержимое по одному фрагменту за раз. Обратите внимание, что вам нужно будет перекрывать окна буфера, чтобы не пропустить строку, разрезанную пополам к началу буфера. Вам нужно будет найти первый символ новой строки в начале фрагмента и отбросить его, прежде чем вы сможете приступить к проверке фрагмента на время. Удаление частичной строки в начале буфера также помогает выровнять конец той же строки с концом буфера, когда вы загружаете предыдущий блок в ваш буфер.

Обработка неполных строк в начале буфера делает этот подход очень уродливым и подверженным ошибкам. Это причина, почему я бы предложил использовать mmap() если это вообще возможно, это позволит вам просто игнорировать эти проблемы.

5

Если производительность не является проблемой, вы можете прочитать весь файл построчно пока вы не достигните запрошенного времени, а затем начните дамп. Нет причин читать весь файл в памяти. Если производительность является проблемой, найдите половину файла, проверьте метку времени, а затем разделите на два снова в режиме двоичного поиска.

3