私は現在、パフォーマンスの問題が発生している組み込みデバイス プロジェクトに取り組んでいます。プロファイリングにより、削除したい O(N) 操作が見つかりました。
私は基本的に2つの配列int A[N]とshort B[N]. のエントリAは一意であり、外部制約によって順序付けられます。最も一般的な操作は、特定の値aが に表示されるかどうかを確認することA[]です。あまり頻繁ではありませんが、依然として一般的なのは、 の要素への変更ですA[]。新しい値は以前の値とは無関係です。
最も一般的な操作は検索であるため、そこに出番があります。これは、B[]インデックスの並べ替えられた配列です。つまり、バイナリ検索を使用して値を見つけることができます。A[]A[B[i]] < A[B[j]]i<jA
もちろん、更新するときはA[k]、検索順序を維持するために、検索して新しい位置に移動する必要がありますk。Bの古い値と新しい値を知っているので、それは の古い位置と新しい位置の間ののサブセットにA[k]すぎません。これは、修正する必要がある O(N) 操作です。の古い値と新しい値は本質的にランダムであるため、平均して約N/2 N/3 要素を移動しています。memmove()B[]kA[k]
述語としてのstd::make_heap使用を検討しました。その場合、 の最小要素を[](int i, int j) { return A[i] < A[j]; }簡単に指摘でき、更新は安価な O(log N) リバランス操作になりました。ただし、通常、A の最小値は必要ありません。特定の値が存在するかどうかを確認する必要があります。そして、これは の O(N log N) 検索になりました。(私の N 要素の半分はヒープ深さ log N にあり、4 分の 1 は (log N)-1 にあるなど)、.B[0]ABBA
O(log N) の挿入と検索があることを考えるstd::setと、更新と検索で同じパフォーマンスを得ることができるはずです。しかし、どうすればそれを行うことができますか？をもう一度注文する必要がありBますか? 違うタイプ？
B現在、short [N]とAをB合わせると、CPU キャッシュのサイズとほぼ同じであり、メイン メモリがかなり遅いためです。6*N バイトから 8*N バイトになるのは良くありませんが、検索と更新が両方とも O(log N) になる場合は許容できます。