avatar
d*e
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相等。
avatar
p*9
2
第一轮两个一组,互相通信
第二轮四个一组,编号0和2的互相通信,1和3的互相通信
第三轮八个一组,0和4,1和5,2和6,3和7互相通信
以此类推,log2(n)完成通信
如果n不是2的指数,需要处理一些边界状况
avatar
f*e
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() {

avatar
d*e
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.
: 学过并行算法的这个应该都知道。

avatar
l*a
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() {

avatar
d*e
6
山寨淘宝。。。
本来是五轮的,然后四轮就拜拜了

【在 l*****a 的大作中提到】
: 什么厂?这么过分
avatar
w*x
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);
}
}
};
avatar
h*6
8
我怎么感觉跟我前几天报的面试题很像啊~
http://www.mitbbs.com/article/JobHunting/32217999_3.html
就是把所有节点构造一个二叉树,然后从root开始recursive。其中send相当于是压栈
然后调用recursive函数,所以相当于block住,然后等着下面一级级传递,然后返回的
时候相当于是receive解除block,其实就是出栈。
avatar
g*y
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,其实就是出栈。

avatar
w*x
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

avatar
d*e
11
这个应该是最好的方法,转化为了二叉树就好理解了

【在 h******6 的大作中提到】
: 我怎么感觉跟我前几天报的面试题很像啊~
: http://www.mitbbs.com/article/JobHunting/32217999_3.html
: 就是把所有节点构造一个二叉树,然后从root开始recursive。其中send相当于是压栈
: 然后调用recursive函数,所以相当于block住,然后等着下面一级级传递,然后返回的
: 时候相当于是receive解除block,其实就是出栈。

avatar
d*e
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

avatar
g*y
13
这道题不可能logn吧,你最起码每个node都要访问一次才能计算sum

【在 w****x 的大作中提到】
:
: 这样是O(n)不是logn

avatar
h*6
14

有道理 就这道题来讲 单线程串行的话确实排列成线性就可以了 不过我在想如果是真
实网络中要是可以多线程(block阻塞是针对单独某个线程来讲的话) 那样组合成树效
果会更好些 另外 你那个代码最后还要把根节点的sum值再传送给所有其他节点 所以你
还得把你那个代码再重复一遍

【在 g****y 的大作中提到】
: 这道题不可能logn吧,你最起码每个node都要访问一次才能计算sum
avatar
g*y
15
bu不用啊,根结点是最后知道sum的

【在 h******6 的大作中提到】
:
: 有道理 就这道题来讲 单线程串行的话确实排列成线性就可以了 不过我在想如果是真
: 实网络中要是可以多线程(block阻塞是针对单独某个线程来讲的话) 那样组合成树效
: 果会更好些 另外 你那个代码最后还要把根节点的sum值再传送给所有其他节点 所以你
: 还得把你那个代码再重复一遍

avatar
h*9
16
MapReduce problem?
avatar
R*y
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的判断就可以了。
avatar
w*o
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);
}
avatar
d*a
19
你能写个程序说明下吗?真没明白你的意思,谢谢!

【在 h******6 的大作中提到】
: 我怎么感觉跟我前几天报的面试题很像啊~
: http://www.mitbbs.com/article/JobHunting/32217999_3.html
: 就是把所有节点构造一个二叉树,然后从root开始recursive。其中send相当于是压栈
: 然后调用recursive函数,所以相当于block住,然后等着下面一级级传递,然后返回的
: 时候相当于是receive解除block,其实就是出栈。

avatar
d*e
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相等。
avatar
p*9
21
第一轮两个一组,互相通信
第二轮四个一组,编号0和2的互相通信,1和3的互相通信
第三轮八个一组,0和4,1和5,2和6,3和7互相通信
以此类推,log2(n)完成通信
如果n不是2的指数,需要处理一些边界状况
avatar
f*e
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() {

avatar
d*e
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.
: 学过并行算法的这个应该都知道。

avatar
l*a
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() {

avatar
d*e
25
山寨淘宝。。。
本来是五轮的,然后四轮就拜拜了

【在 l*****a 的大作中提到】
: 什么厂?这么过分
avatar
w*x
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);
}
}
};
avatar
h*6
27
我怎么感觉跟我前几天报的面试题很像啊~
http://www.mitbbs.com/article/JobHunting/32217999_3.html
就是把所有节点构造一个二叉树,然后从root开始recursive。其中send相当于是压栈
然后调用recursive函数,所以相当于block住,然后等着下面一级级传递,然后返回的
时候相当于是receive解除block,其实就是出栈。
avatar
g*y
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,其实就是出栈。

avatar
w*x
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

avatar
d*e
30
这个应该是最好的方法,转化为了二叉树就好理解了

【在 h******6 的大作中提到】
: 我怎么感觉跟我前几天报的面试题很像啊~
: http://www.mitbbs.com/article/JobHunting/32217999_3.html
: 就是把所有节点构造一个二叉树,然后从root开始recursive。其中send相当于是压栈
: 然后调用recursive函数,所以相当于block住,然后等着下面一级级传递,然后返回的
: 时候相当于是receive解除block,其实就是出栈。

avatar
d*e
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

avatar
g*y
32
这道题不可能logn吧,你最起码每个node都要访问一次才能计算sum

【在 w****x 的大作中提到】
:
: 这样是O(n)不是logn

avatar
h*6
33

有道理 就这道题来讲 单线程串行的话确实排列成线性就可以了 不过我在想如果是真
实网络中要是可以多线程(block阻塞是针对单独某个线程来讲的话) 那样组合成树效
果会更好些 另外 你那个代码最后还要把根节点的sum值再传送给所有其他节点 所以你
还得把你那个代码再重复一遍

【在 g****y 的大作中提到】
: 这道题不可能logn吧,你最起码每个node都要访问一次才能计算sum
avatar
g*y
34
bu不用啊,根结点是最后知道sum的

【在 h******6 的大作中提到】
:
: 有道理 就这道题来讲 单线程串行的话确实排列成线性就可以了 不过我在想如果是真
: 实网络中要是可以多线程(block阻塞是针对单独某个线程来讲的话) 那样组合成树效
: 果会更好些 另外 你那个代码最后还要把根节点的sum值再传送给所有其他节点 所以你
: 还得把你那个代码再重复一遍

avatar
h*9
35
MapReduce problem?
avatar
R*y
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的判断就可以了。
avatar
w*o
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);
}
avatar
d*a
38
你能写个程序说明下吗?真没明白你的意思,谢谢!

【在 h******6 的大作中提到】
: 我怎么感觉跟我前几天报的面试题很像啊~
: http://www.mitbbs.com/article/JobHunting/32217999_3.html
: 就是把所有节点构造一个二叉树,然后从root开始recursive。其中send相当于是压栈
: 然后调用recursive函数,所以相当于block住,然后等着下面一级级传递,然后返回的
: 时候相当于是receive解除block,其实就是出栈。

avatar
w*u
39
mark
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。