問題タブ [union-find]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
algorithm - union-find アルゴリズムの時間の複雑さを分析していますか?
ユニオン検索アルゴリズムの時間の複雑さを分析するための簡潔で簡単なアプローチを教えてください。2 つのケースで 1. 標準的なアプローチ 2. 加重和集合ヒューリスティック アプローチ
標準バージョンでは、その時間の複雑さはO(n^2) であり、重み付きユニオン ヒューリスティック アプローチの場合はO(m + n logn) です。
しかし、私はそれがどのように来ているのかわかりません。仮定: n 個の要素とリンクされたリストのデータ構造があり、各ノードがリストの先頭を指している、m=make set 操作があるとします。
algorithm - 等値演算子と不等値演算子の最適化
比較するには非常に高価な構造がいくつかあります。(実際には、別個の枝を持つツリーです。) それらのハッシュ値の計算にもコストがかかります。
処理を高速化するために一部の結果をキャッシュするeq演算子のデコレータを作成したいと考えています。これは、メモ化にいくぶん似ています。
特に、このようなことが起こってほしいです。A、B、C の 3 つのオブジェクトがあるとします。A と B を比較します。eq演算子が呼び出され、True が返され、結果が格納されます。B と C を比較します。前と同じようにeq演算子が呼び出されます。次に、A と C を比較します。アルゴリズムは、A が B に等しく、B が C に等しいことを検出する必要があるため、コストのかかるeq演算子を呼び出すことなく、A が C に等しいことを返す必要があります。
union-find アルゴリズムを使用したかったのですが、等式のキャッシュのみが許可され、不等式のキャッシュは許可されません。
互いに等しい 2 つのオブジェクト、A と B があるとします。また、等しいオブジェクトの別のペア、C と D があるとします。和集合検索アルゴリズムは、それらを 2 つのカテゴリ (A、B) および (C) に正しくグループ化します。 、D)。ここで、A がC と等しくないと仮定します。私のアルゴリズムは何らかの方法でそれをキャッシュし、 eq演算子が (A, C)、(B, C)、(A, D)、(B, D) のペアで実行されないようにする必要があります。これらのペアはすべて等しくないと推測できます。Union-find はそれを許可しません。正の等式のみを保存し、多くの等しくないオブジェクトを比較する必要がある場合は惨めに失敗します。
私の現在の解決策は次のようなものです：
ハッシュ関数の計算が簡単であれば、この解決策は問題ありませんが、そうではありません。等しい可能性が高いオブジェクトに対して cache.find を呼び出すため、元の等価演算子を呼び出す必要はほとんどありません。しかし、私が言ったように、ハッシュ関数は私のツリーでは非常に遅いです (基本的にすべてのツリーをトラバースし、各ノードのブランチを比較して重複を削除する必要があります)、削除したいと思います。代わりに否定的な結果をキャッシュしたい。
この問題の良い解決策を知っている人はいますか? 肯定的な比較結果だけでなく、否定的な結果もキャッシュする必要があります。
アップデート：
私のために働く私の現在の解決策は次のとおりです。
これにより、eq と hash の両方が高速化されます。
data-structures - 加重ユニオン ルール
最後の手順 (7) でルールを正しく使用しているかどうかを誰かに確認してもらえますか?
アップデート：
括弧内の数字は、Union に参加する各セットの要素数 (重み (?)) です。大文字はセットの名前です。
私が理解しているように、要素の数をランクとして使用していますか? これは紛らわしくなっており、それぞれが同じものに対して異なる用語を使用しています。
組合があります：
- U(1,2,A)
- U(3,4,B)
- U(A,B,C)
- U(5,6,D)
- U(7,8,E)
- U(D,C,F)
- U(E,F,G)
java - 多数のオブジェクトを使用した Union-Find アルゴリズムの処理
パス圧縮を使用して UnionFind 構造アルゴリズムを実装しようとすると、(stackoverflow (hehe) ではなく) Find アルゴリズムに問題があります。
私はintの標準配列を持っていますが、配列はかなり大きくなる可能性があります-> 60.000.000要素までは正常に動作します。
私のユニオン関数は次のようになります。
私の isInSameSet は次のようになります。
私は検索で反復的な方法を試しました:
および末尾再帰:
私のコードで見逃したものはありますか? この種の問題に対する他のアプローチはありますか？
@edit: コンストラクターをコードに追加:
@edit2（より良い説明と新しい発見）：60.000.000要素未満の場合、問題はstackoverflowになくなりました。これは、私の問題を解決するのに十分です。
私は次のようにテストユニオンを呼び出しています:
したがって、エンディングのペアは次のようになります。
これは、手段のみをテストするための最も最適でないオプションの例にすぎません:)
次に、0 の代表がテーブルの最後の要素 (100 要素の場合は 99) であるかどうかを確認し、それが機能するようにします。
問題は、初期要素がそれぞれ独自の結合 (0:0、1:1、2:2、3:3) にある場合にのみ、私のアルゴリズムが機能することです。すでに別のユニオン (0:2、1:6、2:1、3:5、...) を設定している場合、テスト アルゴリズムが機能しなくなります。
私はそれを検索機能の問題に絞り込みました。おそらくパス圧縮に関係しています