需要關於改進我的代碼的建議：搜索算法

Question

我很新的C++，並需要一些建議。 這裏我有一段代碼，用於測量數組中出現任意整數x的次數，並輸出比較結果。但我已經閱讀了使用多路分支（「分而治之！」）技術，我可以使算法運行得更快。

任何人都可以指向正確的方向我應該怎麼做呢？

這裏是我做的另一種方法我工作代碼：

#include <iostream> 
#include <cstdlib> 
#include <vector> 

using namespace std; 

vector <int> integers; 
int function(int vectorsize, int count); 
int x; 
double input; 

int main() 
{ 
cout<<"Enter 20 integers"<<endl; 
cout<<"Type 0.5 to end"<<endl; 

while(true) 
{ 
cin>>input; 

if (input == 0.5) 
break; 

integers.push_back(input); 
} 

cout<<"Enter the integer x"<<endl; 
cin>>x; 

function((integers.size()-1),0); 

system("pause"); 

} 

int function(int vectorsize, int count) 
{ 
    if(vectorsize<0) //termination condition 
{ 
    cout<<"The number of times"<< x <<"appears is "<<count<<endl; 
    return 0; 
}  

if (integers[vectorsize] > x) 
{ 
    cout<< integers[vectorsize] << " > " << x <<endl; 
} 

if (integers[vectorsize] < x) 
{ 
    cout<< integers[vectorsize] << " < " << x <<endl; 
} 
if (integers[vectorsize] == x) 
{ 
    cout<< integers[vectorsize] << " = " << x <<endl; 

    count = count+1; 
} 

return (function(vectorsize-1,count)); 
} 

謝謝！

Answer 1

如果數組未經排序，只需使用單個循環將每個元素與x進行比較。除非你忘了告訴我們，否則我不認爲有任何需要更復雜的東西。

如果對數組進行排序，則會有更好的漸近複雜度的算法（例如二分查找）。但是，對於20個元素的陣列，簡單的線性搜索仍然應該是首選策略。

Answer 2

如果陣列是一個排序的一個，你可以使用分征服策略：

Efficient way to count occurrences of a key in a sorted array

Answer 3

分而治之算法只是有益的，如果你可以消除一些工作的，或者如果你可以在多個計算單元上並行分割的工作部分。在你的情況下，第一個選項是可能的，已經排序的數據集，其他答案可能已經解決了這個問題。

對於第二種解決方案，算法名稱是map reduce，它將數據集分成幾個子集，將子集分配給多個線程或進程，並收集結果以「編譯」它們（該術語實際上是「reduce 「）有意義的結果。在你的設置中，這意味着每個線程都會掃描它自己的數組片段來計算這些項目，並將結果返回給「reduce」線程，這會將它們相加以返回最終結果。 儘管此解決方案僅適用於大型數據集，

有應付MapReduce和C++的SO問題，但我會盡力給你這裏的實現：

#include <utility> 
#include <thread> 
#include <boost/barrier> 

constexpr int MAP_COUNT = 4; 

int mresults[MAP_COUNT]; 

boost::barrier endmap(MAP_COUNT + 1); 

void mfunction(int start, int end, int rank){ 
    int count = 0; 
    for (int i= start; i < end; i++) 
     if (integers[i] == x) count++; 
    mresult[rank] = count; 
    endmap.wait(); 
} 

int rfunction(){ 
    int count = 0; 
    for (int i : mresults) { 
     count += i; 
    } 
    return count; 
} 

int mapreduce(){ 
    vector<thread &> mthreads; 
    int range = integers.size()/MAP_COUNT; 
    for (int i = 0; i < MAP_COUNT; i++) 
     mthreads.push_back(thread(bind(mfunction, i * range, (i+1) * range, i))); 
    endmap.wait(); 
    return rfunction(); 
} 

一旦integers載體已被填充，你可以調用定義的mapreduce功能上面，這應該返回預期的結果。正如你所看到的，實現非常專業：

• 地圖和減少功能是專門針對您的問題，
• 用於地圖的線程數是靜態的，
• 我跟着你的風格和使用全局變量，
• 爲方便起見，我用了一個boost::barrier同步

然而，這應該給你的算法的想法，你如何把它們運用到類似的問題。

警告：代碼未經測試。