問題タブ [disjoint-sets]

質問する

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.

182 問題
Newest
Active
Bountied
318
Unanswered
0 投票する
1 に答える
1546 参照

algorithm - apache spark のばらばらなセット

apache spark を使用して、大量のデータでばらばらなセット (接続されたコンポーネント/ユニオン検索) を検索するアルゴリズムを見つけようとしています。問題はデータ量です。グラフ頂点の Raw 表現でさえ、単一のマシンの RAM には収まりません。エッジもラムに収まりません。

ソース データは、hdfs 上のグラフ エッジのテキスト ファイル: "id1 \t id2" です。

int ではなく文字列値として存在する id。

私が見つけた単純な解決策は次のとおりです。

  1. エッジの rdd を取る ->[id1:id2] [id3:id4] [id1:id3]
  2. エッジをキーでグループ化します。->[id1:[id2;id3]][id3:[id4]]
  3. 各レコードに対して、各グループに最小 ID を設定 ->(flatMap) [id1:id1][id2:id1][id3:id1][id3:id3][id4:id3]
  4. ステージ3から逆rdd[id2:id1] -> [id1:id2]
  5. leftOuterJoinステージ 3 および 4 の rdds の
  6. ステップ3のrddのサイズが変わらない間、ステージ2から繰り返します

ただし、これにより、ノード間で大量のデータが転送されます (シャッフル)。

何かアドバイスはありますか？

0 投票する
1 に答える
1615 参照

c++ - ランクとパス圧縮アルゴリズムによる結合における「ランク」の重要性は何ですか?

私はこのようにアルゴリズムを理解しています...

  • パス圧縮により、検索操作の時間が短縮され、パス圧縮の時間の複雑さが平均して O(1) になります。

  • ランクを見て、2 つのうちどちらが親ノードであるか (ユニオン操作中) を決定します。

しかし、ランクごとの結合が何をするのか理解できませんでした。ここでランクが何を意味するのかを正しく理解しているとは思えません。また、結合する2つのセットのランクが同じ場合、結合中に親のランクが1増加する理由もわかりません。

0 投票する
1 に答える
550 参照

c++ - boost::disjoint_sets_with_storage について

boost::disjoint_sets_with_storageを理解しようとしていますが、可能な限り単純な例でさえ機能せず、その理由がわかりません。

上記のコードはコンパイルされますが、segfault が発生します。要素として整数を使用したいのですが、ブーストのドキュメントには「要素」テンプレート パラメーターがないため、型を推測すると仮定します。しかし、問題は何ですか？ありがとう

0 投票する
1 に答える
1025 参照

algorithm - 最小カットでグラフを同じサイズの素集合に分割する

グラフ ノードを次の条件を満たす 2 つ以上のばらばらなセットに分割するアルゴリズムまたはコードはありますか。まず、エッジのみを削除できます。次に、エッジに重みが付けられ、削除されるエッジには最小の重みが必要です (最小カット アルゴリズム)。第三に、望ましいばらばらのセットは、可能な限り同じサイズを持ちます。

0 投票する
1 に答える
863 参照

algorithm - Union-Find はグラフとどのように関連し、また異なるのでしょうか?

前者はデータ構造、後者は数学的構造と理解しています。

しかし、実装すると、同じ機能と動作の多くを共有しているように見えます。

素集合の各要素は、グラフの頂点と見なすことができます。Union-Find のセットを表すグラフのエッジを使用します。

http://algs4.cs.princeton.edu/15uf/およびhttp://algs4.cs.princeton.edu/42digraph/を確認した後

どちらも次のような質問に答えることができると思います。

  • これらの 2 つの要素/頂点は接続されていますか?
  • サイクルはありますか？

それで、私が見ていない2つの間に大きな違いはありますか? いつどちらを使用するかを選択する必要がありますか?

グラフ アルゴリズムが Union-Find 構造を内部的に使用できることがわかります http://algs4.cs.princeton.edu/43mst/KruskalMST.java.html

実装の詳細ですが、Union-Find の方が高速である場合、深さ優先検索を使用してサイクルをテストするのはなぜですか? http://algs4.cs.princeton.edu/44sp/DirectedCycle.java.html


12345678910