株式会社エス・スリー・フォー

A.2 使用時間とメモリ量

この節では、各種のコレクションおよびコレクション群で一般的な操作を行うのに必要な時間とメモリ量についての分析と比較を行います。この情報は、操作、その操作に必要な時間とメモリ量を示す表にまとめられています。注釈は、表の一番下に記されています。表で使用されている省略記号の意味は、各ページの下に示されています。

この分析を読む場合には、各種のプロセッサ、オペレーティングシステム、コンパイルの最適化、およびその他の要素が記載されている値に影響を与えることに留意してください。これらの表の目的は、「その他すべての条件が同一である」と仮定した場合に、各種のコレクションがどのように動作するかを比較することにあります。アルゴリズムの複雑さについては、Knuth、Sedgewick およびその他の参考文献を参照してください。

Tools.h++コレクションの多くは基本的に同じ様なインタフェースを持つため、別のコレクションを選択するとプログラムにどのような影響があるかを簡単に試してみることができます。

次の表では、

  • N は、コレクションの項目数を表わします。
  • M は、コレクションの現在のサイズを表わします。
  • t は、格納される項目あるいはポインタのサイズを表わします。
  • i は、整数を表わします。
  • p はポインタのサイズを表わします。
  • C は定数を表わします。
  • 各ポインタの間接参照、コピー、破壊、メモリ領域の割り当て、比較に必要な時間は等しいと見なします。
  • コンテナのオーバーヘッドは、2 項の使用メモリ量です。左項は空のコンテナのサイズで、右項はN 個の項目のために追加されたメモリ量を示します。
  • 必要なメモリ量は、挿入と削除の両方を意味しています。「(回復済み)」と記されている必要なメモリ量は、ヒープ領域に戻されたメモリ量を指します。

メモリの割り当てについて記載されている場合は、常に、メモリの割り当て方式は実装によって極端に違うことに留意してください。ただし、一般的に、システム呼び出しに変換されるヒープ領域の割り当て (または解放) はその他の定数量に比べて、よりメモリ量を必要とします。「平均化」と記されたメモリ量は、コレクションの寿命に渡って平均化されています。個々の動作にかかるメモリ量は、平均化された値よりも高いあるいは低い場合があります。

表で使用されている各記号

N
項目数
M
コレクションの サイズ
t
項目の サイズ
i
整数のサイズ
p
ポインタのサイズ
C
定数値

A.2.1 RWGVector、RWGBitVec、RWTBitVec<size>、RWTPtrVector と RWTValVector

操作
必要時間
必要なメモリ量
検索 (標準項目)
N/2
0
項目の変更/置換
C
0
コンテナオーバーヘッド
-
(Mt+2i) + 0
注釈
T の配列の周りを包む (バイトの /ddy をddく)
指定されたときだけサイズ変更する

A.2.2 一重リンクリスト

操作
必要時間
必要なメモリ量
両端のどちらで挿入
C
t + p
中央部に挿入
C (反復子がその位置に配置されていると仮定)
t + p
検索 (標準項目)
N/2
0
項目の変更/置換
C
0
最初の項目を削除
C
t + p (回復済み)
最後の項目を削除
C
t + p (回復済み)
中央部の項目を削除
C (反復子がその位置に配置されていると仮定)
t + p (回復済み)
コンテナオーバーヘッド
-
(2p+i) + N(t+p)
注釈
各挿入ごとに割り当てる。反復子は前進のみ
各項目により異なる。二重リンクリストより少ない

A.2.3 二重リンクリスト

操作
必要時間
必要なメモリ量
両端のどちらで挿入
C
t + 2p
中央部に挿入
C (反復子がその位置に配置されていると仮定)
t + 2p
検索 (標準項目)
N/2
0
項目の変更/置換
C
0
最初の項目を削除
C
t + 2p (回復済み)
最後の項目を削除
C
t + 2p (回復済み)
中央部の項目を削除
C (反復子がその位置に配置されていると仮定)
t + 2p (回復済み)
コンテナオーバーヘッド
-
(2p+i) + N(t+2p)
注釈
各挿入ごとに割り当てる。どちらの方向にも反復する
各項目ごとにより異なる。Slist より多くなる

A.2.4 順序付きのベクトル

操作
必要時間
必要なメモリ量
一端で挿入
C (平均化)
t (平均化)
中央部に挿入
N/2
t (平均化)
検索 (標準項目)
N/2
0
項目の変更/置換
C
0
最初の項目を削除
N
0
最後の項目を削除
C
0
中央部の項目を削除
N/2
0
コンテナオーバーヘッド
-
(Mt+ p + 2i) + 0
注釈
反復子なし (size_t インデックスを使用)。ベクトルが大きくなったときだけ割り当てる
多くの項目を一度に追加するために必要に応じてメモリ量を追加して拡張する。resize() によってのみ縮小する

A.2.5 ソート済みのベクトル

操作
必要時間
必要なメモリ量
挿入
logN + N/2 (平均)
t (平均化)
検索 (標準項目)
logN
0
項目の変更/置換
N
0
最初の項目を削除
N
0
最後の項目を削除
C
0
中央部の項目を削除
N/2
0
コンテナオーバーヘッド
-
(Mt + p + 2i) + 0
注釈
ソート順を基準に挿入が行われる。反復子なし (size_t インデックスを使用)。ソート順を保つために、置換は削除そして追加の順で行う必要がある。ベクトルが大きくなったときだけ割り当てる
多くの項目を一度に追加するために必要に応じてメモリ量を追加して拡張する。resize() によってのみ縮小する

A.2.6 スタックと待ち行列

操作
必要時間
必要なメモリ量
一端で挿入
C
t + p
削除 (ポップ)
C
t + p (回復済み)
コンテナオーバーヘッド
-
(2p+i) + N(t+p)
注釈
一重リンクリストとして実装される。テンプレート化されているものでは、コンテナを選択でき、その選択により、必要な時間とメモリ量が異なる。
-

A.2.7 両頭行

操作
必要時間
必要なメモリ量
一端で挿入
C
t (平均化)
検索 (標準項目)
N/2
0
項目の変更/置換
C
0
最初の項目を削除
C
t (平均化、回復済み)
最後の項目を削除
C
t (平均化、回復済み)
中央部の項目を削除
N/2
t (平均化、回復済み)
コンテナオーバーヘッド
-
(Mt + p + i) + 0
注釈
配列で循環待ち行列として実装されている。ベクトルが大きくなったときだけ割り当てる。
各増加分だけ余分にキャッシュして、必要に応じて拡張または縮小する。

A.2.8 バイナリツリー

操作
必要時間
必要なメモリ量
挿入
logN+C
2p+t
検索 (標準項目)
logN
0
項目の変更/置換
2(logN + C)
0
最初の項目を削除
logN + C
2p+t (回復済み)
最後の項目を削除
logN + C
2p+t (回復済み)
中央部の項目を削除
logN + C
2p+t (回復済み)
コンテナオーバーヘッド
-
(p+i) + N(2p+t)
注釈
ソート順を基準に挿入が行われる各挿入ごとに割り当てる。ソート順を保つために、置換は削除そして追加の順で行う必要がある。ツリーの均衡は自動的には保たれない。上記の数値は均衡のとれたツリーを仮定している。
1 つの項目につき二重リンクリストと同じ時間がかかる。

A.2.9 (多重)マップと(多重)セット群

操作
必要時間
必要なメモリ量
挿入
logN+C
2p+t
検索 (標準項目)
logN
0
項目の変更/置換
2(logN+C) または C
0
最初の項目を削除
logN (最悪の場合)
2p+t (回復済み)
最後の項目を削除
logN (最悪の場合)
2p+t (回復済み)
中央部の項目を削除
logN (最悪の場合)
2p+t (回復済み)
コンテナオーバーヘッド
挿入または削除ごとに均衡をとる可能性がある。
(3p+i) + N(2p+t)
注釈
ソート順を基準に挿入が行われる各挿入ごとに割り当てる。セットの置換は、削除してから挿入する必要がある。マップの場合、値はその位置にコピーされる。均衡のとれた (レッド－ブラック) ツリーとして実装されている。
-

A.2.10 RWBTree, RWBTreeDictionary

RWBTreeOnDisk と RWBTreeDictionary は同様に複雑であるが、RWBTreeOnDisk では「リンクノードをたどる」ことが「ディスクシーク」になるため、ずっと時間がかかり、主メモリの場合よりもずっとディスク容量が必要になる。

操作
必要時間
必要なメモリ量
挿入
logN+C
2p + t + 小さい(完全に平均化されている)
検索 (標準項目)
logN
0
項目の変更/置換
2logN+2 または C
0
最初の項目を削除
2logN(log2(ORDER))+C (最悪の場合)
2p+t (回復済み)
最後の項目を削除
2logN(log2(ORDER))+C (最悪の場合)
2p+t (回復済み)
中央部の項目を削除
2logN(log2(ORDER))+C (最悪の場合)
2p+t (回復済み)
コンテナオーバーヘッド
挿入または削除ごとに均衡をとる可能性がある。ただし、これは、均衡がとれたバイナリツリーではそれほど頻繁には行われない
ノードがどのように完全にパックされるかに依存する。それぞれのノードは ORDER(2p+t+1)+i 必要とし、ノード数は 2N/ORDER より多くなく、min(N/ORDER,1) より少なくない。既にソートされたアイテムを挿入すると、サイズは極大化する傾向にある。Sedgewick によると、ランダムなデータでは、サイズは 1.44 N/ORDER
に近くなる。
注釈
ソート順を基準に挿入が行われる。対数は、B-ツリーの広がりである近似の底 ORDER を持つ(実際の底は、B-ツリーに読み込むものにより、 ORDER と 2ORDER の間になる)。B-ツリーでの置換は、削除してから挿入する必要がある。btreedictionary の場合、値はその位置にコピーされる。
-

A.2.11 ハッシュベースのコレクション

RWSet と RWIdentitySet は、名前に「ハッシュ」が付くコレクションと同様である。

操作
必要時間
必要なメモリ量
挿入
C
p+t
検索 (標準項目)
C
0
項目の変更/置換
2C
0
削除
C
p+t (回復済み)
コンテナオーバーヘッド
-
((M+2)p+i) + N(p+t) (1) (Mp+(2p+i)b_used) + N(p+t) (2) 1: 規格に準拠しているバージョン 2: バージョン 6.1 のハッシュコレクションの場合、b_used は、使用済みのスロット数である。
注釈
挿入はハッシュ関数を基準に行われる。項目がハッシュスロットに散在している場合は一定の時間がかかる。最悪の場合は、スロットごとの項目数に比例する。辞書またはマップでの置換は、新しい値はその位置にコピーされる。それ以外の場合は、削除してから挿入を行う必要がある。
自動的にサイズ変更は行われない。項目数をスロット数の半分から 2 倍にすることを勧める。
επιστημη 2006-04-10