問題タブ [pairing-heap]

すべての通常の操作（merge、delete-minなど）で「ペアリングヒープ」を実装しようとしましたが、新しく構築したヒープ実装を使用してリストを並べ替える関数を作成するように要求されました。残念ながら、何かがうまくいかないようです...

関連するコードは次のとおりです。

そして、これらはあなたがコードを理解するのを助けるかもしれないいくつかのセレクターです：

ここで問題に取り掛かりましょう。「heapsort」を実行すると、次のように「void」でソートされたリストが返されます。

..どうすれば修正できますか？

よろしく、スーパーグアイ

ペアリング ヒープ データ構造を実装しました。ペアリング ヒープは、O(1) 償却時間で挿入、検索分、マージをサポートし、O(logN) 償却時間で削除、削除分をサポートします。しかし、最も顕著な操作は、複雑さ O(log logN) を持つ減少キーです。ペアリング ヒープの詳細については、http://en.wikipedia.org/wiki/Pairing_heapを参照してください。

insert、merge、および delete-min 操作を実装しましたが、ウィキペディアの記事には特定のノードのキーを減らす方法が記載されていなかったため、実装できませんでした。誰かが実際にどのように機能するか教えてもらえますか?

これが私のコードです：

ワーカー スレッドを使用して大規模なアルゴリズムを高速化しようとしたときに、より多くのスレッドで独立した優先キューを使用すると実際にパフォーマンスが低下することに気付きました。そこで、小さなテストケースを書きました。

ここでは、開始するスレッドの数を照会し、各スレッドを独自のプロセッサに設定し、プライオリティ キューから多くのものをプッシュおよびポップします。各スレッドは独自の優先キューを所有しており、それらは個別に割り当てられているため、偽の共有は疑われません。

スニペットよりも長いため、ここにテスト ケースを配置します。(プロセッサ アフィニティ ビットはNCrunchから取得されます)

.NET にはビルトイン キューがなかったため、プライオリティ キューは私自身が作成したものです。違いが生じる場合は、ペアリング ヒープを使用します。

とにかく、1 つのスレッドと 1 つのコアでプログラムを実行すると、約 100% の使用率になります。 2 スレッド/2 コア で使用率が低下し、最終的には 8 コアすべてで 30% の使用率にまで低下します。

パフォーマンスの低下により、マルチスレッド化によるメリットがすべて無効になるため、これは問題です。パフォーマンスの低下の原因は何ですか? 各キューは他のスレッドから完全に独立しています

Pairing heapを読んでいます。

とてもシンプルで、難しいのはdelete_min操作だけです。

唯一の重要な基本操作は、ヒープからの最小要素の削除です。標準的な戦略では、最初にサブヒープをペアでマージし (これは、このデータ構造にその名前を付けたステップです)、次にヒープの結果のリストを右から左にマージします。

wiki リンクにあるので、ここにコードをコピーして貼り付ける必要はないと思います。

私の質問は

1. なぜ彼らはこの2つのパスのマージを行うのですか?

2. なぜ最初にペアをマージするのですか? それらすべてを直接マージしませんか？

3. また、ペアをマージした後、特に右から左にマージするのはなぜですか?

コードでペアリングしようとしていますが、通常のデバイスでしか機能しません。Bluetooth スキャナーを使用するとペアリングされますが、Android の設定に移動して [入力デバイス] チェックボックスを選択するまで、デバイスは機能しません。コードでこれを行うにはどうすればよいですか?

ありがとうございました。

これが私のペアリングコードです：

以下では、ハンガリーのアルゴリズムの複数の割り当ての問題に直面しています。

シナリオ：

100名の学生と5つのコースがあり、学生が優先的に投票できます。そのため、すべての学生が 1 つの特定のコースに割り当てられます。

1 から 5 までの優先度。1 が最低、5 が最高

生データは次のようになります。

明らかに、列よりも行の方が多いです。

私たちが直面している問題は、列ごとに複数の割り当てが必要なことです。

以下は、無効な結果を返すハンガリーのアルゴリズムで代入を行う PHP コードです。

編集: これは、有効な結果を返す Sktip です。

注: しばらくお待ちください。これは Java からの低品質の移植です。

したがって、アルゴリズムはこれの正方行列を作成しているため、結果は破損したデータを示します。

さまざまな解決策を考えました。

列のサイズに合わせて行列を切り取り、多数の正方行列を生成します。これにより、アルゴリズムのメイン関数が壊れる可能性があります。

もう 1 つの解決策は、可能な限り割り当てを行い、エントリがなくなるまで残りを新しいルーチンで処理することです。

どうやら、アルゴリズムはまだこの機能を提供していません。

MySQLでこれを行うための解決策があるかもしれません。したがって、生データはMySQL DBSに保存されます。