0

std::map で多数の検索、挿入、および削除を実行しています。速度を最適化するためにコードを追加することを検討していますが、現在のワークロードに関する統計を収集したいと考えています。具体的には、実行中の集計を維持できるように、各呼び出しで「検索」が通過する必要があるノードの数を追跡したいと考えています。

マップのほとんどの変更が前面で発生する場合、「find」が使用するツリーを使用する前に、最初の N エントリを検索する方がよいのではないかと考えています。

4

2 に答える 2

1

Find は、マップの比較関数を使用して要素を比較する必要があるため、呼び出された回数をカウントするカスタム比較関数を提供して、各呼び出しでどれだけの作業が行われているかを確認できます (基本的に、トラバースされるノードの数)。

ただし、この場合、 find() を呼び出す前に最初の N エントリを検索することがどのように役立つかわかりません。マップ内のエントリを反復処理すると、ソートされた順序でツリーをトラバースするだけなので、比較関数が等価性のチェックよりもはるかに高価でない限り、find() を呼び出すよりも効率的ではありません。

コード例:

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <vector>

using namespace std;

int main() {
    vector<int> v(100);
    iota(begin(v), end(v), 0);
    vector<pair<int, int>> vp(v.size());
    transform(begin(v), end(v), begin(vp), [](int i) { return make_pair(i, i); });

    int compareCount = 0;
    auto countingCompare = [&](int x, int y) { ++compareCount; return x < y; };
    map<int, int, decltype(countingCompare)> m(begin(vp), end(vp), countingCompare);
    cout << "Compares during construction: " << compareCount << "\n";
    compareCount = 0;
    auto pos = m.find(50);
    cout << "Compares during find(): " << compareCount << "\n";
}
于 2013-11-06T22:55:36.083 に答える
0

キー/値構造で実行可能な場合はunordered_map、代わりに (C++11 または TR1 で) 検討する価値があります。 std::map、バランスの取れたツリーであるため、この使用プロファイルではうまく機能しない可能性が高く、最初の N を検索するハイブリッド アプローチは、利益が保証されていないため、私には多くの作業のように思えます。

于 2013-11-06T13:04:36.313 に答える