Previous Next Contents Index


Copyright 1999 Rogue Wave Software
Copyright 1999 Sun Microsystems, Inc.

コレクションの選択

A

Tools.h++ には、多数のコレクションクラスがあります。ユーザーのコードでどれを選択するかを決める場合、多すぎると思われるほどのクラスがあります。この節では、特定のプログラミング作業に最も適したコレクションを選択するうえで役立つ指針と情報を示します。

ユーザーの必要性に最適なコレクションを選択する作業は容易ではありません。まず、ユーザーのコレクション内のデータについて考慮する必要があります。コレクションでデータを順番に格納する必要があるか、重複するデータがあるか、またコレクションでのデータの検索または挿入方法はどうするかを考えます。この付録の前半「Tools.h++ コレクションクラスの選択」では、データに関する特定の質問を考え、その答えを通じて、ユーザーのデータ要件に最適なコレクションを即座に選別できるようにする決定ツリー図を示します。この決定ツリーの前半では、ツリー内に示される質問を説明し、ポインタまたは値にもとづくコレクションのどちらを選択するか、順序付きコレクションをいつ使用するか、ディスクにもとづくアクセスで何を使用するかなどの問題に対応する追加の選択基準をいくつか示します。

この付録の後半では、コレクションとコレクションファミリが、挿入、検索、削除などの共通の操作を実行するために必要とする時間とメモリーの違いを大まかに比較します。

Tools.h++ コレクションクラスの選択

決定ツリー図には、コレクションに格納する予定のデータに関する質問が示されています。このツリーを調べることによって、ユーザーのデータとプログラミングプロジェクトに、どの Tools.h++ コレクションクラスが最も適しているかを即座に判断することができます。

決定ツリーの使用方法

決定ツリーに示される質問は短いので、図を簡単に読み取ることができます。次の質問は、決定ツリーに示された質問を詳しく説明したものです。

  1. コレクション内のデータの順序が意味を持つかどうか。コレクションによっては、コレクション内のデータの位置を指定することができます。たとえば、配列やベクトル、リンクリストはデータを順番に表します。特定の順序、または数値インデックスにもとづいてデータにアクセスする必要がある場合、順序は意味を持ちます。

  2. 重複するエントリが許容されるかどうか。コレクションによっては、すでにコレクション内にある項目と等しい項目を挿入することができないもの (通常は「セット」と呼ばれる) があります。それ以外のコレクションでは重複が認められており、複数の一致する項目を保持するための各種の方法があります。Tools.h++ コレクションは、重複を検査するための機構と重複を保持するための機能の両方を備えています。

  3. 順序が本質的に (データの内容によって) 決定されるかまたは外部的に決定されるか。コレクション内のデータがその挿入方法によって制御される場合、その順序は外部的に決定されることになります。たとえば、ベクトルやリンクリストは外部的に順序付けられます。データが、コレクションによって使用されるアルゴリズムで決定された位置に保存される場合、その順序付けは本質的なものです。たとえば、ソートされたベクトルやバランスツリーは本質的な順序を持ちます。

  4. データが外部キーによってアクセスされるかどうか。値と同じではないキーにもとづいて値にアクセスする場合、そのデータは外部キーによってアクセスされることになります。たとえば、「電話リスト」は、電話番号の形式のデータを、名前の形式をとるキーに関連付けるものです。逆に、委員会のメンバーのリストは、単純に名前の形式をとるデータの集合です。情報を入手するためにキーは必要ありません。

  5. データが数値インデックスによってアクセスされるかどうか。配列またはベクトルに保存されたオブジェクトは、数値インデックスによってアクセスされます。たとえば、位置 12 にあるオブジェクトは、数値インデックス「12」を使用してアクセスして見つけます。

  6. データが「自分自身との比較」によってアクセスされるかどうか。明示的なインデックスまたは明示的なキーのどちらによっても保存されていないデータは、検索したい内容と含まれる内容の間の一致を探すことによって見つけることができます。4 で示した委員会のメンバーのリストは、この種のデータの例です。セットやバッグは、自分自身との比較によってアクセスされるコレクションの例です。

    データが自分自身との比較によってアクセスされる場合、どのような種類の一致が使用されるかも知る必要があります。一致は、あるオブジェクトを別のオブジェクトと直接比較する等値性にもとづくか、またはオブジェクトアドレスを比較する同一性にもとづきます。

  7. リンクノードによるアクセスが最善の方法かどうか。リンクノードを使用するコレクションは通常、リストと呼ばれます。リストを使用すると、コレクションの両端にあるデータに簡単にアクセスすることができます。また、データをコレクションの中に効率的に挿入することができます。しかし、コレクションの中にあるデータに繰り返しアクセスする必要がある場合、リストは他のコレクションほど効率的ではありません。

  8. データへのアクセスのほとんどが、コレクションの両端で行われるかどうか。未知の量のデータを処理しなければならない場合は多数ありますが、データ処理のほとんどは、コレクションの最も新しく、または最も古く挿入されたデータに適用されます。最も新しく追加されたデータの処理に特に有効なコレクションは、「後入れ先出し」の方針をとっています。後入れ先出し (LIFO) のコンテナはスタックです。データを「先入れ先出し」(FIFO) で処理するコレクションはキューと呼ばれます。最も新しく追加されたデータと、最も古く追加されたデータの両方に効率的にアクセスできるようにするコレクションは、デキュー (dequeue)、つまり二重終端キュー (double ended queue) と呼ばれます。

  9. リンクリストの場合、リストの一端だけからデータにアクセスする必要があるか、または両端からアクセスする必要があるか。片方向リストは小さくなりますが、リストの「先頭」からだけのアクセスが可能になります。二重リンクリストのアクセス方針はより柔軟ですが、格納されたオブジェクトごとに追加ポインタが必要になります。

  10. 数値インデックスによってアクセスされるコレクションの場合は、コレクションを自動的にサイズ変更する必要があるかどうか。コレクションに格納される項目の最大数がわかる場合は、固定サイズのコレクションを選択することによって、挿入と削除をすこし効率的に行うことができます。一方で、ほとんど無制限な拡張を許容する必要がある場合は、現在格納しているデータの量に合わせて自動的に自己調整するコレクションを選択する必要があります。

追加の選択基準

どのコレクションを選択するかは、多くの事に依存しています (経験と直感も重要です)。決定ツリーだけでなく、次の質問もコンテナの選択に影響を与えます。

  1. 複数のコレクションで単一のオブジェクトを維持する必要があるかどうか。ポインタにもとづくコレクションを使用してください。

  2. コピーのコストが非常に高いオブジェクトを収集しているかどうか。ポインタにもとづくコレクションを使用してください。

  3. ポインタにもとづくコレクションを使用しなければならない理由があるかどうか。値にもとづくコレクションを使用してください。

  4. コレクション内のオブジェクトの順序を外部的に制御したいかどうか。ベクトルやリストなどの順序付きコレクションを使用してください。

  5. コレクション内に項目を挿入した後、それらの項目を可変にする (固定にしない) 必要があるかどうか。順序付きまたはマッピング (辞書) コレクションを使用してください。マップと辞書は不変キーを持ちますが、値は可変です。

  6. コレクションがオブジェクトの比較にもとづく独自の順序を維持するようにしたいかどうか。セット、マップ、またはソートされたコレクションを使用してください。

  7. コレクション内のオブジェクトに数値インデックスにもとづいてアクセスしたいかどうか。順序付きまたはソートされたコレクションを使用してください。

  8. 非数値キーにもとづいて値を検索する必要があるかどうか。マップまたは辞書を使用してください。

  9. コレクション内のオブジェクトに、比較のためのオブジェクトを提供してアクセスしたいかどうか。セット、マップ、またはハッシュにもとづくコレクションを使用してください。

  10. 意味のある順序付けを実行して、キーによる一定時間の検索ができるかわりに、余分なメモリーを使用するかどうか。ハッシュにもとづくコレクションを使用してください。

  11. 現在の必要に応じて拡大または縮小するコレクション内で高速検索と挿入を必要とするかどうか。b ツリー、または新しい標準 C++ ライブラリにもとづく関連コンテナを使用してください。

  12. データすべてをメモリーに移動しないで、それらのデータにアクセスする必要があるかどうか。RWBTreeOnDisk または RWTValVirtualArray を使用してください。

時間と記憶容量に関する考慮事項

この節では、異なる特定のコレクションとコレクションファミリに対する、各種の共通操作での時間と記憶容量の要件を大まかに分析して比較します。これらの情報は、操作、時間のコストと記憶容量のコストをリストで示した表の集合として示します。コメントはすべて表の下に示してあります。表で使用されるキーの短縮形は、各ページの下にあります。

この分析を読む場合は、各種のプロセッサ、オペレーティングシステム、コンパイルの最適化など多数の要因が正確な値に影響を与えることに注意してください。これらの表の目的は、各種のコレクションの動作がどのように違っていて、それ以外のすべてに等しいかを示すことにあります。アルゴリズムの複雑さに関する詳細については、Knuth、Sedgewick などの文献を参照してください。

多くの Tools.h++ コレクションは、基本的に良く似たインタフェースを備えているので、コレクションの選択によってプログラムにどのような影響が及ぶかを簡単に実験して、判断することができます。

次に、各テーブルの内容を説明します。

割り当てについて説明する場合は、必ずメモリー割り当ての方針が、実装によって大幅に異なることに注意してください。しかし、システムコールに翻訳されるヒープ割り当て (または開放) は、通常、他のほとんどの定数コストよりも高くなります。「償却済み」コストは、コレクションの存続期間を通して平均化されます。個々のアクションのコストは、償却値よりも高くなる場合や低くなる場合があります。

RWGVector、RWGBitVec、RWTBitVec<size>、RWTPtrVector、RWTValVector

操作 時間コスト 必要記憶容量
端への挿入 C 0
中央への挿入 C 0
検索 (平均項目) N/2 0
項目の変更/置換 C 0
最初から削除 C 0
最後から削除 C 0
中央から削除 C 0
コンテナオーバーヘッド 　 Mt+0
コメント T の配列に対する単純なラッパー
(バイトの bitvec:array を除く) 		指示があったときだけサイズ変更する。

片方向リンクリスト

操作 時間コスト 必要記憶容量
端への挿入 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)
コメント 挿入ごとに割り当てる。反復子は前方だけに進む。 項目ごとに拡大縮小する。二重リンクリストよりも小さい。

比較表のキー

N M t i p C
項目のカウント 項目のスペースのカウント sizeof (item) sizeof (int) sizeof (void*) 定数

二重リンクリスト

操作 時間コスト 必要記憶容量
端への挿入 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)
コメント 挿入ごとに割り当てる。反復子は両方向に進む。 項目ごとに拡大縮小する。Slist よりも大きい。

順序付きベクトル

操作 時間コスト 必要記憶容量
端への挿入 C (償却済み) t (償却済み)
中央への挿入 N/2 t (償却済み)
検索 (平均項目) N/2 0
項目の変更/置換 C 0
最初から削除 C 0
最後から削除 C 0
中央から削除 N/2 0
コンテナオーバーヘッド 　 (Mt+ p + 2i) + 0
コメント 反復子なし (size_t インデックスを使用)ベクトルが拡大したときだけ割り当てる。 一度に多数のエントリにスペースを追加することによって、必要に応じて拡大する。resize() を介するときだけ縮小する。

比較表のキー

N M t i p C
項目のカウント 項目のスペースのカウント sizeof (item) sizeof (int) sizeof (void*) 定数

ソートされたベクトル

操作 時間コスト 必要記憶容量
挿入 logN + N/2 (平均) t (償却済み)
検索 (平均項目) logN 0
項目の変更/置換 N 0
最初から削除 N 0
最後から削除 C 0
中央から削除 N/2 0
コンテナオーバーヘッド 　 (Mt + p + 2i) + 0
コメント 挿入はソート順序にもとづいて起こる。反復子なし (size_t インデックスを使用)。ソートを維持するために、置換には削除/追加の順序が必要である。ベクトルが拡大したときだけ割り当てる。 一度に多数のエントリにスペースを追加することによって、必要に応じて拡大する。resize() を介するときだけ縮小する。

スタックとキュー

操作 時間コスト 必要記憶容量
端への挿入 logN + N/2 (平均) t + p
削除 (ポップ) logN t + p (回復済み)
コンテナオーバーヘッド 　 (2p+i) + N(t+p)
コメント 片方向リストとして実装される。

テンプレート化バージョンでは、コンテナを選択できる。時間とスペースのコストはこの選択を反映する。

　

比較表のキー

N M t i p C
項目のカウント 項目のスペースのカウント sizeof (item) sizeof (int) sizeof (void*) 定数

デキュー

操作 時間コスト 必要記憶容量
端への挿入 C t (償却済み)
検索 (平均項目) N/2 0
項目の変更/置換 C 　
最初から削除 C t (償却済み、回復済み)
最後から削除 C t (償却済み、回復済み)
中央から削除 N/2 t (償却済み、回復済み)
コンテナオーバーヘッド 　 (2p+i) + N(t+p)
コメント 配列内の循環キューとして実装される。

コレクションが拡大したときだけ割り当てる。

必要に応じて拡大縮小し、余分な拡大分をサイズの増加とともにキャッシュする。

バイナリツリー

操作 時間コスト 必要記憶容量
挿入 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(2t+p)
コメント 挿入はソート順序にもとづいて起こる。

挿入ごとに割り当てる。

順序を維持するために、置換には削除/追加の順序が必要である。

自動的には均衡化されない。

上記の数字は均衡化されたツリーを仮定する。

項目ごとのコストは二重リンクリストと同じである。

比較表のキー

N M t i p C
項目のカウント 項目のスペースのカウント sizeof (item) sizeof (int) sizeof (void*) 定数

(複数) マップと (複数) セットファミリ

操作 時間コスト 必要記憶容量
挿入 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)
コメント 挿入はソート順序にもとづいて起こる。

挿入ごとに割り当てる。

セットの場合、置換には削除/挿入が必要である。

マップの場合、値は所定の場所にコピーされる。

均衡化 (赤黒) 二分木として実装される。

　

比較表のキー

N M t i p C
項目のカウント 項目のスペースのカウント sizeof (item) sizeof (int) sizeof (void*) 定数

RWBTree、RWBTreeDictionary1

操作 時間コスト 必要記憶容量
挿入 logN+C 2p + t + small (完全に償却済み)
検索 (平均項目) logN 0
項目の変更/置換 2logN+2 or C 0
最初から削除 2logN(log2(ORDER))+C (最悪の場合) 2p+t (回復済み)
最後から削除 2logN(log2(ORDER))+C (最悪の場合) 2p+t (回復済み)
中央から削除 2logN(log2(ORDER))+C (最悪の場合) 2p+t (回復済み)
コンテナオーバーヘッド 再平均化は、挿入/削除ごとに起こる。しかし、バランス化バイナリツリーの場合ほど頻繁には起こらない。 これは、ノードがどれぐらい完全にパックされたかによって決まる。各ノードのコストは ORDER (2p+t+1) で、2N/ORDER 以下、min (N/ORDER,1) 以上のノードがある。事前にソートされた項目を挿入すると、サイズが最大化しやすい。Sedgewick は、ランダムデータでのサイズは 1.44 N/ORDER に近いと言っている。
コメント 挿入はソート順序にもとづいて起こる。対数はおよそ基底 ORDER で、これは b ツリーの広がりである (実際には、基底は b ツリーの実際のロードによって ORDER と 2ORDER の間になる)。

b ツリーの置換には、削除、次に挿入が必要である。btreedictionary の場合、値は所定の位置にコピーされる。

　

ハッシュにもとづくコレクション

操作 時間コスト 必要記憶容量
挿入 C p+t
検索 (平均項目) C 0
項目の変更/置換 C または 2C 0
削除 C p+r (回復済み)
コンテナオーバーヘッド 　 ((M+2)p+i) + N(p+r) (1) (Mp+ (2p+i)b_used + N(p+t) (2)

1: 標準準拠バージョン

2: b_used は「V6.1」ハッシュコレクションの「使用されたスロットの数」を示す。

コメント 挿入はハッシュ関数にもとづいて起こる。

定数時間コストは、項目がハッシュスロットに適切に分散されることを前提とする。最悪の場合は、スロットあたりの項目数に比例する。

辞書またはマップの場合、置換する。新しい値は所定の場所にコピーされる。

そうでない場合、削除、次に挿入が必要である。

自動的にサイズ変更を行わない。

項目数は、頻繁に使用するスロットの数の 1.5 倍から 2 倍の間に設定することを推奨する。

比較表のキー

N M t i p C
項目のカウント 項目のスペースのカウント sizeof (item) sizeof (int) sizeof (void*) 定数


1 RWBTreeOnDisk は RWBTreeDictionary と類似の複雑さを持ちますが、時間オーバーヘッドはこれよりもはるかに大きくなります。これは、「後続のリンクノード」が「ディスクシーク」になり、サイズオーバーヘッドが、主メモリーよりもディスク記憶域に対してはるかに大きな影響を持つためです。


Previous Next Contents Index