3

私は現在確率的最適化アルゴリズムを開発しており、次の問題に遭遇しました (これは他の場所にも現れると思います):完全に不安定な部分ソートと呼ばれる可能性があります:

サイズ n のコンテナとコンパレータが与えられ、エントリが等しく評価されるようにします。最良の k 個のエントリを返しますが、値が等しい場合、それらのいずれかを受け取る可能性は (ほぼ) 等しくなります。

(出力順序は私には関係ありません。つまり、最良の k の間で完全に等しい値をシャッフルする必要はありません。ただし、すべての等しい値をシャッフルすることは、関連する興味深い質問であり、十分です!)

非常に (!) 非効率的な方法はshuffle_randomlyand thenを使用することpartial_sortですが、実際には「選択境界で」同じ値のエントリのブロックをシャッフルするだけで済みます (同じ値のエントリのすべてのブロック、どちらもはるかに高速です)。多分その観察はどこから始めるべきか...

誰かが STL アルゴリズム (または少なくとも大部分) を使用したソリューションを提供できれば、非常に望ましいと思います。どちらも、通常は非常に高速で、適切にカプセル化され、OMP 並列化されているためです。

アイデアをお寄せいただきありがとうございます。

4

4 に答える 4

3

あなたはpartial_sort 最初にしたいです。次に、要素が等しくない場合は、それらを返します。残りのkよりも大きい等しい要素のシーケンスに出会った場合は、シャッフルして最初のkを返します。それ以外の場合は、すべてを返して続行します。

于 2012-11-10T16:26:09.077 に答える
2

あなたの問題を完全には理解していませんが、この問題を解決したのが私だった場合（私が正しく読んでいる場合）...

とにかく指定されたオブジェクトをトラバースする必要があるように見えるので、結果のコピーを作成し、挿入時にソートし、挿入時に「等しい」アイテムをランダム化することもできます。

つまり、指定されたコンテナーから STL リストに項目をコピーしますが、比較演算子をオーバーロードして B ツリーを作成し、挿入時に 2 つの項目が等しい場合は、現在の項目の前または後に挿入することをランダムに選択します。

このようにして、（ツリーであるため）最適にトラバースされ、リストが構築されるたびに等しいアイテムのランダムな順序が得られます。

メモリが 2 倍になりますが、元のリストを変更したくなかったので、これを読んでいました。元のリストをなくしてもかまわない場合は、新しいリストに挿入するときに、元のアイテムから各アイテムを削除してください。渡されたリストがソートされていない可能性があるため、最悪のトラバーサルは関数を初めて呼び出すときです。ただし、リストを並べ替えたコピーに置き換えるため、将来の実行ははるかに高速になり、ルート ノードを length() / 2 の要素として割り当てることで、ツリーのより適切なピボット ポイントを選択できます。

これが役に立てば幸いです。きちんとしたプロジェクトのように聞こえます。:)

于 2012-11-10T16:45:59.733 に答える