2

我是 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));
}

谢谢！

4

3 回答 3

4

如果数组未排序，只需使用单个循环将每个元素与x. 除非您忘记告诉我们某些事情，否则我认为不需要任何更复杂的事情。

如果数组已排序，则存在具有更好渐近复杂度的算法（例如二进制搜索）。然而，对于一个 20 元素的数组，简单的线性搜索仍然应该是首选策略。

于 2013-04-08T16:00:39.730 回答
2

如果您的数组是排序的，您可以使用分治策略：

计算排序数组中键出现次数的有效方法

于 2013-04-08T16:00:59.053 回答
1

分而治之算法只有在您可以消除一些工作，或者如果您可以在多个计算单元上并行化划分的工作部分时才有用。在您的情况下，第一个选项对于已经排序的数据集是可能的，其他答案可能已经解决了这个问题。

对于第二种解决方案，算法名称是 map reduce，它将数据集拆分为几个子集，将子集分配给尽可能多的线程或进程，并收集结果以“编译”它们（该术语实际上是“reduce”）有意义的结果。在您的设置中，这意味着每个线程将扫描自己的数组切片以计数项目，并将其结果返回给“reduce”线程，后者会将它们相加以返回最终结果。不过，此解决方案仅对大型数据集有意义。

在 SO 上有一些关于 mapreduce 和 c++ 的问题，但我会尝试在这里为您提供一个示例实现：

#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，它应该返回预期的结果。如您所见，实现非常专业：

  • map 和 reduce 函数针对您的问题，
  • 用于映射的线程数是静态的，
  • 我按照你的风格使用了全局变量，
  • 为方便起见，我使用了 aboost::barrier进行同步

但是，这应该让您对算法有所了解，以及如何将其应用于类似问题。

警告：代码未经测试。

于 2013-04-08T16:48:25.380 回答