2012年12月25日星期二

Fwd: surface试用小计

之前最担心的是不适应没有触感的键盘,不过用了一段时间,感觉也没那么难用了。如果说在台式机键盘打字聊天体验5星,手机打字1星的话,用surface的cover可以给2星吧。键盘布局像pc,但是没有f1到f12,有些熟悉的快捷键用不了了。好像也有卖有触感的键盘的,很贵。
屏幕更像上网本的感觉,很宽,默认字体很小。清晰度还挺好的,没有太多比较了。有前后两个摄像头,像素不高,不过前置摄像头角度很有意思,是仰视,因为平板立在桌子上的时候是前倾的,所以仰视才能和桌面平行,平视就只能看桌子了。
声音效果不错,看电影有点立体声的效果,貌似有四个出声口,上面两个,两侧各一个。
操作系统用起来感觉一般吧,右侧和左侧滑出菜单的体验挺新颖的。原来用台式机的时候,发呆会在桌面右键弹出菜单点刷新,现在用surface会发呆的时候滑出左侧菜单,有点像切换任务的界面。右侧有点像状态栏。
应用非常少,还很贵,市场里的应用都像是给手机做的。自带的一些很有windows特色的应用,经常让我误以为这就是一台笔记本电脑,比如cmd(ms bash),远程桌面(ms ssh),计划任务程序(crontab)等等。
噪音几乎没有,也不发烫,这点比较像平板。电池也很给力,用了三天了,还有一半电呢,比手机和笔记本电脑都强多了。
奇葩的是windows update,和pc好像。
另外奇葩的是,居然还保留了鼠标的概念,包括右键的上下文菜单,据说是对office的妥协,谁知道呢。真的会用surface办公么?恐怕我还是会给他外接一个usb键盘,一个usb鼠标才能开始干活。。等等,对了surface只有一个usb接口,还得先接一个hub。。。还是等公司给我配一台笔记本电脑吧,surface就留在家里给老婆看视频用好了。

2012年12月1日星期六

推荐系统论坛2012参后感

今天全是干货。
Facebook开篇就提到做unified organic and sponsored recommendation。这恰恰是session亮点和我一直以来的梦想:将广告和推荐结合起来。从某种角度上说,内容推荐是Facebook自己作为广告商的广告,目的是让用户在Facebook上更活跃。基于此,他们建立了统一的优化目标,而不是向淘宝那样广告部和推荐部掐架。
给定用户和上下文:
max predicted CTR * (ad bid + p * click value)
predicted CTR是用户在当前上下文点击被推荐对象的概率。
ad bid是广告投标价格。
p是神奇的pacing parameter,通过一个负反馈系统在线动态调整。
click value是点击被推荐对象对Facebook的价值,反映了Facebook的长期利益。计算方法大致是推荐对象给用户在当前上下文带来的相对边际收益。比如给一个只有2个好友的用户推荐一个好友的相对边际收益是50%,给一个有1000个好友的用户推荐一个好友的相对边际收益是0.1%。
假设Facebook的Inventory也就是右侧栏广告位要被Facebook用于投资,短线投资回报快风险小,也就是卖给广告商在这里打广告,但是要牺牲长远利益即用户体验,长线投资回报慢风险高,也就是内容推荐。所谓Facebook决策者的投资组合,就是设定一个threshold三七开还是二八开,当organic spend > total spend * threshold 时,p减小,反之增加。这样就可以让投资比例稳定在设定值上了。这里非常天才的一点在于,p无需人工设定,系统可以自己收敛到一个稳定值,同时完成量纲转化,鬼知道click value是个什么物理量,和ad bid怎么比。
另外,关于如何向广告商收费。为了防止广告商和广告系统无聊地在线博弈,Facebook采用了符合经济学原理的方式:在Facebook投放广告的价格等于Facebook投放他的机会成本,也就是说,因为投放了你,系统受到多大损失。实现的时候,相当于系统处理两个recommandation request,第一个是有你的情况下,计算按照上述算法推荐的投资组合的收益,第二个request假装没有你,计算投资组合的收益,两者求差,就是机会成本。好像有一套叫VCG的理论支撑这个拍卖模型。
一个好的广告,不仅有ad bid带来的短期价值,还有click value带来的长期价值。好的生态是用户在Facebook上和广告商互动生产内容。

模型:Logistic Regression,理由,大量feature,在线更新。牺牲准确性,应对快速变化,因为需要推荐的对象类型五花八门层出不穷,例如照片,游戏应用等等。
几个特别好用的feature
上次点击这种类型推荐对象的时间到现在的时间间隔。刚点过一段时间不会再点了,但是过一段时间还有可能点。Bucket feature。
上下文类型,比如在照片页面推荐照片,就比较好。

基础设施:hive, scribe,不同的索引用不同的硬件,小一点的用memcached,大一点的用flash disk。
一些数字:
在线更新model时间间隔:30分钟。带来收益约3%。
每个user有billion量级的待推荐对象。
统一organic recommand和sponsored recommand之后,user活跃度上升10%,广告收益也上升10%。

Hulu
在视频里面放弃一些广告位,推荐内容。
推荐相关度直接弹窗问用户,CTR不靠谱。
当全站使用推荐系统时,它将影响用户行为习惯,从而反过来影响自身。就好像成为一个隐函数。不再是y=f(x),而是g(x,y)=0

腾讯
模糊集从公理出发三步就能推出悖论。

百度
技术悲观主义。





2012年9月15日星期六

My Adventure to "Wacity"

人上了岁数就爱怀旧。周末一个人在家无聊,整理资料,翻出来一篇2005年的英语写作课的作业。发现自己年轻的时候想象力真犀利啊。

My Adventure to "Wacity"

I would like to tell you about my adventure to a wacity last Friday, which was very exciting.

I am a farmer in 31 century, and now the scientists can enable people to breathe and live in the water as in the air. So years ago, my family emigrate to a village down the sea, earning lives by growing coral.

Last Friday, when I was working on my coral farm, a shark came out toward to me quickly. I felt so terrified that I hurried jumped into my wajeep (the jeep in water) and escaped away. I speeded it up to the limit, but still couldn't get rid of the shark, which was chasing me nearer and nearer. I do not know how far did I rush, until there came across a watruck suddenly and knocked mine down.

When I woke up, I found myself in a wacity I had never been. My wajeep was gone, and so was the shark. A huge tube appeared in my sight, with a hole on it. I swam to the hold curiously, and when I was at a distance about one meter away, there came an enormous force absorbing me into it! "Hey, where are you from, freshman?" someone asked me. "Coral land" I replied," and what it is, I mean this tube?" "Wahighway." "Wa-highway? But where are the wacars?" At the moment I asked that foolish question, the water in the tube began to flow toward a direction. All the people in the tube, no, the wahighway, floated following the stream. Then I saw what the wahighway meant. "Where are we going?" I asked that man. "The centre of the wacity." he answered.

"Nice," I said to myself, "There I will find the police station and ask them to help me back home!"

When the stream stopped, there opened a hole on the tube. "Excuse me, can you tell me where the nearest police station is please?" I asked an old woman in the street, having come out of the tube. "Well, young man, go along this street and turn left at the first cross, and then turn up at the corner. Then you will find it." "Thank you madam, but what do you mean by 'turn up'?" "You see, in a wacross, we have five choices, instead of three as cross on the ground. You can turn left or right, up or down, or go ahead. Do you understand?"  "I've got it, here we have three dimensions! Thank you very much!"

Several minutes later, I arrived at the police station building. I search around it but didn't find any door! I pondered for a while, and then I opened a window and got into it for help. "This wacity must be designed by Microsoft, or everyone here has got used to windows," I thought associate with the hole on the wahighway tube. In the station, the police officers offered me a lunch, and in the afternoon, they send me back.

"Thanks for the shark, or I won't know there is a wacity in the world!" I thought to myself on my way home.

2012年8月15日星期三

KDD 2012笔记2

闭幕了。
---
时间序列搜索
大概要从trillion量级的时间序列中找到query的时间序列子列,当然定义了两个时间序列子列之间的距离,是最近邻搜素。
实验数据大多来自生物医学,比如DNA序列,脑电波等。
用到了一些技术:z-normalization,每个点减均值除方差。还有是用两条平行的时间序列将目标时间序列夹住,夹得越紧越好,当然被夹的序列抖动比较厉害,夹人的比较平滑。然后用夹人的序列的特征刻画被夹的序列的特征。
还有各种剪枝,由于距离定义的可加性,如果当前子列的距离已经大于已知的最短距离,就可以放弃当前位置,换个地方重新计算。
采样技术,将时间序列连续地采一部分出来,得到了一个较短的子列,如果子列距离就已经超了,这个样本所在的总体就不用考虑了。
还有各种并行化技术,比如有的进程从左往右找,有的进程从右往左找。
不明白索引结构是怎么样的,难道都是这种很苦逼的遍历么,这叫哪门子搜索啊。
---
m6d做的事情和我们组现在做的很像,所以使劲听使劲听。
display ads做的就是browsing pattern。
m6d这个公司有5个data scientists,上千个分类器,每个model有上M个feature,从训练到部署全部自动化,极少人工干预。
个人感觉他们Engineering做得很好,有系统有效的Monitoring,运维的人的成本很低。
feature包括浏览过的网页,还有浏览器信息。
正例是有购买记录的用户。
各种measurement做得很好,比如他们会比同一个model,在不同数据源上的效果好坏。
数据量:production上500多个core,每天处理上B的event
---
Youtube讲视频流行度
很多视频内容都一样,只不过是克隆出来的翻版
建立了流行度和内容之间的线性模型,发现不怎么样,都通不过假设检验
流行度和非内容要素关系更大,例如人们上Youtube就喜欢看新视频,在搜索结果中,新视频也被赋予了很高的权重,总排到上面。
心想,不知Hulu的人看到这会不会鄙视他们。也许人家没把最好的研究拿出来讲吧。
---
Yahoo讲display ads的allocation
在book ad的时候,publisher要马上知道这块inventory上还能不能分配这么多impressions
在impression servering的时候,50ms内决定这个机会应该给哪个ad
5年前,Yahoo使用控制论,也就是负反馈技术,当一个ad deliver的数量超过按计划当前应该deliver的数量时,提高此ad的权重,保证所有ad永远on schedule。
这个算法非常简单,缺点是过于短视,没有往前看。结果有很多under delivery。
二分图匹配问题,把inventory分成许多小块,把ad targeting也分成许多小块。约束:所有ad的impression goal都要被满足,under delivery将得到很大的罚,inventory是根据历史预测出来的,可分配的impression不能超过capacity。得到一个plan,每个ad server按plan执行。
转化成KKT对偶问题,找到一个可行解很容易。online serving的时候很容易实时修正预测误差。
但这个算法有个问题(后边一个session里来自Google的人讲的),就是不好控制每个Ad的delivery pattern,比如都能deliver完,但是都集中在很短的时间,或者很特别的人群上。
advertiser要看top behavior的时候,allocation结果就很难看了,因为有太多的可行解。
当然我相信,引入一些阻尼项,可以让allocation的到很好的结果,但是top behavior可能没有那么鲁棒。
---
Yahoo讲display ad的用户行为分析
convert的过程分为三步:用户来到一个有广告的页面,用户意识到这个页面上有这个广告,用户对此感兴趣并来到广告目标网站上互动。
以前人们建模通常把感兴趣的概率作为model score,作者认为awareness也是一个很重要的因素。展示次数、上下文、广告大小、位置等等会影响awareness。
他建了个模型,融合到固定的interesting model里面,发现可以改进预测精度。
有时候,一个人得反复看才能注意到一个广告。有时候,一个人一个广告看多了就意识不到广告的存在了。
---
插播一个海报,出现在一个人的PPT里,很有意思:上面写着"I don't aways test my code. When I do I do it in production."
---
Google讲Display ad serving
为了smooth delivery,作者将时间切片,在每个时间片段里,用allocation model,控制每个ad的delivery上限。结果是显著降低over delivery,但是under delivery没什么变化。
Google做的是什么生意,竟能允许20%以上的under delivery。
---
下午有一些形而上的发言,有一个说得很好,大数据不是说数据量特别大,而是数据的复杂性高。我觉得很有道理。
另一个说的也很好,大数据的生意应该这样做,提出并解决一个问题,然后refine并scale它。
---
后面的讲座就非常理论了,估计工业界的人这时候都走得差不多了,留下的都是些穷学生等着吃晚饭不听也是闲着。
---
模式识别工作总是弄出来很多重复的pattern,作者定义了pattern之间的相似度和一个偏序,提出了从一堆pattern中,找到一组最小pattern覆盖的算法。
称A优于B,若TP(A)>=TP(B)且FP(A)<=FP(B),就是说,B能分对的,A也都能分对,A分不对的,B也都分不对。
下面给出了一个松弛
称A是delta优于B的,若TP(A)>=TP(B)且|FP(A)\FP(B)|<=delta/(1-delta)|B|,就是说,很少有A分不对B却能分对的。
这里说分对,是说分类器把正例分为正例。
delta优不同于优,他没有传递性。
作者证明了一个非常牛的引理:给一堆pattern,存在唯一一组pattern,完备且无冗余。这里完备和冗余的概念也是用delta优定义的,没记下来。
现实意义,用最小pattern覆盖替代一堆pattern,可以提高AUC。
---
当分布非常不均匀时,有一个多核算法可以让挖掘频繁项加速一个数量级。好像和编译原理有关,都是优化代码路径什么的。
---
click stream中回文的发现
一个序列反转后不变,就是回文。例如AA,ABA都是,AB,ABCA都不是。
内嵌回文:ABCBA中BCB就是内嵌回文。内嵌回文折叠后,外面仍然是回文。但是要注意叠好。例如ABCBDBCBA,如果只叠一个BCB,就成了ABDBCBA,就不是回文了。
有一个利用栈的算法,可以线性时间删除内嵌回文。感觉像一个数据结构的作业题啊。
互联网上很多网站的click stream中回文占90%以上。找出这个结构,可以发现网站导航的一些问题。
比如死链,点进去就点不回来了,只能后退。有的一个hub页面要反复出来进去。
sequence mining是一个很有趣的领域。
---
没了。

回来看到U盘里有一百多篇paper,够看一阵了。

2012年8月14日星期二

KDD 2012 笔记1

很高兴可以用上班时间参加KDD的会议。读研的时候总幻想可以参加这样的会议,可是参加的却是华人数学家大会,各种代数拓扑神马的在他们看来和HTML5一样令人兴奋。
然而我觉得,数学家很难创造什么,他们更多的是发现。构造性的证明总被认为是好的。然而构造性的证明能证明的,往往是不太具有基础的重要性的命题。
构造性的证明,具有积极的建设性,这个和知识发现的工作是相通的。
工作之后第一份工作是程序员,参加的是敏捷开发大会之类的,很文科。所以今天参加KDD会议,很高兴。
---
Bootstrap for big data
把样本空间n切分成大小为b(n)=n^0.6的若干小空间,分别Bootstrap,将结果平均以得到总体的估计。好处是可以并行化。
Matrix completion
将矩阵按列切分,每个分块分别分解,得到总体的近似。
Chinese restaurant process
---
Twitter
典型的用户行为包括hashtag和retweet
twitter用户创造了大量新词汇
不用负样本训练模型
用户贡献了大量标签数据
用户的徽章和行为如何互相解释
7M的用户,只有31个徽章
实验在75K用户上进行,采了300K行为
10%的数据藏起来,做真值
将关键词聚类,得到标签云,有时候很有意思,有时候很不靠谱
可以通过用户行为反过来预测用户的人口统计学信息
用户的行为频率越高,反映的偏好越明确,但是有一个临界值,再多就没有偏好了,成了平均脸。是条抛物线
---
Yahoo
给定一些实体,找到给定用户最感兴趣的实体。
平均每件商品的评论数:Amazon 30K,Yelp 3K(这么多?!)
Ranking based on coverage
真值:Rank review by helpfulness rate by user
每个用户由他的评论在lable上加分,比如David=java(4) algorithm(6)
相机的评论有几个方面:续航能力、便携性等
评论说的全面,说的别人没说过,分就高。稀缺性作为评判的指标。
cover score,一个实例在coverage指标上的边际贡献。
---
效用函数
推荐相关新闻的数量,和用户满意度的关系是亚线性的。
好的推荐系统应该在相关性和多样性之间平衡,比如推荐前面几条推荐和用户兴趣相关的,后面几条推荐五花八门的,扩大用户视野。
当然每个用户效用曲线形状不一样,有的用户就只喜欢看和自己兴趣相关的新闻,给他推荐别的就是浪费。
作者找出了一个方法估计每个用户的效用曲线。
---
播放列表推荐
曲目的元数据很重要
曲目编排的顺序很重要
---
社交计算
例子:每个人是图上的一个点,给定有限种颜色。请选一种颜色画在你的点上,如果和你相邻的点颜色都不相同,你就赢了。
民主选举中的投票
---
编写好的教科书
一本教科书不好的一个特征,就是在解释一个概念之前,就使用它。称之为理解灾难。
作者设计了一个工具,找到一本教科书中,那些章节具有最多的理解灾难,那些概念带来最多的理解灾难。帮助出书者改进教科书。
工具还考虑了如何处理书中对外部概念的引用。好的教科书应该尽量少引用外部概念。
---
把破坏市场经济秩序的坏人揪出来
通过证券交易记录,发现联手操盘的一小撮人。
定义了一种特别的自相关系数。
在用户行为建模方面:如果一个人的意图不能自洽,就不要将他的行为用于构建物品之间关联。
---
推荐系统攻击
一些人想推广商品A,选定一些流行的商品B,注册大量马甲,给B打5分,再给A打5分,然后再假装给不相关的一些物品打2或3分。
根据一般的推荐算法,当普通人浏览B的页面时,系统会推荐A。攻击者就阴谋得逞了。
作者发明了一套算法,把这种人干掉。结果显著提升了user based CF的准确性。
真值:Amazon专家标注的攻击者
Amazon将攻击者分为三类:从来不买东西的蓄意破坏者(删id)、全职写手(显著降低言论的权重)、兼职写软文的(适当降低言论的权重)
---
HP电力管理
在写字楼里,如何安排电路开关和电表?
安装的多了,控制粒度细了,但是费料。
装的少了,控制得不够细,可能造成浪费,有故障电器不能将破坏控制在局部。
---
Twitter抽取突发事件
很多突发事件是从microblog上报道的,如何抽取?
定义了三元组:对象、时间、类型
类型是可枚举的,分类器学出来的
---
如何建立功能和蛋白质之间的联系,构建了二分图,多标签分类模型
---
文本分类
有一个未经检验的假设:被lable的样本和总体同分布。
---
实体匹配
一个Yahoo的Researcher讲,他上来很沮丧地说
这篇Paper的联合作者还有3个人,可是他们现在分别去了facebook, twitter和google,what a shame
如何将internet上重复的entity识别出来?
再给定准确率下界的约束下,最大化召回率。
通过拉格朗日松弛,将问题转化为无约束优化问题。



一天听下来,非常疲惫。感觉也就听懂了2%,对5%的未知事物感兴趣想去进一步了解,剩下的93%既不知所云,也没兴趣。

2012年7月19日星期四

凯立德刷k币脚本更新

几天不写js就难受,正好论坛页面改版,原来的脚本不能用了。改了一下,还是通过自动访问其他用户的主页来赚K币。
有两个很好用的技巧:异步加载外部脚本;用jQuery Attribute Selector获得所需页面元素。

// ==UserScript==
// @name           KLD K coins
// @include        http://www.kldjy.com/home.php#3
// @run-at         document-end
// @description    open 10 space
// @version        1.2
// ==/UserScript==

function main() {
function ingest(precondition, url, dst){
if(!precondition()){setTimeout(function(){ingest(precondition, url, dst)},100);return}
script_node=document.createElement("script")
script_node.setAttribute("type", "text/javascript");
script_node.setAttribute("src", url)
dst.appendChild(script_node)
}
ingest(function(){return true}, "http://code.jquery.com/jquery-git.js", document.head)
function run()
{
ls=$("li a.avt[href*='mod=space&uid']")
if(ls==null){setTimeout(run,101);return;}
for(i=0;i<ls.length;++i)
{
window.open(ls[i].href, "_blank")
}
}
run()
}

var inject = document.createElement("script");

inject.setAttribute("type", "text/javascript");
inject.appendChild(document.createTextNode("(" + main + ")()"));

document.body.appendChild(inject);

2012年6月5日星期二

把一个C的原生二维数组转换成gsl_matrix

如果你希望所有操作在栈上进行,可以考虑这样,利用C的原生二维数组的内存布局和gsl_matrix对内存布局的假设一致:每一行的内容连续存储。


#include <stdio.h>
#include <gsl/gsl_matrix.h>

#define init_matrix(src, dst) \
    gsl_matrix dst; \
    dst.size1 = sizeof(src) / sizeof(src[0]); \
    dst.tda = dst.size2 = sizeof(src[0]) / sizeof(src[0][0]); \
    dst.data = (double*)(void*)src; \
    dst.block = NULL; dst.owner = false;
    
int main() 
{
    double x[3][4];
    for(int i=0;i<3;++i)for(int j=0;j<4;++j)x[i][j]=1+i+0.1*(1+j);
    init_matrix(x, a);
    gsl_matrix_scale(&a, 100);
    gsl_matrix_fprintf(stdout, &a, "%g");
}

结果

110
120
130
140
210
220
230
240
310
320
330
340

2012年6月3日星期日

虚继承的内存布局

一天我一同事向我推荐了一本书,讲C++对象模型的。
周五下班后,我和另一个同事做了个试验:

#include <stdio.h>
struct B{   char c;};
struct B1: virtual B{   char b1;};
struct B2: virtual B{   char b2;};
struct D : public B1, public B2, virtual B{ char d;};

int main()
{
    D _d;
    D* d = &_d;
    d->d = 'd';d->b1='1';d->b2='2';d->c='c';
    B2* b2 = d;
    B1* b1 = d;
    B* b = d;
    printf("sizeof(B), sizeof(B1), sizeof(B2), sizeof(D) = %d %d %d %d\n", sizeof(B), sizeof(B1), sizeof(B2), sizeof(D));
    printf("d %p %p %d %d %d %d\n", d, *(long*)d, long(&d->c) - long(d), long(&d->b1) - long(d), long(&d->b2) - long(d), long(&d->d)-long(d) );
    printf("b1 c,b1 = %c %c\n", b1->c, b1->b1);
    printf("b1 %p %p %d %d\n", b1, *(long*)b1, long(&b1->c) - long(b1), long(&b1->b1) - long(b1) );
    printf("b2 c,b2 = %c %c\n", b2->c, b2->b2);
    printf("b2 %p %p %d %d\n", b2, *(long*)b2, long(&b2->c) - long(b2), long(&b2->b2) - long(b2) );
    printf("b c %c\n", b->c);
    printf("b %p %d\n", b, long(&b->c)-long(b) );
    return 0;
}

g++编译后运行结果

sizeof(B), sizeof(B1), sizeof(B2), sizeof(D) = 1 16 16 32
d 0x7ffff7897d60 0x401178 26 8 24 25
b1 c,b1 = c 1
b1 0x7ffff7897d60 0x401178 26 8
b2 c,b2 = c 2
b2 0x7ffff7897d70 0x401190 10 8
b c c
b 0x7ffff7897d7a 0


貌似是有32个字节的连续内存。d和b1都指向这段内存的首地址,b2指向偏移量为16字节的位置。b指向偏移量为26字节的位置。
前16个字节:前8个字节是B1的虚表的指针,第9个字节存了成员b1,然后是7个字节的padding。
后16个字节:前8个字节是B2的虚表的指针,第9个字节存了成员b2,第10个字节存了成员d,第11个字节存了成员c,然后是5个字节的padding。
内存布局的顺序大约是:第一个父类成员、第二个父类成员、当前类成员、公共虚继承的祖父类成员。
另外一个发现是:指针的类型转换后可能导致指针本身的值的变化,因为子类指针和父类指针可能指向同一段连续内存的不同位置。


2012年5月25日星期五

flip遍历

问题
遍历长度为n的所有可能的0-1向量(N=2^n个),使得相邻输出的两个向量可以通过某一个下标取反得到。

算法1
O(N)时间,O(n)空间
n=4
l=[0]*n
def f(n):
if n<=0:return
n-=1
f(n)
l[n]=1-l[n]
print l
f(n)
f(4)
足够简洁,注意到递归的函数栈深度为n,所以空间复杂度为O(n)

算法2
O(N)时间,O(1)空间
n=4
l=[0]*n
print l
N=pow(2,n)
for step in xrange(1,N):
for p in xrange(1,n+1):
if step%pow(2,p)==pow(2,p-1):
l[p-1]=1-l[p-1]
print l
break
虽然两重循环,看似时间复杂度为O(nN),其实有内层循环有1/2的概率第一次if就break了,有1/4的概率第2次就break了,。。。有1/2^k的概率第k次就break了。
而级数sum{k/2^k}收敛,有上界,上界与n无关。故均摊内层循环时间为O(1),总时间就是O(N)了。

2012年5月12日星期六

新浪App Engine

1分钟点亮,不得不赞。
Google App Engine需要装SDK配yaml,AWS需要有git插件和信用卡绑定。
SAE最简单最符合国情:只需要SVN就能跑了!

2012年5月7日星期一

aws试用小记

有一天晚上,老婆说想弄个网站,搞基于数据分析的新闻调查。我觉得这个交叉学科的小项目很有意思,就开始忙活起来。
step 1 买域名
俗话说,名不正,言不顺。从国内某个从来没听说过的小破网站买了一个看起来很权威的域名www.data-journalist.com
step 2 买主机
国内的主机想都没想,调研了几家国外的VPS,好像都挺贵。于是想起了AWS。AWS已经火了好几年了,前几天和Diane聊天的时候,她提及想找人调研一下。正好我也想借data journalist这个小项目尝试一下传说中的"云计算",就冲向了AWS。注册、身份验证、关联信用卡,这一路没什么难的,新人貌似还有免费试用?
step 3 冒烟elasticbeanstalk
elasticbeanstalk用国内那些小破网站的话说就是一个"一键式建站服务",整合了AWS众多基础设施服务。什么IaaS啦PaaS啦神马的,都是浮云。先搞起再说!
按照官方在线教程get start点了点鼠标,很快搭建了一个php的小网站,程序是AWS自带的,大致内容是"恭喜您blabla"
然后从console里下载了这个示例程序的php代码,貌似入口是index.php
step 4 部署自己的程序
按照另一篇教程deploy下载了git,aws的git插件(有用的就一个shell脚本),稍加配置,然后把自己hack过的index.php给一键部署上去了git aws.push,相比于小时候玩的IIS和Apache,aws真的是太方便了。
console上有一个测试网址
点进去,work了!
step 5 绑定域名
不知道静态IP是啥,可能压根就没有吧。就先用CNAME凑合着吧,回头仔细研究。

P.S. 让人很伤心的是AWS貌似部分被墙了TT

2012年4月29日星期日

Python多进程处理文件

有一天,QA要我写一个程序,处理一个很大的文本文件,通常几百MB,有时几个G。
这个本文本件是一些顺序打印的JSON,需要解析出来,然后按照他们喜欢的格式重新打印。

先写了一个单线程版本,发现很慢,CPU 100%。估计是parse json太慢了。

buf = ""
for line in sys.stdin:
if line[0] == "}":
line = "}"
buf += line
handle(buf)
buf = "{"
else:
buf += line


def handle(buf, m):
o = json.loads(buf)
s = ""
...
sys.stdout.write(s)


记得python的多线程是伪多线程,在多核的机器上CPU还是100%。于是直接采用多进程。

buf_queue = multiprocessing.Queue()

def process(q):
for buf in iter(q.get, None):
handle(buf)
q.put(None)

for _i in xrange(23):
multiprocessing.Process(target=process, args=(buf_queue)).start()

buf = ""
for line in sys.stdin:
if line[0] == "}":
line = "}"
buf += line
buf_queue.put(buf)
buf = "{"
else:
buf += line
buf_queue.put(None)

主进程不断向一个队列里丢字符串,23个子进程谁拿到谁处理。主进程在队列末端放一个None,子进程发现None就退出。
当然,子进程在退出的时候还要往里面放一个None,这样后面的子进程也就可以退出了。
也可以让子进程往队列里放23个None,这样所有子进程也都可以退出了。
iter(q.get, None)
是一个很神奇的语法糖:每次执行q.get()的返回值,作为buf在for代码块中处理。直到q.get()返回了None,for就退出了。

这样有一个问题,多个进程都在stdout上写,会写乱。于是加了一个mutex,multiprocessing.Lock。Lock支持with语法。

然后觉得自己搞fork进程、put/get队列什么的太底层太�嗦了,于是改成了Pool

pool = multiprocessing.Pool()
buf = ""
for line in sys.stdin:
if line[0] == "}":
line = "}"
buf += line
pool.apply_async(handle, (buf, ))
buf = "{"
else:
buf += line

但是multiprocessing.Lock不能pickle串行化,只好改成multiprocessing.Manager.Lock,生成一个委托的锁,在多进程中共享。

俗话说,共享状态和锁是并发程序的天敌。于是继续寻求更好的办法。想,如果每个进程不要自己打印,而是把要打印的字符串扔到一个的队列里面,然后有一个单独的线程打印,就可以避免自己用锁了。不过最后使用了更紧凑的写法:
pool.apply_async(handle, (buf,), callback = sys.stdout.write)
当然handle结尾改成return s
看了源代码,Pool会有一个fork出来的线程负责在所有子进程外面顺序执行callback,从而避免了应用程序显性用锁。当然Pool本身有一个输入队列,一个输出队列,各自有锁,躲不掉的。

2012年4月1日星期日

线程和进程的区别

进程好像有一种copy on write的性质,线程总是共享内存。

from multiprocessing import Process
from threading import Thread

class A(Process):
    def __init__(self):
        Process.__init__(self)
        self.done = 1

    def run(self):
        print self.done, id(self.done)
        self.done += 1
        print self.done, id(self.done)


class B(Thread):
    def __init__(self):
        Thread.__init__(self)
        self.done = 1

    def run(self):
        print self.done, id(self.done)
        self.done += 1
        print self.done, id(self.done)

if __name__ == '__main__':    a=A()
    a.start()
    a.join()
    print a.done, id(a.done)
    b=B()
    b.start()
    b.join()
    print b.done, id(b.done)


结果:
1 90612360
2 90612336
1 90612360
1 90612360
2 90612336
2 90612336

坑啊。。(每当此时,我就格外怀念Erlang。。。)

2012年3月18日星期日

刷碗的概率

我家有一个六面骰子,其中恰有一面写着刷碗。

昨天午饭后又是没人愿意去刷碗。于是老婆说:"这次换个方法掷骰子吧。如果我连掷三次都没掷到刷碗,你就去刷,否则我去"。我说好。

我算了一下,说,不行,要4次。

然后。。。我就去刷碗了。

2012年3月11日星期日

拷贝构造

一天同事考我一个C++的问题,关于STL容器的拷贝构造。
回来写了段代码验证了一下
    struct Foo
    {   
        std::vector<int> v_;
    };
    Foo a, b;
    a.v_.push_back(9);
    b = a;
    printf("%d %d %d %d\n", a.v_.size(), b.v_.size(), a.v_[0], b.v_[0]);
    a.v_[0] = 8;
    printf("%d %d %d %d\n", a.v_.size(), b.v_.size(), a.v_[0], b.v_[0]);
结果
1 1 9 9
1 1 8 9

2012年3月9日星期五

KDD Cup 2012数据集一瞥

官网网址

https://www.kddcup2012.org/c/kddcup2012-track2/

训练集

字段名​

含义​

Click

点击次数​(Metric)


Impression

呈现次数​(Metric)

LandingURL

目标网址​

广告的静态属性​,被散列过​

AdID

(Key)

AdvertiserID

​广告主

广告的静态属性​

Depth

一次搜索呈现的广告个数​

上下文信息​

Position

从上往下数第几个广告​

上下文信息

QueryID

搜索内容(Key)​

引用queryid_tokensid.txt

KeywordID

​购买关键词

广告的静态属性,引用purchasedkeyword_tokensid.txt

TitleID

​小标题

​广告的静态属性,引用

titleid_tokensid.txt

DescriptionID

长描述

广告的静态属性,引用

descriptionid_tokensid.txt

UserID 

谁在看(Key)

引用userid_profile.txt


​花了一晚上下载了2G的数据文件,解压缩后11G

随便截一屏数据

0 1 9279176529507935999 10810874 23649 1 1 1647439 373861 816959 727055 766180

0 1 16794704970244289131 5059558 26286 2 1 549 1934 526 874 766180

1 1 16794704970244289131 5059558 26286 3 2 549 1934 5240 6680 766180

0 1 14600073692226414252 20665843 4004 1 1 315 929 603 2820 766180

0 1 749131116303089246 4211484 19225 2 2 14740491 34718 46130 42358 766180

0 1 1335936110380385740 21381384 33847 2 1 91762 12501 30608 834 766180

0 1 13438413709324680452 20493531 24039 3 1 549 1934 37897 109389 766180

0 1 14600073692226414252 20666004 4004 2 2 91762 58954 5473 4856 766180

0 1 9459177555597690804 8674771 5466 3 2 8378021 150 1378 2741 766180

0 1 14340390157469404125 20640025 23808 2 1 14740491 1901 4426 4790 766180

0 1 7771884441258274609 20447819 32367 2 1 17558 28467 429086 412769 766180

0 1 15234713295054011248 3500007 23964 3 3 8378021 805 1148 1442 766180

0 1 14531867648059391627 21775716 27482 1 1 20617043 542 424 6 766180

0 1 13438413709324680452 20493531 24039 2 2 549 1934 37897 82604 766180

0 1 9459177555597690804 21163057 5466 2 2 17558 28467 179200 172693 766180

0 1 14531867648059391627 21775716 27482 1 1 306 542 424 6 766180

0 1 14340390157469404125 9027437 23808 1 1 320 300 20 20 2331238

0 1 7903914528320191889 21162350 1325 1 1 2478 168 320 932 2331238

0 1 7903914528320191889 21162350 1325 1 1 2478 168 318 925 2331238

0 2 8311784166645421100 21202612 33709 1 1 157 584 731 1022 2331238

0 1 14340390157469404125 6434981 23777 1 1 99562 175 132 190 2331238

0 1 14340390157469404125 9027437 23808 1 1 374 19 20 20 2331238

0 1 1053683433578625187 20363507 1340 1 1 5297 4035 33 13316 2331238

一些统计信息

记录数:150M

用户数:22M

查询数:24M

广告数:0.6M

平均点击数:0.0549163

平均呈现数:1.57434


扫下来十多分钟,在家里的iMac上,awk竟然把内存吃光了,逼我买Xcode写C么

ytwang$ time awk -f general.awk training.txt 

n_row 149639105

n_user 22023547

n_query 24122076

n_ad 641707

avg_click 0.0549163

avg_imp 1.57434

avg_CTR 0.0348821


real 11m24.352s

user 10m25.042s

sys 0m16.313s

ytwang$ cat general.awk 

{

        ++n_row

        ++users[$12]

        ++querys[$8]

        ++ads[$4]

        sum_click+=$1

        sum_imp+=$2

}

END{

        print "n_row", n_row

        print "n_user", length(users)

        print "n_query", length(querys)

        print "n_ad", length(ads)

        print "avg_click", sum_click/n_row

        print "avg_imp", sum_imp/n_row

        print "avg_CTR", sum_click/sum_imp

}


发现,用户很多,但平均每个用户的查询不多,基本1:1,说明用户的多样性和查询的多样性接近。

广告很少,看来soso广告卖的比较谨慎,或者不怎么有人愿意买。我上去搜了几个关键词,都没有广告出来,好不容易出来一个,还是一个叫做"腾讯搜索推广"的house ad,晕。





2012年2月18日星期六

检查程序的python版本兼容性

从前有一家高科技公司,程序用python9写的,后来想升级到最新的python_mx,于是有个程序员写了个脚本来检查老程序能不能用新python运行:
>>
>> grep "^from" *.py | cut -d" " -f2 > /tmp/x
>>
>> grep "^import" *.py | cut -d" " -f2- >> /tmp/x
>>
>> cat /tmp/x | sort | uniq > /tmp/xx
>>
>> while read line; do python_mx -c "import $line"; done < /tmp/xx

他看到了满屏的ImportError和DeprecationWarning,然后就回家了

2012年2月12日星期日

凯立德刷K币

话说道高一尺魔高一丈。先从最弱的一个魔开始吧。

打开一个记事本,粘贴如下代码另存为kld.user.js,然后拖到Chrome或Firefox(Firefox需要安装GreaseMonkey插件)里。

然后在地址栏中输入:
即可获得10个K币:因为访问了个人空间。虽说打开了12个Tab,但是家园的规则是每天由于访问个人空间获得K币的上限=10。

当然,要提前弄好自动登录。为了不影响正常使用家园空间首页,只对加了"#3"无害后缀的网址做批量弹Tab了。

// ==UserScript==
// @name           KLD K coins
// @include        http://www.kldjy.com/home.php#3
// @run-at         document-end
// @description    open 10 space
// @version        1.0
// ==/UserScript==

function main() {
for(i=0;i<$("portal_block_80_content").children[0].children[0].children.length;++i)
{
window.open($("portal_block_80_content").children[0].children[0].children[i].children[0].href, "_blank")
}
}

var inject = document.createElement("script");

inject.setAttribute("type", "text/javascript");
inject.appendChild(document.createTextNode("(" + main + ")()"));

document.body.appendChild(inject);

2012年2月11日星期六

如果我的证明是正确的,就不需要任何其他形式的肯定

想健康并且不浮躁地活,看来必须读一点书了。

2012年2月3日星期五

2012年1月1日不是2012年的第一周

> $ date -d "2012-01-01 00:00:00" +%U

> 01

>

> but in "man date"

> %U     week number of year, with Sunday as first day of week (00..53)

>

> Is it a bug?

给gnu发了封信,得到了详尽的解答,长知识了。

 ISO 8601 是一个神奇的标准,它定义了周数应该怎样数。
美国人按直觉定义每年1月1日所在的周为一年的第一周,而欧洲人制定的标准 ISO 8601 则不然。
首先, ISO 8601 定义每周的第一天为周日,其次,如果一年的第一周天数没有过半,则归入上一年的最后一周,第一个天数过半的周才真的算一年的第一周。
POSIX提供了支持这个标准的实现,也给出了多种其他符合直觉的选择,info date仔细读一下,深了去了。
查了一下中国国标,也是按这个ISO定义的。

2012年1月18日星期三

幂级数

假设有台印钞机每个月能印10元,不费纸不费电还终身保修,卖100元一台,要不要买一台呢?
假设月期望收益率是10%,那么还是不买为好,除非你忘了幂级数。
第一个月的收入折现:10/(1+0.1)=9.1,也就是说,第一个月月底的现金流入,在现在看来,价值只有9.1元。
同理,第N个月的工资折现:10/(1+0.1)^N
N趋于无穷的时候算部分和的极限=100

那应该怎么办呢?
把全部积蓄都拿来买这种印钞机,然后高价兜售给那些不懂幂级数的人XD

2012年1月14日星期六

./

有一天,我的C++程序在工作目录下建立了一个名为-1的目录,我想看看里面是什么鬼东西,不料
-bash-3.2$ ls -1/
ls: invalid option -- /
Try `ls --help' for more information.
分明是Tab出来的,怎么会这样。。。估计是ls的bug吧。cd进去看看?
-bash-3.2$ cd -1/
-bash: cd: -1: invalid option
cd: usage: cd [-L|-P] [dir]
我去。。。估计是没用了,删了吧
-bash-3.2$ rm -rf -1
rm: invalid option -- 1
Try `rm ./-1' to remove the file `-1'.
Try `rm --help' for more information.
原来如此,
rm -r ./-1
之后就天下太平了。

有一天,我的C++程序在工作目录下建立了一个名为~的目录,我一看
-bash-3.2$ tree
.
|-- bin
|   `-- run
`-- ~
    `-- workplace

3 directories, 1 file

没东西,那就删了吧
-bash-3.2$ rm -rf ~
rm: cannot remove directory `/home/ytwang': Permission denied
好生奇怪,我自己的程序跑出来的目录怎么会没有权限,难道程序里面用了sudo不成?。。。等等,为什么是/home。。。啊呀完了,赶快
-bash-3.2$ pwd
/home/ytwang/workplace
-bash-3.2$ ll
total 0
-bash-3.2$ cd
-bash-3.2$ ll
total 0
顿时心中拔凉拔凉的。。。


==结束语==
你永远不知道自己那充满了灵异事件的程序会创建出什么诡异的目录来,一旦他们被放出来,就将会像幽灵一样——你看不见他,而当你想砍死他的时候,自己就死掉了
要养成用./表示当前路径的好习惯
当你听说哪个同事不小心删除了某个重要文件的时候,不要惊讶,要同情

2012年1月7日星期六

驾照换证攻略

转眼驾照6年到期,要换本了。
第-1天:早上去照相馆照1寸照片,官网上给的规格说明很复杂,跟师傅说驾照用的,师傅都知道。非立等可取。15元。
第0天:早上去照相馆取相片。中午饭后在办公室打印《申请表》《身体条件证明》空白表,把自己能填的都填了,各贴一张照片,复印身份证正反面。
1点从朝阳门出发,打的到东直门医院,堵车(亏大了),11元,30分钟。
进门左手边有个门诊办公室,看一眼色盲的本本,然后大夫就边聊天便给你把表填好了,盖章,11元,2分钟。
出医院一路向南走,穿过海运仓小区,过东四十条的马路,再穿过军区总医院(好像这里也能体检),就到达了豆瓣胡同,15分钟。
在一条东西向的巨窄无比的小胡同里的路南,看到一个巨小无比的小门脸,上面写着"顺天府超市",东城交通支队的门就在那旁边了,巨不起眼。
拿号,没什么人,30秒后就到我了。给他《申请表》《身体条件证明》,身份证及复印件,再一张一寸照片,旧驾照。
他在电脑前敲一阵,然后换个窗口给他10元,就看到一张滚烫的新驾照出炉了。5分钟。
走回朝阳门,也就2点多。