алгоритм поиска по большим файлам

Question

Мне нужна помощь в выборе алгоритма поиска для поиска больших файлов.вот что я делаюДопустим, файл состоит из временного диапазона от t1 до t2.(t2> t1)

Мне нужно получить смещения файлов (fseek):

1. время t3, превышающее t1

2. время t4, котороеменьше времени t2

   | ------| ---|----------------|
   
   t1      t3   t4              t2
   

Наивная версия состоит в том, чтобы перебирать строки по всему файлу и возвращать fseek, когда текущее время равно t3, начинать с возвращенного поиска и повторять, пока текущее время равно t4return second fseek

Теперь допустим, файл имеет размер 100 ГБ, и мне нужно перебирать файл, чтобы получить период в 2 секунды.Тогда эта логика становится слишком ЦП и файловая система дорогой.Ищем лучшие решения.Используемый язык - C. Линии в настоящее время имеют фиксированный размер, но я бы хотел заглянуть в будущее и разобраться с алгоритмом, который не использует фиксированный размер.

Answer 1

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

Answer 2

Поскольку значения имеют фиксированную ширину, что-то вроде бинарного поиска или интерполяционного поиска звучит как лучшие варианты. Кроме того, если вы планируете работать с файлами в этих классах размеров (100 ГБ), вам следует рассмотреть возможность использования fgetpos / fsetpos из-за ограничений размера файлов fseek.