计算preFIX总和 [英] calculate prefix sum

问题描述

我有以下code完成preFIX总和的任务：

I have following code to accomplish prefix sum task:

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

从这个维基百科页面 但我已经得到了错误的结果有什么不好？请大家帮忙

From this wikipedia page but i have got wrong result what is wrong? please help

推荐答案

让你的算法工作的最快方法：删除外的（我...）循环，而不是设置我 0，且仅使用内的（十...）循环。

The quickest way to get your algorithm working: Drop the outer for(i...) loop, instead setting i to 0, and use only the inner for (j...) loop.

int main(){
    ...
    int i=0;
    for (int j=0;j<=n-1;j++){
        if (j>=(powf(2,i))){
            int t=powf(2,i);
            x[j]=x[j]+x[j-t];
        }
    }
    ...
}

或等价：

for (int j=0; j<=n-1; j++) {
    if (j>=1)
        x[j] = x[j] + x[j-1];
}

...这是直观的方式做了preFIX总和，也可能是最快的非并行算法。

...which is the intuitive way to do a prefix sum, and also probably the fastest non-parallel algorithm.

Wikipedia的算法被设计成并行运行，使得所有相加是完全相互独立的。它读取所有的值，更增加了他们，然后将它们写回阵列中，所有的并行。在您的版本，当你执行X [J] = X [J] + X [JT]，您使用的是X [JT]您刚才添加， T 迭代前。

Wikipedia's algorithm is designed to be run in parallel, such that all of the additions are completely independent of each other. It reads all the values in, adds to them, then writes them back into the array, all in parallel. In your version, when you execute x[j]=x[j]+x[j-t], you're using the x[j-t] that you just added to, t iterations ago.

如果你真的想重现维基百科的算法，这里有一个方法，但被警告这将是比上述直观的方式要慢得多，除非你使用的是并行化编译器和一台计算机与一大堆的处理器。

If you really want to reproduce Wikipedia's algorithm, here's one way, but be warned it will be much slower than the intuitive way above, unless you are using a parallelizing compiler and a computer with a whole bunch of processors.

int main() {
    int x[16]={39,21,20,50,13,18,2,33,49,39,47,15,30,47,24,1};
    int y[16];
    int n=sizeof(x)/sizeof(int);

    for (int i=0;i<=(Log(n)-1);i++){
        for (int j=0;j<=n-1;j++){
            y[j] = x[j];
            if (j>=(powf(2,i))){
                int t=powf(2,i);
                y[j] += x[j-t];
            }
        }
        for (int j=0;j<=n-1;j++){
            x[j] = y[j];
        }
    }

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

便笺：可以使用 1＆LT;＆LT;我而不是函数powf（2,1），为速度。而作为ergosys提到的，你的日志（）函数需要工作;它返回值太高，这将不会影响在这种情况下，部分和的结果，但会使其需要更长的时间。

Side notes: You can use 1<<i instead of powf(2,i), for speed. And as ergosys mentioned, your Log() function needs work; the values it returns are too high, which won't affect the partial sum's result in this case, but will make it take longer.

这篇关于计算preFIX总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！