如何将树数据结构保存到Haskell中的二进制文件
我试图用Haskell将简单(但非常大)的树结构保存到二进制文件中。结构看起来是这样的:如何将树数据结构保存到Haskell中的二进制文件
-- For simplicity assume each Node has only 4 childs data Tree = Node [Tree] | Leaf [Int]这里是我所需要的数据看磁盘上:
- 每个节点有4个32位偏移到它的孩子,然后按照孩子的开始。
- 我不太在乎叶子,假设它只有n个连续的32位数字。
- 对于实践目的,我需要一些节点标签或其他附加数据 但现在我不关心那么多。
对我来说Haskellers编写二进制文件时的首选是Data.Binary.Put库。但是,由于我在第一号子弹中遇到了问题。特别是,当我要将节点写入文件时,要写下子偏移量,我需要知道当前的偏移量和每个子项的大小。
这不是Data.Binary.Put提供的东西,所以我认为这必须是Monad变形金刚的完美应用。但即使听起来很酷且功能强大,但迄今为止,我还没有采用这种方法取得成功。
我问了另外两个问题,我认为这会帮助我解决问题here和here。我必须说,每次我收到非常好的答案,都会帮助我进一步取得进展,但不幸的是,我仍然无法解决整个问题。
Here是我到目前为止,它仍然泄漏太多的内存是实用的。
我很想拥有使用这种功能的方法的解决方案,但也会感激任何其他解决方案。
这里是由sclv提出的两通解决方案的实现。
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模仿原始树,它不包含数据,但它在每个节点存储树中相应子节点的大小。
我们需要在内存中使用SizeTree,所以值得使它更紧凑(例如用uboxed words替换Ints)。
data SizeTree
= SNode {sz :: Int, chld :: [SizeTree]}
| SLeaf {sz :: Int}
deriving Show
SizeTree在内存中可以以流媒体的方式序列化原始树。
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将两次合并合并成一次是很重要的(在这种情况下,它将把树保存在内存中)。 这里它是通过向函数提供不是树而是树生成器来完成的。
serialize mkTree size = runPut $ putTree (mkTree size) treeSize
where
treeSize = mkSizeTree $ mkTree size
main = L.writeFile "dump.bin" $ serialize makeTree 10
我会考虑两种基本方法。如果整个序列化结构很容易放入内存,则可以将每个节点序列化为一个懒惰的字节串,并使用每个节点的长度来计算当前位置的偏移量。
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)
另一种选择是,序列化节点之后,回去重新写有适当的数据偏移字段。如果树很大,这可能是唯一的选择,但我不知道支持这个的序列化库。这将涉及在IO
和seek
工作到正确的位置。
我想你想要的是一个明确的双通解决方案。第一个将您的树转换为大小注释树。这通过强制树,但事实上,可以完成,没有任何monadic机器通过绑结。第二遍是在朴素的旧Put单元中,并且考虑到大小注释已经被计算出来,应该是非常简单的。
这将工作,但我认为我的解决方案会更有效率的内存。这是因为我的方法会允许在序列化后收集每个子树,并且字节串序列化应该比实际的树小得多。 – 2011-03-02 22:47:06
@约翰 - 你可能是对的。你的解决方案是真正的一次通过,但只是不完全流式传输。 – sclv 2011-03-02 22:48:44
下面是使用Builder一实现中,这是“二进制”包的一部分。我没有正确地分析它,但根据“顶部”它立即分配108兆字节,然后挂在其余的执行。
请注意,我还没有尝试读取数据,因此在我的大小和偏移量计算中可能存在潜在的错误。
-- 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
+1,生成生成器的好方法 – 2011-03-07 05:58:50
这棵树有多大,你想象的文件大小是多少?这个答案决定了你是否可以使用任何类型的put类型结构,或者如果你需要一些涉及单遍遍历但修改已经写好的结构部分的东西...... – sclv 2011-03-01 18:36:43
二进制序列化通常需要知道尺寸要写入的数据(例如列表以长度为前缀)。你可以住文本序列化(可能是更大的文件)?如果不能通过写入中间文件并将它们拼接在一起(可怕但可能)来做一些技巧。 同样在你的测试代码中,输入是合成的 - 如果你的真实数据不是合成的,你可能会在内存中使用它,所以普通的二进制序列化不会强制任何不在堆中的东西。 – 2011-03-01 18:40:30
@sclv,上面提到的“我到目前为止所拥有的东西”的链接指向我一直在研究一段时间的更大程序的摘录。在原始程序中,我读取了一个具有相似结构的二进制文件,对其进行转换(主要是为了节点上没有太多的子节点),然后将其保存回去。源文件的大小介于50MB到200MB之间,所以我认为目标文件的大小相似。 – 2011-03-01 22:23:48