需要关于改进我的代码的建议：搜索算法

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同步

然而，这应该给你的算法的想法，你如何把它们运用到类似的问题。

警告：代码未经测试。