m****u 发帖数: 3915 | 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. |
e*****e 发帖数: 1275 | 2 这题目咋看起来和find medium of k sorted array 那么像?
而且array size 都是N
难道是俺土冒,理解错了? |
x******0 发帖数: 178 | 3 CLRS chapter 9.3?
medium of
【在 m****u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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*******y 发帖数: 232 | 4 是不是sorted之后再在P个sorted array里面做binary search?
of
【在 m****u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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*******4 发帖数: 1401 | 5 让一个machine做master,其他所有人as slaves,进行一个
二分查找
master猜一个可能的中值,发给所有人,每个人看自己有多少个
值小于这个中值,然后告诉master,master就知道这个中值是
大了还是小了 |
s*****g 发帖数: 5159 | 6 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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*****g 发帖数: 5159 | 7 如果这些数的值域远大于N*P,而中位数又不在master machine里面呢?
【在 f*******4 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 让一个machine做master,其他所有人as slaves,进行一个 : 二分查找 : master猜一个可能的中值,发给所有人,每个人看自己有多少个 : 值小于这个中值,然后告诉master,master就知道这个中值是 : 大了还是小了
|
f*******4 发帖数: 1401 | 8 这个。。。有关系么?
【在 s*****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果这些数的值域远大于N*P,而中位数又不在master machine里面呢?
|
s*****g 发帖数: 5159 | 9 具体一下你的二分查找法?
假设P=3, N=5,你选地一台机器做master machine,你选择第一台的median去问其他两
台机器:
机器二:5个数都比第一台的median大。
机器三:4个数比第一台的median大。
下面怎么办?
【在 f*******4 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个。。。有关系么?
|
m****u 发帖数: 3915 | 10 看着很像这个median of median算法
可是感觉又不太对
因为这些数已经分散在各个machine上了
除非你需要把所有的数先放在一个machine里,然后再用median of median算法找合适的pivot
【在 x******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : CLRS chapter 9.3? : : medium of
|
f*******4 发帖数: 1401 | 11 我还要看自己有几个数比median大啊
那个median是master一开始猜的 具体猜法可以用所有机器local
median的平均数(比如)
下面我就知道猜的median是大是小 然后再猜下一个啊 比如 如果小了
那就猜(global_max - median) / 2,一开始大家先告诉master他们
的local_max
这个方法有什么问题么
【在 s*****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 具体一下你的二分查找法? : 假设P=3, N=5,你选地一台机器做master machine,你选择第一台的median去问其他两 : 台机器: : 机器二:5个数都比第一台的median大。 : 机器三:4个数比第一台的median大。 : 下面怎么办?
|
f*******4 发帖数: 1401 | 12 不需要把所有数放一个机器。。。只是消息传递
适的pivot
【在 m****u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 看着很像这个median of median算法 : 可是感觉又不太对 : 因为这些数已经分散在各个machine上了 : 除非你需要把所有的数先放在一个machine里,然后再用median of median算法找合适的pivot
|
s*****g 发帖数: 5159 | 13 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我还要看自己有几个数比median大啊 : 那个median是master一开始猜的 具体猜法可以用所有机器local : median的平均数(比如) : 下面我就知道猜的median是大是小 然后再猜下一个啊 比如 如果小了 : 那就猜(global_max - median) / 2,一开始大家先告诉master他们 : 的local_max : 这个方法有什么问题么
|