10

に関する情報を保持するレコードを作成したい

  • a) どのような要素が存在し、
  • b) 存在する各種類の要素の数

ツリーのノードで。親ノードの情報は、すべての子の情報を組み合わせることで取得できますが、この情報はリーフ ノードにのみ明示的に保存します (たとえば、子 1 には A のオブジェクトが 3 つ、B のオブジェクトが 1 つ、子 2 には 1 つのオブジェクトがあります)。 A のオブジェクト、C の 2 つのオブジェクト -- 親には A の 4 つのオブジェクト、B の 1 つのオブジェクト、C の 2 つのオブジェクトがあります)。

親ノードからこの情報を要求するときは、最初に子ノード、次にその親ノードの情報を要求、使用、および破棄しないように注意しますが、上向きの構築は一般的な操作です。他の 2 つの一般的な操作は、格納したものから直接派生します:種類 X のオブジェクトは存在しますか? また、種類 X のオブジェクトはいくつ存在しますか? また、何種類のオブジェクトが存在しますか?

オブジェクトの種類は整数で表され、オブジェクト番号は常に整数値です。より良い選択 (および選択した選択の引数) は何ですか?

  • を使用しstd::multiset<int>、 および 操作でstd::multiset::count()操作しstd::multiset::find()ます (結合は簡単ですが、要素の複製、別個の要素の合計数を取得するのは困難です)
  • 種類をキーとして、オブジェクトの数を値として使用std::map<int, std::size_t>します (重複する要素がなく、std::map::find()関数が存在し、サイズによって格納されているオブジェクトの種類の正しい数が得られますが、存在しない要素にアクセスするとサイズが意図せず増加します)

ご提案ありがとうございます。

4

2 に答える 2

12

比較述語ごとにk 個の異なる値を持つ合計n 個のアイテムを格納するために、 はn 個の二分探索木ノード (*) を割り当てます。Anは、 k (わずかに大きい) ノードのみを割り当てます。std::multisetstd::map

2 つの項目が比較述語によって等しいと見なされる場合に使用std::multisetしますが、比較述語がチェックしないいくつかの側面が異なるため、明示的に格納する必要があります。また、a を反復処理するとn 個のアイテムがmultisetそれぞれ生成されますが、a はそれぞれのカウントを持つk 個の個別のアイテムをそれぞれ生成します。map

項目が整数のみの場合は、 を使用しstd::mapます。size「個別のアイテムの数」クエリは、定数時間で実行されるへの呼び出しにすぎません。

「存在しない要素にアクセスすると意図せずサイズが大きくなる」という主張は、operator[]ノードへのアクセスに使用する場合にのみ当てはまります。findはこの動作を示しません。

(*) C++ 標準は、これらのコンテナーが (バランスの取れた) BST として実装されることを保証していませんが、私が見たすべての実装ではそうです。

于 2012-06-01T12:57:52.103 に答える
3

ソート済みはstd::vector<int>どうですか？必要な操作は次のように満たすことができます。

  • 種類 X のオブジェクトは存在しますか? std::binary_search
  • 種類 X のオブジェクトはいくつありますか? 、からstd::equal_range減算.first.second
  • オブジェクトは何種類存在しますか？
    • std::unique_copyコピーの後に続くsize()、または...
    • 別のカウンターを使用std::binary_searchし、ベクターに挿入する前に呼び出します

このアプローチの利点は、キャッシュの局所性 (すべてのデータが連続している) と、ツリーのような構造に比べてメモリ フットプリントが少ないことです。あなたのデータについてもっと知らなければ、それが速いか遅いかはわかりません. 調べるにはプロファイリングする必要がありますが、これは予想よりも優れたパフォーマンスを発揮する予感があります。

ここでの最大のトレードオフは表現力です。このstd::mapアプローチはおそらく、何をしているのか、つまりオブジェクト ID とカウントの関係を論理的に伝えるのに適しています。

于 2012-06-01T13:37:40.913 に答える