我与算法的缘分

六年前，我完全不知道算法是什么东西。六年后，我看到算法就两眼放光。六年的时间让我从算法小菜鸟蜕变成算法爱好者。

大一上学期，我对算法一点概念都没有，当时老师让我们用伪代码写算法，我基本上都是从网上找答案或者直接空着不写。给我印象最深的一个算法是计算两个分数相加，其中涉及求最大公约数，用的是辗转相除法。那时觉得这个算法很难懂，现在回首再看时，觉得这个算法还是很简单的。大一下学期，听到算法和数据结构对程序员是如何如何重要的传言，就抱着《零基础学算法》，啃哧啃哧啃了大半个学期也只啃完了前几章。那个学期我学会了二分查找算法，了解了贪心算法，递归算法，分治算法的基本原理。最重要的是我第一次学会了一种编程语言，C。说到学C的经历，我特别特别感谢一个人，我的师傅。我是在一个算法讨论群里认识师傅的，那时我傻傻呼呼的问scanf是什么东西，所有人都笑而不答，只有师傅耐心的回答我是输入的意思。之后，我在C上遇到不懂的就问师傅，结果一个月不到就把那本C语言书啃完了，并练手写了一堆小程序。期间，师傅还给我灌输了代码规范的理念，让我受益匪浅。

大二，师傅又给我推荐ACM群，鼓励我去hdu网站上刷题。我在acm.hdu网站上从最简单的算法题A+B做起，然后就迷上了它，每天下课都去网站做题，不会的就去ACM群里，与来自不同大学的学生讨论。周末从早上起床一直编代码到睡觉，有时觉得编程的人是孤独的，现在回想起那段岁月，都觉得心酸，但当时真的很疯狂很快乐，能做自己喜欢的事是最幸福的。师傅还给了我一张他AC掉的题目列表，让我从容易的题目上手。他比我先刷掉200多题目，我在后面不停地追赶他，他刷掉400多个就停了。我在大二的寒假终于在AC掉的题目数目上超过了师傅，当时还得意洋洋地把这件事告诉了师傅，就像一个小孩考试考了高分，然后眼巴巴地等着大人夸奖自己。ACM刷题经历提高了我写代码的能力和逻辑推理能力，让我对算法设计产生了浓厚的兴趣。大二这一年，我刷过的题目类型有动态规划，贪心算法，数论算法，组合算法，字符串处理，图算法，树算法等等。我对基础算法和数据结构有了一定了解，并写了很多小程序。

大三，我和另一个同学跟着老师做项目，研究蚁群算法在TSP问题中的应用。我先把Marco Dorigo写的书粗读了一遍，了解了一下蚁群算法的原理、信息素的概念和轮盘算法，启发式算法的基本思想，然后按书中的算法步骤把算法实现了。我们当时实现5种蚁群算法，包括AS基本蚁群算法，EAS精华蚁群，ASrank基于排列的蚂蚁系统，MMAS最大最小蚂蚁系统，ACS蚁群系统。

大学前三年都是在学算法，而且没有系统地看过基础理论知识。大四，我认认真真地读完《算法导论》，看完《组合数学》，《数论》，《图论》的北师大视频，读完厚厚一本《离散数学》的经典书籍。再回首看以前的题目，感觉过去很多模糊不清的地方都豁然开朗起来。大四这一年给我留下了太多的回忆，被计算所顺利录取，去图书馆阅读大量书籍，生病半年，父母挚友陪我到处玩，厌学，考试差点考挂了，第一次成功地改进了外排算法，第一次写博客，第一次参加ACM竞赛，第一次在论坛给大家培训ACM……海量浮点数的外排算法涉及到败者树，基数排序，成块I/O等等。我设计并实现的外部排序软件非常快，主要改进点是我自创了一套编码和解码技术，减少了文本中的字符串数字和计算机中的二级制数字转换所需的时间，并利用了单批数据排序后相邻两个数之间的冗余信息。

研一，我了解并实践了推荐算法和搜索引擎。我对推荐算法、机器学习的了解主要源于天猫推荐算法比赛。第一赛季时，主要是理解业务，用一些规则进行筛选，比如最畅销的品牌，最近点击，周期购买等等，使用语言为C++。第二赛季前两周，也是用一些规则进行筛选，使用语言为SQL。后两周使用随机森林建模，共二十几个特征，分数一路飙升，当了一天的第一，第一个月结束时排第四，被邀请到杭州参加研讨会。那两周，我和队友了解了MapReduce编程框架，数据分析基础（折线图，散点图，直方图，相关系数等等），特征选择方法，采样方法，构建训练预测验证数据集，各种模型特点（逻辑回归，随机森林），尝试分组建模，各种去噪方法。后面两个月，我们还尝试了归一化，GBDT模型，曲线拟合，后验概率，模型融合等方法。一个学期下来，我对推荐算法和机器学习的基础知识有了初步的认识。另外，我研究的方向是生物信息学，主攻蛋白质搜索引擎。研一，我参考师兄的毕业论文，自己实现了一个蛋白质搜索引擎，掌握了倒排索引技术和核函数打分技术等。研一主要是基础课程的学习，印象最深的三门课是统计学，随机算法，生物信息学算法三门课。从中我了解到假设检验，随机游走，隐马尔科夫等知识。我通过阅读论文，自己动手实现了个半隐马尔科夫算法，解决的是第三类问题，学习问题，目的是调整模型参数，涉及Baum-Welch算法。

研二，进入实验室，上半个学期主要是接手软件。我接手了两个大不相同的蛋白质搜索引擎，每个引擎的核心代码大约几万行。因为两个软件都是刚写完不久，所以我在阅读代码和测试软件时，发现了不少bug，改得我头都大了。不过从中，我也学到不少东西。最重要的就是索引技术，我们组的索引技术种类繁多，各有各的优势，组合起来非常厉害。比如在蛋白质搜索领域，用后缀数组来构造索引就比普通的倒排索引快得多。另外，我还学习了迭代式的半监督学习算法。1月份的时候参加智能交通算法大赛，用Java实现了深度优先遍历算法，尝试了一些简单的流量控制策略，不过进第二赛季之后就没怎么弄了，听说第一名用的是强化学习算法。研二下学期，也就是今年，我的主要任务是优化蛋白质搜索引擎，完胜前一个版本。之前两个月主要做数据分析，修改原软件的bug，顺便学了pandas数据分析工具。后两个月就是各种尝试，基本流程就是分析数据->修改算法->测评->分析数据->修改算法->测评……

总结一下，学习算法可以沿袭先博后渊的套路。

1、了解《算法导论》里的基础算法，HDOJ上刷题200+或者LeetCode上刷题100+或者在其他OJ上刷掉一定数目的题目，找一下感觉。

2、认真学习一段时间的数学知识，特别是离散数学，强推荐《组合数学》，《数论》，《图论》三套北师大视频。

3、自己动手实现一个”高级“算法去解决实际应用。比如用蚁群算法解决TSP问题，优化外部排序程序，自己写一个简单的搜索引擎等等。这一步能培养一个人的科研能力，能让人长时间专注于一个算法，而不是像第一步那样全面撒网。

4、了解机器学习算法。无论是推荐引擎还是搜索引擎，都会涉及机器学习算法。了解回归，分类问题的基础算法，来一个问题，大致知道它是属于哪类问题。比如预测用户下个月是否购买某商品，可以将其划为分类问题，成绩排名预测可以将其划为排名问题，使用learning to rank方法求解，资金流入流出预测属于回归问题或时间序列预测问题。了解一些常用的线性模型，非线性模型。

5、深度研究一种算法。

文章首发于我的CSDN博客。

ps：研二结束的那年暑假，CSDN举办了一个征文活动，我的这篇文章有幸榜上有名，获得了一本技术书——《算法的乐趣》。