📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 4327| 回复: 7
跳转到指定楼层
上一主题 下一主题
收起左侧

Facebook, 计算分布在多台机器上数的median

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
实际上是一个设计题, 很多机器,每台机器上都有很一部分数据,如何输出分布在所有机器上的所有数据的median

上一篇:Google : 随机生成圆中的点
下一篇:Microsoft : 找出BST上任意节点的下一个节点
🔗
 楼主| wwwyhx 2011-9-4 03:37:54 | 只看该作者
全局:
说说我的见解, 有更好的请补充:

1. 首先无序数组中partition成对等的两部分,左边部分小于等于右边部分, 中间的那个数是median, 典型的top-k问题,O(n).

2. 给定两个数组,如何求他们的median? 分别求出两个数组的median m1, m2, 两个数组的median就在m1, m2之间,这样每次缩短了数组的范围.

3. 多台机器上的情况, 两台机器分别求出自己的那部分然后再merge到其中一台机器上. 整个过程就像一颗二叉树,节点只指向父节点, 从底层开始向上merge, root的那台机器上得到结果, 像mapreduce
回复

使用道具 举报

🔗
nooneknow 2011-11-2 09:12:01 | 只看该作者
全局:
说说我的见解, 有更好的请补充:

1. 首先无序数组中partition成对等的两部分,左边部分小于等于右边部分, 中间的那个数是median, 典型的top-k问题,O(n).

2. 给定两个数组,如何求他们的median? 分别求出两个数组的median m1, m2, 两个数组的median就在m1, m2之间,这样每次缩短了数组的范围.

3. 多台机器上的情况, 两台机器分别求出自己的那部分然后再merge到其中一台机器上. 整个过程就像一颗二叉树,节点只指向父节点, 从底层开始向上merge, root的那台机器上得到结果, 像mapreduce
wwwyhx 发表于 2011-9-4 03:37


merge的代价高啊。找median可以不用merge。

每台机器先sort自己的那部分。假设有机器1,2,……,M。把机器1当做main server。
假设每个机器上都有n个元素。a[i, j]表示第i个机器上的第j个元素。利用二分查找的思想。

先令mid = a[1, n/2]为基准。
然后在机器2到M上二分查找多少个元素比a[1, n/2]小,假设有k个。
把所有的k传输到机器1,求和。再加上n/2-1 。 假设为K。
如果K大于nM/2,left = 0, right = n/2。
如果K小于nM/2,left = mid, right = n。
repeat上面的过程,直到K == nM/2。

个人感觉要最小化不同机器之间的通信量。而不是机器本地的计算量。因为通信延迟比cpu计算要慢很多。
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-11-2 09:31:34 | 只看该作者
全局:
merge的代价高啊。找median可以不用merge。

每台机器先sort自己的那部分。假设有机器1,2,……,M。把机器1当做main server。
假设每个机器上都有n个元素。a表示第i个机器上的第j个元素。利用二分查找的思想。

先令mid = a[1, n/2]为基准。
然后在机器2到M上二分查找多少个元素比a[1, n/2]小,假设有k个。
把所有的k传输到机器1,求和。再加上n/2-1 。 假设为K。
如果K大于nM/2,left = 0, right = n/2。
如果K小于nM/2,left = mid, right = n。
repeat上面的过程,直到K == nM/2。

个人感觉要最小化不同机器之间 ...
nooneknow 发表于 2011-11-2 09:12


算法没看懂, 确定是正确的?
把所有机器的数据都传到一台上处理是不是有不妥,
网络带宽有限, 都穿到一台机器上还是要排队的, 要是丢包频繁的话效率更低,
我的merge方法实际上是同时进行的, logn的量级把,
没看出你的方法哪传得少了 ....
回复

使用道具 举报

🔗
Roquin 2011-11-4 20:38:27 | 只看该作者
全局:
本帖最后由 Roquin 于 2011-11-4 20:42 编辑

其实把Median of Medians algorithm改成m-way就可以了啊

m台机器分别partition by median并返回median  //O(n)
求m个median的median  //O(m)
每次大约可以排除1/2的数。不过因为排除后每台机器上剩下的数的数量不同,还有一些细节要处理。
m<<n AND m>5的话就是O(n)的时间和O(m*lgn)的数据传输量
回复

使用道具 举报

🔗
nooneknow 2011-11-5 10:18:45 | 只看该作者
全局:
其实把Median of Medians algorithm改成m-way就可以了啊

m台机器分别partition by median并返回median  //O(n)
求m个median的median  //O(m)
每次大约可以排除1/2的数。不过因为排除后每台机器上剩下的数的数量不同,还有一些细节要处理。
m
Roquin 发表于 2011-11-4 20:38


算法代码在这里,其实麻烦的不行。。。
http://www.leetcode.com/2011/03/median-of-two-sorted-arrays.html
不过我上面那方法也没说的很清楚。
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-11-5 10:27:24 | 只看该作者
全局:
算法代码在这里,其实麻烦的不行。。。

不过我上面那方法也没说的很清楚。
nooneknow 发表于 2011-11-5 10:18



    地里很多人在mitbbs上混啊, 难怪id看着眼熟, 嘿嘿
回复

使用道具 举报

全局:
既然都sort了,还怕merge么。。。。
sort复杂度nlogn+merge复杂度nlogk=nlogn
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表