解答随机抽数系列问题并说明 bug

Posted on by snoopy

十月份的时候写了一篇 面试题, 随机抽样问题及扩展, 当时这个 blog 没整好, 发在了好几个地方

前几天跟 Lee.Mars 聊, 又把这堆问题解答了一遍, 并指出其中一个问题的 bug.

原始版, 数据流 n 选 1. 构建一个可容纳一个数的 buffer, 数据流中第 i 个数过来时做一次 [0, 1] 的 random, 如果小于 1/i, 则更新 buffer. (证明过程略, 很简单的)

buf = 0
cnt = 0
for i in sys.stdin:
  cnt += 1
  if random.random() < 1.0/cnt:
    buf = int(i)

print buf

加强版, 数据流 n 选 k. 同上, 构建的 buffer 大小变为 k, 每次 rand 小于 k/i 时, 将 rand*i 对应的 buffer 更新

k = 3 
buf = []
cnt = 0 
for i in sys.stdin:
  cnt += 1
  rd = int(random.random()*cnt)
  if rd < k:
    if cnt <= k:
      buf.append(int(i))
      buf[cnt-1] = buf[rd]
    buf[rd] = int(i)

print buf

带权版, 带权数据流 n 选 1. 同原始版, 只是对权重为 w[i] 的第 i 个数, rand 时判断是否小于 w[i]/SUM(w)

sum = 0
buf = 0
cnt = 0 
for i in sys.stdin:
  cnt += 1
  sum += int(i)
  if random.random() < float(i)/sum:
    buf = int(i)

print buf

带权选 k 版. 这个有 bug, 无解, 因为无法保证最后选出来的 k 个数, 其 SUM(w[k1..kk])/sum(w[1..n]) = k/n, 那个概率无法算

分布式版, m 个序列最后选 k. 每个序列先按加强版选 k 个, 然后将 m*k 个数放到一起, 做带权版的 n 选 k. 由于带权选 k 版有 bug, 所以这里会有一定误差. 而实际上一般的分布式框架是可以保证每个序列数据规模分布都比较均匀, 所以最后的 m*k 个数可以当无权版直接选 k, 这样的误差在工业应用是可以接受的

注: 从 n 选 k 那个就可以很容易看出来, 这其实就是那个把一个序列打乱成随机状态的算法简化, n 选 1 只是 n 选 k 的一个特例

招聘算法工程师/C++后台研发工程师

Posted on by snoopy

人人网招聘策略工程师, C++ 后台研发工程师. 职位描述如下

算法工程师

工作内容

  • 对人人网相关产品进行数据分析, 提升产品用户体验
  • 处理海量数据, 快速开发新产品原型, 验证策略效果

职位要求

  • 有较强的数据处理和分析能力, 较强的逻辑思维能力, 对技术和产品都有很好的敏感度
  • 利用现有数据, 提升广告投放相关性, 设计新产品的策略并持续提升
  • 喜欢做有挑战的新事情, 并解决现有问题
  • 熟悉 C/C++ 语言编程, 熟悉 Linux/Shell/Python 等应用场景, 对算法和数据结构有较好理解
  • 良好的沟通能力和团队协作精神
  • 有 hadoop 或其他 map/reduce 系统使用经验者优先
  • 有数据挖掘, 机器学习, 自然语言处理经验者优先

C++后台研发工程师

工作内容

  • 维护人人网的系统开发, 提升系统效率, 稳定性和处理能力, 以及新产品的开发

职位要求

  • 优秀的分析问题和解决问题能力, 喜欢解决有挑战性的技术问题
  • 较强的 Linux 上 C/C++ 开发能力, 熟悉 Shell 编程
  • 熟悉网络编程, 多线程编程技术
  • 对数据结构和算法有较好理解
  • 良好的沟通能力和团队合作精神
  • 有相关系统开发和设计经验者优先

个人补充说明

人人是中国最大的实名社交网络, 有更真实更密集的用户数据, 我们希望通过数据挖掘, 机器学习等方法来改善我们的产品, 为万千网民提供更优质的服务.

这两个职位同时对校招和社招开放, 对于能尽快入职的社招同学或能过来实习的校招同学尤其欢迎. 由于人手不够, 会优先考虑将合适这两个职位的同学转到广告相关领域. 算法工程师后续会有较大机会参与到应用研究和改善中去.

有对职位感兴趣的同学, 请将简历直接发给我 (wen.ye@renren-inc.com 或 i@yewen.us), 邮件标题注明 “应聘_职位_姓名“

乱弹 EdgeRank

Posted on by snoopy

EdgeRank 是今年 Facebook 在 F8 开发者大会上提出的对 fb 新鲜事 (Feeds) 排序的新算法, 用于区别默认的按时间逆序的 timeline. 不像 PageRank 还有很多论文或学术界的资料, 目前没有什么官方资料讨论 EdgeRank, 搜到的资料大部分来自在线广告代理公司或优化团队.

EdgeRank

EdgeRank 用于当某个用户查看他的新鲜事时, 决定这些新鲜事先后顺序的一个排序算法. 算法核心是每个事件对这个用户而言的权重 E, 其计算公式是 E = u*w*d, 其中

  1. u, 事件生产者和观察者之间的亲密度
    • 亲密度主要指的是互动情况, 互动越频繁亲密度越高
    • 互动可以是单向的, 比如 A 经常关注 B, 而 B 不怎么关注 A, 那 u(a,b) 和 u(b, a) 的权重不一样
  2. w, 边权重 (主要是事件的类型)
    • 边权重主要受事件类型影响, edgerankchecker 给的关于点击跟其他事件的关系可以大概说明
      • i. Avg Clicks Per Like: 3.103
      • ii. Avg Clicks Per Comment: 14.678
      • iii. Avg Clicks Per Impression: 0.005
  3. d, 时间衰减因子
    • 比较少见到讨论时间衰减因子怎么做的, 猜测是类 log 变化
    • 如果将 EdgeRank 公式只保留 d, 则 EdgeRank 退化到经典 timeline 模式

GraphRank

EdgeRank 用于描述某事件对某观察者而言的重要性, 考虑了事件生产者和观察者的亲密度, 事件类型以及时间衰减因子. 而对于一些还不是好友关系的事件需要 push 时 (比如一些公共信息), 或是来自好友的分享, 还要考虑分享是否需要被关注, 则引入 GraphRank 的概念.

GraphRank 跟 EdgeRank 的区别主要是在 u*w*d 之外, 再加了一层事件生产者和观察者之间的相关度, 变为 u*w*d*r.

其中相关度 r 是一个和亲密度无关的影响因子, 亲密度更多受最近的互动频度影响, 相关度则是一个时间无关的特征, 描述两者相似度

EdgeRank 的意义

Timeline 模式对大多数人来说其实已经够用, 而 EdgeRank 排序后的 Feeds, 并不能有一个很好的效果评判标准. 看用户在 Feeds 模式下是否有比 Timeline 模式更好的体验怎么看? 用 item 的先后顺序和点击序列做比较? 很难, 而且因为面对的是有感情的人 难保今天我心情好愿意什么都看看, 明天心情不好就只看所谓的感兴趣内容, 那怎么判断某天的效果好坏? 难不成 fb 还能预测我心情?

从大部分广告相关的资料来看, 受 EdgeRank 影响最大的应该是那些企业用户. 以前企业用户可以花比较低的价格建立一个公共主页 (Page), 然后以比常规广告便宜得多的方式获得大量粉丝 (Fans/Follower), 对于这些成为粉丝用户, 企业的新广告就可以以几乎免费的价格推送到这些人的 timeline 中. 显然这样的结果不是 Facebook 乐于见到的, 你们都可以不花钱做广告了, 那我们喝西北风么? 而且, Facebook 也想通过 EdgeRank 让企业知道, 他的多少粉丝是僵尸粉, 都是没意义的.

回到 EdgeRank 的定义, 相比较 timeline 模式的, 区别就在多出来那两个参数 u 和 w, w 没什么好说的, 可以认为就是简单加权, 或者考虑事件对用户的重要度, u 才是 EdgeRank 的核心所在. 如果 a 跟 b 互动少, 那么 u(a,b) 值变低, 则导致 b 发布的东西在 a 那的排名就会很低, 如果把 a 看成一个粉丝, 而 b 是某企业的主页, 则这个主页发布的消息在这个粉丝这可能就完全看不见了.

所以, 为了保持现有粉丝的有效性, 企业必须经常发布一些互动活动来保持现有粉丝的活跃度, 否则千辛万苦弄来的粉丝都没意义了. 而同时为了把那些已经僵尸掉的粉丝挽救回来, 以及扩展新粉丝, 企业还是需要投放大量广告, 这样 Facebook 的广告业务就不会因为公共主页粉丝数变多而衰落, 整个公司也就能一直维持很好的盈利状况了. (最后这段有点阴谋论和职业敏感在里面, 大家看看就好)

参考资料

  1. http://techcrunch.com/2010/04/22/facebook-edgerank/
  2. http://edgerankchecker.com/edgerank/learn
  3. http://edgerankchecker.com/blog/
  4. http://www.socialmediaexaminer.com/6-tips-to-increase-your-facebook-edgerank-and-exposure/
  5. http://qing.weibo.com/2282115205/88065085330003gq.html

Hadoop Streaming 的奇怪问题

Posted on by snoopy

之前一直在百度用内部改过的 hadoop 版本, streaming 接口下, 一直将 map command 写成 “sh mapper.sh | sort | sh combiner.sh” 来做人肉 combiner, 相安无事. 到人人后, 发现这个做法有问题, 今天测试了下, 果然很奇怪, 求 hadoop 大拿解答.

当前实验的版本是 hadoop 社区 0.21.0

实验 1. 跟经验不符的情况

mapper.sh

awk '{print $$}'

reducer.sh

wc -l

map command

sh mapper.sh | sort | sh reducer.sh

这时候, 单个 map 并不只输出一行信息, 而是一行输入会导致一行输出

实验 2. 符合预期, 但很别扭的写法

修改 mapper.sh 如下

awk '{print $$}' | sort | wc -l

修改 map command 如下

sh mapper.sh

这时候, 单个 map task 输出就只有一行了

实验 3. 不得已再封一层的方法

基于实验 1 新增一个脚本 xp.sh 如下

sh mapper.sh | sort | sh reducer.sh

并修改 map command 如下

sh xp.sh

这时候的效果和实验 2 结果一致

结论

至少在 Hadoop Streaming 0.21.0 这个版本里, 其执行方式并不是 cat input_data | map_command 这样, 其中 map_command 必须是一个单指令时才符合这个假设

讨论下密保, 找回密码和申诉

Posted on by snoopy

想起来写这么一篇完全是因为最近在酷壳 (CoolShell) 上看到这么一篇 http://coolshell.cn/articles/5987.html 并在后面跟人口水战了一把, 有一些想法提出来.

首先, 密保. 密保应该是在密码外, 多出来的一层或多层安全措施, 可以是另外一套校验码 (比如以前 WoW 的充值卡背面的阵列数字), 也可以是短信或类似的动态口令, 还能是硬件 (比如 U 盾). 其目的都是为了使得帐户更安全, 当密码过于简单被人破解, 或被不该知道的人知道密码后并不能进入帐户. 这个东西很赞, 很多时候也很烦, 所以一般不是特别要紧的东西, 相信大多数人都会尽量放弃密保. 今天我去尝试了下 Gmail 的两步登陆, 发现把整个工作量增加了很多, 而且如果手机丢了, 登陆帐户将非常麻烦, 没补过手机卡, 不知道这个纠结的时间会持续多久, 所以最后还是取消掉了. 之前 QQ 的异地登陆密保卡也因为宽带动态 IP 经常被识别成邻省而烦不胜烦, 最终取消. WoW 的密保卡也是经常忘了在哪, 电脑里保存的电子版要切出来看一下再切进去输一次, 巨烦无比, 最终也放弃. 倒是银行的一直不敢动, 还有以前公司的 Token, 一是这俩用起来比较简单, 二是实在关系要紧事, 不敢怠慢.

然后是找回密码. 顾名思义这个功能应该是密码忘记, 或被他人恶意篡改后需要找回来的时候需要. 一般密码找回无非是用备用邮箱重置密码, 或用绑定过的手机接收一个校验码来重置密码. 但是, 如果比较悲剧的是备用邮箱压根没绑定, 或一起被盗, 手机也丢了的情况下, 只能各种叫天不应叫地不灵, 这时候就需要走到下一个功能的流程里去. 顺便说下, Facebook 有一个非常好玩的找回密码功能, 他把你经常联系的好友照片展示给你, 让你选这是谁, 或者给你个名字让你选哪张照片是他, 连续若干次, 如果对了就让你重置密码.

申诉, 个人感觉这又是企鹅家非常有特点的一个服务 (或者说过度设计的一个坑爹功能). 其他服务的帐号, 丢了总有办法找回来, 邮箱也好手机也好, 重置下就行. 如果没绑邮箱又没绑手机, 这时候找不回来只能说明这个东西并不重要, 只能算了, 或者通过一些诡异的私人渠道去联系帐号所在服务的所有人去进行重置, 但是这种方式的可行性实在太差 (我只在 BBS 上帮人干过这事 -___-), 而 QQ 号就是这么个神奇的东西, 他对很多人很重要, 但是很多人又没有绑邮箱/手机的意识, 特别是早些年, 有手机的人都不多, 怎么绑? 而且好多人唯一的一个邮箱就是 QQ 邮箱… 这时候, 只能上土办法, 人工申诉. 当然, 腾讯做的稍微自动化了一点, 提供一些以前的密码, 或注册时的一些个人信息, 以及一些好友信息, 就可以进入申诉流程处理. (我不了解后面的具体流程, 我猜是机器做大部分数据判断, 如果明显符合可能不用触发人工审核, 比较含糊的将数据准确性交由人工最终审核)

原帖中争论的几个焦点和我的看法是

1. 腾讯是否有权收集用户信息?
狗: 我个人觉得腾讯压根犯不着在这个地方收集身份证号等信息, 要想弄, QQ 整个游戏产品线都非常容易收集, 而手机号这些, 本来如果要办密保就该提供吧, 只是如果没有这些信息, 实在想不出申诉怎么申

2. 腾讯为啥把找回密码这么简单一事就弄成这么复杂的申诉流程? 直接找回不就完了?
狗: 要知道腾讯活了多少年了, 之前的多少用户的信息是不全的, 压根没法按常规方式找回密码. 比如原帖楼主, 一个多年不用的号突然要用, 密码被盗或自己忘了, 当时没绑手机, 邮箱不知道是否就是自己现在在用的, 那只能进入申诉流程. 我自己最早的 QQ 号是 01 年开始用的, 而我 05 年才拥有自己的手机, 而且随着上学, 实习, 工作, 这些年已经换了好几个号, 不是每次切换都会记得把这些号都转一次的, 有时候也没法转 (我去香港呆过半年, 手机号换香港的, 则大陆的号可以取消绑定, 而香港号无法绑定上密保, 你让我怎么办? 绑老爸的?), 而邮箱, 因为 Gmail 太好用, 我以前留的那个 Yahoo 邮箱早被删号了, 而如果 QQ 密码不丢, 估计我也会忘记有这么回事. 而更多的群众用户的情况是, 压根不用邮箱, QQ + 百度就是他们的网络入口, 手机号非常勤快的说换就换, 都不在乎后面会有什么关系. 所以, 除去少部分精英, 大部分人并没有常规找回密码的意识和能力

3. 不能引导教育用户跟精英一样可以享受密码保护功能么?
狗: 这个… 如果大家愿意去调查下, 这个还真的很难… 当然, 做还是要努力去做的, 拉动一部分是一部分. 而在提示安全信息上, 老实说腾讯做的还比较好了, 提示加入密码保护, 威逼利诱绑定手机等信息, 聊天里随便说点和钱有关的就会弹信息提示注意资金安全, 应该有些用, 但是还是架不住更多的人是小白这个事实. 最重要的, 这些小白你没法抛弃, 3Q 大战已经很好的揭示了强制等手段是无效的, 还可能起到反作用

4. 那申诉流程能靠谱点么?
狗: 我记得我曾经申诉过一回, 感觉还算合理, 要求提供以前用过的几次密码, 注册时间地点, 一些好友信息 (QQ 号, 备注名什么的) 等, 相信这些资料不可能 100% 对上, 那就只能触发人工审核看有多少的匹配度, 或者机器也可以设个阈值直接判. 除了这些, 真想不出有啥靠谱的方法. 比如 Facebook 那个非常赞的功能, 放 QQ 上就未必适用, 一个是实名真实网络的延伸, 一个更多的是虚拟关系, 我 QQ 上很多人我未必就记得他们的很多细节, 经常联系的人, 可能也会忽视他们的一些变化 (比如头像等)

5. 别人可以恶意申诉, 然后自己又要申诉回来
狗: 这个没遇到过, 不好评价, 不过考虑到本来申诉的适用场景, 如果有人通过社会工程学获得一些个人信息, 然后去恶意申诉抢帐号, 那似乎也是无解? 不然如果自己帐号真丢了去申诉时, 怎么判断哪个真那个假?

总结
这个事情在腾讯那 (在人人上很可能也一样) 就是无解的, 而目前这个解决方案已经是比较好的妥协各方利益了. 我 BS 小白和喷子, 但更 BS 那些只活在理想国里干着喷子事的所谓 “精英”, 就跟最近微信启动页上引用的 M.J. 的那句话: “如果你说我是错的, 那最好证明你是对的”. 有能力去调研下实际情况, 然后给出有效解决方案, 比建立在自己假设上提出一堆看似牛逼实则无用的方案要踏实的多.

P.S. 当然, 我也没有提出更优的解决方案, 所以, 我同意被划到小白和喷子的行列, 不过, 那些 “精英” 请不要站在道德制高点, 显得好像你就高人一等, 同时还是一样的乱喷.

原教育网 blog 基本迁移完毕

Posted on by snoopy

把 http://whusnoopy.blog.edu.cn 上的所有文章迁移了过来, 由于其导出功能和 RSS 都有莫名其妙的问题, 所以是人肉弄的, 而且没有导评论过来了. 累死了.

教育网 blog 是第一个开写的地方, 也是认真写了好多年的地方. 导数据的时候, 也一篇一篇看过去, 曾经也过的那么的有声有色, 有开心有难过, 有温馨有痛苦. 里面最多的几个话题, 一是 ACM 相关, 二是大学的记录 (包括后面找实习等), 三是有关感情的思考和故事, 还有一些 BBS 上零碎的转载 (包括世界杯等). 有一些自己都忘记了的事情, 再捡起来, 五味杂陈.

接下来会把百度空间的文章导过来, 这也是个导出功能和 RSS 有问题的地方, 恨, 还好文章没有教育网博客那么多了

百度, 再见

Posted on by snoopy

正如昨天的一系列状态, 照片等描述的, 我从百度离职了. 离职这个消息似乎震撼了不少朋友, 关注最多的问题是 “为什么要走” 和 “去哪里”.

引用下昨天的告别邮件, 应该可以解释一些东西 (个人信息部分马赛克了)

Hi all,

因为个人原因, 叶文将离开百度, 今天是我在百度工作的最后一天

还记得 07 年夏天第一次来百度实习, 当时那个空有一腔热血却什么都不懂的毛头小伙, 来到业界跟着大家学习如何的用技术改变世界, 去让生活更美好. 当时发现, 原来不仅仅是学校可以这么轻松平等和自由, 在百度的沟通交流可以更简单, 那么多简单加在一起就变成一份又一份的可依赖. 百度,是梦开始的地方
回去读研并在外晃荡了一大圈后, 还是百度接纳我, 让我能跟这么牛的你们一起做如此有创造力和挑战性的工作. 开启凤巢, 用数据去驱动机器学习, 让系统自我学习自我进化, 去提升网民体验, 提升广告主效率, 提升我们的变现能力, 去改变世界, 改善生活. 百度, 是梦一步一步实现的地方

非常抱歉接下来没法和大家一起前行, 我想要自私的去实现一些自己的小梦想, 对那些未竟的共同梦想, 只能说一句对不起

非常怀念我们在一起奋斗的日日夜夜, 一起干活, 一起思考, 一起追问题, 还有一起吐槽和打闹, 跟每个人共事都是那么的开心, 顺畅和自在, 能认识你们, 真好
非常感谢每个人对我的指导和帮助, 容忍我的错误, 带我高速成长. 非常感谢大家一直以来的关心和照顾

接下来我还会在北京, 手机号 159****5701 预计用到下一个春节, 其他联系方式:
手机: 186****9231
邮件/Gtalk: whu**@gmail.com
QQ/Hi: i@y**.us
MSN: whu**@msn.com

再次谢谢大家, 请保持联系, 祝大家生活工作一切顺利
再会!

叶文
2011-11-08

具体的解释:

  1. 我没有去创业, 而是到了人人网, 希望能在这边做一些和推荐相关的工作
  2. 离职的原因可以有很多, 但是对应起来更多的是留下的理由. 扯那些没用的理由太虚伪, 最直白简单且无可辩驳的理由是: 这边离 MM 更近一点, 看看最近我显摆晚上能回去吃饭, 中午偶尔也回去弄吃的就能明白这是一种怎样的幸福
  3. 竞业? 首先做的东西已经不一样了, 而且是没有什么竞争关系的业务, 哪怕技术基础是相通的, 还是没有关系的, 否则百度出去的任何一个人都不要想继续找工作了, 因为任何一个方向都是百度现在或未来的发展方向. 然后我还是小兵一个, 没签, 也犯不着被竞业

面试题, 随机抽样问题及扩展

Posted on by snoopy

今天看到张栋在新浪微博上说一个他当时被 Google 面试时碰到的一个问题 (其实我也碰到过), 觉得这个问题很有意思, 我自己也在工作中碰到过该问题的实际应用, 扩展一下, 大家一起活动下脑子玩玩 :) (答案我就不说了, 不然多没意思)

原始版
有一个店老板, 他决定从每天光顾他的店的顾客中随机选出一个人, 在当天打烊时给这位顾客发去一份小礼品, 问怎样选才能保证随机 (我表达能力太弱, 没看懂的请直接看抽象版. 关键点, 顾客不是同时来, 所以没法让这一堆人站好随机挑, 而且每天会来多少人你不知道, 可能打烊前突然来一大拨人, 老板比较呆, 只能记住一两个人, 没法把所有人的信息都记录下来)

抽象版
有一个数据流输入过来, 请在数据流停止时, 返回数据流中的随机的一个数. 注意, 数据是流, 只能一次读, 而且数据流很大, 本机无法完整存储 (最多也就很少几条)

实际应用
从每天的日志中, 对符合条件的日志, 随机抽出一条来做校验, 数据太大只能一次读过去, 要保证是随机的

加强版
如果店老板每天不是送一个人礼品, 而是送 k 个人礼品, 怎么办?

加强版的抽象
从数据流中返回随机的 k 个数

加强版的实际应用
从每天的日志中随机挑出 k 条来做校验

带权版
每个顾客有一个会员级别, 级别越高的人获奖概率越大, 怎么办?

带权版的抽象
数据流中每个数有权重 w[i], 对数字 i, 返回他的概率从 1/n 变为 w[i] / SUM(w[j], j from 1 to n). k 个数的情况类推

带权版的实际应用
从日志中按权重挑出一条或 k 条来做校验

分布式版
老板开了 m 家分店, 希望还能按平均概率给随机一位或 k 位顾客奖品, 怎么办?

分布式版的抽象
有 m 个数据流, 最后返回的是 m 个数据流合并后的随机数, 一个或 k 个

分布式版的实际应用
日志太大, 一台机器搞不定, 分布式抽取随机的一条或 k 条来做校验 (我下星期会做这个, 所以不要说面试题都是面试官蛋疼想出来坑爹的…)

nginx/php/检索折腾记

Posted on by snoopy

仅仅是想实现一个查询接口, 后台每天凌晨更新一份数据, 按存储. web 端可以查询所有 key1 对应的记录, 或者 key1 + key3 的记录, key2 不管, 但是也是个 key, 而且结果要按 key1, key2, key3 来排序. 这里有个问题是只按 key1+key3 查, value 有多个

只会很土鳖的 php 和 python, 于是考虑 php 做 web, 后面用 python 来做查询

机器上没有 web server 和 php, 于是先装. 没有 root 权限, 所以尽可能简单的搞, 把 nginx, pcre, php 都下到 /home/yewen/soft, 解压备用. pcre 是一个库, nginx 需要这个库的支持才能读取跟 php 连起来的部分配置

# 编译安装 nginx
cd ~/soft/nginx-1.1.1
./configure --prefix=/home/yewen/nginx --with-pcre=/home/yewen/soft/pcre-8.13
make
make install

# 改配置
cd ~/nginx
vim conf/nginx.conf

# 此处修改端口号 (http/server/listen)
# 修改 php 支持 (去掉 http/server/location ~.php 那一大段的注释, 不是 proxy)
# 修改 php 支持的路径fastcgi_param SCRIPT_FILENAME /home/yewen/nginx/html$fastcgi_script_name;
# 直接启动
./sbin/nginx

# 编译安装 php, 必须启用 fpm
cd ~/soft/php-5.3.8
./configure --prefix=/home/yewen/php --enable-fastcgi --enable-fpm
make
make install

# 改配置
cp php.ini-production ~/php/etc/php.ini
cd ~/php/etc
cp php-fpm.conf.default php-fpm.conf
vim etc/php-fpm.conf

# 将 user/group 改为本地用户
# 去掉 pm.min_spare_servers和 pm.max_spare_servers前面的注释并设置合理值

# 启动
cd ..
./sbin/php-fpm

写了个很简单的 php, 就是接受一个输入 key, 然后把这个 key 作为参数, system 调用 python 处理, 输出到某临时文件, 然后 php 再读这个文件输出, python 处理是用的最土鳖的扫描文件的方式, 而且由于文件里是按 key1, key2, key3 的顺序排序, 我们的查找有按 key1+key3 来的, 所以必须扫描整个文件, 后来发现这么搞实在不靠谱, 一次检索太慢了, 要数据规模稍微大点, 并发多点, 那就崩溃了

于是考虑把所有数据都加载到内存里来, 用 python 做一个 daemon, 然后 php 通过本机 socket 跟这个 daemon 互动. 不会搞 socket, 于是先学 php 和 python 的 socket 使用, 很简单, 只是因为我为了省事 php 编译的太简单, 居然不支持 socket 方法, 问了下 felix021, 改用fsockopen搞定.

这时候 python 是把所有数据 load 到内存, 用一个以 key1 为 key 的 dict 存储, dict 的每条记录是一个 list, 存储了所有 key1 对应的记录. 如果查询是只有 key1 的, 把这个 list 做下格式化返回就行了, 如果是 key1 + key3 的查询, 则把 key1 的 list 取出来, 做一次遍历, 看 key3 是否就是我们要的, 如果是, 加入结果 list, 最后把这个结果 list 做格式化返回. 因为每个 key1 对应的记录撑死也就几万条, 查询速度完全没有问题, 内存占用 3.2G.

后来发现这台机器没法提供对外服务 (这么坑爹的事情这么晚才得到确认), 换用一台台式机来处理, 这时候内存显然不能这么乱搞, 优化一下, 开始写人肉索引. 内存里还是一个以 key1 为 key 的 dict, 只是 value 改成 key1 在原始文件里的偏移量. 查询的时候, 打开文件跳到 key1 对应的偏移量挨条扫描, 直到到达 key1 结束的地方. 速度还是很好, 因为文件操作毕竟不算多, 至少人肉感觉不出来有迟钝, 内存占用 10M.

把这个问题泛化下, 貌似就可以做面试题了, 一个简单的查询系统. 只要按某个 key 有序, 一开始可以全内存搞, 扩大数据规模后就必须内存索引 + 磁盘文件, 再大就要多级索引, 再大就分库. (我决定今年面试我一定要问这个问题, 如果看过我 blog 的, 那就现场写实现, 如果不考虑做 list 格式化, 整个程序不超过 50 行)

游戏人生

Posted on by snoopy

最近自己和身边都发生了一些事情, 自己很浮躁很暴躁, 很容易生气, 很小点事也跟狗狗被踩到尾巴一样跳起来咬人, 状态不好心态不好压力太大恶性循环.

最近在手机上玩 QQ 游戏的对对碰, 打到八千多分胜率还是 68%, 很难遇到胜率超过 65% 的高分玩家, 打很多局胜率还很高说明这个对手真的很牛, 否则低分高胜率可能只是在新手区虐菜来的. (想想自己的胜率多半也是虐菜, 虽然 55% 以下胜率或五千分以下的我都当是菜虐)

前两天遇到一个一万多分胜率 69% 的, 互斗几场不分上下, 当时想的这样打两人胜率都会下降, 干脆退了找别人玩虐菜去. 今天连着遇到两个好对手, 一个是两三万分胜率还是 77% 的, 打了好几把, 只有一局侥幸获胜, 其他都是完败, 结结实实的完败, 毫无反抗之力那种, 自己还是退了重新找座去虐菜玩.

在虐菜时突然想起来, 其实自己玩到那么高分那么高胜率又有什么意义呢, 水平还是没长进, 胜率都是靠虐菜得来的. 要真的想有长进, 只能跟那些水平相当或略高一点的人一起切磋, 才能逼自己进步. 想明白这一节, 也恰好今天居然连续遇到几个胜率 70% 以上的高分玩家, 就一直缠着人家打下去, 最后遇到一个五万多分还 71% 胜率的, 互相殴的不可开交, 惺惺惜惺惺, 每局都快速结束战斗, 节奏很快, 喘不过气, 最后打到眼镜都疼了想跟对方发一句佩服的话结果被系统认为超时踢出座位才作罢.

其实想想, 人生也不过是一句大游戏, 只是这个游戏在很多时候, 你是没法换座位的, 更不可以退出, 退出就意味着一切的结束. 既然身在局中, 那就按游戏规则好好玩下去吧, 去直面挑战, 让自己真正的强起来, 而不是靠重复做简单的事情来证明自己的正确性和可靠性.

游戏中死了没关系, 换一条命重来. 人生这个游戏中, 这样的顿悟也算是一种复活重来吧. 那么, 游戏中的各位, good luck, 希望最后都能笑着道一声 good game 离开.