等値性トップ文字列性能特性目次

性能特性

ここまでの説明で異なるコレクション型は異なる性能特性を持つ点を明らかにしてきました。 これは他の型ではなくあるコクション型を選択する主な理由となります。 コレクションの主要な演算に対する性能特性は以下の2つの 表に要約できます。

列型の性能特性
head tail apply 更新 先頭に追加 末尾に追加 insert
不変
List定数定数線形線形定数線形-
Stream定数定数線形線形定数線形-
Vector実質定数実質定数実質定数実質定数実質定数実質定数-
Stack定数定数線形線形定数線形-
Queue償却定数償却定数線形線形線形定数-
Range定数定数定数----
String定数線形定数線形線形線形-
可変
ArrayBuffer定数線形定数定数線形償却定数線形
ListBuffer定数線形線形線形定数定数線形
StringBuilder定数線形定数定数線形償却定数線形
MutableList定数線形線形線形定数定数線形
Queue定数線形線形線形定数定数線形
ArraySeq定数線形定数定数---
Stack定数線形線形線形定数線形線形
ArrayStack定数線形定数定数償却定数線形線形
Array定数線形定数定数---
集合とマップ型の性能特性
参照 add remove min
不変
HashSet/HashMap実質定数実質定数実質定数線形
TreeSet/TreeMap対数対数対数対数
BitSet定数線形線形実質定数3
ListMap線形線形線形線形
可変
HashSet/HashMap実質定数実質定数実質定数線形
WeakHashMap実質定数実質定数実質定数線形
BitSet定数償却定数定数実質定数4

これらの2つの表の中身は次のような意味です:

定数
演算は(高速な)定数時間かかります。
実質定数
演算は実質的に定数時間かかりますが、ベクタの長さやハッシュキーなどの仮定に依存します。
償却定数
演算は償却定数時間かかります。演算の呼び出しはより長い時間かかる場合がありますが、大量に呼び出されれば演算1回あたりは平均で定数時間しかかかりません。
対数
演算はコレクションの大きさの対数に比例する時間かかります。
線形
演算はコレクションの大きさに比例する時間かかります。
-
演算はサポートされません。

最初の表では列型—不変なものも可変なものも—を以下の演算で処理しています:

head
列の最初の要素を選択する。
tail
最初の要素以外からなる新しい列を作成する。
apply
添字付け
更新
不変な列に対しては(updatedによる)関数的更新で、可変な列に対しては(updateによる)副作用のある更新。
先頭への追加
列の先頭に要素を追加する。不変な列に対してはこれは新しい列を作成する。可変な列に対しては既存の列を変更する。
末尾への追加
列の末尾に要素を追加する。不変な列に対してはこれは新しい列を作成する。可変な列に対しては既存の列を変更する。
insert
列に任意の位置に要素を追加する。これは可変な列にのみ直接サポートされる。

2番目の表では可変および不変な集合とマップを以下の演算で処理しています:

参照
集合に要素が含まれるか調べる、またはキーに関連付けられた値を選択する。
add
集合に値、またはマップにキーと値のペアを追加する。
remove
要素から値、またはマップからキーを削除する。
min
集合の最小の値、またはマップの最小のキー。

続いては: 等値性

等値性トップ文字列性能特性目次