d********w 发帖数: 363 | 1 我记得linkedin有道题问
给个tree,让你把每个结点的值更新为自己子树的sum,
写个多线程版本,改怎么做么?
是不是还有并行的quicksort, mergesort |
s******n 发帖数: 3946 | 2 假设K个线程,先BFS,得到K个子树后分别加,主程序等线程结束再累加。
排序的话就是先k个线程排序,再k-way merge吧。 |
d********w 发帖数: 363 | 3 先BFS,得到K个子树后分别加?还是不明白呢,能写过框架看看么
【在 s******n 的大作中提到】 : 假设K个线程,先BFS,得到K个子树后分别加,主程序等线程结束再累加。 : 排序的话就是先k个线程排序,再k-way merge吧。
|
s******n 发帖数: 3946 | 4 int sum = 0;
queue.add(root)
while (queue.size < K) {
node = queue.pop()
sum += node.value
queue.add(node.children)
}
create "queue.size" threads to sum each subtree
wait threads to finish....
for (int i=0; i
P.S.没看见要求每个node都要标sum,这样的话最后一步复杂点
【在 d********w 的大作中提到】 : 先BFS,得到K个子树后分别加?还是不明白呢,能写过框架看看么
|
r**********g 发帖数: 22734 | 5 merge sort并行性能很好,quicksort 不是那么好并行滴
【在 d********w 的大作中提到】 : 我记得linkedin有道题问 : 给个tree,让你把每个结点的值更新为自己子树的sum, : 写个多线程版本,改怎么做么? : 是不是还有并行的quicksort, mergesort
|
d********w 发帖数: 363 | 6 我记得linkedin有道题问
给个tree,让你把每个结点的值更新为自己子树的sum,
写个多线程版本,改怎么做么?
是不是还有并行的quicksort, mergesort |
s******n 发帖数: 3946 | 7 假设K个线程,先BFS,得到K个子树后分别加,主程序等线程结束再累加。
排序的话就是先k个线程排序,再k-way merge吧。 |
d********w 发帖数: 363 | 8 先BFS,得到K个子树后分别加?还是不明白呢,能写过框架看看么
【在 s******n 的大作中提到】 : 假设K个线程,先BFS,得到K个子树后分别加,主程序等线程结束再累加。 : 排序的话就是先k个线程排序,再k-way merge吧。
|
s******n 发帖数: 3946 | 9 int sum = 0;
queue.add(root)
while (queue.size < K) {
node = queue.pop()
sum += node.value
queue.add(node.children)
}
create "queue.size" threads to sum each subtree
wait threads to finish....
for (int i=0; i
P.S.没看见要求每个node都要标sum,这样的话最后一步复杂点
【在 d********w 的大作中提到】 : 先BFS,得到K个子树后分别加?还是不明白呢,能写过框架看看么
|
r**********g 发帖数: 22734 | 10 merge sort并行性能很好,quicksort 不是那么好并行滴
【在 d********w 的大作中提到】 : 我记得linkedin有道题问 : 给个tree,让你把每个结点的值更新为自己子树的sum, : 写个多线程版本,改怎么做么? : 是不是还有并行的quicksort, mergesort
|
g*****e 发帖数: 282 | 11 这个准确的说是thread safe tree。可以建一个lock array,对应各个nodes,计算一
个subtree时,把subtree root和其他node都lock。
【在 d********w 的大作中提到】 : 我记得linkedin有道题问 : 给个tree,让你把每个结点的值更新为自己子树的sum, : 写个多线程版本,改怎么做么? : 是不是还有并行的quicksort, mergesort
|
e***s 发帖数: 799 | 12 大牛能不能详细讲解一下. 能递归下去的时候新建出线程来吗?
比如 root.Value = getSum(root.Left) + getSum(root.Right);
改成 root.Value = new Thread(getSum(root.Left)).Start() + new Thread(getSume
(root.Right)).Start(); |
g*****e 发帖数: 282 | 13 一楼的multi thread不是这么理解的把?我的理解是k个thread要update这个tree,不
受tree控制
getSume
【在 e***s 的大作中提到】 : 大牛能不能详细讲解一下. 能递归下去的时候新建出线程来吗? : 比如 root.Value = getSum(root.Left) + getSum(root.Right); : 改成 root.Value = new Thread(getSum(root.Left)).Start() + new Thread(getSume : (root.Right)).Start();
|