d**e
发帖数: 6098 | 1 好像在版上没见过。我没做出来，于是直接被提前轰了出去。。。
------------------------------------
有n个节点，id为1到n,各有一个value，两send和receive的api
class node {
int id; // 已知
int value; // 已知
int sum; // 在下面run函数里设定，是所以节点的value的sum.
void send(int toId, int value);
int receive(int fromId);
void run() {
// 现实这个功能
sum = ....
}
}
这个是block send block receive,任意两个节点，比如a和b，一定要是a在receive b
而 b又准备send a，这个通信才能成功，否则比如a, b, c
a send to b
b receive from c
c send to a
没有两个配对，于是都在相互等待，通信不成功。
算法就是设计上面run功能，n个节点同时运行run(),使成这n个节点通信成功，更新各
自的sum值，要求最后平衡或者通信结束时所有的sum相等。 |
p******9
发帖数: 47 | 2 第一轮两个一组，互相通信
第二轮四个一组，编号0和2的互相通信，1和3的互相通信
第三轮八个一组，0和4，1和5，2和6，3和7互相通信
以此类推，log2(n)完成通信
如果n不是2的指数，需要处理一些边界状况 |
f*****e
发帖数: 2992 | 3 首先进程i与i+n/2通信，进程i存和。这个为一个step，并行进行。所有进程参与通信。
再进程i与i+n/4通信，进程i存和。进程0至n/2参与通信
.
.
.
最后进程0与1通信，进程0存和。
然后上面过程倒过来propagate sum
总共2log(n) steps.
学过并行算法的这个应该都知道。
【在 d**e 的大作中提到】
: 好像在版上没见过。我没做出来，于是直接被提前轰了出去。。。
: ------------------------------------
: 有n个节点，id为1到n,各有一个value，两send和receive的api
: class node {
: int id; // 已知
: int value; // 已知
: int sum; // 在下面run函数里设定，是所以节点的value的sum.
: void send(int toId, int value);
: int receive(int fromId);
: void run() {
|
d**e
发帖数: 6098 | 4 看来不是难题
而且经你一提，类似的题以前是见过，只不过我遇到这道是经过变形
我没能举一反三
信。
【在 f*****e 的大作中提到】
: 首先进程i与i+n/2通信，进程i存和。这个为一个step，并行进行。所有进程参与通信。
: 再进程i与i+n/4通信，进程i存和。进程0至n/2参与通信
: .
: .
: .
: 最后进程0与1通信，进程0存和。
: 然后上面过程倒过来propagate sum
: 总共2log(n) steps.
: 学过并行算法的这个应该都知道。
|
l*****a
发帖数: 14598 | 5 什么厂？这么过分
【在 d**e 的大作中提到】
: 好像在版上没见过。我没做出来，于是直接被提前轰了出去。。。
: ------------------------------------
: 有n个节点，id为1到n,各有一个value，两send和receive的api
: class node {
: int id; // 已知
: int value; // 已知
: int sum; // 在下面run函数里设定，是所以节点的value的sum.
: void send(int toId, int value);
: int receive(int fromId);
: void run() {
|
d**e
发帖数: 6098 | 6 山寨淘宝。。。
本来是五轮的，然后四轮就拜拜了
【在 l*****a 的大作中提到】
: 什么厂？这么过分
|
w****x
发帖数: 2483 | 7 这题真TM坑爹啊~~
class node
{
int id;
int value;
int sum;
void send(int toId, int value);
int receive(int fromId);
void run()
{
int tmp = x;
int nLev = 0;
vector vec;
while (tmp%2 == 0)
{
int nRecv = x - (1 << nLev);
sum += receive(nRecv);
vec.push_back(nRecv);
nLev++;
}
if (id != n)
{
int nSend = min(id + (1 << nLev), n);
send(nSend, sum);
sum = receive(nSend);
}
else
{
int nBase = 0;
int nLft = id;
while (nLft > 1)
{
int nFlg = 1;
while (nFlg > nLft)
nFlg = (nFlg << 1);
if (nFlg == nLft) return;
nFlg = (nFlg >> 1);
sum += receive(nBase + nFlg);
vec.push_back(nBase + nFlg);
nBase += nFlg;
nLft -= nFlg;
}
for (vector::iterator it = vec.begin(); it != vec.end(); it++)
send(*it, sum);
}
}
}; |
h******6
发帖数: 2697 | 8 我怎么感觉跟我前几天报的面试题很像啊~
http://www.mitbbs.com/article/JobHunting/32217999_3.html
就是把所有节点构造一个二叉树，然后从root开始recursive。其中send相当于是压栈
然后调用recursive函数，所以相当于block住，然后等着下面一级级传递，然后返回的
时候相当于是receive解除block，其实就是出栈。 |
g****y
发帖数: 240 | 9 我感觉是一样的，受了你的启发，感觉不用构造二叉树，就直接排成一条直线send就好
了。1 -> 2,
2 -> 3, 3->n,然后n->3, 3->2, 2->1
def run():
value_from_left = 0
if id != 1:
value_from_left = receive(id - 1)
if id != n:
send(id + 1, value + value_from_left)
value_from_right = 0
if id != n:
value_from_right = receive(id + 1)
if id != 1:
send(id - 1, value + value_from_right)
sum = value_from_left + value + value_from_right
【在 h******6 的大作中提到】
: 我怎么感觉跟我前几天报的面试题很像啊~
: http://www.mitbbs.com/article/JobHunting/32217999_3.html
: 就是把所有节点构造一个二叉树，然后从root开始recursive。其中send相当于是压栈
: 然后调用recursive函数，所以相当于block住，然后等着下面一级级传递，然后返回的
: 时候相当于是receive解除block，其实就是出栈。
|
w****x
发帖数: 2483 | 10
这样是O(n)不是logn
【在 g****y 的大作中提到】
: 我感觉是一样的，受了你的启发，感觉不用构造二叉树，就直接排成一条直线send就好
: 了。1 -> 2,
: 2 -> 3, 3->n,然后n->3, 3->2, 2->1
: def run():
: value_from_left = 0
: if id != 1:
: value_from_left = receive(id - 1)
: if id != n:
: send(id + 1, value + value_from_left)
: value_from_right = 0
|
|
|
d**e
发帖数: 6098 | 11 这个应该是最好的方法，转化为了二叉树就好理解了
【在 h******6 的大作中提到】
: 我怎么感觉跟我前几天报的面试题很像啊~
: http://www.mitbbs.com/article/JobHunting/32217999_3.html
: 就是把所有节点构造一个二叉树，然后从root开始recursive。其中send相当于是压栈
: 然后调用recursive函数，所以相当于block住，然后等着下面一级级传递，然后返回的
: 时候相当于是receive解除block，其实就是出栈。
|
d**e
发帖数: 6098 | 12 强！
【在 g****y 的大作中提到】
: 我感觉是一样的，受了你的启发，感觉不用构造二叉树，就直接排成一条直线send就好
: 了。1 -> 2,
: 2 -> 3, 3->n,然后n->3, 3->2, 2->1
: def run():
: value_from_left = 0
: if id != 1:
: value_from_left = receive(id - 1)
: if id != n:
: send(id + 1, value + value_from_left)
: value_from_right = 0
|
g****y
发帖数: 240 | 13 这道题不可能logn吧，你最起码每个node都要访问一次才能计算sum
【在 w****x 的大作中提到】
:
: 这样是O(n)不是logn
|
h******6
发帖数: 2697 | 14
有道理 就这道题来讲 单线程串行的话确实排列成线性就可以了 不过我在想如果是真
实网络中要是可以多线程（block阻塞是针对单独某个线程来讲的话） 那样组合成树效
果会更好些 另外 你那个代码最后还要把根节点的sum值再传送给所有其他节点 所以你
还得把你那个代码再重复一遍
【在 g****y 的大作中提到】
: 这道题不可能logn吧，你最起码每个node都要访问一次才能计算sum
|
g****y
发帖数: 240 | 15 bu不用啊，根结点是最后知道sum的
【在 h******6 的大作中提到】
:
: 有道理 就这道题来讲 单线程串行的话确实排列成线性就可以了 不过我在想如果是真
: 实网络中要是可以多线程（block阻塞是针对单独某个线程来讲的话） 那样组合成树效
: 果会更好些 另外 你那个代码最后还要把根节点的sum值再传送给所有其他节点 所以你
: 还得把你那个代码再重复一遍
|
h**********9
发帖数: 3252 | |
R********y
发帖数: 88 | 17 可以log n吧。
run(){
int j = 0;
while (true) {
if (2^j >= n) break;
if (i % 2^j == 0 && i + 2^j <= n)
val += receive(i+2^j);
else
send(i-2^j, val);
j++;
}
}
最后结果存在第一个节点。
这里假设只有receive会block，send不会。否则，send那层再加一个i%2^j == 1&& i-2
^j>0的判断就可以了。 |
w***o
发帖数: 109 | 18 run() {
sum = value;
if (id * 2 <= n)
sum += receive(id * 2);
if (id * 2 + 1 <= n)
sum += receive(id * 2 + 1);
if (id != 1)
{
send(id / 2, sum);
sum = receive(id / 2);
}
if (id * 2 <= n)
send(id * 2, sum);
if (id * 2 + 1 <= n)
send(id * 2 + 1, sum);
} |
d******a
发帖数: 238 | 19 你能写个程序说明下吗？真没明白你的意思，谢谢！
【在 h******6 的大作中提到】
: 我怎么感觉跟我前几天报的面试题很像啊~
: http://www.mitbbs.com/article/JobHunting/32217999_3.html
: 就是把所有节点构造一个二叉树，然后从root开始recursive。其中send相当于是压栈
: 然后调用recursive函数，所以相当于block住，然后等着下面一级级传递，然后返回的
: 时候相当于是receive解除block，其实就是出栈。
|
d**e
发帖数: 6098 | 20 好像在版上没见过。我没做出来，于是直接被提前轰了出去。。。
------------------------------------
有n个节点，id为1到n,各有一个value，两send和receive的api
class node {
int id; // 已知
int value; // 已知
int sum; // 在下面run函数里设定，是所以节点的value的sum.
void send(int toId, int value);
int receive(int fromId);
void run() {
// 现实这个功能
sum = ....
}
}
这个是block send block receive,任意两个节点，比如a和b，一定要是a在receive b
而 b又准备send a，这个通信才能成功，否则比如a, b, c
a send to b
b receive from c
c send to a
没有两个配对，于是都在相互等待，通信不成功。
算法就是设计上面run功能，n个节点同时运行run(),使成这n个节点通信成功，更新各
自的sum值，要求最后平衡或者通信结束时所有的sum相等。 |
|
|
p******9
发帖数: 47 | 21 第一轮两个一组，互相通信
第二轮四个一组，编号0和2的互相通信，1和3的互相通信
第三轮八个一组，0和4，1和5，2和6，3和7互相通信
以此类推，log2(n)完成通信
如果n不是2的指数，需要处理一些边界状况 |
f*****e
发帖数: 2992 | 22 首先进程i与i+n/2通信，进程i存和。这个为一个step，并行进行。所有进程参与通信。
再进程i与i+n/4通信，进程i存和。进程0至n/2参与通信
.
.
.
最后进程0与1通信，进程0存和。
然后上面过程倒过来propagate sum
总共2log(n) steps.
学过并行算法的这个应该都知道。
【在 d**e 的大作中提到】
: 好像在版上没见过。我没做出来，于是直接被提前轰了出去。。。
: ------------------------------------
: 有n个节点，id为1到n,各有一个value，两send和receive的api
: class node {
: int id; // 已知
: int value; // 已知
: int sum; // 在下面run函数里设定，是所以节点的value的sum.
: void send(int toId, int value);
: int receive(int fromId);
: void run() {
|
d**e
发帖数: 6098 | 23 看来不是难题
而且经你一提，类似的题以前是见过，只不过我遇到这道是经过变形
我没能举一反三
信。
【在 f*****e 的大作中提到】
: 首先进程i与i+n/2通信，进程i存和。这个为一个step，并行进行。所有进程参与通信。
: 再进程i与i+n/4通信，进程i存和。进程0至n/2参与通信
: .
: .
: .
: 最后进程0与1通信，进程0存和。
: 然后上面过程倒过来propagate sum
: 总共2log(n) steps.
: 学过并行算法的这个应该都知道。
|
l*****a
发帖数: 14598 | 24 什么厂？这么过分
【在 d**e 的大作中提到】
: 好像在版上没见过。我没做出来，于是直接被提前轰了出去。。。
: ------------------------------------
: 有n个节点，id为1到n,各有一个value，两send和receive的api
: class node {
: int id; // 已知
: int value; // 已知
: int sum; // 在下面run函数里设定，是所以节点的value的sum.
: void send(int toId, int value);
: int receive(int fromId);
: void run() {
|
d**e
发帖数: 6098 | 25 山寨淘宝。。。
本来是五轮的，然后四轮就拜拜了
【在 l*****a 的大作中提到】
: 什么厂？这么过分
|
w****x
发帖数: 2483 | 26 这题真TM坑爹啊~~
class node
{
int id;
int value;
int sum;
void send(int toId, int value);
int receive(int fromId);
void run()
{
int tmp = x;
int nLev = 0;
vector vec;
while (tmp%2 == 0)
{
int nRecv = x - (1 << nLev);
sum += receive(nRecv);
vec.push_back(nRecv);
nLev++;
}
if (id != n)
{
int nSend = min(id + (1 << nLev), n);
send(nSend, sum);
sum = receive(nSend);
}
else
{
int nBase = 0;
int nLft = id;
while (nLft > 1)
{
int nFlg = 1;
while (nFlg > nLft)
nFlg = (nFlg << 1);
if (nFlg == nLft) return;
nFlg = (nFlg >> 1);
sum += receive(nBase + nFlg);
vec.push_back(nBase + nFlg);
nBase += nFlg;
nLft -= nFlg;
}
for (vector::iterator it = vec.begin(); it != vec.end(); it++)
send(*it, sum);
}
}
}; |
h******6
发帖数: 2697 | 27 我怎么感觉跟我前几天报的面试题很像啊~
http://www.mitbbs.com/article/JobHunting/32217999_3.html
就是把所有节点构造一个二叉树，然后从root开始recursive。其中send相当于是压栈
然后调用recursive函数，所以相当于block住，然后等着下面一级级传递，然后返回的
时候相当于是receive解除block，其实就是出栈。 |
g****y
发帖数: 240 | 28 我感觉是一样的，受了你的启发，感觉不用构造二叉树，就直接排成一条直线send就好
了。1 -> 2,
2 -> 3, 3->n,然后n->3, 3->2, 2->1
def run():
value_from_left = 0
if id != 1:
value_from_left = receive(id - 1)
if id != n:
send(id + 1, value + value_from_left)
value_from_right = 0
if id != n:
value_from_right = receive(id + 1)
if id != 1:
send(id - 1, value + value_from_right)
sum = value_from_left + value + value_from_right
【在 h******6 的大作中提到】
: 我怎么感觉跟我前几天报的面试题很像啊~
: http://www.mitbbs.com/article/JobHunting/32217999_3.html
: 就是把所有节点构造一个二叉树，然后从root开始recursive。其中send相当于是压栈
: 然后调用recursive函数，所以相当于block住，然后等着下面一级级传递，然后返回的
: 时候相当于是receive解除block，其实就是出栈。
|
w****x
发帖数: 2483 | 29
这样是O(n)不是logn
【在 g****y 的大作中提到】
: 我感觉是一样的，受了你的启发，感觉不用构造二叉树，就直接排成一条直线send就好
: 了。1 -> 2,
: 2 -> 3, 3->n,然后n->3, 3->2, 2->1
: def run():
: value_from_left = 0
: if id != 1:
: value_from_left = receive(id - 1)
: if id != n:
: send(id + 1, value + value_from_left)
: value_from_right = 0
|
d**e
发帖数: 6098 | 30 这个应该是最好的方法，转化为了二叉树就好理解了
【在 h******6 的大作中提到】
: 我怎么感觉跟我前几天报的面试题很像啊~
: http://www.mitbbs.com/article/JobHunting/32217999_3.html
: 就是把所有节点构造一个二叉树，然后从root开始recursive。其中send相当于是压栈
: 然后调用recursive函数，所以相当于block住，然后等着下面一级级传递，然后返回的
: 时候相当于是receive解除block，其实就是出栈。
|
|
|
d**e
发帖数: 6098 | 31 强！
【在 g****y 的大作中提到】
: 我感觉是一样的，受了你的启发，感觉不用构造二叉树，就直接排成一条直线send就好
: 了。1 -> 2,
: 2 -> 3, 3->n,然后n->3, 3->2, 2->1
: def run():
: value_from_left = 0
: if id != 1:
: value_from_left = receive(id - 1)
: if id != n:
: send(id + 1, value + value_from_left)
: value_from_right = 0
|
g****y
发帖数: 240 | 32 这道题不可能logn吧，你最起码每个node都要访问一次才能计算sum
【在 w****x 的大作中提到】
:
: 这样是O(n)不是logn
|
h******6
发帖数: 2697 | 33
有道理 就这道题来讲 单线程串行的话确实排列成线性就可以了 不过我在想如果是真
实网络中要是可以多线程（block阻塞是针对单独某个线程来讲的话） 那样组合成树效
果会更好些 另外 你那个代码最后还要把根节点的sum值再传送给所有其他节点 所以你
还得把你那个代码再重复一遍
【在 g****y 的大作中提到】
: 这道题不可能logn吧，你最起码每个node都要访问一次才能计算sum
|
g****y
发帖数: 240 | 34 bu不用啊，根结点是最后知道sum的
【在 h******6 的大作中提到】
:
: 有道理 就这道题来讲 单线程串行的话确实排列成线性就可以了 不过我在想如果是真
: 实网络中要是可以多线程（block阻塞是针对单独某个线程来讲的话） 那样组合成树效
: 果会更好些 另外 你那个代码最后还要把根节点的sum值再传送给所有其他节点 所以你
: 还得把你那个代码再重复一遍
|
h**********9
发帖数: 3252 | |
R********y
发帖数: 88 | 36 可以log n吧。
run(){
int j = 0;
while (true) {
if (2^j >= n) break;
if (i % 2^j == 0 && i + 2^j <= n)
val += receive(i+2^j);
else
send(i-2^j, val);
j++;
}
}
最后结果存在第一个节点。
这里假设只有receive会block，send不会。否则，send那层再加一个i%2^j == 1&& i-2
^j>0的判断就可以了。 |
w***o
发帖数: 109 | 37 run() {
sum = value;
if (id * 2 <= n)
sum += receive(id * 2);
if (id * 2 + 1 <= n)
sum += receive(id * 2 + 1);
if (id != 1)
{
send(id / 2, sum);
sum = receive(id / 2);
}
if (id * 2 <= n)
send(id * 2, sum);
if (id * 2 + 1 <= n)
send(id * 2 + 1, sum);
} |
d******a
发帖数: 238 | 38 你能写个程序说明下吗？真没明白你的意思，谢谢！
【在 h******6 的大作中提到】
: 我怎么感觉跟我前几天报的面试题很像啊~
: http://www.mitbbs.com/article/JobHunting/32217999_3.html
: 就是把所有节点构造一个二叉树，然后从root开始recursive。其中send相当于是压栈
: 然后调用recursive函数，所以相当于block住，然后等着下面一级级传递，然后返回的
: 时候相当于是receive解除block，其实就是出栈。
|
w****u
发帖数: 3147 | |
