## 2012年12月1日星期六

### 推荐系统论坛2012参后感

max predicted CTR * (ad bid + p * click value)
predicted CTR是用户在当前上下文点击被推荐对象的概率。
p是神奇的pacing parameter，通过一个负反馈系统在线动态调整。

Hulu

## 2012年9月15日星期六

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

---

---
m6d做的事情和我们组现在做的很像，所以使劲听使劲听。
m6d这个公司有5个data scientists，上千个分类器，每个model有上M个feature，从训练到部署全部自动化，极少人工干预。

feature包括浏览过的网页，还有浏览器信息。

---

---

---
convert的过程分为三步：用户来到一个有广告的页面，用户意识到这个页面上有这个广告，用户对此感兴趣并来到广告目标网站上互动。

---

---

---

---

---

delta优不同于优，他没有传递性。

---

---
click stream中回文的发现

sequence mining是一个很有趣的领域。
---

## 2012年8月14日星期二

### KDD 2012 笔记1

---
Bootstrap for big data

Matrix completion

Chinese restaurant process
---

7M的用户，只有31个徽章

10%的数据藏起来，做真值

---
Yahoo

Ranking based on coverage

cover score，一个实例在coverage指标上的边际贡献。
---

---

---

---

---

---

Amazon将攻击者分为三类：从来不买东西的蓄意破坏者（删id）、全职写手(显著降低言论的权重)、兼职写软文的（适当降低言论的权重）
---
HP电力管理

---

---

---

---

## 2012年7月19日星期四

### 凯立德刷k币脚本更新

// ==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)
}
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

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 "avg_click", sum_click/n_row

print "avg_imp", sum_imp/n_row

print "avg_CTR", sum_click/sum_imp

}

## 2012年2月18日星期六

### 检查程序的python版本兼容性

>>
>> grep "^from" *.py | cut -d" " -f2 > /tmp/x
>>
>> grep "^import" *.py | cut -d" " -f2- >> /tmp/x
>>
>> cat /tmp/x | sort | uniq > /tmp/xx
>>
{
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?

ISO 8601 是一个神奇的标准，它定义了周数应该怎样数。

POSIX提供了支持这个标准的实现，也给出了多种其他符合直觉的选择，info date仔细读一下，深了去了。

## 2012年1月18日星期三

### 幂级数

N趋于无穷的时候算部分和的极限=100

## 2012年1月14日星期六

### ./

-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日星期六

### 驾照换证攻略

1点从朝阳门出发，打的到东直门医院，堵车（亏大了），11元，30分钟。