工作点滴

工作后的记录

自吐 & 自勉

Posted on by snoopy

今天百度最高奖, 看了下, 最终入围的五个团队有三个自己呆过, 拿奖的仨也呆过俩, 好多认识的人, cong~ (附: 拿奖的新浪微博消息) 他们都做的很赞, 自己曾经在这么好的团队, 耐不住性子, 做不出东西, 因种种原因离开, 开花结果自然无份

现在么, 好好做事, 手头事情也很有搞头, 那就好好搞吧, 皇天不负有心人 :P

自吐部分开始, 曾经有一个帖再引用了以前的一个段子 (原文见: 被诅咒的 Snoopy)

Me 13:23:45
我从 b 家离职后不久, b 家的碳酸饮料就免费了
我从 g 家离职后不久, 餐补就直接发钱了, 等我开学, 上海也是自助餐了
小强 13:25:56
你快点离开武大
Me 13:26:16
why?
Me 13:26:23
这样师弟师妹的伙食就有希望了?
小强 13:26:57
恩
小强 13:27:18
你离开acm acm就拿到金牌了
Me 13:28:20
…

我一定要把这个段子续下去:

* 2007 年夏离开武大 ACM 队, 该年秋天武大第一次拿区域赛金牌, 第一次进入世界总决赛
* 2008 年初进微软俱乐部, 该年夏令营活动被取消
* 2009 年初离开微软俱乐部, 该年夏令营活动恢复, 并增加 UCLA 夏令营
* 2009 年秋天回归百度, 过了一个月从普天搬西二旗, 自助碳酸饮料机被取消了
* 2011 年秋天离开百度, 半年后自己做废了的俩项目重新上线
* 2011 年秋天离开百度, 次年原团队拿百度最高奖

读完了数学之美

Posted on by snoopy

正如上一篇日志中提到的, 最近买了吴军博士的数学之美并利用晚上的时间在看. 粗粗的过了一遍, 把以前很多没明白的东西给理顺了下, 具体的一些数学推导没来得及去验证. 书的后半部分感觉比较凌乱和随意, 不过还是值得购买去支持的, 如果大家都不买书, 那以后也会越来越难读到经典之作.

读的过程中用手机简单记了些简单的笔记, 现在回头想想, 再过一下:

方法论

1. 做事要简洁高效: 简单粗暴的方法, 只要是对的那就应该这么做, 与其花非常大的代价弄一个貌似完美的系统, 最后还不一定能保证结果, 还不如花很短的时间去做一个能达到 90% 性能的可用系统, 并用若干个 90% 性能的系统组合起来达到完美效果. 这一点也是我非常认可和坚持的, 在团队里也需要贯彻下去.

2. 凡事都需要可解释: 做策略做算法, 一定要对每个 case 给出合理的解释, 这样才能知道怎么去改进. 吴军在书里举的例子是说搜索, 一开始要用简单高效的系统和特征来保证鲁棒性和可调试性, 其实在计算广告和推荐系统里也是一样, 只是我们现在总会一上来就弄很多复杂的上去, 导致很难调试和追查, 最后就一把烂账怎么也算不清. 这点上自己一直做的不好, 要好好注意.

3. 真理应该拥有简单漂亮的描述: 自然真理的本质描述往往是很简单的很漂亮的, 如果搞的太复杂, 就不太对头, 多半是方向都错了. 书里的例子是说描述太阳系的行星运动, 地心说的模型需要用 40 层圆周修正, 日心说则可以降低到 8-10 个圆周修正, 但最后的真理却是一个椭圆方程就完美解释.

具体案例

1. 新闻/文本分类中的加权. 在做余弦相似度计算时, 需要考虑位置加权, 词性加权等影响. 对于位置加权, 一般的思路都是对树形结构做加权, 比如普通文章的标题/摘要等, 网页则一般是 HTML 语法树的加权, 实际上 Google 在很早之前就开始模拟网页渲染, 做物理位置的加权, 而这一套网页渲染的技术, 用来开发 Chrome 不是正好? 而且随着 Chrome 的市场占有率上升, 也可以逼迫高质量网站的网页代码会更标准, 至少是可以兼容 Chrome 的标准, 这样 Google 可以获得更准确的页面渲染效果并用于权重计算, 现在很多别的公司也开始关注浏览器, 但是不知道有没有想到这一层用法. 词性加权这又回到 NLP 的基础建设上, 果然做互联网, 要做精做深, NLP 是个绕不开的大坑, 就算数学模型如此优雅和有用, 但还是需要有基础数据才能去计算.

2. Logistic Regression 在工业界的广泛应用. 自己好像在生产环境中就用过这一种模型, 接触过线性回归和 Naive Bayes, 但是都没能去深入理解, 其他 boosting 和 SVM 等方法, 每次都是听了个大概, 一直没空去试. 根据自己的经验, 以及吴军的说法, LR 最大的优点是线性叠加, 皮实耐操以及水平扩展性好, 这几个都挺符合方法论的. 不过在点击率非常低的环境下, 要用好 LR 确实很难, 吴军说的是特征权重在 [-6, +6] 区间才有意义, 按 Sigmod 变换函数 1/(1+exp(-z)) 计算, -6 对应的也不过是 0.247%, 这个点击率在搜索广告以外的很多地方还是挺难达到的, 加上位置, beta0 等修正后可以让值很接近, 但是精度又受很大影响, 之前想过把某个小区间做放大处理, 但是一直没想清楚到底要怎么扩, 怎么能维持相对关系并可以还原, 求指点.

机器学习手记系列 2: 离线效果评估

Posted on by snoopy

上一次说到选特征的一个简单方法, 但是如果真的要评估一个方法或者一类特征的效果, 简单的相似度计算是不够的, 在上线实验之前, 还是需要有一些别的方式来做验证.

我遇到过的大部分机器学习问题, 最终都转成了二分类问题 (概率问题). 最直白的比如 A 是否属于集合 S (某照片中的人脸是否是人物 Z), 排序问题也可以转换为二分类问题, 比如广告点击率或推荐的相关度, 把候选集分为点击/不点击或接受推荐/不接受推荐的二分类概率. 那在上线之前, 可以用过一些分类器性能评估的方法来做离线评估.

分类器的正确率和召回率

前几天在无觅上看到有人分享了一篇 数据不平衡时分类器性能评价之ROC曲线分析, 把这个问题已经讲差不多了, 我这复述一下.

先说混淆矩阵 (confusion matrix). 混淆矩阵是评估分类器可信度的一个基本工具, 设实际的所有正样本为 P (real-Positive), 负样本为 N (real-Negative), 分类器分到的正样本标为 pre-Positive’, 负样本标为 pre-Negetive’, 则可以用下面的混淆矩阵表示所有情况:

              | real-positive       | real-negative
pre-positive' | TP (true positive)  | FP (false positive)
pre-negative' | FN (false negative) | TN (true negative)

通过这个矩阵, 可以得到很多评估指标:

FP rate = FP / N
TP rate = TP / P
Accuracy = (TP + TN) / (P + N)    # 一般称之为准确性或正确性
Precision = TP / (TP + FP)        # 另一些领域的准确性或正确性, 经常需要看上下文来判断
Recall = TP / P                   # 一般称之为召回率
F-score = Precision * Recall

在我接触过的大部分工作中, 大家都在关注 Precision 和 Recall. 同引用原文中提到的, 这样的分类评估性能只在数据比较平衡时比较好用 (正负例比例接近), 在很多特定情况下正负例是明显有偏的 (比如万分之几点击率的显示广告), 那就只能作为一定的参考指标.

分类器的排序能力评估

很多情况下我们除了希望分类器按某个阈值将正负样本完全分开, 同时还想知道候选集中不同条目的序关系. 比如广告和推荐, 首先需要一个基础阈值来保证召回的内容都满足基本相关度, 比如我一大老爷们去搜笔记本维修代理你给我出一少女睫毛膏的广告或推荐关注, 我绝对飙一句你大爷的然后开 AdBlock 屏蔽之. 在保证了基础相关性 (即分类器的正负例分开) 后, 则需要比较同样是正例的集合里, 哪些更正点 (其实说白了就是怎样才收益最大化). 一般来说, 如果分类器的输出是一个正例概率, 则直接按这个概率来排序就行了. 如果最终收益还要通过评估函数转换, 比如广告的 eCPM = CTR*Price, 或推荐里 rev = f(CTR), (f(x) 是一个不同条目的获益权重函数), 那么为了评估序是否好, 一般会再引入 ROC 曲线和 AUC 面积两个指标.

ROC 曲线全称是 Receiver Operating Characteristic (ROC curve), 详细的解释可以见维基百科上的英文词条 Receiver_operating_characteristic 或中文词条 ROC曲线. 我对 ROC 曲线的理解是, 对某个样本集, 当前分类器对其分类结果的 FPR 在 x 时, TPR 能到 y. 如果分类器完全准确, 则在 x = 0 时 y 就能到 1, 如果分类器完全不靠谱, 则在 x = 1 时 y 还是为 0, 如果 x = y, 那说明这个分类器在随机分类. 因为两个都是 Rate, 是 [0, 1] 之间的取值, 所以按此方法描的点都在一个 (0, 0), (1, 1) 的矩形内, 拉一条直线从 (0, 0) 到 (1, 1), 如果描点在这条直线上, 说明分类器对当前样本就是随机分的 (做分类最悲催的事), 如果描点在左上方, 说明当前分类器对此样本分类效果好过随机, 如果在右下方, 那说明分类器在做比随机还坑爹的反向分类. 引用维基百科上的一个图来说明:

ROC 曲线示例

其中 C’ 好于 A (都是正向的), B 是随机, C 是一个反效果 (跟 C’ 沿红线轴对称, 就是说把 C 的结果反过来就得到 C’).

如果我们有足够多的样本, 则对一个分类器可以在 ROC 曲线图上画出若干个点, 把这些点和 (0, 0), (1, 1) 连起来求凸包, 就得到了 AUC 面积 (Area Under Curve, 曲线下面积). 非常明显, 这个凸包的最小下面积是 0.5 (从 (0, 0) 到 (1, 1) 的这条线), 最大是 1.0 (整个矩形面积), AUC 值越大, 说明分类效果越好.

用 ROC 曲线定义的方式来描点计算面积会很麻烦, 不过还好前人给了我们一个近似公式, 我找到的最原始出处是 Hand, Till 在 Machine Learning 2001 上的一篇文章给出 [文章链接]. 中间的推导过程比较繁琐, 直接说我对这个计算方法的理解: 将所有样本按预估概率从小到大排序, 然后从 (0, 0) 点开始描点, 每个新的点是在前一个点的基础上, 横坐标加上当前样本的正例在总正例数中的占比, 纵坐标加上当前样本的负例在总负例数中的占比, 最终的终点一定是 (1, 1), 对这个曲线求面积, 即得到 AUC. 其物理意义也非常直观, 如果我们把负例都排在正例前面, 则曲线一定是先往上再往右, 得到的面积大于 0.5, 说明分类器效果比随机好, 最极端的情况就是所有负例都在正例前, 则曲线就是 (0, 0) -> (0, 1) -> (1, 1) 这样的形状, 面积为 1.0.

同样给一份 C 代码实现:

struct SampleNode {
  double predict_value;
  unsigned int pos_num;
  unsigned int neg_num;
};

int cmp(const void *a, const void *b)
{
   SampleNode *aa = (SampleNode *)a;
   SampleNode *bb = (SampleNode *)b;
   return(((aa->predict_value)-(bb->predict_value)>0)?1:-1);
}

double calcAuc(SampleNode samples[], int sample_num) {
  qsort(samples, sample_num, sizeof(SampleNode), cmp);

  // init all counters
  double sum_pos = 0;
  double sum_neg = 0;
  double new_neg = 0;
  double rp = 0;
  for (int i = 0; i < sample_num; ++i) {
    if (samples[i].neg_num >= 0) {
      new_neg += samples[i].neg_num;
    }

    if (samples[i].pos_num >= 0) {
      // calc as trapezium, not rectangle
      rp += samples[i].pos_num * (sum_neg + new_neg)/2;
      sum_pos += samples[i].pos_num;
    }
    sum_neg = new_neg;
  }

  return rp/(sum_pos*sum_neg);
}

分类器的一致性

如果分类器的概率结果就是最终结果序, 那 AUC 值基本可以当作最终效果来用. 但是实际应用中分类器的结果都要再做函数转换才是最终序, 则评估的时候需要将转换函数也带上去做 AUC 评估才行. 某些应用中这个转换函数是不确定的, 比如广告的价格随时会变, 推荐条目的重要性或收益可能也是另一个计算模型的结果. 在这种情况下, 如果我们可以保证分类器概率和实际概率一致, 让后续的转换函数拿到一个正确的输入, 那么在实际应用中才能达到最优性能.

为了评估分类器概率和实际概率的一致性, 引入 MAE (Mean Absolute Error, 平均绝对误差) 这个指标, 维基百科对应的词条是 Mean_absolute_error. 最终的计算方法很简单, 对样本 i, fi 是预估概率, yi 是实际概率, 则 i 上绝对误差是 ei, 累加求平均就是 MAE:

MAE 公式

MAE 的值域是 [0, +∞), 值越小说明分类器输出和实际值的一致性越好. 我个人认为如果 MAE 和实际概率一样大, 那这个分类器的波动效果也大到让预估近似随机了.

MAE 看起来和标准差有点像, 类似标准差和方差的关系, MAE 也有一个对应的 MSE (Mean Squared Error, 均方差?), 这个指标更多考虑的是极坏情况的影响, 计算比较麻烦, 一般用的也不多, 有兴趣的可以看维基百科上的词条 Mean_squared_error.

MAE 计算太简单, MSE 计算太纠结, 所以都不在这给出代码实现.

机器学习手记系列 1: Pearson 相关系数

Posted on by snoopy

系列说明

按合总指示, 给人人的机器学习小组写点科普性质的东西. 其实自己好像一直都没去系统的学过这些东西, 都是野路子乱搞, 这里把过去学的一点东西写出来, 记录一下, 班门弄斧, 欢迎拍砖.

自己接触到的机器学习, 几乎都是在用历史预估未来某事件发生的概率 (广告点击率, 推荐接受度, 等等).

将这个过程细化一下, 首先都是对历史样本提取特征, 将样本转换成用特征序列来描述, 将同类事件合并, 然后通过某种拟合方式去让特征带上合适的权重, 用于描述事件发生的概率, 最后对还未发生的同类事件, 同样将其转换成特征序列, 用学出来的权重转换成预估概率.

这里有两个关键问题, 一是特征选取, 二是拟合还原方法. 特征选取是为了将样本做合理拆分合并, 同质的才划分到一起, 不然就最后的预估还是随机猜. 拟合还原方法是保证在对数据做了合理拆分后, 能将特征的权重拟合到原数据上且能在预估时还原成概率.

问题

对怎么选特征, 似乎从来都没有好的普适性方法, 但是怎么验证选的特征靠不靠谱, 方法倒是挺多. 先抛开选特征的指导方向不说 (说也说不清), 如果我们选出了一类描述特征, 怎么验证其效果?

特征效果验证

最直接粗暴也是终极方案就是直接拿到线上去应用, 好就是好, 不好就是不好. 这是一句彻底的废话, 也是真理… 不过实际操作中很难真的去这么做, 一是如果要完成整个流程会比较耗时和麻烦, 二是没有那么多线上资源拿来实验, 三是如果实验不好带来的负面影响会非常大, 广告会损失收入, 推荐会严重影响用户体验. 所以如果线下没验证的心里有谱, 没人敢直接拍上去实验的, 老板也不会让乱来, 都是钱和能转换成钱的用户啊.

退回到离线验证上, 终极离线验证也还是拿机器学习的产出 (分类树, LR 模型, 或别的什么) 去评估一部分实验数据, 然后看对实验数据的预估结果是否和实验数据的实际表现一致. 这个还是存在耗时耗资源的问题, 后面再说, 先说简单的.

不管是分类树, 还是 LR 或别的 boosting 什么的, 都是希望能找到有区分度的特征, 能将未来不同的数据尽可能划开. 如果特征是一个 0/1 特征, 那数据就应该能明显被分成不一样的两份. 比如在豆瓣, “历史上关注过计算机类别书目的人” 是一个 0/1 特征, 如果拿这个特征来分拆人群, 并评估 “未来是否关注计算机类别书目”, 评估指标的 1 绝大部分都落在区分特征的 1 中, 那说明这是一个非常正相关的区分 (曾经干过某事的人会继续干另一件事), 效果很好, 反之拿去评估 “未来是否关注女性言情小说类别书目”, 很可能评估指标的 1 绝大部分都落在区分特征的 0 里, 那是非常负相关的区分 (曾经干过某事的人不会再干另一件特定的事), 效果也挺好, 但是如果是评估 “未来是否会关注武侠”, 评估指标的 1 是比较均匀的散布在区分特征的 0/1 里, 那就说明这个特征对该评估指标没有区分度, 还不如没有. (这些例子是随便拍脑袋写的, 不保证其正确性)

如果是一维连续特征, 则最后总特征总可以转换成一个一维向量 (连续值可以离散化成整数区间), 跟 0/1 特征一样, 比较这个特征的自变量取值向量和对应到评估数据上的取值向量的相关度就能判断效果好坏 (正相关或负相关都是好的). 一般最简单的是使用 Pearson (皮尔生) 乘积矩相关系数 r 来做是否线性相关的判断, 英文 wiki 上的条目 Pearson product-moment correlation coefficient 对该系数的含义和计算方法有比较详细的说明, 中文翻译比较杂, 百度百科上的是皮尔森相关系数, 微软的翻译是皮尔生相似度. 简要的说, pearson 相关系数是一个 [-1, 1] 之间的实数, 取值越接近 -1 表示特征值和评估值越负线性相关, 越接近 1 表示越正相关, 越接近 0 表示越不相关 (只是线性, 可能会有其他相关的关系).

还是拿豆瓣的例子说, 比如 “历史上关注过计算机类别书的数量” 作为一个人群划分特征, 那这维特征的自变量向量会是 <0, 1, 2, ...>, 为了取值方便, 将其截断到超过十本的也等于 10, 则向量变为 <0, 1, ..., 10>, 如果去评估 “继续关注计算机类别书的概率”, 这个概率取值可能是 <0.0, 0.1, ..., 1.0>, 则其 Pearson 相似度会是 1. (当然, 这个例子举的太假了点, 先这么着吧)

将问题化简为算特征取值和评估指标的 Pearson 相似度后需要做的工作就会少很多, 直接跑个 Map/Reduce 从 LOG 里提取下数据, 然后看看值的相关性就知道特征是否有区分度了, 没区分度的可以先不考虑 (或者将曲线相关的可能转变成线性关系, 再判断), 有区分度的才继续走更完整的离线验证, 加入分类树或概率模型和其他特征一起作用看效果, 如果还不错就上线实验.

微软的 Excel 里就带了 Pearson 相似度的计算公式, 可以很方便的拿来评估, 说明和用法请见微软帮助页面 PEARSON 函数. 如果要自己计算, 可以参考 wiki 的这个公式:

Pearson 相似度计算公式

C 的实现源码如下 (注意某些情况下可能会有计算精度丢失, 带来结果的不确定性)

double pearson_r(double x[], int x_n, double y[], int y_n) {
  if (x_n != y_n || x_n == 0) {
    return 0;
  }

  double n = (double)(x_n);
  double sum_x = 0;
  double sum_y = 0;
  double sum_x_sq = 0;
  double sum_y_sq = 0;
  double sum_x_by_y = 0;
  
  for (int i = 0; i < x_n; ++i) {
    sum_x += x[i];
    sum_y += y[i];
    sum_x_sq += x[i]*x[i];
    sum_y_sq += y[i]*y[i];
    sum_x_by_y += x[i]*y[i];
  }
  double res = n*sum_x_by_y - sum_x*sum_y;
  res /= sqrt(n*sum_x_sq - sum_x*sum_x);
  res /= sqrt(n*sum_y_sq - sum_y*sum_y);
  return res;
}

紧张起来

Posted on by snoopy

五一前调整了一段时间的作息, 本可以每天早上七点以前起来, 做个操活动下筋骨, 每天工作效率也还好. 五一后又变成了早上睡不醒, 更糟糕的是晚上又开始失眠. 印象中真正遭受失眠困扰只有 09 年在香港的某一段时间, 赶 paper, 想 idea, 做实验, 每天过的兢兢战战.

到人人也有半年了, 但是很多事情进展的不如想象的顺利, 有环境的因素, 很多时候也还是自己的推动力不够, 没能找到一种更合适的方法将自己和团队赶到一条能很 high 的狂奔向前的路上. 有时候总会把原因推到外部原因上去, 比如有依赖的什么没有怎样, 又有等合作的数据没有怎样. 有些东西必须自己去推, 有些事情, 虽然说也要放事情下去做, 让下面人成长起来, 这样大家都能过的更舒服, 但是总难找到好的平衡点.

紧张起来, 让自己绷紧点, 同时对别人也 tough 一点, 没有成果, 再 nice 也毫无意义.

Python 的对象模型到底是怎样的?

Posted on by snoopy

今天写个小工具, 中间调的欲仙欲死, 直接上图, 大家看看这个程序会输出啥? 环境是 Python 2.7.2, 某 Linux 发行版 (服务器, 我也不知道具体是啥, 可能是 CentOS)

我的理解是如果我的写法有问题, 那应该两个 print m1 的时候的结果都跟 print m2 一样, 要不两个结果应该都不一样, 所以我确认了 model_path 都正确赋值后, 就认为 model_dict 也都被正确赋值了. 但是调试的时候发现两个 model_dict 调用的结果居然一模一样, 然后带的 model_path 还不一致 (当然, 我中间做了很多别的操作, 一开始没验证两个 model_dict 里面的内容). 后面把 model_dict 的内容也打出来就傻眼了, 这俩为啥都一样呢? 就因为一个是字符串一个是 dict? 跑到万能的 PUZZLES 群去问了下, 立马有人说你这个初始化不是应该在 __init__ 里做才对么? 于是将代码改成这样就 OK 了:

后来跟 @runnery 和 @LeeMars 讨论了下, 终于明白是怎么回事了, 先上一张 @runnery 给我的解释图

按这个理解, 我的两次操作都是在操作类属性, 最后的输出应该都是 m2.reload() 后的值. 而实际上第一份代码的里, 两个实例初始化时, model_dict 和 model_path 都还是类属性, 而调用 reload() 的过程中, 我做了一个 self.model_path = path 的操作, 而正是这个操作, 让两个实例分别将 model_path 变成了实例属性, 而 model_dict, 对不起, 我从来没修改过他具体的指向, 做的 clear() 操作什么的都还是在原来的 dict 上在操作, 所以一直是类属性.

总结: 这就是一个坑, 对语言不熟的坑

杂而不精

Posted on by snoopy

今晚调模型调郁闷了, 发现没个顺手的工具确实不行, 于是把拖了很久, 本来指派给别人但一直没完成的 debug 工具给完成了大半.

很早写过一个 python 脚本, 在命令行下调用, 但是不方便输入和构造数据, 看起来也不是很方便, 但一直也有别的事情, 觉得这事优先级不高就一直搁着. 后来要做不同数据下的对比, 除了自己还是没人写这个, 于是把 python 脚本完善了下, 支持多输入, 多输出带对比, 还是没去写界面或数据构造. 再后来在做别的事情的时候, 顺便把这个 python 脚本也做了一次简单重构, 使其兼容线上配置, 逻辑也保持完全一致, 并将其作为一个 daemon, 用 php 写了个界面, 一堆参数可以简单的用 html 表单 (选择框, 下拉菜单什么的) 来生成, 默认值也好指定, 输出还是把原 python 输出到命令行的东西原封不动输出到网页, 但是不支持多输入. 最后就是今天实在忍不了土鳖的开两个窗口去调试对比 (顺带吐槽下其实是某从的显示器不够大, 开两个窗口并排放不开), 把那个 daemon 改的支持多输入, 并将输出做了一些简单的格式化, 还是裸文本但是看起来有条理多了, 并且把模型/数据/配置等支持在线重载, 免得换个数据就去 kill daemon 然后重启时又提示端口号还没释放.

晚上回来的时候看到汤永程在写他去参加天天向上的事, 说到语言学习, 就突然想回忆下, 自己到底一天都在用哪些语言, 好像我也会挺多, 但是都杂而不精. (前面那句话里两个语言指代不一样, 显然笨狗只会程序设计语言…) 按接触/学习的时间排序如下, 记录兼娱乐, 其中一些自己觉得好的书和资料给了链接, 希望对别人有帮助. 写完回头看, 怎么看都是一部扭曲的非主流码农成长史, 而且发现这都能当简历了 -.-|

PASCAL
– 第一个正式去学的语言, 高中玩 OI 竞赛时学的, 也仅仅用于竞赛而已
– 可以应对 03 年 NOIp 高中组级别的题, 没做过实用化工作, 竞赛中用过两年多, 现在应该忘的差不多了

C
– 大学入学前跟着去玩 ACM 开始去学, 一直到现在还在学, 大一作为必修课马马虎虎学过去了, 到大三大四时通读 C 程序设计语言 并完成所有例题和习题, 很薄的一本真的认真看完花了好久, 这本书真的非常赞, 后面就在工作中一直作为主力高级语言在用了
– 可以应对一般的 ACM 水题, 能独立完成计算机专业 C 语言大作业, 看过/实现过一些简单库函数, 结合 APUE (Unix 环境高级编程) 将其和 *nix 底层对接学习了下, 学习/实习/工作中将其混着一点点 C++ 用了几年, 参考别人的开源项目完成过一个 Online Judge 的内核, 这些年代码量加起来我猜应该够十万行了, 但是大部分还是在已有框架下写策略细节, 没做过大项目整体框架比较遗憾

C++
– 单独从 C 里列出来是想说明我真的不会 C++… 曾经在玩 ACM 的时候用过一点点 vector 什么的, 但是这种应该不叫去学 C++ 吧, 大四实习时因为工作需要时翻了下 C++ Primer Plus, 翻了几章后发现买错书了, 本来应该是买 C++ Primer 的… 刚好那段时间的实习也都在做偏策略的东西, 一直没去看工程细节, 结果就一直不会工程了
– 能看懂简单的 C++ 代码, 能将简单的 C++ 写成 C, 剩下的, 我真的不会 C++…

HTML
– 忘了啥时候开始学的了, 反正成天看网页, 看人源代码, 抄抄改改, 从学校图书馆借过很土鳖的类似 xx 天入门的书学过下后就再没系统的学习过, 倒是折腾过很多地方, WHUACM 那现在还有不少页面是我写的或是基于我写的改的, 后来做 RA 和工作时发现很多需要可视化的结果还是用 HTML 来的爽, 零零碎碎写过一些在行家眼里看来就是三岁小孩折腾的小站
– 能看懂简单的 HTML 框架, 能写简单的 HTML, 比如 yewen.us 这样的 (blog 是 WordPress, 特此说明)

CSS
– 这算语言么? 经历/水平同 HTML

Java
– 大学的选修课, 也仅仅到大学的选修课, 考试过后就没再写过了, 买过 Thinking in Java 但是从来没看完过
– 能完成几年前 Java 1.4 时代的课程大作业水平, 仅此而已, 我真的也不会 Java (猎头问你是 Java 程序员还是 C++ 程序员的时候是最伤人的时候, 我回答都不会后对面口气立马就变的很鄙夷, 连猎头都 bs… 这码农当的太失败了)

JSP
– 本来是想去接手第一版的 woj 然后做第二版的, 后来还没开始正儿八经学就发现不如推倒换 php 重来
– 不会, 曾经还会在 Eclipse 里开个新工程的, 也仅仅会开个新工程, 现在啥也不会了

Linux Shell
– ACM 比赛会用到, 同时本着 “一个合格的计算机专业学生应该会 Linux” 这样的想法自己去折腾过, 选修课上迷迷糊糊学过, 实习的时候开始天天用, 一直都在抄别人的来改, 到现在还是三脚猫功夫, 一直没去找系统学习的方法, 也懒得去系统的学, 觉得是工具用的时候能捡起来就行了, 目前计划在可预见的未来系统的去学学 Shell 脚本学习指南
– 日常工作使用语言, 能写简单的控制脚本, 有若干脚本还在线上系统应用

awk
– 第一次实习的时候因工作关系开始用, 也是从那个时候开始领悟 Linux 的设计哲学, 就是用一堆合适的工具去干一件超酷的事情, 而不要想着为了做一件大事情而去发明一个万能工具 (所以我不是 Emacs 党么?), 一直也还是抄抄改改, 没去系统去学, 有 sed 与 awk 这本书, 但还是只想当工具书用不想系统去学
– 日常工作使用的简单脚本, 能写比较简单的文件级 awk

sed
– 同 awk, 用的更少, 几乎忘光了, 用的时候查 Google/Baidu/参考书

C#
– 某年为了贪一次微软夏令营的机会答应了别人的坑蒙拐骗去当武大微软技术俱乐部主席 (结果那年居然没办夏令营, 真是… 动机不纯必无善果), 一看自己会都跟微软特色没关系, 还是学点啥吧. 瞄上 C#, 从 MSDN 上下了个视频教程对着写完过, 然后, 然后就没有然后了. 在 MSRA 的时候修改的那个原型到底用的 C# 还是 C++ 都忘记了
– 不会, 但是真心觉得比 Java 优美, 特别是现在还在持续改进中

Python
– 好奇心强显然会对各种东西感兴趣, 从研究生开始将 python 作为主力思考/原型实现语言, 写起来确实快, 而且喜欢用缩进来控制语法, 从根本上杜绝了把代码写的很难看或读到很难看的代码 (当然, 有人炫技也还是可以很变态的…). 从 A Byte of Python (中文版) 入门, 再通过 Dive into Python (中文版) 略提高, 再又是抄抄改改了, 成天拿来做系统原型和算法/策略调研和实现, 压根没做 Web 框架什么的 (Django 什么的继续不会). 手头有一本 Python Cookbook, 无奈此书奇技淫巧过多, 只敢将其当工具书偶尔翻看
– 日常工作使用的主力语言, 若干自己的小系统, 若干系统原型 (还有一些一直懒得改和没人改的在线上用)

PHP
– 既然会 HTML 了总该会门动态语言来做交互吧, JSP 看起来就很重那就玩比较好上手的 PHP 咯, 又是一门通过抄抄改改入门的语言, 到现在还是抄抄改改的水平, 手里常备PHP官方手册做参考, 反正也不是项目必须语言, 做点调试工具什么的还是够了
– 菜鸟入门水平, 有一些小原型和调试工具

JavaScript
– 没学过, 不会, 会抄简单的样例连蒙带猜的改, 还是比如 yewen.us 的导航栏效果, 比如会知道怎么改参数用 HighCharts 的简单功能

Perl
– 一直觉得 Perl 是很神奇很牛逼的语言, 但是由于此语言装逼者众多, 且语言本身设计初衷很大一部分就是为了装逼, 而且本来很多不想装逼的因为语言特性又很容易将代码写的巨扭曲, 所以一直没能像别的那样连蒙带猜拆拆改改的去入门乃至提高. 为了使用和改动迪生大神的某 perl 脚本时下决心去学学, 去年换工作前利用平常和周末不加班省出来的时间完整的学了一遍 Perl 语言入门 (小骆驼书), 感觉确实很精妙很方便, 但一直没实际用过, 有需要的时候大部分时间都顺手用 python 解决了, 现在恐怕又忘光了, 但是要捡起来应该比较快, 但要估计这辈子都不打算达到装逼级的熟悉和精通了, 打酱油的 3P 党就好 (Perl/PHP/Python)
– 系统入门过的语言, 从来没实战过的语言

果然都是杂而不精, 同笨狗一贯性格, 甚至现在都还有兴趣去看看 Go 和 Lua, 前者是因为 Google 和设计者名身在外想看看是不是能从中看出点什么未来趋势, 同时悟点以前没悟出来的本质性东西, 后者是听说游戏领域用的很多 (这个应该是受云风影响), 而且很方便实现 robots 做模拟测试, 想看看以后工作中是不是能用的上 (实在不知道 robots 翻译成什么好, 总感觉用 机器人 这个词怪怪的). 如果闲的蛋疼, 还想去看看 ruby 和 lisp, 一个是经常拿来跟 python 对比的语言, 自己一直用 python, 也想看看他山之石, 另一个好歹也活了这么久, 是跟计算机科学和人工智能一起萌芽发展起来的东西, 膜拜下也好, 而且随着多核架构和并行架构越来越普遍, 据说会更有优势?

不过, 要专注, 要做事, 要带人, 而且参考一贯的光说不练的风格, 估计也就这样了… 偶尔打酱油插科打诨还可以.

有些笔试题的存在意义就是搞笑么?

Posted on by snoopy

昨天有个以前一起玩 ACM 的队友跟我说个题, 说是前几天腾讯实习生招聘的笔试题之一, 原文如下

已知a[0],a[1]…a[n-1]
现在要构造b[0],b[1]…b[n-1]
其中 b[i]=a[0]*a[1]*….a[n-1]/a[i]
要求，不能用除法，不能使用其他任何存储变量，除了循环变量i,j之类的
要求O(1)的空间复杂度，O(n)的时间复杂度

关键是不能用除法

看到这题后的第一反应是这特么不会爆类型么? double 也经不起这么搞吧. 然后就冷静下来想怎么解决, 不能用除法就避开那个除法操作咯, 把 b[i] 的推导公式换成 a[0]*…*a[i-1]*a[i+1]*…*a[n-1] 就是了, 一看就像个 DP. 推了下后写了这么个代码 (假设所有数都是 int 且不爆类型大小)

// 先构造一遍, 使得 b[i] = a[0]*...*a[i-1]
b[0] = 1;
for (int i = 1; i < n; ++i) {
  b[i] = b[i-1]*a[i-1];
}

// 逆序, 使得遍历到 b[i] 时, sum = a[i+1]*...*a[n-1]
//这时候 b[i]*sum = a[0]*...*a[n-1]/a[i]
int sum = 1;
for (int i = n-1; i >= 0; --i) {
  b[i] *= sum;
  sum *= a[i];
}

然后被提醒说 sum 这个变量也不能有, 好像原文中是说了不能用其他存储变量… 但是这不还是 O(1) 的空间复杂度么, 腾讯好像经常喜欢搞这种无聊的要求 (卡一两个变量), 于是当场就怒了

叶文/Snoopy阿排 20:41:49
那把他写到循环里好了… -.-|
叶文/Snoopy阿排 20:42:32
老实说, 这个题出的很烂…
叶文/Snoopy阿排 20:42:36
烂的无与伦比
** 20:43:05
哈哈
叶文/Snoopy阿排 20:43:15
首先, 这种奇技淫巧没有任何意义
其次, 连乘更大的问题是爆数据类型…
** 20:44:41
是啊
** 20:44:51
关键一点就是没有任何意义
叶文/Snoopy阿排 20:45:41
而且, 要真抠细节, 他没说不能修改 a 的值, 我在做逆序的时候把 sum 换成 a[] 就行了

果然改 a 数组的值就达到目的了? 好像是? 这样有意思么?

最后, 真心求既不使用多余变量, 且不修改 a 的值的做法.

档案户口迁移记

Posted on by snoopy

去年曾答应某人写这么一篇教程, 后来想想这样对度娘太不厚道, 而且那个朋友最后也没走, 所以搁下. 不过很遗憾今年很多前同事也走了, 问起来似乎这方面有经验的就是我了, 那就写个教程吧. 以下内容适用于户口/档案由度娘委托海淀人才保管, 且是市内迁移到其他人才机构托管的情况, 其他迁移请查阅相关资料. 由于某狗没入党, 所以没有党组关系迁移的手续, 如果是党员的请注意党组关系要怎么转.

离职流程参考度娘内网, 有很详细的流程, 按图走就行了. 记得工作交接清楚, 能解除的报警短信都解了, 不要像我, 隔三差五还能收到报警短信, 都不知道找谁把那个报警去掉.

档案户口比较烦, 一步一步写.

1. 新单位调档函 (新单位办理)

到新单位要一份调档函, 一般都是一份打印好了直接填个名字就行的表, 并确认新单位的户口/档案托管机构是哪里, 去看看户口/档案调入须知, 比如朝阳区中智的集体户口迁入迁出.

2. 档案户口迁出申请 (度娘处办理)

度娘的档案存在海淀人才, 按海淀人才的档案调入调出页面上的提示, 打印调出表, 填好, 找直接经理签字, 找 HR 盖章. (我上次去的时候 HR 在大厦的 F1-CE 区集中办公)

一定要注意的是, 我们的档案里没有定级表 (研究生) 或见习考核鉴定表 (本科生), 其实已经成了死档, 无法调入调出, 还需要去海淀人才下载中心下载定级表 (研究生用) 或见习考核鉴定表 (本科生用), 跟档案调出表一样, 自己填好个人信息部分, 找直接经理签字, 找 HR 盖章 (什么定级工资啥的都空着, 海淀人才会帮你填, 日期最好也空着找海淀人才填).

离职的时候在 HR 那要求开一份档案/户口转出介绍信, 盖章.

3. 档案户口迁出办理 (海淀人才处办理)

从软件园广场坐 982 到四季青桥北, 下车后往回走小几十米, 路西就是海淀人才服务大厅, 进门, 右拐上二楼, 拿一个档案的号和一个户口的号 (似乎是一个 2 开头一个 3 开头).

办户口那人一般很少, 直接去说要办市内迁移, 他要什么材料就给他什么材料, 完了签字登记, 户口页原件到手.

档案排队人一般很多, 先在拿号那的收款处查下自己的档案托管费是否结清, 度娘似乎是半年一结, 所以一般会欠海淀人才几个月的托管费, 自己补上吧, 如果新单位给报销, 记得要发票. 拿着新单位调函, 档案转出表, 交费单, 定级表或鉴定表, 到办档案的窗口办理档案迁出, 他查好后会让你到另一个没有叫号的窗口去排队等拿资料, 等档案袋调出来, 把你该塞进去的塞进去, 一封口, 档案原件到手.

4. 档案户口迁入办理 (新单位委托的人才机构)

先看看要迁入地的要求, 要复印证件就复印证件, 要填表就填表. 户口还要求有无犯罪记录证明, 这个可以找四季青派出所开, 也可以在自己租房所在地找片警开, 我当时是没时间去四季青派出所, 就找社区里的片警开的.

这个不同的地方有不同的要求, 一般按其网站上的说明来就行了, 没什么要注意的坑, 不行的话问问新单位的 HR, 或打电话问问新委托机构, 而且办理过程一般都很快. (顺带吐槽下, 海淀人才的电话非办公时间没人接, 办公时间根本打不进去, 早上九点卡点打才比较靠谱)

5. 社保?

只要还在北京市, 社保什么都是无缝迁移, 可以不管. 但是缴纳方式可能要注意, 我就是新单位交社保交挂了才想起来要去办户口/档案迁移的.

我毕业时户口还是外地, 所以社保一直按 外埠城镇 缴纳, 到新单位时想户口都落好了, 应该是 本埠城镇 了吧, 结果 HR 告诉我社保交不上去, 还得按原来的交, 然后自己改. (两者缴纳的比例是完全一样的, 2012 年开始单位缴纳比例也完全一样了, 不知道还有什么区别, 我猜改成本埠的要靠谱点)

怎么改直接问新单位的 HR, 我得到的信息是提供: a) 身份证双面复印件 (复印在一张 A4 纸上); b) 户口本户主页 (显示户别类型: 本市城镇页) 和本人页的复印件 (复印在一张 A4 纸上), 后面的事情让 HR 办. 户口那个复印件必须要去托管的人才机构办 (办户口迁移时过自己手的只有本人页的原件), 而且建议是等新委托的机构落户完成后去办理. (这个我还没办完, 此流程仅供参考)

—-伤感的分割线—-

曾经一起追梦的少年, 终究也还是散落四方. 不同于毕业那几天内就人走楼空, 周围熟悉的人慢慢的一个一个少掉这才更让人难过. 祝大家一切都好, 保持联系, 坚持最初的梦想.

互联网企业的 x 文化?

Posted on by snoopy

在去年的年度盘点里有提到一些公司文化差异的问题, 当时想说的是这个世界越来越 x 的文化导向, 怎么就变这样了呢? 民间口语中略有轻浮个人觉得还能接受, 可以用尚未开化完全或民风彪悍等理由解释. 但是在一些公众场合, 特别是有影响力的公众场合, 还是觉得很难忍受, 过 x 的文化在很多地方会被认定为性骚扰才对?

这个问题最早是看 CCAV 某年的内部年会 东方红时空 时想到的, 里面有不少荤段子, 具体细节现在回忆不起来了. 当时看到平常很严肃那些主持人什么的也这么恶搞和低俗, 有点震撼. 不过要说那个片子留下了什么, 最有影响力的应该是电影剪接恶搞的兴起 (胡戈早期的剪接作品都是如此, 一个馒头引发的血案和讲春运的那个), 以及敬一丹还是谁说的一句 “在这样的夜晚, 除了创造人类, 我们还有什么追求”. 但是跟后面的那些比起来, 这个又算很纯洁的了.

后面看到网络上一些对阿里系的传闻, 觉得明显过头了, 比如知乎上在淘宝的工作挑战这个问题中提到的男女关系, 这里面的内容我向一些阿里的员工求证过, 无法证实, 但是从交谈来看, 很多无法证伪不那么夸张的事情似乎也是事实, 甚至都算公司文化了. 另一件很震撼的事是 @Fenng 曾经在新浪微博上转过一个淘宝新人培训时跳恰恰舞的图, 但他转的那个原微博已经被删, 只找到这张图, 搜 “百淘 新人” 能找到不少淘宝人的辟谣, 结合人人奥斯卡上类似的那一段, 应该是谣言. 去年冬天跟一去了淘宝的大学同学聚时也聊了下这方面的话题, 感觉阿里在那方面的企业文化确实是明显超过我的底线了, 淫而不荡, 这个太难了, 在网络上见过太多说着说着就成真的事了. 个人认为之所以阿里系会这样, 是因为阿里是一个销售导向的企业, 当今社会很多生意和黄赌毒都有说不清道不明的关系, 那销售等对外团队中这种文化就比较盛行, 继而带的整个公司都是这样. 由于这个文化冲突, 找实习, 毕业找工作, 换工作时, 阿里系都是被我直接忽略的对象.

到人人后只是觉得这边的某些文化更本土化一些, 连加入的第一个群名字都叫 “土俗骚”, 日常也有一些比较三俗的事, 但是整体还好, 不会过. 在人人奥斯卡上是被小震撼了把, 虽然以前也听说过会很黄很暴力, 但是一看这名字 基情穿越, 再结合下内容, 确实也还是有点过. 听闻销售那边会比较狠, 技术方向会稍微好一点.

回想下以前呆过的那些地方, 似乎都比较保守, 外企对这个问题都很敏感, 毕竟性骚扰是很严重的问题. 百度也挺保守的, 最多就是很熟的小圈子内闷骚下. 是说这些地方的大部分人以前在学校还是比较传统的乖宝宝, 所以比较正派?

不管是假正经还是真正派, 希望自己能一直光明向前, 言行一致. 不抽烟不喝酒, 只混技术圈, 远离人情世故, 会丢掉一些东西损失一些朋友和感情, 但是留下的会是更经得起考验的朋友吧. 不抽烟是因为家里没人抽烟, 自己也没兴趣, 对身体也不好, 不喝酒是因为酒精过敏 (海鲜过敏一般认为是个悲剧, 酒精过敏我看来还算好事了), 只混技术圈是因为不会人情世故不会说话, 出去绝对被各种拍死. 似乎杜月笙还谁说过, 如果一个男人不抽烟不喝酒, 那还有什么靠得住的 (大意如此), 我说是因为那年代没别什么能爱好了吧, 现在随便找个爱好就各种耗时烧包了.