Двоичная сериализация для списков неопределенной длины в Haskell

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

Одним из решений было бы разобраться с форматом файла, чтобы изменить начальный счетчик, а затем просто добавить мои элементы. Но это не очень приятно, не говоря уже о том, чтобы быть чувствительным к будущим изменениям в формате файла в результате нарушения абстракции. Итераторы / перечислители приходят на ум в качестве привлекательного варианта здесь. Я искал библиотеку, объединяющую их с двоичной сериализацией, но ничего не нашел. Кто-нибудь знает, было ли это уже сделано? Если нет, то будет ли полезна библиотека для этого? Или я что-то упустил?

Источник

2 ответа

Решение

Поэтому я говорю придерживаться Data.Binary но напишите новый экземпляр для растущих списков. Вот текущий (строгий) экземпляр:

instance Binary a => Binary [a] where
    put l  = put (length l) >> mapM_ put l
    get    = do n <- get :: Get Int
                getMany n

-- | 'getMany n' get 'n' elements in order, without blowing the stack.
getMany :: Binary a => Int -> Get [a]
getMany n = go [] n
 where
    go xs 0 = return $! reverse xs
    go xs i = do x <- get
                 x `seq` go (x:xs) (i-1)
{-# INLINE getMany #-}

Теперь, версия, которая позволяет вам потоковое (в двоичном виде) добавлять к файлу, должна быть нетерпеливой или ленивой. Ленивая версия является самой тривиальной. Что-то вроде:

import Data.Binary

newtype Stream a = Stream { unstream :: [a] }

instance Binary a => Binary (Stream a) where

    put (Stream [])     = putWord8 0
    put (Stream (x:xs)) = putWord8 1 >> put x >> put (Stream xs)

    get = do
        t <- getWord8
        case t of
            0 -> return (Stream [])
            1 -> do x         <- get
                    Stream xs <- get
                    return (Stream (x:xs))

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

Источник

Прошло четыре года с тех пор, как на этот вопрос был дан ответ, но я столкнулся с теми же проблемами, что и gatoatigrado в комментарии к ответу дона Стюарта. put метод работает как рекламируется, но get читает весь ввод. Я полагаю, что проблема заключается в сопоставлении с образцом в кейсе, Stream xs <- get, который должен определить, являются ли остальные get это Stream a или нет, прежде чем вернуться.

Мое решение использовало пример в Data.Binary.Get в качестве отправной точки:

import Data.ByteString.Lazy(toChunks,ByteString)
import Data.Binary(Binary(..),getWord8)
import Data.Binary.Get(pushChunk,Decoder(..),runGetIncremental)
import Data.List(unfoldr)

decodes :: Binary a => ByteString -> [a]
decodes = runGets (getWord8 >> get)

runGets :: Get a -> ByteString -> [a]
runGets g = unfoldr (decode1 d) . toChunks
  where d = runGetIncremental g

decode1 _ [] = Nothing
decode1 d (x:xs) = case d `pushChunk` x of
                     Fail _ _ str  -> error str
                     Done x' _ a   -> Just (a,x':xs)
                     k@(Partial _) -> decode1 k xs

Обратите внимание на использование getWord8 Это читать закодированный [] а также : в результате определения put для экземпляра потока. Также обратите внимание, что поскольку getWord8 игнорирует закодированные символы [] и:, эта реализация не обнаружит конец списка. Мой закодированный файл был просто одним списком, так что он работает для этого, но в противном случае вам придется изменить.

В любом случае это decodes работал в постоянной памяти в обоих случаях доступа к голове и последним элементам.

Источник
Другие вопросы по тегам