問題タブ [set-intersection]

2 つのセット (C++) が与えられた場合、割り当てなしで交差点のサイズを取得する便利な方法があります (std::set_intersection のように)

確かに、実装から割り当てを差し引いたものをコピーすることはできますが、私は常に車輪を再発明することはしません

std::set_intersection を使用して「カウント」インターレーターを渡すことを検討していました...?

効率的な時間で 2 セットの交差セットを取得する方法について多くのクエリを探しています。そして、非常に効率的な方法を探しています。私自身の方法に近づく前に、Javaに同じことを実行するメソッドを構築するように依頼できないのはなぜですか。なぜ Java は、ソート メソッドやコレクションのどこかに、コレクション クラスの交差のようなメソッドを構築していないのですか? この背後にある理由はありますか？

これは、セット上の交差のフィットフォールに関する議論であると考えてください。

ありがとう、

解決する必要がある問題がありますが、これはやや単純ですが、解決できません。どんな助けでも大歓迎です。

わかった。100 万件のレコードのデータセットがあります。

Origin には 2 つのオプションがあります: [Credit, Current]

ここで、PersonGUID が Credit と Current の両方に少なくとも 1 行あるトランザクションのみにフィルターをかける必要があります。

これは PythonPandas で簡単に実行でき、CSV にロードできますが、すべてのデータのダッシュボードを作成するので、2 つのデータセットは必要ありません。

ブール論理計算フィールドを推測していますが、うまくいきません。

ありがとう

ロブ

私は非常に簡潔で直感的な C++ 構文を使用して、2 つのソート済み の共通部分を見つけ、vectorその結果を 3 番目の に入れていvectorます。

これは、がソートされていると仮定して、 cintersection( a, ) に設定する必要があります。bab

しかし、単に使用するとどうなりますc.begin()か (これのどこかで例を見たと思ったので、そうしました):

set_intersectionそのパラメータで を期待OutputIteratorします。私が信じている標準では、 a を返すことだけが必要c.begin()です。forward iteratorOutputIterator

とにかく、c.begin()clangの下でコンパイルされたコード。

標準で保証されていることは何ですか? これがコンパイルされた場合、何が起こる可能性がありますか?つまり、によって返されたイテレータc.begin()が最終的にベクターの終わりを超えてインクリメントされ、ポイントされた要素にアクセスしようとすると、何が起こる必要がありますか? この場合、適合する実装はサイレントにベクトルを拡張できるのでbegin()、実際には追加OutputIteratorのようなものback_inserterですか?

私は主に、標準がイテレータでどのように機能するかを理解するためにこれを求めています。つまり、実際に何が起こっているのかを理解して、STL を使用してコピーアンドペーストを超えて移動できるようにします。

可変数のセット (数nと呼びましょう) があり、それぞれに最大で m 個の要素がある場合、セットのすべてのペアのペアごとの交差を計算する最も効率的な方法は何ですか? これは、 n 個すべての集合の交点とは異なることに注意してください。

たとえば、次のセットがあるとします。

私は見つけることができるようにしたい:

もう 1 つの許容される形式 (簡単にする場合) は、特定のセット内のアイテムの、同じアイテムを含むセットへのマップです。例えば：

その方法の 1 つは、 n 個すべてのセットの和集合の各値をそれが発生するセットのリストにマッピングする辞書を作成し、それらのすべての値を繰り返し処理してintersections_C上記のようなリストを作成することであることはわかっていますが、nが増加し、セットのサイズが大きくなりすぎると、それがどのようにスケーリングするかはわかりません。

いくつかの追加の背景情報:

1. 各セットはほぼ同じ長さですが、非常に大きい (すべてをメモリに格納するのが現実的な問題であり、必須ではありませんが、それを回避するアルゴリズムが望ましい)。
2. 任意の 2 つのセット間の交点のサイズは、セット自体のサイズに比べて非常に小さい
3. それが役に立てば、入力セットの順序付けについて必要なことは何でも想定できます。

整数を使って単純な「交差」操作を大量に実行しようとしています。残念ながら、セットアップで numpy/scipy を利用できず、それを変更することはできません。

スタックオーバーフローで、Python の set操作がデータを適切に並べ替えていることに気付きました。これは、ケースのロードを高速化するだけでなく、私の場合、実際にデータも並べ替えたいので、素晴らしいボーナスになるでしょう。

いつもうまくいくとは限らないのではないかと心配しているので、テストに行きました：

その結果、すべてのサンプルがソートされます (間違ったケースは印刷されません)。

これは非常に説得力がありますが、集合交差を使用するときに整数が完全にソートされない場合があるかどうかを知りたいですか?

セットのリストがあります：

セットの全方向の比較が必要です。これは、2^n 個のセットです。

Javaでこれを行う最良の方法は何ですか?

たとえば、5 セットしか使用していなかったとします。5 円のベン図のすべての重なりにデータを入力できるようにしたいと考えています。

私はセットのリストでこれをやろうとしています:

次のような結果を見つけたいと思います。

基本的に私が求めているのは、セットユニオンと組み合わせたパワーセットアルゴリズムを適用する方法です。

次の問題を効率的に処理するための特定のデータ構造/アルゴリズムを知っている人はいますか?

Aセットとセットのセットが与えられた場合、S = {X,Y,Z..}A と S のすべてのセットの間の交差のサイズを計算したいと思います。それらのほとんどが互いに素ではない、つまり共有数であるという事実を利用します。

例: と が与えられたA = {1,2...10}場合、X = {1,3,4,5,7}と、、 、およびの交点を計算し、結果を合計する 方Y = {2,4,5,7,9,10}が効率的です。AX intersect YAX - X intersect YAY - X intersect Y

実際の例としては、テキストの一部を共有する大量のドキュメント セットでキーワードの出現回数を見つけることができます (合計ではなく、ドキュメントごとです)。

Map-Reduce との唯一の違いは、ドキュメントがテキストの一部を共有し、それらの部分を 1 回だけ解析する必要があることです。

これが助けになる場合、私が現在問題について推論している方法は、ノードが重なり合っている領域であり、そのO(n)トラバーサルが A と S のすべての要素の間の交差のサイズを与えるグラフ/ツリーです。私が直面している問題使用するノードの最適なセットを見つける方法です。しかし、それに対する既製のソリューションがすでにあるかもしれません。