有沒有更高效的方法來做這個算法？

據我所知，這種算法會在需要時正確搜索並變爲真。在課堂上，我們談論的是大O分析，所以這個任務是展示遞歸搜索如何比迭代搜索更快。重點是搜索一個數字，使得A [i] = i（找到一個與存儲在索引處的數字相同的索引）。該算法與迭代算法相差僅約100納秒，但有時迭代速度更快。我使用rand（）函數設置主要矢量。我運行這兩種算法一百萬次並記錄時間。我問的問題是，這個算法是否儘可能高效，或者有更好的方法來做到這一點？有沒有更高效的方法來做這個算法？

bool recursiveSearch(vector<int> &myList, int beginning, int end) 
{ 
    int mid = (beginning + end)/2; 

    if (myList[beginning] == beginning) //check if the vector at "beginning" is 
    {          //equal to the value of "beginning" 
     return true; 
    } 

    else if (beginning == end) //when this is true, the recursive loop ends. 
    {       //when passed into the method: end = size - 1 
     return false; 
    } 

    else 
    { 
     return (recursiveSearch(myList, beginning, mid) || recursiveSearch(myList, mid + 1, end)); 
    } 

}

編輯：在傳遞之前，該列表預有序和一個檢測在主做是爲了確保開頭和結尾都存在

來源

2014-01-24 user2908474

對於大O分析，無論您檢查元素的順序如何：線性（迭代）還是跳躍（遞歸），在未排序數組中查找值的最佳方式爲「O（n）」同樣好。但是，實際運行時間可能會有很大差異。通常你不關心這些微小的差異（時間上，也就是說，速度可能快1.5倍，但如果差距是100ns，誰在乎？），然而（你總是可以購買更快的機器;-)）。 –

我擔心時差的唯一原因是因爲我的教授想證明這一點。這兩種算法在我的機器上相差大約7微秒（在對我的向量的參考之後），實際上這並不重要，但它的任務說 – user2908474

@ user2908474你不能着手「證明」。你運行實驗，並報告你的發現。雖然兩種算法都是O（N），但理論上，遞歸有更多的開銷WRT迭代。另一方面，C和C++編譯器非常擅長將遞歸代碼優化爲迭代代碼。因此，在不同的優化級別上查看這兩種方法產生的彙編代碼可能是值得的。 – juanchopanza

一個可能的「改善」將不可複製每個遞歸中的向量通過傳遞一個引用：

bool recursiveSearch(const vector<int>& myList, int beginning, int end)

來源

2014-01-24 07:47:04 juanchopanza

此外，使用'operator []'而不是'at（）'會節省邊界檢查。 –

使用方括號並使用引用，它將算法加速了大約7微秒，在這個用法中足以證明這是一個更快的算法。謝謝！ – user2908474

@ user2908474這（它比迭代更快）讓我感到驚訝。您的迭代方法能否也存在一些不必要的低效率？而且，這必須是矢量中元素數量的函數。同樣值得用許多不同的隨機種子進行測試以獲得全部種羣或結果。 – juanchopanza

一個明顯的「改進」是在所有其餘的內核上運行線程。只需將vector分配給number of cores - 1件，並使用條件變量在找到時發出主線程信號。

來源

2014-01-24 07:59:07

除非您知道有關數據排序的特殊內容，否則執行此類分區搜索絕對沒有好處。

事實上，你的代碼實際上是[嘗試]做一個線性搜索，所以它實際上實現了一個簡單的for循環，其代價是大量的堆棧和開銷。

請注意，您的代碼中存在一個奇怪的現象：如果第一個元素不匹配，您將致電recursiveSearch(myList, beginning /*=0*/, mid)。由於我們已經知道元素0不匹配，所以您將再次細分，但只能在重新測試元素之後再進行細分。

因此，考慮有沒有匹配6種元素的載體，你要撥打：

recursiveSearch（myList中，0,6）; - > < recursiveSearch（myList，0，3）|| recursiveSearch（myList，4，6）; > - > < recursiveSearch（myList，0，1）|| recursiveSearch（2，3）> < recursiveSearch（myList，4，5）; || recursiveSearch（myList，5，6）; > - > < recursiveSearch（myList，0，0）|| recursiveSearch（myList，1，1）> < recursiveSearch（myList，2，2）|| recursiveSearch（myList中，3,3）> ...

最後，你沒有在給定的指標，因爲你達到這樣的開始和結束都是這個值，這似乎是一種昂貴的方式，條件消除每個節點，並且最終結果不是分區搜索，它是一種簡單的線性搜索，您只需使用大量堆棧深度即可實現。

所以，一個簡單和快速的方式來做到這一點是：

for (size_t i = beginning; i < end; ++i) { 
    if (myList[i] != i) 
     continue; 
    return i; 
}

因爲我們想在這裏最優化，這是值得指出的是MSVC，GCC和Clang的所有假設if表示可能案例，所以我在這裏優化退化的案例，我們有一個沒有或沒有晚期匹配的大型向量。如果我們運氣好，我們會盡早找到結果，那麼我們願意爲潛在的分支小姐付出代價，因爲我們正要離開。我意識到，分支緩存將很快弄清楚了這一點對我們來說，但又 - 優化;-P

正如其他人所指出的那樣，你也可以從不能按值傳遞的載體（強制複印件）

受益

const std::vector<int>& myList

來源

2014-01-24 08:07:50 kfsone

如果您需要在未排序數組中找到一個元素，例如A[i] == i，那麼唯一的方法就是遍歷每個元素，直到找到一個元素。

要做到這一點最簡單的方法是，像這樣：

bool find_index_matching_value(const std::vector<int>& v) 
{ 
    for (int i=0; i < v.size(); i++) { 
     if (v[i] == i) 
      return true; 
    } 
    return false; // no such element 
}

這是O(n)，而你不會是能夠做到任何比這更好的算法。所以我們必須把注意力轉向微觀優化。一般來說，如果在現代機器上，你的遞歸解決方案比上面簡單的解決方案更快，我會感到非常驚訝。儘管編譯器可能（可能）能夠移除額外的函數調用開銷（有效地將遞歸解決方案轉換爲迭代解決方案），但按順序（如上所述）依次運行數組允許優化使用緩存，而對於大數組，你的分區搜索不會。

來源

2014-01-24 08:09:58

有沒有更高效的方法來做這個算法？

回答

相關問題