純粋関数型では配列はつらいのかどうなのか

Haskell

純粋関数型言語では配列の扱いが若干厄介だ。
というのも、配列というものが本来mutableな使い方を想定するものだからだろう。
(定数オーダでテーブルを参照したいようなケースもあるが…)
参照透明を守る形で配列を実装する方法は大体以下の通り。
(計算量O(1)のものに限らない)

  • リストを使う

計算量O(n)なのがネック。

  • ツリー(など)を使う

計算量O(logn)。バランス重視。

  • 関数配列(?)

用語は適当…
更新のたびにその要素に対してその値を返す関数を付加していくような感じ。
計算量は書き込み回数に比例。

  • 毎回フルコピー

更新のたびにその要素のみが異なる配列を作成する。
read-onlyならばこれが最適だろうか。
読み込みO(1)、書き込みO(n) (ただし、nは配列の長さ)
多分HaskellのData.Arrayの実装はこれ。

  • 副作用によるもの

他の言語の配列と同様。
HaskellならIOモナドにせざるを得ないが、
Cleanなら線形論理でいけるだろう。
読み書きがO(1)で出来るが、これが良いとは思えない。


HaskellにはData.Arrayに純関数な配列が、
Data.Array.IOなどにmutableな配列が用意されている。
実際のところどれがどの程度の速度なのかよくわからないので、
ベンチマークしてみることにした。
作ったソースは http://fxp.infoseek.ne.jp/haskell/arrayBench.hs これ。
リストとArrayとIOUArrayの読み書き速度を計ってみた。
結果は以下の通り。

$ ./a.out
list read speed...
Read List     [0..1023] 1000000 times : 7.89100 sec.
Read List     [0.. 255] 1000000 times : 3.69600 sec.
Read List     [0.. 127] 1000000 times : 2.99400 sec.
Read List     [0..  15] 1000000 times : 2.46400 sec.
Read List     [0..   0] 1000000 times : 2.28299 sec.

array read speed...
Read Array    [0..1023] 1000000 times : 2.27300 sec.
Read Array    [0.. 255] 1000000 times : 2.32399 sec.
Read Array    [0.. 127] 1000000 times : 2.33300 sec.
Read Array    [0..  15] 1000000 times : 2.30299 sec.
Read Array    [0..   0] 1000000 times : 2.25300 sec.

iouarray read speed...
Read IOUArray [0..1023] 1000000 times : 2.56400 sec.
Read IOUArray [0.. 255] 1000000 times : 2.57399 sec.
Read IOUArray [0.. 127] 1000000 times : 2.56400 sec.
Read IOUArray [0..  15] 1000000 times : 2.57300 sec.
Read IOUArray [0..   0] 1000000 times : 2.49399 sec.

list write speed...
Write List    [0..1023] 1000000 times : 3.23400 sec.
Write List    [0.. 255] 1000000 times : 3.08499 sec.
Write List    [0.. 127] 1000000 times : 3.11399 sec.
Write List    [0..  15] 1000000 times : 2.84399 sec.
Write List    [0..   0] 1000000 times : 2.12400 sec.

array write speed...
Write Array   [0..1023] 1000000 times : 19.51800 sec.
Write Array   [0.. 255] 1000000 times : 6.51900 sec.
Write Array   [0.. 127] 1000000 times : 4.42600 sec.
Write Array   [0..  15] 1000000 times : 2.58400 sec.
Write Array   [0..   0] 1000000 times : 2.26299 sec.

iouarray write speed...
Write IOUArray  [0..1023] 1000000 times : 2.17300 sec.
Write IOUArray  [0.. 255] 1000000 times : 2.17399 sec.
Write IOUArray  [0.. 127] 1000000 times : 2.20299 sec.
Write IOUArray  [0..  15] 1000000 times : 2.20299 sec.
Write IOUArray  [0..   0] 1000000 times : 2.12300 sec.

配列サイズを1〜1024にして計測、計算量のオーダがわかるようにした。
それぞれ100万回読み書き。
2秒強ぐらいは乱数生成に使われていると思われる。
読み込みのみならやはりArrayが優秀か。
IOUArrayはIO呼び出しのオーバーヘッドがあると思ったが予想外に大きい。
オーダはArray,IOUArrayともに定数オーダのようである。


書き込み、listのパフォーマンスが明らかにおかしいが、
これはlistがnon-strictだからである。
めんどくさいので直さず…リストの処理速度は大体わかるし。
Arrayへの書き込みはやはり重たいようである。
でかいArrayへの書き込みは厳禁のようだ。
IOUArrayは読み込み時と打って変わってオーバーヘッドが少ない。
なぜだろう。


・結果
大きいデータを読み書きしたい場合はIOArrayを使わざるを得ないようである。
オーダがO(logn)で良いときはFiniteMapという選択肢もあるが。
値を読むだけのテーブルならArrayが最適。
リストは正直あまりパフォーマンスが良くないな。
ただ、non-strictなので問題によってはオーダがO(n)以下になりうる。

追記

Haskell 
main = do
  seed <- newStdGen
  timePrint "loop" 0 $ foo seed -- 適当に定義した時間計測関数
  where
    foo seed = seq d $ return () where
      d = foldl' (+) 0 $ take 1000000 $ randomRs (0,127) seed :: Int

このようなコードを書いて
配列アクセス以外のオーバーヘッドを計ってみたところ、

$ ./a.out
loop : 2.28299 sec.

このようになった。
これを考えるとData.Arrayはかなり高速だということがわかる。
100万回で数十ms、1回当たり数十nsなので、
PentiumM1Ghz上で実行していることを考えると数十クロックで
アクセスできていることになる。
反面IOUArrayは数百クロックかかっているようである。