問題タブ [set-intersection]

私は現在、2D の架空の宇宙に数千の星がある趣味のプロジェクトに取り組んでいます。これらの星を画面にレンダリングする必要がありますが、すべての星を操作する必要はなく、常に表示されている星のみを操作する必要があることは明らかです。

概念を証明するために、すべての星を見て、プレイヤーの画面の境界に対してその座標をテストするブルート フォース アルゴリズムを作成しました。

この不格好な方法は、実際には目に見える星だけを画面に描画しますが、明らかに線形時間で動作します。星は背景の一部にすぎず、率直に言って、プロセッサがフィルタリングに時間を費やす最も重要なものではないため、負荷を軽減するためのより高速なアルゴリズムを考案したいと考えています。

したがって、私の現在の考えは、バイナリ検索を使用して関連する星を見つける方法に沿っています。このためには、明らかにデータを並べ替える必要があります。ただし、座標データを並べ替える方法がよくわかりませんでした。(x 座標と y 座標の両方に関して) データを昇順で適切に並べ替えることができる絶対的な順序は考えられませんでした。 .

そこで、2 つの新しいコンテナーを実装しました。1 つは x 座標でソートされたデータ用で、もう 1 つは y 座標でソートされたデータ用です。私の最初の考えは、これらの 2 つの並べ替えられたセットの交点を取得し、結果の星を画面に描画することでした (x 座標と y 座標が画面の境界内にある星)。

次に、これらのコンテナーを並べ替えました。

残念ながら、std::set_intersection の適切な比較関数や、イテレータを使用して手動で座標を比較できる方法を思い付くことができないようです。

私を正しい方向に向けてもらえますか？私の方法論や実装に関するフィードバックは大歓迎です。

御時間ありがとうございます！

C++で2つの範囲の交点を見つける最良の方法は何ですか? たとえば、[1...20] を含む範囲と [13...45] を含む別の範囲がある場合、[13...20] を取得します。

C++ でネイティブの集合交差関数を使用することを考えましたが、最初に範囲を集合に変換する必要があり、大きな値に対して計算時間がかかりすぎます。

まず第一に、私の目的は、両方の既知のセットから 1 つの要素のみをランダムに取得することです。だから私の元の方法は、まず2つのセットを交差させます. そして、交差した集合から要素をランダムにピックアップします。しかし、これはばかげています。必要なのは要素だけで、交差するセットだけだからです。

したがって、set.intersection() のアルゴリズムを見つける必要があります。

「set.intersection()」と「for{for{}}」のメソッドのコスト時間を比較します。Set.intersection() は他のものよりも高速です (100 倍)。したがって、「for{for{}}」を使用してランダムに要素を選択することは賢明ではありません。

Pythonのset.intersection()の背後にあるアルゴリズムは何ですか?

この形式の単一リンクリストでそれぞれ表される2つのセットの交差と差を取得しようとしています

リスト内の要素の数を計算し、特定の要素がリストに含まれているかどうかを判断する前のタスクで、この関数を既に作成しました。

次の関数をコーディングする必要がありますが、その方法がわかりません。1 つのリストをループし、リスト内のすべての要素について 2 番目のリストをループして、2 番目のリストに含まれているかどうか (違い) を確認する必要がありますか? このタスクは複雑に思えますが、もっと簡単な方法があるはずです。あなたが私を助けてくれることを願っています

皆さんこんにちは :) 個人的なセット クラスを作成し、演算子 /= をオーバーロードしたいのですが、私のクラスの場合、この演算子は 2 つのセットのインタースティションを取るために使用する必要があります。次のエラーが発生しました。

エラー: 読み取り専用の場所 '__result.std::_Rb_tree_const_iterator<_Tp>::operator*()' の割り当て

これは私にこのエラーを与えるコードの一部です:

私はC ++を初めて使用し、読み取り専用の場所に何かを割り当てようとしている場所がわかりません...教えてください。set_intersectionを正しく使用する方法を教えてください（ライブラリから

おおよその英語で申し訳ありませんが、すでに助けてくれてありがとう= D

配列とベクトルの交点を取得しようとしています。cplusplus.com が例を示しているため、両方をベクトルにすることにしました。

これは私が得るエラーメッセージです:

ここに私のコードがあります：

関数はgetNumbers()配列を返します。

編集

関数は次のgetNumbers()とおりです。同じ戻り値の型のプロパティを返すだけです。

どのように機能するかを理解しようとしていますthrust::set_intersectionが、テスト結果から、この関数が何をしているのかについてさらに混乱しています。

以下にいくつかの例を示します。

戻り値2, 3, 4, 5

戻り値2, 3, 4, 5, 6

何も返さない

私はデフォルトが何をするかを理解してset_intersectionおり、結果に同意しますが、他の例では、結果がどこから来たのか完全に失われていますか? あるいはどのように計算されたのですか？

このアルゴリズムがどのように機能するかはわかっていますか? 誰かがそれを説明できますか？

編集：

私の目標には、2セットのタプルが与えられます(サイズ2としましょう):

したがって、演算子を満たすすべての要素を返す >< のようなタプルで on 演算子を定義したいと思います。

><のように定義a.first > b.first && a.second < b.second

したがって、答えは A[0] と B[0] のみです。

それで、あなたはこれをset_intersection正しく達成することはできませんか？

編集回答:これらのルールによって、ここ で回答が見つかったことを気にしないでください。そのような演算子は「厳密な弱い順序付け」演算子にはなりません。