檢查點是否已經在矢量/列表 - 性能

我點即會，例如，存儲100K +點的矢量。

std::vector<Point> point_vec;

我要檢查，如果要添加的位置（x，Y，Z）是已經在point_vec（由class Point實例表示）。下面的函數將檢查這個（在for環）

bool samePoints(const Point& p1, 
       const double x1, 
       const double y1, 
       const double z1) { 

    return fabs(p1.x - x1) < EPSILON && 
      fabs(p1.y - y1) < EPSILON && 
      fabs(p1.z - z1) < EPSILON; 
}

但是，我想檢查是否x in list/ vector將是一個代價高昂的操作。我想知道是否有更好的方法來檢查a）點是否相等（可能是類Point上的運算符「=」和（b）是否存在其他更好的數據結構，而不是我應該創建的「vector」如果在矢量上有一個操作會加快檢查'相同點'

對於（b）請注意，我需要對std :: sort進行排序，所以任何其他的數據結構你可以建議應該能夠對這些點進行排序。

UPDATE

我想只有分類狀態的點。這僅僅是載體不排序的（所以我需要進行排序化經營ñ。我應該使用std::set<Point> point_set而不是std::vector <Point> point_vec嗎？如果是這樣：是否將每個點添加到一個昂貴的操作？或者，我最終做的「向量」排序結果總體上代價高昂？

來源

2010-02-20 memC

點總是排序的集合還是它有時必須處於未排序狀態？如果前者，std：;點集將快速確定一個點是否已經存在，並且將按排序順序維護這些點。你將不得不提供一個合適的排序功能（不是平等的），這可能比你的平等測試更快。

來源

2010-02-20 13:09:54

@neil：嗨！點的集合從開始就是* not *在排序狀態。但是，最後，我確實希望所有點都是'排序'的。因此，我並不需要'未排序'點。所以你是否首先使用'std :: set point_set'而不是'std :: vector point_vec'來推薦？ – memC

@memC如果排序和查找速度是最重要的是。但集合不支持其他操作，例如，您可能需要的使用op []的隨機訪問。另一種方法是按排序順序維護矢量，並使用二分查找來檢查特定點是否在那裏。 – 2010-02-20 13:23:56

@尼爾：不好意思，但是你的意思是「合適的訂購功能」？ – memC

std::set內部排序項目。你只需要提供比較功能。

來源

2010-02-20 13:10:09 Vlad

STL集或hash_set可能會有所幫助。構建結構比構建矢量或列表要慢，但查找點會快得多。

或者，您也可以使用四叉樹或八叉樹。

來源

2010-02-20 13:10:44 Patrick

注意：只有當你的點有整數座標時，hash_set纔會起作用。 – Patrick

@Neil，我的意思是sets和hash_sets，而不是地圖（我對此有點太快）。 – Patrick

雖然Niel和Vlad有正確的想法，但他們忽略了一個特別重要的細節：如果你想成爲一個一維比較器，你不可能明智地訂購N維點只糾正到epsilon而不是完全正確。

Patrick在四叉樹/八叉樹目標上，但沒有使用散列哈希隱式地需要一個映射，其中所有在3D中關閉的項必須在1D（沿着散列）靠近映射，這是不可能的。

因此，假設您可以使用一個比較線性排序的一組開始喜歡

x1<x2 || (x1==x2 && (y1<y2 || (y1==y2 && z1<z2))

這裏就是你需要做什麼：

把你的矢量和沿每個減小量尺寸。對該元素的索引進行二進制搜索（如果有的話）。打電話i0
帶上你的矢量，並沿每個維度添加epsilon。對該索引進行二進制搜索。呼叫i1
搜索i0和i1線性之間的一切，看看是否有這些其實都是你的載體的小量內每尺寸（不只是在一維排序方向）。

如果你的點是隨機分佈的，這將比構造一個八叉樹更快。如果你的點傾向於沿着直線下降（例如，對於許多z，x1 == x2，y1 == y2），那麼這個方案通常會挑選出大量的列表作爲使用線性排序不可區分的列表，而應該使用一個oct快速搜索的樹。

來源

2010-02-20 15:23:26

檢查點是否已經在矢量/列表 - 性能

回答

相關問題