c++ - 计算前缀和

Question

我有以下代码来完成前缀和任务:

  #include <iostream>
  #include<math.h>
  using namespace std;

  int Log(int n){
      int count=1;
      while (n!=0){
          n>>=1;
          count++;

      }
      return count;
  }
  int main(){
    int x[16]={39,21,20,50,13,18,2,33,49,39,47,15,30,47,24,1};
    int n=sizeof(x)/sizeof(int );
    for (int i=0;i<=(Log(n)-1);i++){
          for (int j=0;j<=n-1;j++){
              if (j>=(std::powf(2,i))){
                  int t=powf(2,i);
                  x[j]=x[j]+x[j-t];

              }
          }
     }
     for (int i=0;i<n;i++)
          cout<<x[i]<< "  ";

     return 0;
  } 

来自 this wikipedia page但我得到了错误的结果 出了什么问题？请帮忙

Answer 1

我不确定您的代码应该做什么，但实现前缀和实际上非常简单。例如，使用任意操作计算迭代器范围的(独占)前缀和:

template <typename It, typename F, typename T>
inline void prescan(It front, It back, F op, T const& id) {
    if (front == back) return;
    typename iterator_traits<It>::value_type accu = *front;
    *front++ = id;
    for (; front != back; ++front) {
        swap(*front, accu);
        accu = op(accu, *front);
    }
}

这遵循 C++ 标准库算法的界面风格。

要在您的代码中使用它，您可以编写以下内容:

prescan(x, x + n, std::plus<int>());

您是否正在尝试实现并行前缀和？这只有在您实际并行化您的代码时才有意义。就目前而言，您的代码是按顺序执行的，不会从您似乎使用的更复杂的分而治之逻辑中获得任何好处。

另外，你的代码确实有错误。最重要的一个:

for(int i=0;i<=(Log(n)-1);i++)

在这里，您将迭代直到 floor(log(n)) - 1 .但是伪代码指出您实际上需要迭代直到 ceil(log(n)) - 1。 .

此外，考虑一下:

 for (int j=0;j<=n-1;j++)

这不是很常见。通常，您会编写如下代码:

for (int j = 0; j < n; ++j)

注意我使用了 <而不是 <=并从 j - 1 调整边界至 j .外循环也是如此，所以你会得到:

for (int i = 0; i < std::log(n); ++i)

最后，代替std::powf ，您可以使用 pow(2, x) 的事实与1 << x相同(即利用以 2 为基数的操作被有效地实现为位操作这一事实)。这意味着您可以简单地写:

if (j >= 1 << i)
    x[j] += x[j - (1 << i)];