標準コンテナの比較

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

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

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

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

• 要素を「追加」 : O(1), cons 演算(::)
• 長さ : O(n), 関数 List.length
• i番目の要素のアクセス: O(i)
• 要素の探索 : O(n)

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

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

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

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

• 要素を「追加」: O(n)
• 長さ: O(1), 関数 Array.length
• i番目の要素のアクセス: O(1)
• 要素の探索: O(n)

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

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

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

• 要素を「追加」: O(log n)
• 要素の数を返す: O(n)
• 要素の探索 : O(log n)

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

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

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

• 要素の追加: O(1) - テーブルの初期サイズが含まれる要素の数よりも大きい場合; O(log n) - 初期値が n よりも小さい表に追加する場合の平均
• 要素の数を返す: O(1)
• 要素の探索 : O(1)

Buffer: 伸縮性のある文字列

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

• 文字を追加: O(1) - バッファが十分に大きい場合; O(log n) - バッファの初期サイズがバイト数 n よりも小さい場合の平均。
• k 文字分の文字列を追加: O(k * 「文字を追加」)
• 長さ: O(1)
• 要素iのアクセス: O(1)

キュー(Queue)

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

• 要素の追加: O(1)
• 要素の取り出し: O(1)
• 長さ: O(1)

スタック(Stack)

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

• 要素の追加: O(1)
• 要素の取り出し: O(1)
• 長さ: O(n)