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

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

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

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

std::ifstream * myfunc( uint32_t timestamp)

пример:

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

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

В файле журнала могут быть записи 500k +, и в 99% случаев отметка времени будет в последних 100 строках, поэтому начало в начале файла и проверка каждой строки для правильной временной метки будет очень неэффективной.

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

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

Ответ 1

Ну, я нашел такой интересный материал, поэтому я применил доказательство концепции

Вывод:

"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

Ответ 2

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

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

Ответ 3

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