并行前缀总和-最快的实现

一尘不染

并行前缀总和-最快的实现

algorithm

我想使用C ++实现并行前缀和算法。我的程序应采用输入数组x[1....N]，并应在数组中显示输出y[N]。（请注意，N的最大值为1000。）

到目前为止，我浏览了许多研究论文，甚至浏览了Wikipedia中的算法。但是我的程序还应该显示输出，步骤以及每个步骤的操作/指令。

我想要最快的实现，就像我想要最小化操作数量和步骤一样。

例如：：

x = {1, 2, 3,  4,   5,   6,   7,  8 } - Input
y = ( 1, 3, 6, 10, 15, 21, 28, 36) - Output

但是，除了将y数组显示为输出之外，我的程序还应该显示每个步骤的操作。我还引用此线程计算前缀和，但可以从中获得很多帮助。

阅读 445

2020-07-28

共1个答案

一尘不染

遵循以下代码即可完成工作

void prfxSum()
{
    int *x=0;
    int *y=0;
    int sum=0;
    int num=0;
    int i=0;

    cout << "Enter the no. of elements in input array : ";
    cin >> num;

    x = new int[num];
    y = new int[num];

    while(i < num)
    {
        cout << "Enter element " << i+1 << " : ";
        cin >> x[i++];
    }

    cout << "Output array :- " << endl;
    i = 0;
    while(i < num)
    {
        sum += x[i];
        y[i] = sum;
        cout << y[i++] << ", ";
    }

    delete [] x;
    delete [] y;
}

以下是执行时的输出

Enter the no. of elements in input array : 8
Enter element 1 : 1
Enter element 2 : 2
Enter element 3 : 3
Enter element 4 : 4
Enter element 5 : 5
Enter element 6 : 6
Enter element 7 : 7
Enter element 8 : 8
Output array :- 
1, 3, 6, 10, 15, 21, 28, 36

您可以通过从文件等中输入数组x []来避免用户输入1000个元素。

2020-07-28