最近、index (a.k.a. offset, cursor) accessが可能で、かつ高速なデータ構造に興味があり、Arrayを再訪している

ElmのArrayのindex accessパフォーマンスはどうなってるのだろうか。ベンチしてみた。

項目が多くなったので、結構時間がかかる

ソース: https://github.com/ymtszw/elm_array_bench

結果は下の方に画像付きで。まとめると、

Array では、要素数のオーダー増加に対してindex accessの速度低下は定数倍以内に収まっている。 O(1)

一方参考として挙げた List では、当然要素数増加に比例してきれいにindex accessが遅くなっている(要素数100倍でaccess速度は1/100)。 O(N)

Array.Hamt はindex accessに関してはビルトインの Array に対して顕著な優位性があるわけではない。

固定長のInitializeに関しては、 Array , Array.Hamt , List いずれも O(N) で、 List が一番速い=オーバーヘッドが少ない模様

この部分のbenchは1回うまく実行できたのだがなぜかその後crashするようになってしまった

とりあえず、高速index accessできるcontainerがほしければ、ElmのArrayは十分実用的に見える

Array.Hamt の優位性はこの部分にはないようなので、あえて入れなくてもよさそう

MacBookPro mid-2014, 2.2 GHz Intel Core i7