Collections

性能特性

Info: JavaScript is currently disabled, code tabs will still work, but preferences will not be remembered.

これまでの説明で異なるコレクションが異なる性能特性 (performance characteristics) を持つことが分かった。性能特性はコレクション型を比較する第一の基準としてよく使われる。以下の 2つの表にコレクションの主な演算の性能特性をまとめた。

列型の性能特性:

	head	tail	apply	更新	先頭に追加	最後に追加	挿入
不変
`List`	定数	定数	線形	線形	定数	線形	-
`Stream`	定数	定数	線形	線形	定数	線形	-
`Vector`	実質定数	実質定数	実質定数	実質定数	実質定数	実質定数	-
`Stack`	定数	定数	線形	線形	定数	線形	線形
`Queue`	ならし定数	ならし定数	線形	線形	線形	定数	-
`Range`	定数	定数	定数	-	-	-	-
`String`	定数	線形	定数	線形	線形	線形	-
可変
`ArrayBuffer`	定数	線形	定数	定数	線形	ならし定数	線形
`ListBuffer`	定数	線形	線形	線形	定数	定数	線形
`StringBuilder`	定数	線形	定数	定数	線形	ならし定数	線形
`MutableList`	定数	線形	線形	線形	定数	定数	線形
`Queue`	定数	線形	線形	線形	定数	定数	線形
`ArraySeq`	定数	線形	定数	定数	-	-	-
`Stack`	定数	線形	線形	線形	定数	線形	線形
`ArrayStack`	定数	線形	定数	定数	ならし定数	線形	線形
`Array`	定数	線形	定数	定数	-	-	-

集合とマップ型の性能特性:

脚注: ¹ ビットが密にパックされていることを前提にしている。

表の値を以下に説明する:


定数	演算は (高速な) 定数時間で完了する。
実質定数	演算は実質定数時間で完了するが、ベクトルの最大長やハッシュキーの分布など何らかの前提に依存する。
ならし定数	演算は「ならし定数時間」で完了する。演算の呼び出しの中には定数時間よりも長くかかるものもあるが、多くの演算の実行時間の平均を取った場合定数時間となる。
Log	演算はコレクションのサイズの対数に比例した時間で完了する。
線形	演算は線形時間、つまりコレクションのサイズに比例した時間で完了する。
-	演算はサポートされていない。

最初の表は、不変と可変両方の列型の以下の演算の性能特性をまとめる:


head	列の最初の要素を選択する。
tail	最初の要素以外の全ての要素から成る新たな列を生成する。
apply	添字によるアクセス。
更新	不変列のときは (`updated` による) 関数型の更新、可変列のときは (`update` による) 副作用としての上書き更新。
先頭に追加	列の先頭への要素の追加。不変列のときは新たな列を生成する。可変列のときは現在の列を上書きする。
最後に追加	列の最後に要素を追加する。不変列のときは新たな列を生成する。可変列のときは現在の列を上書きする。
挿入	要素を列の任意の位置に挿入する。この演算は可変列にのみサポートされている。

次の表は、不変と可変両方の集合とマップの以下の演算の性能特性をまとめる:


検索	要素が集合に含まれるかを調べるか、マップからキーに関連付けられた値を選択する。
追加	集合に新たな要素を追加するか、マップにキー/値ペアを追加する。
削除	集合から要素を削除するか、マップからキーを削除する。
最小	集合の最小要素かマップの最小キー。