問題タブ [multiset]

セット内のすべてのオブジェクトに対して一意の値を生成する必要があるタスクがあります。ハッシュコードコントラクトで衝突が許可されていない場合は、ハッシュコードを使用するのが最適です。

1つのアイデア：すべてのオブジェクトのハッシュコードをマルチセットに記録します。次に、一意の識別子としてハッシュコードを使用しますが、そのハッシュコードがセットに複数回含まれている場合は、セットに含まれていない別の値を使用します。しかし、これはかさばり、ぎこちなく感じます。

より良いアイデア？

これが私がすでに持っているものです：

編集：これは元々明確ではなかったと思いますが、ID番号はオブジェクトの関数である必要があります。これは、何度も呼び出され、同じ値に対して同じ結果が得られるgetVertexName(V)ことを期待しているためです。V

また、頂点タイプはジェネリックです。したがって、これを修正するために特定のクラスに変更を加えることはできません。

32 ビット整数のリストと、マルチセット (メンバーの重複を許可するセット) に 32 ビット整数の同じコレクションがあるとします。

Sets は順序を保持しませんが、List は保持するので、リストよりも少ないビット数で Multiset をエンコードできるということですか?

もしそうなら、マルチセットをどのようにエンコードしますか?

これが本当なら、順序を保存する必要のない他の例はビットを保存しますか?

例として 32 ビット整数を使用したことに注意してください。エンコーディングでデータ型は重要ですか? 節約するために、データ型は固定長で比較可能である必要がありますか?

編集

重複が少ないコレクションと重複が多いコレクションでは、どのソリューションもうまく機能するはずです。単純に重複をカウントするだけでマルチセットをエンコードする高重複の明らかな方法は非常に簡単ですが、コレクションに重複がない場合、これはより多くのスペースを必要とします。

マルチセットの .Net 実装を探しています。誰かが良いものを推薦できますか？

(マルチセットまたはバッグは、重複する値を持つことができるセットであり、交差、差などのセット操作を実行できます。たとえば、ショッピング カートは、複数の値を使用できるため、マルチセットと考えることができます。同じ商品です。）

私はプロのプログラマーではないので、遠慮なく明白に述べてください。

私の目標は、呼び出されたstd::multisetコンテナ（ ）を使用して、型の構造体のリストを整理し、クラスのメンバーに新しい構造体を時々追加させることです。構造体は、メンバーの1人である時間によってソートされることになっています。私がやろうとしていることのどれだけが合法であるかはわかりません。g ++コンパイラは（「Host.h」で）「エラー：'EventMultiSet'は宣言されていません」と報告します。これが私がしていることです：typedef EventMultiSetcurrentEventsEventHostEventcurrentEvents

主な質問

1. EventMultiSet typedefをどこに含める必要がありますか？
2. 私のEventMultiSetポインターは明らかに問題がありますか？
3. 私のイベント構造体内の比較関数は（理論的には）大丈夫ですか？

事前にどうもありがとうございました。

マルチセットコンテナによる奇妙な動作のデバッグにご協力いただければ幸いです。場合によっては、コンテナが並べ替えを停止しているように見えます。これはまれなエラーであり、久しぶりの一部のシミュレーションでのみ明らかになり、アイデアが不足しています。（私はアマチュアプログラマーです。あらゆる種類の提案を歓迎します。）

私のコンテナは構造体std::multisetを保持するものですEvent：

メンバーEventでソートされた構造体を使用して：double time

プログラムは、順序付けられていない時間のイベントを追加しEventPQ currentEvents、次にイベントを順番にプルする期間を繰り返します。まれに、いくつかのイベントが追加された後（完全に「合法的な」時間で）、イベントが順不同で実行され始めます。

イベントが適切に順序付けられない原因は何ですか？（または、イテレータを台無しにする可能性がありますか？）追加されたすべてのイベント時間が正当である（つまり、すべてが現在のシミュレーション時間を超えている）ことを確認しました。また、2つのイベントがスケジュールされているため、エラーが発生しないことも確認しました。同時に。

これをどのように処理するかについての提案が欲しいです。

好奇心旺盛な方のために、イベントを実行および追加するためのコードを以下に示します。

イベントが実行されると、から他のイベントが削除される場合があることを追加する必要がありますcurrentEvents。これはで行われます

このコードは問題ないように見えますが、何が起こっているのかを調べる他の方法を知りたいです。現在、多くのasserts（）とcout<<チェックを使用しています。

ここで問題が発生しました。C++ マルチセットを使用しています。これがテストファイルです。

上記のテスト ファイルから読み取るために、while ループと ifstream (fin1) を使用しています。

最後のelseステートメントで、すべての名前を（勝ち/負け/引き分けに関係なく）mysetに挿入しています。しかし、勝った/引き分けた試合の名前だけが必要です。

一致が失われた名前は myset に含まれません。上記のテスト ファイルでは、1 対 2 で負けた試合が 1 つだけあり、"Ben" を削除したかったのです。どうやってやるの？

myset.erase() を使用しようとしましたが、Ben をポイントして myset から削除する方法がわかりません。

どんな助けでも大歓迎です。ありがとう。

multiset質問が述べているように... s / multimapsについての要点がわかりません。

それで、目的は何ですか？

Google Collections Multisetは、それぞれがカウントを持つ (つまり、複数回存在する可能性がある) 要素のセットです。

次のことを何回やりたいかわかりません

1. ヒストグラムを作成する (正確には Multiset)
2. ヒストグラムからカウントごとに上位 N 個の要素を取得する

例: 上位 10 個の URL (# 回言及)、上位 10 個のタグ (# 回適用)、...

Google Collections マルチセットを指定して #2 を行う標準的な方法は何ですか?

これについてのブログ投稿がありますが、そのコードは私が望むものではありません。まず、上位 N だけでなく、すべてを返します。次に、コピーします (コピーを避けることは可能ですか?)。第三に、私は通常、決定論的な並べ替え、つまりカウントが等しい場合のタイブレークが必要です。その他のニット: 静的ではないなど。

記録が必要な理由を誰か説明してもらえますか? ループを使用してPL/SQLで同じ操作を実行することはできませんか。また、マルチセット レコード クエリはいつ使用できますか? つまり、どのタイプの状況で、どちらが優先されるのでしょうか?

熱心なプログラミングを行っているときに、この問題に遭遇しました。問題は次のように表現できます。

マルチセット A について、P(A) が A のすべての可能な順列のセットを表すとします。P(A) は、等価関係が「循環シフトによって関連付けられる可能性がある」状態で、等価クラスである互いに素なサブセットに自然に分割されます。それぞれから正確に 1 つのメンバーを生成することにより、これらすべての等価クラスを列挙します。

たとえば、マルチセット {0, 1, 1, 2} を考えてみましょう。順列 "0112" と "1201" は一意の順列ですが、後者は前者を循環シフトすることで見つけることができ、逆も同様です。目的のアルゴリズムで両方を生成することはできません。

もちろん、強引なアプローチも可能です。循環重複に関係なく、任意のマルチセット置換アルゴリズムを使用して順列を生成し、以前の結果との比較によって見つかった重複を破棄するだけです。ただし、これは実際には非効率的である傾向があります。必要なアルゴリズムは、簿記がゼロではないにしても、最小限で済む必要があります。

この問題への洞察は深く感謝しています。