C++（およびQt）を使用すると、大量の3D座標を処理する必要があります。3D座標がすでに使用されているかどうかを調べる最速の方法
具体的には、3次元座標（3倍）を受け取った場合、この座標がすでに処理されているかどうかをチェックする必要があります。 そうでなければ、それを処理してリスト（またはコンテナ）に追加します。
座標の量が非常に大きくなることができますので、私は、3D座標がすでにコンテナに含まれているかどうかをチェックすることは、高速であることが保証されますコンテナで処理された座標を格納する必要があります。
マップのマップを使用して、x座標を格納し、次にy座標をz座標に格納することを考えていましたが、これはかなり面倒です。実際には私が考えることができないそれを行うためのより良い方法。
このような処理を高速化する最も簡単な方法は、既に処理された点をOctreeに保存することです。重複のチェックは対数に近づくでしょう。
また、座標の平等ではなく、ポイント間の距離を確認することで丸め誤差を許容するようにしてください。
よく、それは最も重要なことに依存します...トリプルマップが使いすぎて、それ以外のデータ構造を実装しようとするのではないでしょうか？
トリプルマップソリューションの醜さを回避したい場合は、3つのパラメータを持つアクセス関数を使用して別のコンテナクラスにラップし、それを内部的に地図で囲むことをすべて隠すだけです。
あなたはこの事の実行時のパフォーマンスの詳細心配している場合は、Octreeの座標を格納することは良い考えかもしれません。
浮動小数点数または倍精度でこれらの種類を実行すると、（0、0、0.01）（0、0、0.01000001）と同じ座標の場合、精度に非常に注意する必要があります。そうであれば、データ構造にかかわらず、使用する比較関数を調べる必要があります。それはまたあなたの座標のソースにも依存します。
正確なマッチが必要ですか？これらはダブルスで実行するのが難しいかもしれません。たとえば、（1.0,1.0,1.0）を処理して（0.9999999999999,1.0,1.0）受け取ったとしますか？そうであれば、ある種の近似を適用するか、エラー境界を定義する必要があります。
しかし、質問自体に答えるために：まず思い浮かぶの方法を単一のインデックス（文字列またはビット列のいずれか、あなたは物事がなりたい方法を読める応じて）を作成することです。たとえば、文字列 "（1.0,1.0,1.0）"を作成し、これをマップのキーとして使用します。これにより、マップを簡単に参照できるようになり、コードを読み取り可能にします（また、デバッグ目的でマップの内容を簡単にダンプすることができます）。はるかに高速なパフォーマンスが必要な場合は、文字列を経由せずに数値的に3つの座標を結合するハッシュアルゴリズムを使用することができます。
座標にboost :: tupleを使用し、タプルをマップのインデックスとして保存する方法はありますか？
（あなたは、この回答から除算イプシロンアイデアを実行する必要があるかもしれません。）
1つの単位は、許容可能な小箱と未だの整数部分を説明するようにすることにより座標をスケーリングするために一定のピック絶対値で最大の成分は32ビットの整数に収まります。結果のX、Y、Z成分を整数に変換し、一緒にハッシュします。これをマップやハッシュテーブルのハッシュ関数として使用します（配列インデックスとしてではなく、衝突に対処する必要があります）。
また、わずかに異なる浮動小数点値を取得する可能性があるため、座標を比較する際にファジィファクターを使用することを検討することもできます。レンダリング時の亀裂を避けるためにそれらを一緒に溶接することが通常です。
3D座標のユニークな変換を使用し、結果のリストのみを保存します。
例： md5（ 'X、Y、Z'）は一意であり、結果の文字列のみを保存できます。
ハッシュは優れたアイデアではありませんが、あなたはその概念を得ています。あらゆる独特な変容を見つけ、あなたはそれを持っています。
/VEY
あなたは、単純なパブリックインターフェイスを持つヘルパークラスを記述する場合は、それが大幅にmap<map<map<>>>の使用のような実装の詳細の実用的な退屈を軽減します。カプセル化の美しさ！
これは、トリックをうまくやるためにハッシュマップを作成することができるかもしれないと言いました。 3つのダブルスを一緒にハッシュして、ポイント全体のキーを取得します。対称座標（例えば（1,2,3）や（3,2,1）など）を持つポイント間の衝突が心配されている場合は、ハッシュキーをx、yに対して非対称にするだけです、およびz座標を使用して、ビットシフトなどを使用します。
ハッシュ可能なタイプのhash_setを使用できます。たとえば、各タプルを "（x、y、z）"という文字列に変換できます。 hash_setは高速ルックアップを行いますが、衝突をうまく処理します。
どのような保存方法であっても、ε（2つの座標を区別する最小浮動小数点距離）を決定し、すべての座標をεで除算し、整数として格納することをお勧めします。
多分この方向で何か：
struct Coor {
Coor(double x, double y, double z)
: X(x), Y(y), Z(z) {}
double X, Y, Z;
}
struct coords_thesame
{
bool operator()(const Coor& c1, const Coor& c2) const {
return c1.X == c2.X && c1.Y == c2.Y && c1.Z == c2.Z;
}
};
std::hash_map<Coor, bool, hash<Coor>, coords_thesame> m_SeenCoordinates;
テストされていない、あなた自身の危険を覚悟で使用:)
ダブルスは実生活でそのように比較されていません... –
座標がどこにあるかによって、丸めが座標が作られたポイントで行われた場合は、==をdoubleに使うことができます。彼らが '自由形式'と計算された場合、はい、イプシロンと比較する必要があります。 – Roel
すでに、クラスを座標ハッシュ関数を追加し、座標のhash_setを維持していると仮定。個別のビンに
struct coord_eq
{
bool operator()(const Coordinate &s1, const Coordinate &s2) const
{
return s1 == s2;
// or: return s1.x() == s2.x() && s1.y() == s2.y() && s1.z() == s2.z();
}
};
struct coord_hash
{
size_t operator()(const Coordinate &s) const
{
union {double d, unsigned long ul} c[3];
c[0].d = s.x();
c[1].d = s.y();
c[2].d = s.z();
return static_cast<size_t> ((3 * c[0].ul)^(5 * c[1].ul)^(7 * c[2].ul));
}
};
std::hash_map<Coordinate, coord_hash, coord_eq> existing_coords;
デバイドあなたのスペース： は、次のようになります。無限に深い四角形であっても、キューブであってもかまいません。処理された座標を単純なリンクリストに格納します。各ビンに好きな場合はソートされます。新しい座標を取得すると、囲みビンにジャンプし、リストを歩いて新しいポイントを探します。
浮動小数点比較に注意してください。値を整数に変換する（例えば、1000を乗算してトランケートする）か、2つの値がどれくらい近いかを判断する必要があります。
1レベルのコンパレータを簡単に定義することができます（std::map）ので、参照が煩雑にならないようになります。それを恐れる理由はありません。コンパレータは、マップの_Keyテンプレート引数の順序を定義します。マルチマップと集合コレクションにも使用できます。
例：
#include <map>
#include <cassert>
struct Point {
double x, y, z;
};
struct PointResult {
};
PointResult point_function(const Point& p) { return PointResult(); }
// helper: binary function for comparison of two points
struct point_compare {
bool operator()(const Point& p1, const Point& p2) const {
return p1.x < p2.x
|| (p1.x == p2.x && (p1.y < p2.y
|| (p1.y == p2.y && p1.z < p2.z)
)
);
}
};
typedef std::map<Point, PointResult, point_compare> pointmap;
int _tmain(int argc, _TCHAR* argv[])
{
pointmap pm;
Point p1 = { 0.0, 0.0, 0.0 };
Point p2 = { 0.1, 1.0, 1.0 };
pm[ p1 ] = point_function(p1);
pm[ p2 ] = point_function(p2);
assert(pm.find(p2) != pm.end());
return 0;
}
がのstd ::セットを使用してください。オペレータ<が定義されている3次元座標の型を定義します（またはboost :: tupleを使用します）。要素を追加するときは、それをセットに追加することができ、追加された場合は処理を行います。追加されていない場合（既にそこに存在しているため）、処理しないでください。
ただし、ダブルスを使用している場合は、アルゴリズムが予測できない動作につながる可能性があることに注意してください。 IE（1.0,1.0,1.0）は（1.0,1.0,1.000000001）と同じですか？
これを行うにはいくつかの方法がありますが、まずあなたの前提と条件は何かを尋ねなければなりません。
したがって、あなたのスペースのサイズが限られていて、最大正確さが分かっていると仮定すると、（x、y、z）を与えて一意の数または文字列に変換する関数を作成できます。正確さが限定されていることが分かっている場合（例えば、2つのエンティティが同じ立方センチメートルを占めることはできません）の場合にのみ実行してください。 座標をエンコードすると、O（1）で1つのマップ/ハッシュを使用できます。
もしあなたが示唆したように3つの埋め込みマップを使用することも、平均探索でO（logN）を与えたにもかかわらずOcTreeなどの空間分割アルゴリズムに向かうこともできますあなたが望むかもしれない追加情報（隣人、人口など）は、実装することはもちろん困難です。
次のように簡単にセットを使用することができます。
#include <set>
#include <cassert>
const double epsilon(1e-8);
class Coordinate {
public:
Coordinate(double x, double y, double z) :
x_(x), y_(y), z_(z) {}
private:
double x_;
double y_;
double z_;
friend bool operator<(const Coordinate& cl, const Coordinate& cr);
};
bool operator<(const Coordinate& cl, const Coordinate& cr) {
if (cl.x_ < cr.x_ - epsilon) return true;
if (cl.x_ > cr.x_ + epsilon) return false;
if (cl.y_ < cr.y_ - epsilon) return true;
if (cl.y_ > cr.y_ + epsilon) return false;
if (cl.z_ < cr.z_ - epsilon) return true;
return false;
}
typedef std::set<Coordinate> Coordinates;
// Not thread safe!
// Return true if real processing is done
bool Process(const Coordinate& coordinate) {
static Coordinates usedCoordinates;
// Already processed?
if (usedCoordinates.find(coordinate) != usedCoordinates.end()) {
return false;
}
usedCoordinates.insert(coordinate);
// Here goes your processing code
return true;
}
// Test it
int main() {
assert(Process(Coordinate(1, 2, 3)));
assert(Process(Coordinate(1, 3, 3)));
assert(!Process(Coordinate(1, 3, 3)));
assert(!Process(Coordinate(1+epsilon/2, 2, 3)));
}
あなたは、3Dのstd::set座標、またはソートstd::vectorを使用することができます。どちらも対数時間ルックアップを提供します。どちらの場合でも、3D座標クラスに比較演算子以下を実装する必要があります。
なぜ気になるのですか？あなたは何を「処理中」していますか？非常に複雑でない限り、巨大な地図やハッシュテーブルで物事を見て時間を浪費するのではなく、計算をやり直す方が速いでしょう。
これは、最新のCPUについてより直観的なものの1つです。計算は高速で、メモリは低速です。
私はそれがあなたの質問に疑問だ、これは本当にあなたの質問への答えではありません実現しています。この種の問題は、グラフィカル・科学アプリケーションで何回も をアップしますので
しかし、（初期の最適化==ルート（悪））！=（パフォーマンスは問題ありません） – sum1stolemyname
良い質問...それは、多くのソリューションを持っている一つです。
あなたが必要とするソリューションによっては、フードの下ではかなり複雑かもしれませんが、 ケースが少なくても必ずしも高速であるとは限りません。
が ---一般的に、あなたは のtypedefやラッパークラスでこれを回避することができます「しかし、これは、それはかなり退屈使用できるようになります」（この場合はラッパーを強く推奨されます）。
3D座標を空間的に意味のある方法で使用する必要がない場合は（ 「ポイントPのX距離以内にすべてのポイントを与える」のようなもの）、 各ポイントをハッシュして、単一のハッシュマップ... O（n）の作成、O（1） アクセス（処理済みかどうかを確認する）を使用すると、それ以上のことはできません。
さらに詳しい情報が必要な場合は、明示的に が必要なコンテナが必要です。 選択したコンテナのタイプは、データセットに依存します。あなたが良い場合は あなたが受け取る値の範囲の知識があれば役立ちます。
既知の範囲でよく分散されたデータを受信する場合は、octreeとしてください。
分散する傾向がある場合は、k-d treesとしてください。新しい座標を入力した後にk-dツリーを再構築するには、 が必要です（必ずしも過度に不均衡になったときに必ずしもそうであるとは限りません）。簡単に言えば、Kd-treesはOctreesと似ていますが、不均一な分割があります。
これをより高いレベルで処理する可能性はありますか？たとえば、座標を制御できる場合は、処理されたかどうかを示すフラグが含まれている可能性があります。 –