約 700,000 エントリのデータ セットがあり、各エントリは、名前、タイムスタンプ、ID などの属性を持つ 3D 座標のセットです。
現在、座標を読み取って OpenGL のポイントとしてレンダリングしています。ただし、各ポイントを対応する属性に関連付けたいと考えており、それらの属性に基づいて実行時にそれらを並べ替えて選択できるようにしたいと考えています。効率的な方法でこれを達成するにはどうすればよいですか？
データを構造体に入れ、並べ替えにstl sortを使用できることはわかっていますが、それは良い設計上の選択ですか、それとも問題を処理するより効率的/エレガントな方法がありますか?
私がこれらのデザインの選択を検討する方法は、最初に標準ライブラリ コンテナーの 1 つを使用することです (ところで、ルックアップを「単に」行う必要がある場合は、必ずしも並べ替える必要はありませんが、ルックアップを許可するコンテナーが必要です)。 、次に、これが問題の「十分に効率的な」解決策であるかどうかを確認します。
通常は、より効率的で洗練されたカスタム ソリューションを考え出すことができますが、それには次の 2 つの問題が発生する傾向があります。
1) 何らかのタイプのコンテナーを実装する必要が生じます。これは、既に存在する十分に理解され、テストされたコンテナーと比較して、実装とデバッグの両方に時間がかかります。ほとんどの場合、コードを追加して問題を大きくするよりも、目の前の問題を解決しようとする方がよいでしょう。
2) ある時点で他の誰かがあなたのコードを保守する必要がある場合、その人は設計と実装の両方の観点から標準ライブラリ コンポーネントに精通している可能性がありますが、カスタム コンテナーには精通していないため、学習曲線が長くなります。
ポイント クラスの各属性をベクトルのコンポーネントと見なす場合、選択プロセスはリージョン クエリになります。文字列属性が何かに等しいという例は、領域が実際にはデータ空間内の行であることを意味します。ただし、その選択内の他の属性に対してソートは行われません。自分で実装する必要がありますが、データを順序付けられた領域に分割する octree の場合は比較的簡単です。
別の回答で提唱されているように、最初に既存の標準ソリューションを試してください。これらのデータ構造のいずれかのシェルフ実装を見つけることができる場合:
それからそれのために行きます。これらは、空間データ管理に推奨するデータ構造です。
空間データを操作できる組み込み RDBMS を使用することもできます (通常、空間インデックス作成用に R ツリーを実装します) が、データセットが動的でない場合は面白くないかもしれません。
データセットが 10000 エントリの範囲内に収まる場合、今日の標準ではそれほど大きくないため、より単純な構造を使用すれば十分です。その境界では、最初に単純なを使用しstd::vector、 と を使用std::sortしstd::findて小さいセットのデータをフィルタリングし、後で並べ替えます。
2 回目の試行では、最もクエリの多い属性で順序付けられたセットまたはマップを試してから、いくつかのベンチマークを実行して、よりパフォーマンスの高いソリューションを選択します。
より効率的な 1 次元のインデックス作成アルゴリズム (本質的には、セットとマップが何であるか) については、B-treesを試してみてください。Googleから入手できる C++ 実装があります。
私の 3 回目の試みは、OpenCL ソリューションに向けたものです (OpenGL レンダリングを大量に実行している場合は、代わりに CPU で作業を行うことを好むかもしれませんが、それはフレームレートのニーズによって異なります)。
データセットがはるかに大きいように思われる場合は、最初にリストしたより複雑なソリューションの 1 つを検討してください。
いずれにせよ、データセットとそれをどのように使用する予定かについての詳細がなければ、適切なソリューションを提供することは難しいため、私たちが提供できる唯一の本当のアドバイスは、できる限りのことを試してベンチマークすることです.