6

你有两个数组

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 个或更多部分，并将每个段分配给一个线程来执行计算。注意-> 面试官建议使用多线程

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

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

注意：-> 我们真的不需要 temp[]，我们也只能使用 Array c 来做到这一点。只是为了以简单的方式在 SO 上解释这一点。

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

4

5 回答 5

5

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

首先应该分两步完成。第 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 的更新答案。

于 2013-07-19T07:36:42.887 回答
4

正如你所说，你可以做第 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];
于 2013-07-19T08:09:58.060 回答
1

实际上你可以在这个任务中使用多线程。您的算法将包括两部分：

  1. 应用 Q1 算法 - 这部分将利用多线程的优势。

  2. 仅在三分之一循环中应用 formyla: c[n] = c[n] + c[n-1], n=1...999999.

于 2013-07-19T07:34:51.657 回答
1

您可以按照第一个问题的方式在此处使用多线程。我的意思是你可以计算

sumA0B0 = a[0] + b[0];

在单独的线程中，甚至等待计算（同步，即在 a[i] 上）。然后在单独的线程中你可以计算 c[i] = sumAiBi + c[i-1];

于 2013-07-19T07:35:29.833 回答
0

对 Q2 使用多线程的一种方法是分两次执行（每次在内部使用 T 个线程，其中 T 可以自由选择）：

  1. 以通常的多线程方式计算c[i] = a[i] + b[i] + c[i-1]所有单元格，即将输入划分为范围 [0,r1), [r1,r2), ... [rk,n) 并将一个线程应用于每个范围。是的，这对于除第一个范围之外的所有范围都是不正确的，步骤 2 将更正它。

  2. 再次以多线程方式计算校正。为此，我们查找每个范围的最右边的值，即corr1:=c[r1-1],corr2:=corr1+c[r2-1]等corr3:=corr2+c[r3-1]，这为我们提供了每个线程的校正值，然后再次使用与以前相同范围的多线程计算，c[i] += corrk哪里corrk是第 k 个线程的线程特定校正值。（对于第零个线程，我们可以使用corr0:=0，因此该线程不需要做任何事情。）

这将理论运行时间提高了一个因子 T，其中 T 是线程数（可以自由选择），因此就多线程而言，这是一个最佳解决方案。

为了说明这是如何工作的，这里是一个我们假设数组长度的例子n==30。我们进一步假设我们使用 3 个线程：一个用于计算范围c[0..9]，一个用于计算，一个c[10..19]用于计算c[20..29]。

显然，目标是在 cell 中c[i]，对于 any 0<i<n，我们得到

c[i] == a[0]+...+a[i]+b[0]+...+b[i]

（即 alla[0..i]和 all的总和b[0..i]）在算法完成后。让我们看看算法是如何到达那里的，例如 cell i==23。此单元格由第三个线程处理，即负责范围的线程c[20..29]。

第 1 步：线程集

c[20] = a[20]+b[20]
c[21] = c[20]+a[21]+b[21] == a[20]+a[21]+b[20]+b[21]
c[22] = c[21]+a[22]+b[22] == a[20]+a[21]+a[22]+b[20]+b[21]+b[22]
c[23] = c[22]+a[23]+b[23] == a[20]+a[21]+a[22]+a[23]+b[20]+b[21]+b[22]+b[23]
...

因此，在第 1 步完成后，我们有了一些 ofa[20..23]和b[20..23]in cell c[23]。缺少的是 和 的a[0..19]总和b[0..19]。

类似地，第一个和第二个线程已经将值设置为c[0..9]andc[10..19]使得

c[0] = a[0]+b[0]
c[1] = c[0]+a[1]+b[1] == a[0]+a[1]+b[0]+b[1]
...
c[9] = a[0]+...+a[9]+b[0]+...+b[9]

和

c[10] = a[10]+b[10]
...
c[19] = a[10]+...+a[19]+b[10]+...+b[19]

步骤2：第三个线程的校正值，corr2是第二个线程计算的最右边值的总和corr1，而corr1第一个线程计算的最右边的值。因此

corr2 == c[9]+c[19] == (a[0]+...+a[9]+b[0]+...+b[9]) + (a[10]+...+a[19]+b[10]+...+b[19])

这确实是c[23]第 1 步之后的值缺失的总和。在第 2 步中，我们将此值添加到所有元素c[20..29]，因此，在第 2 步完成后，c[23]它是正确的（所有其他单元格也是如此）。

这样做的原因是单元格值的计算是从左到右的严格增量操作，并且计算单个单元格的操作顺序无关紧要（因为+是关联的和可交换的）。因此，步骤 1 之后任何给定线程的最终结果（“最右边的值”）可用于更正步骤 2 中负责其右侧范围的线程的结果。

于 2013-07-19T07:34:21.063 回答