爲什麼我的二進制搜索如此瘋狂地比迭代更慢？

我正在寫一個自動完成程序，它發現所有可能的匹配字符或給定字典文件和輸入文件的字符集。我剛剛完成了一個在迭代搜索中實現二分搜索的版本，並認爲我可以提高程序的整體性能。爲什麼我的二進制搜索如此瘋狂地比迭代更慢？

事情是，二進制搜索幾乎是慢9倍，比迭代搜索慢。是什麼賦予了？我認爲我通過迭代使用二進制搜索來提高性能。

運行時間（BIN搜索到左）[Larger]： testing the time of each version

下面是各個版本的重要組成部分，完整的代碼可以內置在my github與cmake的運行。

二進制搜索功能（而經由輸入循環給定調用）

bool search(std::vector<std::string>& dict, std::string in, 
     std::queue<std::string>& out) 
{ 
    //tick makes sure the loop found at least one thing. if not then break the function 
    bool tick = false; 
    bool running = true; 
    while(running) { 
     //for each element in the input vector 
     //find all possible word matches and push onto the queue 
     int first=0, last= dict.size() -1; 
     while(first <= last) 
     { 
      tick = false; 
      int middle = (first+last)/2; 
      std::string sub = (dict.at(middle)).substr(0,in.length()); 
      int comp = in.compare(sub); 
      //if comp returns 0(found word matching case) 
      if(comp == 0) { 
       tick = true; 
       out.push(dict.at(middle)); 
       dict.erase(dict.begin() + middle);  
      } 
      //if not, take top half 
      else if (comp > 0) 
       first = middle + 1; 
      //else go with the lower half 
      else 
       last = middle - 1; 
     } 
     if(tick==false) 
      running = false; 
    } 
    return true; 
}

迭代搜索（包括在主循環）：

for(int k = 0; k < input.size(); ++k) { 
     int len = (input.at(k)).length(); 
     // truth false variable to end out while loop 
     bool found = false; 
     // create an iterator pointing to the first element of the dictionary 
     vecIter i = dictionary.begin(); 
     // this while loop is not complete, a condition needs to be made 
     while(!found && i != dictionary.end()) { 
      // take a substring the dictionary word(the length is dependent on 
      // the input value) and compare 
      if((*i).substr(0,len) == input.at(k)) { 
       // so a word is found! push onto the queue 
       matchingCase.push(*i); 
      } 
      // move iterator to next element of data 
      ++i;  
     } 

    }

例如輸入文件：

z 
be 
int 
nor 
tes 
terr 
on

來源

2013-09-26 Syntactic Fructose

「一封信或一組字母」是否意味着它們在搜索到的單詞的開頭？ – SJuan76

@ SJuan76我在樣本文件中編輯過，包括圖片中使用的搜索項，是的，字母是單詞的開頭。 –

'擦除'vector'內的項目是很昂貴的。 – deepmax

而不是擦除矢量中間的元素（這相當昂貴），然後開始搜索，只是比較找到的項目前後的元素（因爲它們應該都是相鄰的）直到找到所有匹配的項目。

或使用std::equal_range，這確實如此。

來源

2013-09-26 23:33:22

這將是罪魁禍首：

dict.erase(dict.begin() + middle);

您反覆從你的字典裏刪除項目天真地使用二進制搜索找到的所有有效的前綴。這增加了巨大的複雜性，並且是不必要的

取而代之的是，一旦你找到了一個匹配，退後一步，直到你找到第一個匹配，然後前進，將所有匹配添加到你的隊列。請記住，因爲您的字典已排序，並且您僅使用前綴，所有有效的匹配將連續出現。

來源

2013-09-26 23:33:35 paddy

dict.erase操作的字典大小是線性的：它將整個數組從中間拷貝到數組的開頭。這使得「二進制搜索」算法在dict的長度上可能是二次的，而O（N^2）昂貴的存儲器複製操作。

來源

2013-09-26 23:38:43 Michael

爲什麼我的二進制搜索如此瘋狂地比迭代更慢？

回答

相關問題