求篇John Wiley的 paper - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Biology - 生物学

求篇John Wiley的 paper

求篇John Wiley的 paper# Biology - 生物学

m*u2013-05-30 07:05

1 楼

Given P machines, each containing an array of N elements, find the medium of
the array resulted by concatenating all the arrays on the machines.
You cannot move data across machines.

h*r2013-05-30 07:05

2 楼

Title:
Construction of a set of convenient saccharomyces cerevisiae strains that
are isogenic to S288C
DOI: 10.1002/yea.320110107
Yeast
Volume 11, Issue 1, pages 53–55, January 1995
My email is m******[email protected] Thank you so much!

e*e2013-05-30 07:05

3 楼

这题目咋看起来和find medium of k sorted array 那么像？
而且array size 都是N
难道是俺土冒，理解错了？

h*r2013-05-30 07:05

4 楼

不用了，我自己在Winston lab的主页上下到了。多谢！

x*02013-05-30 07:05

5 楼

CLRS chapter 9.3?

medium of

【在 m****u 的大作中提到】

: Given P machines, each containing an array of N elements, find the medium of
: the array resulted by concatenating all the arrays on the machines.
: You cannot move data across machines.

b*y2013-05-30 07:05

6 楼

是不是sorted之后再在P个sorted array里面做binary search？

of

【在 m****u 的大作中提到】

: Given P machines, each containing an array of N elements, find the medium of
: the array resulted by concatenating all the arrays on the machines.
: You cannot move data across machines.

f*42013-05-30 07:05

7 楼

让一个machine做master，其他所有人as slaves，进行一个
二分查找
master猜一个可能的中值，发给所有人，每个人看自己有多少个
值小于这个中值，然后告诉master，master就知道这个中值是
大了还是小了

s*g2013-05-30 07:05

8 楼

This involves odd and even number case. For simplicity, we assume P and N ar
e both odd.
We sort the P arrays on the P machines, each of them has a mediam within the
machine.
We sort the P medians, and get an order.
The (N-1)/2 * (P-1)/2 numbers that larger than the larger (P-1)/2 medians ar
e dismissed.
The (N-1)/2 * (P-1)/2 numbers that smaller than the smaller (P-1)/2 medians
are dismissed.
Look at the following chart
A1 > B1 > C1 > D1 > E1
A2 > B2 > C2 > D2 > E2
A3 > B3 > C3 > D3 > E3
and C1 >C2 >C3,
we could dismiss A1, B1, and D3, E3.
Now we compare sort D1, C2, and B3, we could again dissmiss the numbers are
two corners. Recursively doing this will result in a chain of totally ordere
d element so that you could pick the median.
I feel something is missing in this question. Some relations ship between P
and N, and whether they are odd or even.

of

【在 m****u 的大作中提到】

: Given P machines, each containing an array of N elements, find the medium of
: the array resulted by concatenating all the arrays on the machines.
: You cannot move data across machines.

s*g2013-05-30 07:05

9 楼

如果这些数的值域远大于N*P，而中位数又不在master machine里面呢？

【在 f*******4 的大作中提到】

: 让一个machine做master，其他所有人as slaves，进行一个
: 二分查找
: master猜一个可能的中值，发给所有人，每个人看自己有多少个
: 值小于这个中值，然后告诉master，master就知道这个中值是
: 大了还是小了

f*42013-05-30 07:05

10 楼

这个。。。有关系么？

【在 s*****g 的大作中提到】

: 如果这些数的值域远大于N*P，而中位数又不在master machine里面呢？

s*g2013-05-30 07:05

11 楼

具体一下你的二分查找法？
假设P=3, N=5，你选地一台机器做master machine，你选择第一台的median去问其他两
台机器：
机器二：5个数都比第一台的median大。
机器三：4个数比第一台的median大。
下面怎么办？

【在 f*******4 的大作中提到】

: 这个。。。有关系么？

m*u2013-05-30 07:05

12 楼

看着很像这个median of median算法
可是感觉又不太对
因为这些数已经分散在各个machine上了
除非你需要把所有的数先放在一个machine里，然后再用median of median算法找合适的pivot

【在 x******0 的大作中提到】

: CLRS chapter 9.3?
:
: medium of

f*42013-05-30 07:05

13 楼

我还要看自己有几个数比median大啊
那个median是master一开始猜的具体猜法可以用所有机器local
median的平均数（比如）
下面我就知道猜的median是大是小然后再猜下一个啊比如如果小了
那就猜(global_max - median) / 2，一开始大家先告诉master他们
的local_max
这个方法有什么问题么

【在 s*****g 的大作中提到】

: 具体一下你的二分查找法？
: 假设P=3, N=5，你选地一台机器做master machine，你选择第一台的median去问其他两
: 台机器：
: 机器二：5个数都比第一台的median大。
: 机器三：4个数比第一台的median大。
: 下面怎么办？

f*42013-05-30 07:05

14 楼

不需要把所有数放一个机器。。。只是消息传递

适的pivot

【在 m****u 的大作中提到】

: 看着很像这个median of median算法
: 可是感觉又不太对
: 因为这些数已经分散在各个machine上了
: 除非你需要把所有的数先放在一个machine里，然后再用median of median算法找合适的pivot

s*g2013-05-30 07:05

15 楼

Here is an example:
master machine: 1 2 3 4 5
slave machine 1: 100 200 300 400 500
slave machine 2: 1*10^10 2*10^10 3*10^10 4*10^10 5*10^10
You could claim we choose slave machine 1 as master machine by looking
through all elements in all machines. Still, you need to write an
automatic algorithm, for example, in C or Java, and see your worst case
complexity.
Say fill up the following function:
/*machines is the PxN array that represents the elements. You are not
allow to use more than O(P) space. Your are not allow to move elements
between machines[i][m] and machines[j][n] unless i==j. Return the median
element in machines*/
int find_median(int** machines, int N, int P)
{
}

【在 f*******4 的大作中提到】

: 我还要看自己有几个数比median大啊
: 那个median是master一开始猜的具体猜法可以用所有机器local
: median的平均数（比如）
: 下面我就知道猜的median是大是小然后再猜下一个啊比如如果小了
: 那就猜(global_max - median) / 2，一开始大家先告诉master他们
: 的local_max
: 这个方法有什么问题么