计算前缀总和

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;
  } 

从这个维基百科页面, 但我有错误的结果有什么问题？请帮忙

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)];

Answer 2

我认为 std::partial_sum 做你想要的 http://www.sgi.com/tech/stl/partial_sum.html