collections

性能特性

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

列型の性能特性:

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

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

  検索 追加 削除 最小
不変        
HashSet/HashMap 実質定数 実質定数 実質定数 線形
TreeSet/TreeMap Log Log Log Log
BitSet 定数 線形 線形 実質定数1
ListMap 線形 線形 線形 線形
可変        
HashSet/HashMap 実質定数 実質定数 実質定数 線形
WeakHashMap 実質定数 実質定数 実質定数 線形
BitSet 定数 ならし定数 定数 実質定数1
TreeSet Log Log Log Log

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

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

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

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

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

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

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