添加两个阵列的元素

Question

你有两个数组

int[] a = {......} // Total elements 1 million
int[] b = {......} // Total elements 1 million , Length is same for both arrays.

Q1.我必须创建一个数组

int[] c 

其元素是a []和b [] Ex的相应索引的总和.

 c[0] = a[0] + b[0];
 c[1] = a[1] + b[1];
 c[2] = a[2] + b[2];

解决方案: - >我可以利用多线程.将整个数组划分为10个或更多部分,并将每个段分配给线程以执行计算.注意 - >访员建议使用多线程

Q2.现在它有点改变.数组C的元素将具有如下值: - >

c[0] = a[0] + b[0];
c[1] = a[1] + b[1] + c[0]; // At this line c[0] is Sum of a[0] + b[0]; The Above Line
c[2] = a[2] + b[2] + c[1]; // At this line c[0] is Sum of a[1] + b[1]+ a[0] + b[0]; The Above Line

MySolution->解决第1部分(Q1)并创建一个临时数组,然后我们必须执行这样的添加.

C[1] = temp[1]+temp[0]
C[2] = temp[2]+temp[1]

注意: - >我们真的不需要temp [],我们只能使用Array c这样做.只是简单地在SO上解释这一点.

问题 - >我不认为在问题2中我们可以使用多线程.有没有更好的方法来解决Q2？我们可以利用多线程吗？

Answer 1

在我看来,对于问题二你有两种技巧:

首先应该分两步完成.步骤1使用您可以添加的线程

 c[0] = a[0] + b[0];
 c[1] = a[1] + b[1];
 c[2] = a[2] + b[2];

正如你的建议.

但是步骤2应该按顺序进行.因为c[ i + 1]价值取决于更新的价值c [i]

第二种技术有点复杂但可以很快.

你在第二个问题中被要求做的是做类似的事情:

 c[0] = a[0] + b[0];
 c[1] = a[1] + b[1] + a[0] + b[0];
 c[2] = a[2] + b[2] + a[1] + b[1] + a[0] + b[0];

这可以是平行的.

c[i] =  thread1( sum(a[0]...a[i] )) + thread2( sum(b[0]...b[i] ))
         for i >= 0

好的是这种技术,你可以c[i]并行计算所有i(它的两个像水平线程模型).

你可以进一步改进thread1/thread2函数作为多线程与子线程来执行求和 - 但是记住有时多线程代码运行速度比单线程代码慢,因为线程上下文切换时间(所以你应该给每个线程足够的任务量) ).

与第二种技术不同的一点是"线程的大部分内容与线程c[i]的内容相同c[i-1]".
感谢@ jogojapan让我知道这个缺点.

为了更好的技术阅读Mr.Jogojapan 更新的答案.

Answer 2

你可以像你说的那样做第 1 部分多线程 -

temp[0] = a[0] + b[0];
temp[1] = a[1] + b[1];
temp[2] = a[2] + b[2];
etc....

那么第 2 部分的计算就变成了 -

c[0] = temp[0];
c[1] = temp[1] + temp[0];
c[2] = temp[2] + temp[1] + temp[0];
c[3] = temp[3] + temp[2] + temp[1] + temp[0];
etc...

尽管这看起来是连续的并且不可能并行化，但它实际上是一种非常常见的操作，称为“前缀和”或“扫描”。有关更多详细信息，包括如何并行化，请参阅Wikipedia或Blelloch。

在 8 个元素的情况下，情况如下，其中每个递归阶段都可以并行化，因为每个计算不依赖于同一阶段中的其他计算。

// 1st phase 
u[0] = temp[0] + temp[1];
u[1] = temp[2] + temp[3];
u[2] = temp[4] + temp[5];
u[3] = temp[6] + temp[7];

// 2nd phase
v[0] = u[0] + u[1];
v[1] = u[2] + u[3];

// 3rd phase
w[0] = v[0] + v[1];

// final phase
c[0] = temp[0];
c[1] = u[0];
c[2] = u[0] + temp[2];
c[3] = v[0];
c[4] = v[0] + temp[4];
c[5] = v[0] + u[2];
c[6] = v[0] + u[2] + temp[6];
c[7] = w[0];