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

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

19 голосов
/ 01 июня 2011

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

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

Ответы [ 2 ]

7 голосов
/ 01 июня 2011

Так что я говорю придерживайтесь 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))

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

3 голосов
/ 06 августа 2015

Прошло четыре года с тех пор, как на этот вопрос был дан ответ, но я столкнулся с теми же проблемами, что и gatoatigrado в комментарии к ответу дона Стюарта. Метод put работает так, как объявлено, но get читает весь ввод. Я полагаю, что проблема заключается в сопоставлении с шаблоном в операторе case 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 работал в постоянной памяти в обоих случаях доступа к голове и последним элементам.

...