尋找一個有效的數據結構來做一個快速搜索

Question

我有一個1000左右的元素列表。每個元素（我從文件中讀取的對象，因此我可以在開始時有效地安排它們）包含4個變量。所以現在我正在做以下事情，這是非常低效的事情的宏偉計劃：

void func(double value1, double value2, double value3) 
{ 

     fooArr[1000]; 

     for(int i=0;i<1000; ++i) 
     { 
        //they are all numeric! ranges are < 1000 
        if(fooArr[i].a== value1 
         && fooArr[i].b >= value2; 
         && fooArr[i].c <= value2; //yes again value2 
         && fooArr[i].d <= value3; 
        ) 
        { 
          /* yay found now do something!*/ 
        } 
     } 
} 

空間不是太重要！

每個請求

Answer 1

可以對其進行修改空間不是太重要了，最簡單的辦法是創建基於「」根據你有多少衝突得到「A」可能是有意義的哈希使哈希表中的每個節點都指向基於「b」的二叉樹如果b有很多衝突，請對c執行相同的操作。

根據多少次衝突，第一個進入散列的索引將爲很少的編碼或數據結構工作節省大量時間。

Answer 2

看，這只是一個線性搜索。如果你可以做一個更好的搜索，這將是很好的，但是你的複雜匹配要求使我不清楚是否可以保留它並且使用二分搜索。

話雖如此，也許有一種可能性是產生一些索引。主索引可能是a屬性中的一個字典，將其與具有該屬性的相同值的元素列表關聯。假設這個屬性的值是分佈很好的，它會立即消除絕大多數的比較。

如果該屬性的值有限，那麼您可以考慮添加一個附加索引，該索引對b的項目進行排序，甚至可以按c（但順序相反）對其進行排序。

Answer 3

由於您只有三個屬性可以匹配，所以可以使用散列表。執行搜索時，您可以使用散列表（索引a-屬性）來查找匹配SomeConstant的所有條目。之後，你檢查b和c是否也與你的常量相匹配。這樣可以減少比較次數。我認爲這會加快搜索速度。

除此之外，你可以建立三個二叉搜索樹。一個按每個屬性排序。在搜索完他們三個之後，對每個樹中與您的值相匹配的人執行您的操作。

Answer 4

如果您的應用程序已經在使用數據庫，那麼只需將它們放在一個表中並使用查詢來查找它即可。我在我的一些應用程序中使用mysql，並會推薦它。

Answer 5

首先，在增加a和減少b時對列表進行排序。然後建立一個索引（值從0到999的整數所以，我們已經有了

int a_index[1001]; // contains starting subscript for each value 
a_index[1000] = 1000; 

for (i = a_index[value1]; i < a_index[value1 + 1] && fooArr[i].b >= value2; ++i) 
{ 
    if (fooArr[i].c <= value2 && fooArr[i].d <= value3) /* do stuff */ 
} 

假設我沒有在這裏犯了一個錯誤，這限制了搜索，其中a和b是標有效，這可能會大大縮短您的搜索時間。

Answer 6

您可以使用標準模板庫（STL）中的hash_set，這將爲您提供非常高效的實現。您搜索的複雜性是O（1）

這裏是鏈接：http://www.sgi.com/tech/stl/hash_set.html

- 編輯 -

宣佈新的結構將舉行的變量，超載比較運營商與本作的的hash_set新的結構。每次你想搜索時，用你的變量創建一個新對象，並將它傳遞給hash_set方法「find」。

看來的hash_set不是強制的STL，因此你可以使用集，它會給你O（LOGN）的複雜搜索。 這裏是例子：

#include <cstdlib> 
#include <iostream> 
#include <set> 

using namespace std; 

struct Obj{ 

public: 
     Obj(double a, double b, double c, double d){ 
       this->a = a; 
       this->b = b; 
       this->c = c; 
       this->d = d; 
     } 

     double a; 
     double b; 
     double c; 
     double d; 
     friend bool operator < (const Obj &l, const Obj &r) { 
       if(l.a != r.a) return l.a < r.a; 
       if(l.b != r.b) return l.a < r.b; 
       if(l.c != r.c) return l.c < r.c; 
       if(l.d != r.d) return l.d < r.d; 
       return false; 

     } 
    }; 


int main(int argc, char *argv[]) 
{ 
set<Obj> A; 

A.insert(Obj(1,2,3,4)); 
A.insert(Obj(16,23,36,47)); 
A.insert(Obj(15,25,35,43)); 

Obj c(1,2,3,4); 

A.find(c); 
cout << A.count(c); 



system("PAUSE"); 
return EXIT_SUCCESS; 
} 

Answer 7

根據你所說的話（在這兩個問題和評論）現在只有極少數值a（像10）。

既然如此，我會建立在a的值的索引，其中，直接每一個點在fooArr所有元素與a該值：

std::vector<std::vector<foo *> > index(num_a_values); 

for (int i=0; i<1000; i++) 
    index[fooArr[i].a].push_back(&fooArr[i]); 

然後，當你得到一個值查找一個項目，你直接去那些其fooArr[i].a==value1：

std::vector<foo *> const &values = index[value1]; 
for (int i=0; i<values.size(); i++) { 
    if (value2 <= values[i]->b 
     && value2 >= values[i]->c 
     && value3 >= values[i]->d) { 
      // yay, found something 
     } 
} 

這種方式，而不是看着fooArray每次1000個項目，你看，平均每次100。如果你還想要更快的速度，下一步就是根據b的值對索引中每個向量中的項進行排序。這將使您可以使用二分搜索而不是線性搜索來找到value2的下限，從而將~50個比較減少到〜10。由於您已按b排序，因此從此時起，您無需將value2與b進行比較 - 您確切知道滿足不平等的其餘數字在哪裏，因此您只需比較c和d 。

您也可以考慮基於數字的有限範圍內的另一種方法：0到1000可以用10位表示。使用一些比特操作，你可以將三個字段組合成一個32位數字，這樣編譯器可以一次比較所有三個數字，而不是三個單獨的操作。做到這一點是有點棘手的，但是一旦你來了，它可能會再次提高速度的三倍。

Answer 8

我想用kd樹是適當的。 如果與a沒有多少衝突，則散列/索引a可能會解決您的問題。

無論如何，如果我建議使用kd樹不起作用。

首先做的多KD樹的表。使用a作爲索引。

然後在方向b,c,d的方向上爲每個a值實施kd樹。

然後搜索時 - 第一個索引到合適的kd樹a，然後從kd樹與限制搜索。基本上你會做範圍搜索。

Kd-tree

你會得到你的答案O(L^(2/3)+m)，其中L是在適當的KD-tree和m元素的數量是匹配點的數量。

我發現更好的東西是Range Tree。這可能是你正在尋找的。 速度很快。它會在O(log^3(L)+m)中回答您的查詢。 （不幸的是不知道的範圍樹很多。）

Answer 9

首先對每個a做不同的表...

做TABEL num爲具有相同a數字。

做2個索引表格，每個表格有1000行。

索引表包含一個拆分的整數表示，其中涉及 號碼。

例如假設您的陣列 中有值（忽略a因爲我們每個a值的表）

b = 96 46 47 27 40 82 9 67 1 15 
c = 76 23 91 18 24 20 15 43 17 10 
d = 44 30 61 33 21 52 36 70 98 16 

那麼該行50索引表中的值，20：

idx[a].bc[50] = 0000010100 
idx[a].d[50] = 1101101001 
idx[a].bc[20] = 0001010000 
idx[a].d[20] = 0000000001 

所以我們假設你做功能（a，20，50）。 然後讓這些數字涉及你：

g = idx[a].bc[20] & idx[a].d[50]; 

然後g有1-S爲每個要處理數。如果您不需要 需要數組值，那麼您可以在g上執行populationCount。和 做內心事popCount(g)次。

你可以做

tg = g 
n = 0 
while (tg > 0){ 
    if(tg & 1){ 
    // do your stuff 
    } 
    tg = tg >>> 1; 
    n++; 
} 

也許它可以在tg = tg >>> 1; n++;部分被跳過許多零得到改善，但我不知道如果這是可能的。它應該比當前的方法快得多，因爲循環的所有變量都在寄存器中。

Answer 10

好吧，讓我們走了。

首先，==運算符要求採用鴿子洞方法。由於我們在[0,1000]範圍內討論int值，因此一張簡單的表格就很好。

std::vector<Bucket1> myTable(1001, /*MAGIC_1*/); // suspense 

課程的想法是，你會發現在其a屬性值......什麼魔法到目前爲止所定義的桶YourObject實例。

現在在新的東西。

&& fooArr[i].b >= value2 
&& fooArr[i].c <= value2 //yes again value2 
&& fooArr[i].d <= value3 

使用的value2是棘手的，但你說你不關心空間權;）？

typedef std::vector<Bucket2> Bucket1; 
/*MAGIC_1*/ <-- Bucket1(1001, /*MAGIC_2*/) // suspense ? 

一個BucketA實例將在其第i個位置的YourObject針對yourObject.c <= i <= yourObject.b

所有實例，現在，隨着d相同的方法。

typedef std::vector< std::vector<YourObject*> > Bucket2; 
/*MAGIC_2*/ <-- Bucket2(1001) 

的想法是，在std::vector<YourObject*>第i個索引包含一個指向的YourObject所有實例其中yourObject.d <= i

乾脆把它！

class Collection: 
{ 
public: 
    Collection(size_t aMaxValue, size_t bMaxValue, size_t dMaxValue); 
    // prefer to use unsigned type for unsigned values 

    void Add(const YourObject& i); 

    // Pred is a unary operator taking a YourObject& and returning void 
    template <class Pred> 
    void Apply(int value1, int value2, int value3, Pred pred); 

    // Pred is a unary operator taking a const YourObject& and returning void 
    template <class Pred> 
    void Apply(int value1, int value2, int value3, Pred pred) const; 

private: 
    // List behaves nicely with removal, 
    // if you don't plan to remove, use a vector 
    // and store the position within the vector 
    // (NOT an iterator because of reallocations) 
    typedef std::list<YourObject> value_list; 

    typedef std::vector<value_list::iterator> iterator_vector; 
    typedef std::vector<iterator_vector> bc_buckets; 
    typedef std::vector<bc_buckets> a_buckets; 
    typedef std::vector<a_buckets> buckets_t; 

    value_list m_values; 
    buckets_t m_buckets; 
}; // class Collection 

Collection::Collection(size_t aMaxValue, size_t bMaxValue, size_t dMaxValue) : 
    m_values(), 
    m_buckets(aMaxValue+1, 
      a_buckets(bMaxValue+1, bc_buckets(dMaxValue+1)) 
      ) 
) 
{ 
} 

void Collection::Add(const YourObject& object) 
{ 
    value_list::iterator iter = m_values.insert(m_values.end(), object); 

    a_buckets& a_bucket = m_buckets[object.a]; 
    for (int i = object.c; i <= object.b; ++i) 
    { 
    bc_buckets& bc_bucket = a_bucket[i]; 
    for (int j = 0; j <= object.d; ++j) 
    { 
     bc_bucket[j].push_back(index); 
    } 
    } 
} // Collection::Add 

template <class Pred> 
void Collection::Apply(int value1, int value2, int value3, Pred pred) 
{ 
    index_vector const& indexes = m_buckets[value1][value2][value3]; 
    BOOST_FOREACH(value_list::iterator it, indexes) 
    { 
    pred(*it); 
    } 
} // Collection::Apply<Pred> 

template <class Pred> 
void Collection::Apply(int value1, int value2, int value3, Pred pred) const 
{ 
    index_vector const& indexes = m_buckets[value1][value2][value3]; 

    // Promotion from value_list::iterator to value_list::const_iterator is ok 
    // The reverse is not, which is why we keep iterators 
    BOOST_FOREACH(value_list::const_iterator it, indexes) 
    { 
    pred(*it); 
    } 
} // Collection::Apply<Pred> 

因此，加入和刪除項目的收藏將花費。

此外，你有(aMaxValue + 1) * (bMaxValue + 1) * (dMaxValue + 1) std::vector<value_list::iterator>存儲，這是很多。

然而，Collection::Apply複雜大致是Predk應用中k爲符合其參數的項目數。

我要尋找的評論在那裏，不知道我得到了所有的指標權OO

Answer 11

正如PMG說，這個想法是消除儘可能多的比較成爲可能。顯然你不會有4000比較。那將需要所有1000個元素通過第一次測試，這將是多餘的。顯然只有10個值a，因此10％通過檢查。那麼，你會做1000 + 100 +？ +？檢查。我們假設+ 50 + 25，共計1175.

您需要知道如何分配a，b，c，d和值1,2和3以確定最快速度。我們只知道a可以有10個值，並且我們假定value1具有相同的域。在這種情況下，通過a合併可以將其減少到O（1）操作以獲得正確的bin，再加上相同的175個檢查。但是，如果b，c和value2有效地形成50個桶，則可以在O（1）中再次找到合適的桶。但是現在每個桶平均有20個元素，所以你只需要35次測試（減少80％）。所以，數據分配在這裏很重要。一旦你理解了你的數據，算法就會變得清晰。