4

Haskell を使用して、単純な (しかし非常に大きな) ツリー構造をバイナリ ファイルに保存しようとしています。構造は次のようになります。

-- 簡単にするために、各ノードには 4 つの子のみがあると仮定します。
データ ツリー = ノード [ツリー] | リーフ [中]
そして、ディスク上でデータをどのように表示する必要があるかを次に示します。

  1. 各ノードは、その子への 4 つの 32 ビット オフセットで始まり、子に続きます。
  2. リーフについてはあまり気にしません。たとえば、n 個の連続した 32 ビットの数字だとしましょう。
  3. 実用的な目的で、いくつかのノード ラベルやその他の追加データが必要になりますが、今のところ、どちらもあまり気にしません。

Haskeller がバイナリ ファイルを作成する際に最初に選択するのは、Data.Binary.Put ライブラリであるように思えます。しかし、それで私は箇条​​書き＃1に問題があります。特に、ノードをファイルに書き込もうとしているときに、子のオフセットを書き留めるには、現在のオフセットと各子のサイズを知る必要があります。

これは Data.Binary.Put が提供するものではないので、Monad トランスフォーマーの完璧なアプリケーションに違いないと思いました。しかし、クールで機能的に聞こえますが、これまでのところ、このアプローチは成功していません。

こことここで問題を解決するのに役立つと思われる他の 2 つの質問をしました。私は、私がさらに進歩するのに役立つ非常に素晴らしい回答を受け取るたびに、残念ながら私はまだ問題を全体的に解決することができていないと言わなければなりません.

ここに私がこれまでに得たものがありますが、まだメモリリークが多すぎて実用的ではありません。

このような機能的なアプローチを使用するソリューションがあれば幸いですが、他のソリューションにも感謝します。

4

4 に答える 4

2

「バイナリ」パッケージの一部であるBuilderを使用した実装を次に示します。私はそれを適切にプロファイリングしていませんが、「トップ」によると、すぐに 108 M バイトを割り当て、残りの実行のためにそれを保持します。

データを読み取ろうとしていないことに注意してください。そのため、サイズとオフセットの計算にエラーが潜んでいる可能性があります。

-- Paste this into TreeBinary.hs, and compile with
--    ghc -O2 --make TreeBinary.hs -o TreeBinary

module Main where


import qualified Data.ByteString.Lazy as BL
import qualified Data.Binary.Builder as B

import Data.List (init)
import Data.Monoid
import Data.Word


-- -------------------------------------------------------------------
-- Test data.

data Tree = Node [Tree] | Leaf [Word32] deriving Show

-- Approximate size in memory (ignoring laziness) I think is:
-- 101 * 4^9 * sizeof(Int) + 1/3 * 4^9 * sizeof(Node)

-- This version uses [Word32] instead of [Int] to avoid having to write
-- a builder for Int.  This is an example of lazy programming instead
-- of lazy evaluation. 

makeTree :: Tree
makeTree = makeTree1 9
  where makeTree1 0 = Leaf [0..100]
        makeTree1 n = Node [ makeTree1 $ n - 1
                           , makeTree1 $ n - 1
                           , makeTree1 $ n - 1
                           , makeTree1 $ n - 1 ]

-- --------------------------------------------------------------------
-- The actual serialisation code.


-- | Given a tree, return a builder for it and its estimated length in bytes.
serialiseTree :: Tree -> (B.Builder, Word32)
serialiseTree (Leaf ns) = (mconcat (B.singleton 2 : map B.putWord32be ns), fromIntegral $ 4 * length ns + 1)
serialiseTree (Node ts) = (mconcat (B.singleton 1 : map B.putWord32be offsets ++ branches), 
                           baseLength + sum subLengths)
   where
      (branches, subLengths) = unzip $ map serialiseTree ts
      baseLength = fromIntegral $ 1 + 4 * length ts
      offsets = init $ scanl (+) baseLength subLengths


main = do
   putStrLn $ "Length = " ++ show (snd $ serialiseTree makeTree)
   BL.writeFile "test.bin" $ B.toLazyByteString $ fst $ serialiseTree makeTree
于 2011-03-06T21:17:10.520 に答える
2

私が検討する基本的なアプローチは 2 つあります。シリアル化された構造全体が簡単にメモリに収まる場合は、各ノードを遅延バイト文字列にシリアル化し、それぞれの長さを使用して現在の位置からのオフセットを計算できます。

serializeTree (Leaf nums)  = runPut (mapM_ putInt32 nums)
serializeTree (Node subtrees) = mconcat $ header : childBs
 where
  childBs = map serializeTree subtrees
  offsets = scanl (\acc bs -> acc+L.length bs) (fromIntegral $ 2*length subtrees) childBs
  header = runPut (mapM_ putInt32 $ init offsets)

もう 1 つのオプションは、ノードをシリアル化した後、戻って適切なデータでオフセット フィールドを書き直すことです。ツリーが大きい場合はこれが唯一のオプションかもしれませんが、これをサポートするシリアル化ライブラリを知りません。それには、正しい場所で作業しIOて移動する必要があります。seek

于 2011-03-01T20:39:32.143 に答える
2

これは、 sclvによって提案された 2 パス ソリューションの実装です。

import qualified Data.ByteString.Lazy as L
import Data.Binary.Put
import Data.Word
import Data.List (foldl')

data Tree = Node [Tree] | Leaf [Word32] deriving Show

makeTree 0 = Leaf $ replicate 100 0xdeadbeef
makeTree n = Node $ replicate 4 $ makeTree $ n-1

SizeTree は元の Tree を模倣しており、データは含まれていませんが、各ノードで対応する子のサイズを Tree に格納します。
メモリ内に SizeTree を保持する必要があるため、よりコンパクトにする価値があります (たとえば、Int を ubox 化された単語に置き換えます)。

data SizeTree
  = SNode {sz :: Int, chld :: [SizeTree]}
  | SLeaf {sz :: Int}
  deriving Show

メモリ内の SizeTree を使用すると、元の Tree をストリーミング方式でシリアル化できます。

putTree :: Tree -> SizeTree -> Put
putTree (Node xs) (SNode _ ys) = do
  putWord8 $ fromIntegral $ length xs          -- number of children
  mapM_ (putWord32be . fromIntegral . sz) ys   -- sizes of children
  sequence_ [putTree x y | (x,y) <- zip xs ys] -- children data
putTree (Leaf xs) _ = do
  putWord8 0                                   -- zero means 'leaf'
  putWord32be $ fromIntegral $ length xs       -- data length
  mapM_ putWord32be xs                         -- leaf data


mkSizeTree :: Tree -> SizeTree
mkSizeTree (Leaf xs) = SLeaf (1 + 4 + 4 * length xs)
mkSizeTree (Node xs) = SNode (1 + 4 * length xs + sum' (map sz ys)) ys
  where
    ys = map mkSizeTree xs
    sum' = foldl' (+) 0

GHC が 2 つのパスを 1 つにマージしないようにすることが重要です (その場合、メモリ内にツリーが保持されます)。ここでは、ツリーではなくツリージェネレーターを関数に供給することによって行われます。

serialize mkTree size = runPut $ putTree (mkTree size) treeSize
  where
    treeSize = mkSizeTree $ mkTree size

main = L.writeFile "dump.bin" $ serialize makeTree 10
于 2011-03-06T12:40:10.423 に答える
2

あなたが望むのは、明示的な 2 パス ソリューションです。1 つ目は、ツリーをサイズの注釈付きツリーに変換します。このパスはツリーを強制しますが、実際には、ノットを結ぶことにより、モナド機構をまったく使用せずに実行できます。2 番目のパスは単純な古い Put モナドであり、サイズの注釈が既に計算されていることを考えると、非常に簡単なはずです。

于 2011-03-02T16:00:23.013 に答える