Chip-Seq 样品制备求助# Biology - 生物学
w*o
1 楼
一共有N个机器,每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找
到N^2个数的中数(median)?
我只能想到一种方法:如果知道数的总range,就把数划分成N个range,每个机器都算
自己range里面的数的个数,这样就知道median在哪个range的第K大。然后再把那个
range的拿出来同样分布到N个机器上处理,这样递归下去直到数目很小可以直接一台机
器sort找到。
但是这样只能对均匀分布才行,如果某个range的数特别多,一台机器都放不下就不行
了。
到N^2个数的中数(median)?
我只能想到一种方法:如果知道数的总range,就把数划分成N个range,每个机器都算
自己range里面的数的个数,这样就知道median在哪个range的第K大。然后再把那个
range的拿出来同样分布到N个机器上处理,这样递归下去直到数目很小可以直接一台机
器sort找到。
但是这样只能对均匀分布才行,如果某个range的数特别多,一台机器都放不下就不行
了。