w****o
发帖数: 2210 | 1 一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找
到N^2个数的中数(median)？
我只能想到一种方法：如果知道数的总range，就把数划分成N个range，每个机器都算
自己range里面的数的个数，这样就知道median在哪个range的第K大。然后再把那个
range的拿出来同样分布到N个机器上处理，这样递归下去直到数目很小可以直接一台机
器sort找到。
但是这样只能对均匀分布才行，如果某个range的数特别多，一台机器都放不下就不行
了。 |
h*********3
发帖数: 111 | 2
一个笨办法是：
每台机器放n个数，然后排序。
然后挨个数，直到找到median.
【在 w****o 的大作中提到】
: 一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找
: 到N^2个数的中数(median)？
: 我只能想到一种方法：如果知道数的总range，就把数划分成N个range，每个机器都算
: 自己range里面的数的个数，这样就知道median在哪个range的第K大。然后再把那个
: range的拿出来同样分布到N个机器上处理，这样递归下去直到数目很小可以直接一台机
: 器sort找到。
: 但是这样只能对均匀分布才行，如果某个range的数特别多，一台机器都放不下就不行
: 了。
|
l*****a
发帖数: 14598 | 3 你做得就是正解
为啥没有信心呢
【在 w****o 的大作中提到】
: 一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找
: 到N^2个数的中数(median)？
: 我只能想到一种方法：如果知道数的总range，就把数划分成N个range，每个机器都算
: 自己range里面的数的个数，这样就知道median在哪个range的第K大。然后再把那个
: range的拿出来同样分布到N个机器上处理，这样递归下去直到数目很小可以直接一台机
: 器sort找到。
: 但是这样只能对均匀分布才行，如果某个range的数特别多，一台机器都放不下就不行
: 了。
|
c*****n
发帖数: 96 | 4 My thought on this issue:
To generalize the problem, let say, for machine i, it has an array A[i], A[i
+1] ... A[j]. The initial state is i = 0; j = N-1;
Assuming there is a controller machine C.
1) Sort N numbers on each machine.
2) For each machine, randomly pick up a number A[k] (i<=k<=j) and send it to
the controller C. The Controller C calculates the median M from these N
numbers
3) Controller sends M back to each machine and let them report P[i] back
which is number of data that are less than M on the machine i.
let T = P[0]+P[1]+...+P[n],
M = lower(N*N/2) + 1
if T = M, then we find the median;
if T > M, then the problem becomes finding the median in N machines, for
ith machine, the array is A[i]...A[i+P[i]-1]
if T < M, then the problem becomes finding the (M-T)th item in N machine,
for ith machine, the array is A[i+P[i]+1]..A[j]
so the problem can be solved recursively.
The time complexity should be O(N*N), since each number should only be
visited once. |
g***y
发帖数: 764 | 5 你说的办法对非均匀分布也可以用，就是动态地去re-range，要求scheduler比较智能
可以根据动态信息重新schedule job.
【在 w****o 的大作中提到】
: 一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找
: 到N^2个数的中数(median)？
: 我只能想到一种方法：如果知道数的总range，就把数划分成N个range，每个机器都算
: 自己range里面的数的个数，这样就知道median在哪个range的第K大。然后再把那个
: range的拿出来同样分布到N个机器上处理，这样递归下去直到数目很小可以直接一台机
: 器sort找到。
: 但是这样只能对均匀分布才行，如果某个range的数特别多，一台机器都放不下就不行
: 了。
|
h*********3
发帖数: 111 | 6 为啥是正解呢？把数按range分到各个机器的时候，不就已经统计出在这个range有多
少个数了吗？那么为什么还需要在每个机器上统计各个range有多少个数呢？不如就把
这些数存在本机的disk上？
【在 l*****a 的大作中提到】
: 你做得就是正解
: 为啥没有信心呢
|
g***y
发帖数: 764 | 7 不是， 加入知道这些数range是0-1000，那假设是均匀分布的，如果有10台机器，
那就按0-100，100-200，分给这些机器处理。每个机器负责数range内的个数。
如果分着分着发现有的机器明显overload,有的underloda,那scheduler可以再进行
re-range, load balancing..
【在 h*********3 的大作中提到】
: 为啥是正解呢？把数按range分到各个机器的时候，不就已经统计出在这个range有多
: 少个数了吗？那么为什么还需要在每个机器上统计各个range有多少个数呢？不如就把
: 这些数存在本机的disk上？
|
h*********3
发帖数: 111 | 8
当你分得时候，你就已经统计出来各个range里的数目了吧。
何必还需要各个机器在统计数目呢？
【在 g***y 的大作中提到】
: 不是， 加入知道这些数range是0-1000，那假设是均匀分布的，如果有10台机器，
: 那就按0-100，100-200，分给这些机器处理。每个机器负责数range内的个数。
: 如果分着分着发现有的机器明显overload,有的underloda,那scheduler可以再进行
: re-range, load balancing..
|
g***y
发帖数: 764 | 9 当然没有。加入有1000个数放在network file system上面，10台机器都去读这些数，
机器1只负责数0-100内的数，加入读到range外面的，ignore。
【在 h*********3 的大作中提到】
:
: 当你分得时候，你就已经统计出来各个range里的数目了吧。
: 何必还需要各个机器在统计数目呢？
|
h*********3
发帖数: 111 | 10 题目是n台机器，没台n个数吧。
如果是你说的这种情况（有1000个数放在network file system上面),也不需要每台
机器都读阿。如果10台都读，那就读了1000*10次，还不如就一台读，那就是1000次，
一样得到了分布情况阿。
【在 g***y 的大作中提到】
: 当然没有。加入有1000个数放在network file system上面，10台机器都去读这些数，
: 机器1只负责数0-100内的数，加入读到range外面的，ignore。
|
g***y
发帖数: 764 | 11 n台机器 每个n个数 同样可以用类似的办法，分m个range(noted as 0,1,2,..m-1),每
台机器负责数自己的n个数，输出m个，key是0,1...m-1, value包括range
内出现的个数，和一个pointer指向local n个数中range内的那部分数。
全部弄完后，n台机器在进行aggregation,产生最终,这时候value是
aggregated value, 到这时候，可以看出median具体在哪个range内。剩下的工作就是
告诉n台机器去找这个range内的第X个数了。
【在 h*********3 的大作中提到】
: 题目是n台机器，没台n个数吧。
: 如果是你说的这种情况（有1000个数放在network file system上面),也不需要每台
: 机器都读阿。如果10台都读，那就读了1000*10次，还不如就一台读，那就是1000次，
: 一样得到了分布情况阿。
|
R***i
发帖数: 78 | 12 随机一个数字, 发送到每台机器上
每台电脑返回大于次数的数字个数x, 以及小于此数的数字个数y
如果X1+X2+...+Xn == Y1+Y2+...Yn, 则找到median
不然就用二分法生产一个新的数字继续发送到每台电脑上，循环 |
