標準コンテナの比較

(Redirected from ja/comparison_of_standard_containers)

これは、OCaml 言語あるいは OCaml 標準ライブラリで提供される、 異なるコンテナ型のラフな比較である。 それぞれのケースにおいて n はコンテナ内の有効な要素数である。

いくつかの操作については、 ビッグO(ランダウの記号) で現在の実装におけるコストを表示するが、 公式ドキュメントでは保証されていないことに注意。 希望的観測では悪くなることはないだろう。 ともかく、詳細が欲しければ各モジュールのドキュメントを読むこと。 また、対応する実装を読むのも有益だろう。

参考: 標準ライブラリの例

リスト: 変更されない単方向リスト

要素を加えると常に、要素xとリストtlからなる新しいリストが生成される。 tl は変更されないしコピーもされない。

最適な用途: IO、パターン・マッチング

あまり効率的でない: ランダムアクセス、索引付き要素

配列と文字列: 変更可能なベクトル

配列と文字列は非常に似ている。 文字列は文字の並び(バイト列)の格納に特化しており、 便利な構文を備えコンパクトに格納出来る。

最適な用途: サイズが既知である要素集合であり、 数値インデックスでアクセスし、その場変更するようなもの。 基本的な配列や文字列は固定長である。 伸縮する文字列には標準 Buffer 型(後述)が使える。

Set(集合)とMap(写像):　変更されないツリー

リストと同様、これらも変更されず、また部分木を共有するかもしれない。 旧バージョンの要素集合を保持するのにもってこいだ。

Set と Map は編集とメタプログラミングに特に有用であるが、 他の場合はハッシュ表のほうがたいてい適切だろう(後述)。

Hashtbl: 伸縮性のあるハッシュ表

OCaml のハッシュ表は変更可能なデータ構造であり、 (キー、データ)の組を一箇所に格納するのに向いている。

Buffer: 伸縮性のある文字列

バッファは一箇所にバイト列を蓄積する効率的な方法を提供する。 これらは変更可能である。

キュー(Queue)

OCaml のキューは変更可能な先入れ先出し (FIFO) データ構造である。

スタック(Stack)

OCaml のスタックは変更可能な後入れ先出し (LIFO) データ構造である。 変更可能であることを除けばリストとちょうど同じである。 すなわち、要素の追加は新しいスタックを生成するのではなく、 スタックに単に追加する。