recursion - パフォーマンスの問題: セグメント ツリー、更新機能

Question

このような関数でセグメント ツリーを更新します。プロファイリングによると、ボトルネックは次のとおりです。

void update (int tree[], int root, int left, int right, int pos, double val)
{
    if (left == right)
    {
        data[tree[root]] = val;
    }
    else
    {
        int middle = (left + right) / 2;
        if (pos <= middle)
            update(tree, root*2, left, middle, pos, val);
        else
            update(tree, root*2+1, middle+1, right, pos, val);
        tree[root] = indexOfMax(tree, tree[root*2], tree[root*2+1]); // simple comparations
    }
}
// indexOfMax is just a simple comparation
int indexOfMax(int tree[], int a, int b)
{
    //cout << data[tree[a]] << " > " << data[tree[b]] << " ? " << tree[a] << " : " << tree[b] << endl;
    return data[a] > data[b] ? a : b;
}

また、メモリ操作は高速ですが、再帰オーバーヘッドが原因であるかどうか疑問に思っていますが、その深さは通常 20 を超えていません。

プリミティブ プロファイラーから得られるものは次のとおりです。

• 4.39434ms - データに対する単一バイナリ検索の平均時間
• 2642.94ms - 1 回の更新からの時間
• 19.9097ms - 単一の RMQ クエリの時間。

だから..単一の更新に費やされる時間は劇的です:)。

回答: 非表示の std::find オーバー マップが 1 つ見つかりました。