データ構造列伝

リスト
- セルオートマトン
Set
- 速いnub
Heap
- トップ3
Seq
- 例 TBD
- fingertree
配列(Boxed Vector)
- 例
Map
Skew binary random access list
- Leonardo random access list

Haskellの世界にはたくさんのデータ構造があり、魅力の一つであるとも言える。とは言え、どれを使えばいいのかは悩みの種。Haskellで実装されている様々なデータ構造の特徴と使い方を紹介する。

rule110 :: Bool -> Bool -> Bool -> Bool
rule110 False a b = a || b
rule110 True a b = a /= b

automata :: (Bool -> Bool -> Bool -> Bool) -> [Bool] -> [Bool]
automata f xs = go ([False, False] ++ xs ++ [False, False]) where
  go (x : ys@(y : z : _)) = f x y z : go ys
  go _ = []

main = putStr $ unlines
  $ map (map (\b -> if b then '.' else ' '))
  $ take 80
  $ iterate (automata rule110) [True]

Set

難易度: ☆☆

Setはその名の通り集合を表すデータ構造で、順序と重複の概念がない。要素を追加・削除するinsertとdelete、要素の存在を確かめるmemberが基本操作となる。

insert :: Ord a => a -> Set a -> Set a
delete :: Ord a => a -> Set a -> Set a
member :: Ord a => a -> Set a -> Bool

もちろん集合演算もあり、小さい方をmとして計算量はO(m*log(n/m + 1))となかなか優秀だ。

union :: Ord a => Set a -> Set a -> Set a
difference :: Ord a => Set a -> Set a -> Set a
intersection :: Ord a => Set a -> Set a -> Set a

必要な場面はそこまで多くはないが、要素の有無を確かめたり、集合の演算を使いたい時に気軽に持ち出せる。

利点

各種操作が速く使いやすい

欠点

要素の比較演算にパフォーマンスが左右される

速いnub

Setを利用するとリストの重複をData.List.nubよりも効率よく取り除ける。

import qualified Data.Set as Set

ordNub :: Ord a => [a] -> [a]
ordNub xs = foldr (\x k s -> if Set.member x s
  then k s
  else x : k (Set.insert x s))
  (const []) xs Set.empty

Heap

難易度: ☆

heapsのData.Heapは、Bootstrapped skew binomial heapの実装である。Setと違い、重複した要素を持つことができる。

insert :: a -> Heap a -> Heap a
viewMin :: Ord a => Heap a -> Maybe (a, Heap a)

挿入だけでなく、結合(mappend)も定数時間なのが面白い、クセの少ない構造である。

タプルとよく似たEntry型が定義されており、大小比較がpriorityフィールドに基づいて行われる。優先度付きキューとして使うときに有用だ。

data Entry p a = Entry { priority :: p, payload :: a }

利点

優秀なヒープの実装である

欠点

挿入・取り出し・結合以外の操作はやや苦手

トップ3

標準入力から受け取った整数のうち、トップ3を表示する。

insertN :: Ord a => Int -> a -> H.Heap a -> H.Heap a
insertN n a h = case H.insert a h of
  h' | H.size h' <= n -> h'
     | otherwise -> H.deleteMin h'

main = interact $ unlines . map show . toList
  . foldl' (flip $ insertN 3) H.empty
  . map (read :: String -> Int) . lines

Seq

難易度: ☆☆☆

containersのData.Sequenceモジュールは2-3 Finger treeというデータ構造を実装している。

要素の追加・削除を含め、両端へのアクセスはO(1)、任意の要素でもO(log n)と、カタログスペックは優秀だ。しかし、リストと比べると、オーダーは同じでも定数倍の違いは大きく、実は使いこなすのが難しい上級者向けの構造だ。

<|演算子で左に要素を追加する。

(<|) :: a -> Seq a -> Seq a

|>演算子で右に要素を追加する。

(|>) :: Seq a -> a -> Seq a

左端の要素はviewlで取り出す。

viewl :: Seq a -> ViewL a
data ViewL = EmptyL | a :< (Seq a)

右端の要素はviewrで取り出す。

viewr :: Seq a -> ViewL a
data ViewL = EmptyR | Seq a :> a

結合(mappend)もsplitAtも対数時間である。

splitAt :: Int -> Seq a -> (Seq a, Seq a) -- O(log(min(i, n - i)))

両端のアクセスが定数時間であるという性質を生かし、手軽なキューとしてしばしば使われる。永続性を生かしつつ様々な操作をバランスよく組み合わせたいという状況に刺さることもある。

利点

操作が充実しており、オーダーも良い
要素数が多いほど時間計算量の面で有利

欠点

利点を生かしにくい

例 TBD

fingertree

テキストエディタyiやパーサーコンビネータtrifectaでは、亜種のfingertree を文字列の表現に活用している。新たな型変数vに位置を、要素としてバイト列を当てはめることで、柔軟かつ高速な文字列の操作を実現できる。

配列(Boxed Vector)

難易度: ☆☆

vectorパッケージでは、一次元の配列Vectorが定義されている。配列なので、要素へのアクセス(index)が定数時間である。要素数が変わらないような演算、例えばmapやzipWithなどを多用するときに適している。

要素を更新したいときはaccumでまとめて更新するとお得だ。

accum :: (a -> b -> a)
  -> Vector a
  -> [(Int, b)]
  -> Vector a

個々の要素の更新は得意ではなく、それが必要な場合はMVectorというミュータブルな表現に一度変換する必要がある。基本は簡単だが、性能を活かそうとなるとややテクニカルな側面がある。

Data.Vector.Unboxed、Data.Vector.Storableという変種もあり、要素の型に制約がある代わり、より高いメモリ効率とパフォーマンスを持つ。Data.Vector.StorableはFFIを使う際のマストアイテムだ。

利点

定数時間で要素にアクセスできる
融合変換が充実しており、高速なコードになりやすい
メモリ効率が良い

欠点

　consのような構造が変わる操作は、線形時間を使って丸々作り直さないといけない チューニングが難しい

例

任意の範囲について、平均を定数時間で得られる表現を作る。

import qualified Data.Vector.Unboxed as U

newtype Integrated a = Integrated (U.Vector a) deriving Show

integrate :: (Num a, U.Unbox a) => [a] -> Integrated a
integrate = Integrated . U.postscanl' (+) 0 . U.fromList

average :: (Fractional a, U.Unbox a) => Integrated a -> Int -> Int -> a
average (Integrated v) i j = (v U.! j - v U.! i) / fromIntegral (j - i + 1)

Map

難易度: ☆☆

import qualified Data.Map.Stric as M
import Data.Map.Strict ((!))
import qualified Data.List as L

ns = M.fromList $ zip [1..100] fact
  where fact = tail $ L.scanl (*) 1 [1..]

ms = M.insert 1 1 ns

ls = M.delete 1 ms

main = print $ ls ! 10

containersパッケージに値を正格評価で保持するのData.Map.Strictや値を非正格に保持するData.Map.Lazyが定義されている。挿入と削除、検索が純粋なので配列の代わりに使ったりもできる。似たようなものとしてキーがIntの場合のみ利用できるIntMapがある。

利点

挿入、削除、検索がO(log N)で行える。
操作が純粋である。

欠点

配列等と比べるとメモリ効率や操作のオーダが劣る。

Skew binary random access list

難易度: ☆☆

数列系データ構造(@fumievalの勝手な命名)の一つ。2のべき乗のような特定の数列は、 要素を組み合わせると任意の自然数を表現できる という性質を持つ。これを応用し、 数列に対応する要素数を持つデータ構造を組み合わせ、任意の個数を格納できるようにした のが数列系データ構造である。

このデータ構造はSkew binaryと呼ばれる特殊な記数法に基づいている。位は1, 3, 7, 15, n, 2n + 1, …という数列に対応しており、以下を見れば規則性がわかりやすい。数字が二つ並んでいると、次に繰り上がるのがわかる。

数字nを大きさnの木にし、足し算の代わりにリストで木を集めることで晴れてデータ構造になる。繰り上がりが高々一回 であるという性質を、 定数時間のcons に対応させるのがこのデータ構造のポイントである。

data Tree a = Leaf a | Bin a (Tree a) (Tree a)

type List a = [(Int, Tree a)] -- 高速化のため、要素数をあらかじめ記録しておく

cons :: a -> List a -> List a
cons a ((m, l) : (n, r) : xs)
  | m == n = (2 * m + 1, Bin a l r) -- 2n + 1個の木に繰り上がる
cons a xs = (1, Leaf a) : xs

uncons :: List a -> Maybe (a, List a)
uncons [] = Nothing
uncons ((_, Leaf a) : xs) = Just (a, xs)
uncons ((n, Bin a l r) : xs) = let h = n `div` 2 in Just (a, (h, l) : (h, r) : xs)

dropはやや複雑だが、このデータ構造の利点を最もよく活かせる操作である。DPS(drop per second)が指数関数的に増加しながら木を削ぎ落とすので、対数時間で完了する。

drop :: Int -> List a -> List a
drop 0 xs = xs
drop n ((m, t) : xs)
  | n >= m = drop (n - m) xs
  | otherwise = dropTree n m t xs
  where
    dropTree 0 m t xs = (m, t) : xs
    dropTree _ _ (Leaf _) xs = xs
    dropTree n m (Bin _ l r) xs
      | n > h = dropTree (n - h - 1) h r xs
      | otherwise = dropTree (n - 1) h l ((h, r) : xs)
      where
        h = m `div` 2
drop _ [] = []

遅延評価によるストリームとしての表現力を失った代わりに、対数時間の操作を手に入れたデータ構造である。de Bruijn indexやTVarへの格納など、永続性とランダムアクセスの両立が求められる場面において、その実力を発揮できるだろう。連鎖こそしないが、落ち物パズル的な振る舞いの面白さも見逃せない。

Leonardo random access list

フィボナッチ数列の亜種であるレオナルド数列をベースに構築することもできる。木は平衡ではなく右寄りになるが、かえって分岐予測やキャッシュとのシナジーが生まれ、Skew binary版よりも速くなるらしい。

Part 1: Leonardo Random Access Lists

データ構造列伝

リスト

セルオートマトン

Set

速いnub

Heap

トップ3

Seq

例 TBD

fingertree

配列(Boxed Vector)

例

Map

Skew binary random access list

Leonardo random access list