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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 让一个machine做master，其他所有人as slaves，进行一个
: 二分查找
: master猜一个可能的中值，发给所有人，每个人看自己有多少个
: 值小于这个中值，然后告诉master，master就知道这个中值是
: 大了还是小了
|
f*******4
发帖数: 1401 | 8 这个。。。有关系么？
【在 s*****g 的大作中提到】
: 如果这些数的值域远大于N*P，而中位数又不在master machine里面呢？
|
s*****g
发帖数: 5159 | 9 具体一下你的二分查找法？
假设P=3, N=5，你选地一台机器做master machine，你选择第一台的median去问其他两
台机器：
机器二：5个数都比第一台的median大。
机器三：4个数比第一台的median大。
下面怎么办？
【在 f*******4 的大作中提到】
: 这个。。。有关系么？
|
m****u
发帖数: 3915 | 10 看着很像这个median of median算法
可是感觉又不太对
因为这些数已经分散在各个machine上了
除非你需要把所有的数先放在一个machine里，然后再用median of median算法找合适的pivot
【在 x******0 的大作中提到】
: 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 的大作中提到】
: 具体一下你的二分查找法？
: 假设P=3, N=5，你选地一台机器做master machine，你选择第一台的median去问其他两
: 台机器：
: 机器二：5个数都比第一台的median大。
: 机器三：4个数比第一台的median大。
: 下面怎么办？
|
f*******4
发帖数: 1401 | 12 不需要把所有数放一个机器。。。只是消息传递
适的pivot
【在 m****u 的大作中提到】
: 看着很像这个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 的大作中提到】
: 我还要看自己有几个数比median大啊
: 那个median是master一开始猜的 具体猜法可以用所有机器local
: median的平均数（比如）
: 下面我就知道猜的median是大是小 然后再猜下一个啊 比如 如果小了
: 那就猜(global_max - median) / 2，一开始大家先告诉master他们
: 的local_max
: 这个方法有什么问题么
|
