0

があるとしますstd::vector<std::map<std::string, T> >。mapすべての が同じキーを持っていることがわかります。で初期化されている可能性があります

typedef std::map<std::string, int> MapType;
std::vector<MapType> v;
const int n = 1000000;
v.reserve(n);
for (int i=0;i<n;i++)
{
    std::map<std::string, int> m;
    m["abc"] = rand();
    m["efg"] = rand();
    m["hij"] = rand();
    v.push_back(m);
}

キー (例: "efg") を指定すると、指定されたキー (すべてのマップに確実に存在する) のマップのすべての値を抽出したいと思います。

次のコードを高速化することは可能ですか?

std::vector<int> efgValues;
efgValues.reserve(v.size());
BOOST_FOREACH(MapType const& m, v)
{
    efgValues.push_back(m.find("efg")->second);
}

値は必ずしも ではないことに注意してくださいint。プロファイリングにより、ほとんどの時間が find 関数に費やされていることが確認されたので、すべてのマップのキーに基づいてマップ内の要素を見つけることを回避する (GCC および MSVC 準拠の C++03) 方法があるかどうかを考えていました。すべてのマップの構造が等しいためです。

いいえの場合、boost::unordered_map(上記のコードを使用したマシンでは 15% 遅くなります) で可能でしょうか? 文字列のハッシュ値をキャッシュすることは可能でしょうか?

PS: がstd::map<std::string, std::vector<T> >あれば問題が解決することはわかっています。ただし、データ構造を変更することはできません (実際には、ここで示したものよりも複雑です)。

4

1 に答える 1

2

ステートフル コンパレータを使用して、一連の比較結果をキャッシュおよび再生できます。しかし、それは厄介なことです。解決策は、データ構造を調整することです。「できない」はありません。実際には、ステートフル コンパレータを追加すると、データ構造が変更されます。その要件は、ほとんどすべてを除外します。

Tもう 1 つの可能性は、別のルックアップなしで各マップから次のマップに移動できるように、タイプのオブジェクト間でリンクされたリストを作成することです。いずれかのマップから開始する可能性がある場合 (構造をリファクタリングしてください)、循環リストまたは二重リンク リストを使用するとうまくいきます。

プロファイリングにより、ほとんどの時間が検索機能に費やされていることが確認されるため

ツリー データ構造を保持し、比較を最適化すると、比較が高速化されます。で時間が費やされない限り、operator< (std::string const&, std::string const&)リンク方法を変更する必要があります。

于 2013-01-16T08:07:34.557 に答える