如何爲搜索應用程序找到正確的數據結構？

我的問題可以在兩個不同的方面提出：一個是從數據結構的角度來看，另一個是從圖像處理的角度。讓我們從數據結構的角度開始：現在假設我有一個幾個小的項目，如以下類組成成分示出了：如何爲搜索應用程序找到正確的數據結構？

class Component 
{ 
public: 
    struct Point 
    { 
    float x_; 
    float y_; 
    }; 
    Point center; 
    Point bottom; 
    Point top; 
}

在上述例子中，Component類是由成員變量如中心，底部的和頂部（小物品）。

現在我有一堆組件（組件數量在1000到10000之間），並且堆棧中的每個組件都被分配了不同的值，這意味着堆棧中沒有重複的組件。然後，如果組件中的一個小項目（例如所示類中的'center'）是已知的，我們可以在堆棧中找到唯一的組件。之後，我們可以檢索組件中的其他屬性。那麼我的問題是，如何構建一個正確的容器數據結構以使搜索更容易？現在我正在考慮使用矢量和STL發現算法（僞）：

vector<Component> comArray; 
comArray.push_back(component1); 
..... 
comArray.push_back(componentn); 
find(comArray.begin(), comArray.end(), center);

我想知道是否有更有效的容器來解決這個問題

我還可以從圖像處理解釋我的問題。在圖像處理中，連接組件分析是目標識別的一個非常重要的步驟，現在我的應用程序可以獲取圖像中的所有連接組件，並且我還發現有趣的對象應該滿足以下要求：它們的連接組件中心應該在特定的範圍內，因此，由於這個約束，我可以消除許多連接的組件，然後在候選組件上工作上述過程中的p是如果給出中心座標約束，如何搜索候選連通分量。任何想法將不勝感激。

來源

2012-07-27 feelfree

你需要能夠搜索每個領域？ – SingerOfTheFall 2012-07-27 09:34:00

否。實際上，組件中的每個項目都可以用作關鍵字搜索詞。在這個問題中，我使用「中心」作爲搜索關鍵詞。也可以只使用'底部'或'頂部'。 – feelfree 2012-07-27 09:36:14

如果你需要能夠讓他們相當快，這裏有一個奇怪的解決方案給你。

請注意，這是一個不好的解決一般講，但它可能西裝你。

你可以做一個普通的vector<component>。或者甚至可以是一個簡單的數組。然後，讓三張地圖：

map< Point, Component *>center 
map< Point, Component *>bottom 
map< Point, Component *>top

與center，bottom和top作爲鑰匙的所有可用值填充它們，並以相應的組件值提供指針（你也可以在一個向量只使用索引，所以它將是map< Point, int >）。

之後，你只需要使用center[Key]，bottom[Key]或top[Key]，並獲得無論是你的價值（如果您存儲指針），或數組中的值的索引（如果您存儲索引）。

我不會經常使用這種方法，但它可以工作，如果值不會改變（所以你可以填充索引圖一次），並且數據量是相當大的（所以通過未分類搜索矢量很慢），和您需要經常搜索。

來源

2012-07-27 09:40:26 SingerOfTheFall

'map'查找是O（log（n）），而不是O（1）。 – 2012-07-27 10:07:46

@Yurikilochek，是的，你是對的，謝謝 – SingerOfTheFall 2012-07-27 10:10:16

這是一個很好的解決方案，在我的情況下，值不會改變，因此我可以填充索引圖一次。 – feelfree 2012-07-27 10:50:38

我想你想用map或hash_map來根據「中心」值有效地查找你的組件。

std::map<Component::Point, Component> lookuptable; 
lookuptable[component1.center] = component1; 

.... 

auto iterator = lookuptable.find(someCenterValue) 
if (iterator != lookuptable.end()) 
{ 
    componentN = iterator->second; 
}

至於在你的集合中找到在給定的協調範圍內的元素。有幾種方法可以做到這一點。一種簡單的方法是隻需要有兩個排序的元件列表陣列，一個排列在X軸上，另一個排列在Y軸上。然後，爲了找到匹配的元素，您只需在離您目標最近的那個軸上進行二進制搜索。然後展開掃描陣列，直到您超出範圍。你也可以看看使用kd-tree並找到所有最近的鄰居。

來源

2012-07-27 09:34:42 selbie

使用'unordered_map'精確搜索浮點數可能會產生意想不到的結果。與'地圖'的一維。 – 2012-07-27 09:38:25

好點。他可以考慮將他的浮點數歸一化爲整數表示。地圖是1-d的事實對單個元素查找來說很好。 – selbie 2012-07-27 09:44:00

您可能想要spatial indexing data structures。

來源

2012-07-27 09:37:17

謝謝，我不熟悉這個主題。在快速瀏覽你提出的鏈接之後，我想知道是否有像STL這樣的庫來使用這些數據結構。你有一些簡單的程序可以遵循嗎？謝謝。 – feelfree 2012-07-27 10:38:59

@feelfree恐怕不是，但是像'quadtree'這樣的谷歌搜索的東西肯定會變成一些東西。 – 2012-07-27 11:12:15

如果您想在常量時間訪問它們並且不想修改它們。我認爲std :: set是你的代碼的好選擇。

set<Component> comArray; 
comArray.push_back(component1); 
..... 
comArray.push_back(componentn); 
set<Component>::iterator iter = comArray.find(center)

當然，您應該爲類Component和嵌套struct Point編寫operator ==。

來源

2012-07-27 09:54:00 Shining100

這看起來很有趣，但是你確定在std :: set中搜索會花費const時間嗎？對不起，我找不到任何關於它的文件。 – feelfree 2012-07-27 10:08:15

@feelfree它不是。 'set'和'map'查找都具有O（log（N））複雜度。 – 2012-07-27 10:12:29

如何爲搜索應用程序找到正確的數據結構？

回答

相關問題