StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Here is implementation of two pass solution proposed by <strong>sclv</strong>.</p> <pre><code>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 </code></pre> <p>SizeTree mimics original Tree, it does not contain data but at each node it stores size of corresponding child in Tree.<br> We need to have SizeTree in memory, so it worth to make it more compact (e.g. replace Ints with uboxed words).</p> <pre><code>data SizeTree = SNode {sz :: Int, chld :: [SizeTree]} | SLeaf {sz :: Int} deriving Show </code></pre> <p>With SizeTree in memory it is possible to serialize original Tree in streaming fashion.</p> <pre><code>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 </code></pre> <p>It is important to prevent GHC from merging two passes into one (in which case it will hold tree in memory). Here it is done by feeding not tree but tree generator to the function.</p> <pre><code>serialize mkTree size = runPut $ putTree (mkTree size) treeSize where treeSize = mkSizeTree $ mkTree size main = L.writeFile "dump.bin" $ serialize makeTree 10 </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload