arrays - 两个数组的元素相加

Question

你有两个数组

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

Q1。我必须创建一个数组

int[] c 

其元素为a[]和b[]对应索引之和前任。

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

解决方案:-> 我可以利用多线程。将整个数组分成 10 个或更多部分，并将每个部分分配给一个线程来执行计算。注意->面试官建议使用Multithreading

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

在我看来，对于问题二，您有两种技巧:

首先应该分两步完成。step-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让我知道这个缺点。

为了更好的技术阅读更新 answer作者:Jogojapan 先生。