2010年2月28日星期日

Space rail

听zeta同学推荐,订了一个space rail,貌似很好玩的样子,相当期待。在YY的时候,忽然发现这个东东貌似很适合搞软件的团队做team building~
需求:造出来的过山车要能转起来(functional),而且样子要酷(polished)
设计:利用力学原理(theory),设计轨道(architecture)造型(product)
构建:每个人组装(implement)一个模块(module),确保小球在给定进入速度范围内可以通过自己的模块,并且离开速度满足给定要求(unit test),然后集成(integration)
管理:分配底座、支架、轨道等零件(resource)给各个玩家(engineer),协调各个模块组装的进度等
迭代:当过山车做装好后(release),每当有了新装置或设想(new feature),稍加改动(refactoring)就可以安装到成品中,而不需要全部拆散重来(redesign/rewrite),并且递归地,改动后的过山车仍然具有此属性(continual improvement)。

2010年2月19日星期五

春节。上海。西塘。杭州。

以为,杭州是一个充满了怨念的城市,可我还是去了。
大年初二凌晨5点,和LP踏上了南灰的旅途。落地是上海时间10:30,淅淅沥沥下着雨,冷得棉袄里面好像装着冰。下午从南站往嘉善。
晚上赶到西塘,被嘉善的出租车黑了。不能怪公交车收的早,也不能怪正品黑车杀人不见血,只能怪晚辈我人生地不熟不敢跟人家犯蛮,成全了那披着出租车绿皮的黑车。
晚上住在杨老板家,杨老板人很好,给我们热粽子吃。终于见识了南方的冬天没有暖气的冷是啥滋味。
初三,天晴了,西塘上午的阳光真的非常非常亚克西。只想坐在水边的石台上一直发呆,看着游人走着石板路,看着爱人吃着煮青豆,看着老太太不急不忙地递过来臭豆腐、粉蒸肉,惬意地只想睡了算了。LP食欲和玩心超好,逢食必吃,逢店必进,逢景必拍照,活蹦乱跳。
下午在杨老板的帮助下换到了提前发往杭州的汽车票,于是两个小P孩拍PP走了。一觉醒来,就到了莫干山路pod,传说中的家庭房,超cute的小房间。晚饭杭大路尘衣食府,尘依小炒和扒羊肉相当不错(偷偷拍照),片儿川没有下次了。
初四,彻底在武林门/广场迷失了方向,因为杭州修轨道一号线,公交车已经不再既定路线上行动了。灵隐,九溪,都没去成,因为找不到Y1,Y2,很崩溃。只想摔了手机,卸了Google
Map。中午灰溜溜地去河坊街吃王润兴,吃到一半犯病了,不知道是不是因为太难吃了。比08年来杭州那次犯得还厉害。下午继续在河坊街逛,买了丝巾和被面,反正不会砍价,索性没有砍,宰就宰吧,反正杭州我已经来四次了,没有下次了。
初四晚上,一咬牙一瞪眼,回到北京了。

春节前:
阳光明媚。上班浪费。

春节:
怨念沪杭。怀念西塘。

春节后:
龙体欠安。提前下班。

2010年2月12日星期五

Happy Chinese New Year!

富饶之城,赛乐堡,全城热恋,放鸽子

春节快到了,娱乐活动多了起来。
周四午饭和501的同事一起吃,那些家伙比传说中的客气。饭后响应weiwei的号召去玩富饶之城。我是第一次玩,还是挺有意思的。桌游的魅力在于现场互动,大家都相当生动。Free有一局不幸地当了我的替罪羊被刺了,然后从此一蹶不振,Snow是永远的军阀,挣钱就是拆台,口号是我赢不了谁也别想赢,Dandan为了争第二费劲了心思,我一直很想在博物馆下面藏一个大学,因为觉得那样特别逗,不过一上来就被军阀摧了。赢家当然是weiwei,在正确的时机建造了八级浮屠,不愧是有经验的玩家。
下午公司里人越来越少,每个人起身离去都要和剩下的所有人告别说"明年见",搞得我越来越没心情coding了。下班后跑到赛乐堡和朋友K歌,含自助晚餐。因为下班前吃了一包饼干,不饿,于是我说,"你们先吃,我给你们唱歌!",然后开开原唱,到处找调。找到所有人都吃饱了我也没找到调。5个人水平都一般,个别人个别曲目个别段落有感觉有旋律,大多时候有感觉没旋律或没感觉。然而非常High,不知不觉4个小时过去了,还有4屏的曲目没轮上,就很伤心的走了。
周五叫嚣着去上班,然而早上起床后发现阳光明媚,心想上班浪费,于是和MM去看全城热恋了。虽然很肥皂很商业,但是还是有几处很有趣的。最逗的是字幕,在显示人物发短信的时候,居然可以支持退格!还有就是显示制作群的时候,文字可以配合音乐抖啊抖的。两只小鱼的动画也很搞。
下午回家干活,处理了服务器上的一个小事件,又读了篇PM的Design。然后上Skype,发现DZF在线上,一个昨天也号称今天要去上班的童鞋,结果一问,啊哈,也没去公司,再一问XXX,也没去。。。瀑布汗,今天503貌似就剩前台姐姐了。。。心中顿时升起一坨坨的歉意。
明儿就三十儿了,大后天就去南方玩了,保佑我们的Server keep alive吧!

2010年2月10日星期三

The limitation of the sampling algorithm: a simple case

一个不能用采样算法的问题的例子
网站某天有N个request,每个request都包含一个session_id,现在希望统计y=平均每个session有几次request。若M为distinct的session的个数(通常M<N),则y=N/M。
现在从N个request中随机取n个,记这其中distinct的session的个数为m,令随机变量X=n/m,则EX!=y
反例:当n=1时,m恒=1,X恒=1。
问题:是否存在一个采样算法,使得算法的输出是y的无偏、相合估计?

2010年2月7日星期日

The impact of resampling to RSE in sampling algorithms

采样算法中,是否可重复采样对相对标准差的影响

在古典概型中有放回和无放回差别很大。在随机采样算法中,对已经采过的样本,是否还可以再采?
问题:
假设有N个零件,次品率为p(即有pN个次品)。现在已知N,要求通过采样率为q(检查qN次)算法来估计p。

有放回算法:
依次生成qN个独立同分布U[0,N)的随机数xi,检查第xi个零件是否为次品,记随机变量X为检查出的次品的个数。来求X的分布。
令Xi=1表示第xi个零件为次品,则X=X1+...+X_qN
P(Xi=1)=p,EXi=p,根据期望线性性,EX=EX1+EX_qN=pqN,DX=pqN(1-p)
相对标准差的平方RSE2为DX/(EX)^2=(1-p)/(pqN)

无放回算法:
一次从N个零件中随机抽取qN个零件,记其中次品个数为X,则X服从超几何分布
EX=pqN,DX=p(1-p)q(1-q)N,RSE2=(1-p)(1-q)/(pqN)

对比发现,两个算法的RSE2就差个(1-q),即相同采样率q下,无放回更精确。当然,对于千分之一的采样率,二者差别可以忽略,但是如果要采50%的样,最好用无放回算法了。这也符合物理直观。
但是不管有没有放回,RSE都关于p,q,N单调递减,因此,固定p(p来自问题域),可以通过调节qN来寻求性能与精度的平衡――
当N较小时,用比较大的q来维持精度,反正样本数qN也不大。
当N较大时,不需要很大的q,因为反正RSE2的分母上已经有个N了:)