两个数组元素的相加

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的一小部分changed.Elements将有如下的值:->

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-> Solve Part 1 (Q1)并创建一个临时数组，之后我们必须像这样执行加法。

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

注意:->我们真的不需要temp[]，我们也可以使用数组c来做这件事。只是简单地解释一下。

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

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

Answer 2

在我看来，对于第二个问题，你有两种技术：

第一步应该分两步完成。第1步使用您可以添加的线程

 c[0] = a[0] + b[0];
 c[1] = a[1] + b[1];
 c[2] = a[2] + b[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

这个技术很好，你可以并行地计算所有i的c[i] (它的两级线程模型)。

您可以进一步改进thread1/thread2作为多线程的函数来执行求和，但请记住，有时由于线程上下文切换时间的原因，多线程代码的运行速度会比单线程代码慢(因此您应该为每个线程分配足够的任务)。

与第二种技术不同的一点是“c[i]的线程所做的大部分工作与c[i-1]的线程所做的工作是相同的”。

感谢@jogojapan让我知道这个缺点。

有关更好的技术，请阅读Mr.Jogojapan更新的answer。

Answer 3

实际上，你可以在这个任务中使用多线程。你的算法由两部分组成：

1. apply Q1 algorithm这一部分将利用在单线程循环中的优势应用formyla：c[n] = c[n] + c[n-1]，