Самый эффективный способ поиска в большом файле

Какой самый эффективный способ обработки действительно больших двоичных файлов в Haskell?

Стандартный ответ - прочитать весь файл как ленивый ByteString, а затем использовать что-то вроде бинарного пакета для написания парсера над ним. Есть пара проблем с этим...

Во-первых, библиотеки, такие как Binary, не справляются с синтаксическим разбором, и я явно ожидаю, что синтаксический анализ будет неудачным.

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

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

Мне также может понадобиться искать назад или, может быть, конкретное смещение байта в файле, что, похоже, не очень хорошо поддерживается ленивым подходом ByteString. (Существует серьезная опасность завершения хранения всего файла в ОЗУ.)

Альтернативой, конечно же, является чтение отдельных байтов один за другим, чередующихся с командами hSeek. Но теперь проблема в том, насколько эффективно чтение файла по одному байту за раз? Похоже, это может быть довольно медленным. Я не уверен, что hSetBuffering влияет на это. (?)

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

Что мы думаем, ребята? Каков наилучший способ приблизиться к этому, с точки зрения производительности ввода-вывода и поддерживаемости кода?

Ответ 1

У меня была аналогичная проблема при работе с парсером PDF. Первоначально я использовал пакет iteratee (он поддерживает произвольный доступ). AFAIK - это единственная библиотека IO со случайной поддержкой IO.

Мой текущий подход основан на пакете io-streams. Мне было удобнее. Производительность достаточно хороша, attoparsec интеграция из коробки, много комбинаторов включены.

Вот базовый пример использования iteratee для случайного ввода-вывода:

[email protected]:/tmp/shum$ cat test.hs 

import qualified  Data.Iteratee as I
import qualified Data.Attoparsec.Iteratee as I
import qualified Data.Attoparsec.Char8 as P
import Control.Monad.IO.Class
import System.Environment

main :: IO ()
main = do
  [file] <- getArgs
  flip I.fileDriverRandom file $ do
    I.seek 20
    num1 <- I.parserToIteratee P.number
    liftIO $ print num1
    I.seek 10
    num2 <- I.parserToIteratee P.number
    liftIO $ print num2
[email protected]:/tmp/shum$ cat in.data 
111111111
222222222
333333333
[email protected]:/tmp/shum$ runhaskell test.hs in.data 
333333333
222222222
[email protected]:/tmp/shum$