std::multisetをstd::priority_queueに置き換えようとしています。しかし、私はスピードの結果に失望しました。アルゴリズムの実行時間は50％増加します...

対応するコマンドは次のとおりです。

priority_queueの実装の速度に驚いています。異なる結果を期待していました（PQの方が良い）...概念的には、マルチセットが優先キューとして使用されています。優先キューとマルチセットのパフォーマンスが異なるのはなぜ-O2ですか？

10件の結果の平均、MSVS 2010、Win XP、32ビット、メソッドfindAllKNN2（）（以下を参照）

これらの結果の原因は何ですか？ソースコードの他の変更は行われていません...あなたの助けに感謝します...

MSの実装：

方法：

PQの実装（遅い、なぜですか？）

方法：

データ構造マルチセット、C ++に格納されている値にアクセスするにはどうすればよいですか？

誰かが、少なくとも私にとって非常にトリッキーなアルゴリズムを手伝ってくれることを願っています.

問題

結合する必要があるリスト ( )のリスト( 1 <= size <= 5、ただしサイズは実行時まで不明) があります。1 <= size <= 2これが私が見ているものの例です:-

だから、私がする必要があることには2つの段階があります:-

(1)。すべての組み合わせが各リストから正確に 1 つの項目を持つように、内部リストを組み合わせる必要があります。つまり、ここでの結果セットで可能な組み合わせは次のようになります。

• 1,2,2,4,2
• 1,2,2,4,3
• 1,2,3,4,2
• 1,2,3,4,3
• 1,3,2,4,2
• 1,3,2,4,3
• 1,3,3,4,2
• 1,3,3,4,3

デカルト積がこれを処理するので、ステージ 1 が完了します.....今、ここに私が理解できないひねりがあります-少なくとも私はそれを行う LINQ の方法を理解できません (私はまだLINQ初心者）。

(2)。このデカルト積から重複する結果を除外する必要があります。この場合の重複は、別の行と同じ数の個別のリスト要素を持つ結果セット内の任意の行を構成します。つまり、

1,2,2,4,3 は 1,3,2,4,2 と「同じ」

最初のリスト内の個別の各項目は、両方のリストで同じ回数出現するためです (1 は各リストで 1 回、2 は各リストで 2 回、....

したがって、最終的な結果セットは次のようになります...

• 1,2,2,4,2
• 1,2,2,4,3
• --
• 1,2,3,4,3
• --
• --
• --
• 1,3,3,4,3

もう 1 つの例は、ListOfLists が {{2,3}、{2,3}、{2,3}、{2,3}、{2,3} である最悪のシナリオ (組み合わせの観点から) です。 }、つまり、最大サイズの内部リストを含むリスト - この場合、デカルト積の結果セットには明らかに 32 の結果がありますが、取得しようとしているプルーニングされた結果セットは次のようになります。

• 2,2,2,2,2
• 2,2,2,2,3 <-- 4 つの 2 と 1 つの 3 (任意の順序) を含む他のすべての結果は抑制されます
• 2,2,2,3,3 <-- 3 つの 2 と 2 つの 3 を含む他のすべての結果は抑制されます。
• 2,2,3,3,3
• 2,3,3,3,3
• 3,3,3,3,3

そこにいる数学に関心のある人々へ-あなたが助けてくれることを願っています. 私は実際にパート 2 の有効なソリューションを手に入れましたが、これは完全なハックであり、計算量が多いため、プルーニングの問題に対するよりエレガントで効率的な LINQ ソリューションを見つけるためのガイダンスを探しています。

読んでくれてありがとう。

ピップ

これまでに使用したいくつかのリソース (デカルト積を取得するため)

• linq を使用したデカルト積の計算
• c-permutation-of-an-array-of-arraylists
• msdn

更新 - 解決策

これをすぐに投稿しないことをお詫びします...以下を参照してください

そのサブインターフェイスjava.util.Collectionを効果的にマルチセット（別名バッグ）と定義しました。それはnull私の質問にとって重要ではありませんが、要素が含まれていない可能性があります。インターフェイスによって定義されたequalsコントラクトは、予想どおりです。

• obj instanceof MyInterface
• objthis（by equals）と同じ要素が含まれています
• obj各要素に同じ数の重複が含まれています
• 要素の順序は無視されます

今、私は自分のメソッドを書きたいと思いhashCodeます。私の最初のアイデアは次のとおりです。

com.google.common.collect.Multisetただし、 （Guavaから）ハッシュコードが次のように定義されていることに気付きました。

空のマルチセットのハッシュコードが0になるのは奇妙なことですが、さらに重要なのは^ count(o)、すべての複製のハッシュコードを単純に合計することの利点を理解していないことです。たぶんそれは同じハッシュコードを2回以上計算しないことについてですが、それならなぜ* count(o)ですか？

私の質問：効率的なハッシュコード計算は何でしょうか？私の場合、要素の数を安く取得できるとは限りません。

グアバにマルチセットがあり、このマルチセットを反復せずに特定の要素のインスタンス数を取得したい (すべてのコレクションを調べるため、反復にはかなりの時間がかかると想定しているため、反復したくない) ）。

そのために、最初に multiset の entryset() メソッドを使用して、単一のインスタンスとそれに対応するカウントを含むセットを取得することを考えていました。次に、このセットをハッシュマップに変換します (キーはセットの要素で、値はインスタンス カウントです)。ハッシュマップのメソッドを使用して、キーから値を直接取得できるためです。しかし、これは、(すべての要素を反復せずに) セットをハッシュマップにすばやく変換できる場合にのみ意味があります。それは可能ですか?

（私が言ったように、この質問には複数の点で欠陥があると予想しています。私がおそらくここで犯す概念的な間違いに光を当てることができれば幸いです.Thx!）

サイズ m の文字のバッグB(マルチセット) とサイズ n の文字列テキスト S が与えられます。BS で (4!=24 の組み合わせ)によって作成できるすべての部分文字列を線形時間で見つけることは可能O(n)ですか?

例：

私が見つけた最速の解決策は、各キャラクターのカウンターを保持し、各ステップでそれをバッグと比較することです。したがって、ランタイムはO(n*m). 必要に応じてアルゴリズムを表示できます。

ソートされたマルチセット (TreeMultiset) から n 個の上位エントリを取得する効率的な方法はありますか?

私が何を意味するかを指定するために、非効率的なソリューションを投稿します。

この例では、DataSet は Object と見なすことができ、this.coreData は下層の TreeMultiset です。

私はそのトピックに本当に慣れていないので、あらゆる種類のコメントをいただければ幸いです。

私は現在、Bag抽象データ型を実装しようとしている割り当てに取り組んでいます（したがって、完全なコードを投稿したくありません）。

以下は、私が現在実装しようとしているメソッドです。

要素を動的配列として格納しています。

私の問題は、新しいバッグが返送されたときにカーディナリティを細かく印刷できることです（4に印刷すると、元のバッグにはそれぞれ2つの要素があります）が、動的配列には数値が含まれていません（次のような乱数が出力されます）。 -1789102）。しかし、バッグを返却する前に要素を印刷しようとすると、うまく印刷されます。

些細なことになることは間違いありませんが、助けていただければ幸いです。

ありがとう。

MultiSet クラスのメソッドのいくつかに問題があります。これはテスターであり、MultiSet クラスは "Succes!" という出力を取得する必要があります。正しく動作する場合。これはテスターです：

そして私のMultisetクラス：

途中で追加または削除のいずれかを手伝っていただければ、おそらくもう一方を解決できるでしょう。

また、equals が正しく機能していないようで、String toString で "res" を計算する方法がわかりません。return ステートメントは気にしないでください。見栄えを良くするために、後で括弧などを挿入します。

ご協力ありがとうございました。// クリス

これは私のクラスです：

したがって、基本的に、要素をに追加または削除するには、add/remove-methods を正しく実装する必要がありSetます。

私には、私の意見equalsが正しいように思えますが、Eclipse は次のように述べています。

unchecked cast from object to Multiset<E> 何か考えはありますか？

また、私のtoString方法では、「res」を定義する方法が100％わかりませんか？

ありがとう、// クリス