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();
|
