看着网络上各路牛人的年末总结，也想跟风自己来写一个， 只可惜拖的时间有点长，到现在才开始发表。

2012年对我来说绝对是不一样的一年，求职，面试，外推，实习， 以前对我来说很遥远的事情在这一年真真切切的发生。 有成功，也有失败，有欢笑，也有泪水，有面临抉择时的犹豫不决， 也有选择之后的淡定从容。这些经历，大多是艰辛的， 却没有将我击垮，能让自己觉得人生的充实。世界末日都照样过了， 还有什么挺不过呢？

在学习方面，2012年学习了很多新技术，新的语言， 对于算法，也有了更深入的理解。总的来说，还是广度有余，深度不足。 多多接触一些新的东西当然是有必要的，无论是对于开阔视野还是为了选择一个自己感兴趣的方向， 可是一个人必须要有所专长，在一个方面成为专家，这样才能体现个人的价值， 我在这方面仍然有所欠缺，希望在未来几年能够再某一个方面深入研究下去。 为什么是几年，因为我觉得有所建树，必须经过几年的积累。

在其他方面，相对来说就做得太少了一点，生活显得略微单调了一些。 空闲时间除了打打球，打打dota，似乎就没有干过别的什么事。更让我觉得愧疚的事， 很少看专业方面的其他书，思考的方式也越来越朝着计算机那个非0即1的方向去转了。 现在的情商好像是在下降，在2013年中一定要强迫自己多读书，多读与专业无关的书籍。

今年最好用的工具还是微博，在这上面可以很好地打发时间， 同时可以获取很多很有意思的信息。虽然说能学到的东西很少， 但它确实能很大程度地开阔视野，你能了解到很多你在现实生活中很难碰到的一些人和事。 喜欢微博，喜欢它带给我的快节奏信息。

今年最深的几点感触：

1. 在面临选择时，不要过分地去权衡利弊，在做出选择之后坚定地超前走才是最重要的。
2. 不要固执地去争论一个观点的正确性，这并不是一个非黑即白的世界
3. 严于律己，宽以待人
4. 多看书，多思考，思考和学习一个都不能落下
5. 珍惜别人给自己的每一条建议

2013 To-Do-List:

1. 多看书，多感受生活，开阔自己的胸襟
2. 学习一门新的编程语言，可能是go或者erlang
3. 学完完有关数据挖掘的基础知识
4. 为github上的一个库提交代码

祝愿我的亲人和朋友身体健康，考研的同学考上好的学校， 工作的同学工作顺心。

广度优先遍历

对于广度优先遍历，在每次遍历时，都试图把同一个级别的所有节点先遍历， 再遍历下一个级别的节点。它的实现方式是通过一个队列保存需要去遍历的节点， 在每次遍历到一个节点时，都把它的邻接节点放入队列（如果这个节点没有被遍历过的话）等待着被遍历， 这样能保证更深层次的节点会遍历在它的任何邻接节点的后面，因为它的邻接节点更先进入队列。

广度优先遍历可以用来求解无权图中的单源最短路径问题， 对于节点s，在它上面执行一次广度优先遍历就能求出各个节点和s相距的节点数， 这也就是它们到达节点s所需的距离。对于广度优先遍历， 算法首先会发现和s距离为k的所有节点，然后再去发现和s距离为k+1的节点。 这其实和Dijkstra算法是采用同样的思想，先找出和s距离更近的节点， 在这基础上再找出更远的节点，因为这样的话当确定好了更远节点的路径时， 就不需要反过来再去修改更近节点的路径，因为通过更远节点的路径肯定没有先前的那条路径好。

深度优先遍历

深度优先遍历与广度优先遍历不一样，在遍历到每一个节点时，尽量往更深节点去遍历， 遍历完之后再考虑同一个级别的节点。它的实现方式不需要队列， 直接通过递归函数就可以完成这个步骤。每次遍历到一个节点时，先把当前的节点设为已经遍历过， 然后在它的邻接节点上执行递归遍历的函数（没有遍历过的邻接节点）。如果对整个图进行深度优先遍历， 首先会选定一个节点，然后在它上面执行深度优先遍历，如果遍历到了所有节点就停止， 否则选择另一个没有遍历到的节点重复这个过程直至所有的节点都遍历完。在深度优先搜索的过程中， 会形成一棵棵以挑选出的节点为根的深度优先树组成的深度优先搜索森林。

在深度优先遍历遍历到每一个节点时，可以利用一个计数器记录遍历节点开始时的时间和结束时的时间， 依据这个时间来确定节点遍历的相对顺序。设节点v遍历的开始时间为d[v]，结束时间为f[v]， 那么时间区间[d[v], f[v]]就代表了这个节点处在遍历过程中的时间，更具体的说， 是节点处在递归函数的栈中的时间。因此对于任何节点u, v， [d[v], f[v]]和[d[u]， f[u]]只能是不相交或者是一个包含另一个。 （通过栈可能更好理解一点）

利用这样的计数器，可以完成对图的很多操作，比如说拓扑排序和有向图的连通性检查。

贪心算法

动态规划是一种解决问题的通用方法， 在求解最优化问题的时候， 动态规划能够综合考虑到各种情况然后做出最优的选择。 可是，对于一些特殊的问题， 在从子问题中做出选择时，可以不用考虑所有的子问题， 而只需要考虑一个子问题， 因为选择这个子问题一定可以达到一个最优解， 在这种情况下，就可以采用贪心算法来解决。 贪心算法的好处在于，不需要考虑所有的子问题， 只需要考虑一种情况，这时求解的子问题的数目就减少了， 同时，可以采用一种自顶向下的方法解决问题， 逐步地把问题转化为更小的子问题，直到可以轻易解决。

从动态规划到贪心

书上给出了一个这样的例子来说明从动态规划算法转化到贪心算法。

有n个活动组成集合$S = \{a_1, a_2, ..., a_n\}$，它们需要占用同一个资源， 这个资源在同一个时间只能被一个活动占用，每一个活动$a_i$使用资源的起始时间和结束时间分别为 $s_n, f_n$，如果区间$[s_i, f_i)$与区间$[s_j, f_j)$不重叠， 就称活动$a_i$与活动$a_j$是兼容的，求S的一个由互相兼容的活动组成的最大子集， 假设活动已经按结束时间排好序。

对于这个问题，可以定义如下子问题$S_{ij}$， 表示从S的子集$S_{ij}$中得到的最大兼容子集， 其中$S_{ij} = \{ a_k \in S: s_k \geq f_i and f_k < s_j \}$， 也就是说，$S_{ij}$是由所有在$a_i$结束之后开始， 在$a_j$开始之前结束的活动组成的集合。 通过定义这样一个子问题， 就可以很容易地得出如下递推公式，

从而利用动态规划解决这个问题。

然而，动态规划并不是一个最优的解法， 因为要求解的子问题的个数为$O(n^2)$个， 而且求解每个子问题时选择的个数也有$O(n)$个， 这就导致了通过动态规划求解问题所需的复杂度为$O(n^3)$。

如果采用贪心的算法，每次通过选取$S_{ij}$中具有最早结束时间的活动$a_m$作为划分元素的话， 那么就可以通过

得到一个最优的解，而不用考虑其它元素作为划分元素时的子问题。

红黑树的扩充

由于红黑树这种结构很好的平衡性（树的高度不会很高）， 对于动态变化的集合插入，查找，删除等操作的复杂度都比较低， 通过给它的节点增加一些其他的属性， 能够得到一些在特定情况下很有用的数据结构。

扩充数据结构的四个步骤

1. 选择基础的数据结构
2. 确定需要给数据结构添加哪些信息， 这些信息可能被添加到每个节点中，也可能被添加作为整体数据结构的性质
3. 验证在数据结构的基本操作的过程中，这些信息可以被有效的维护， 这里的有效是指不会因为维护这些信息增加基础操作的复杂度
4. 利用这些信息提供一些有用的操作

通过扩充红黑树得到顺序统计

通过给红黑树的每一个节点x附加属性size[x]， 表示以x为根的子树的节点个数， 可以通过递归确定一棵红黑树的第i小关键字的元素。 由于包含n个元素的红黑树的高度为$O(\lg n)$，每次递归高度都会下降一层， 所以查找第i小关键字的时间复杂度为$O(\lg n)$。

在第9章中，给出了获取n个元素的数组中第i个元素的$\Theta(n)$的算法， 而一个包含n个元素的数组如果是有序的话，那么获取第i个元素的复杂度是$O(1)$。 但是这种扩充的数据结构的好处在于它的动态性，它的插入和删除的时间复杂度也是$O(\lg n)$， 而一个有序数组的插入和删除的复杂度是$O(n)$。

通过扩充红黑树得到区间树

在区间树中，每一个节点x包含了一段区间int[x]，同时包含了一个max[x]， 表示以x为根的子树中所有区间的右端点的最大值，同时每一个节点的key[x] = low[int[x]]， 也就是说是把每一个节点所包含区间的左端点作为key。

区间树使得查找整个红黑树中与某一个区间i重合的区间变得十分容易， 可以如下递归实现：

1. 如果当前节点为空，返回空节点
2. 如果区间i与当前节点的区间重合，返回当前节点
3. 如果区间i的左端点小于当前节点左儿子的max，递归查找左子树
4. 否则递归查找右子树

情况1，2很自然，情况4也比较好理解， 因为如果i的左端点大于左儿子的max，它就大于那么对于左子树中所有节点的右端点， 左子树中一定不存在和区间i重合区间。情况3需要一定的思考， 因为如果i的左端点小于当前节点左儿子的max，并不能保证它一定不会与右子树中的区间重合， 所以如果只是递归查找左子树，如果左子树中有区间和i重合，那么能够返回正确结果 （因为只需要找到一个和i重合的区间就可以），如果左子树中没有区间与i重合， 那右子树中可能会有区间与i重合，导致没有返回正确的结果。情况是这样的吗？

不是这样的，下面可以证明在情况3时如果左子树中没有找到与i重合的区间， 那么在右子树中也一定不存在和i重合的区间。

假设左儿子的max来自于high[j]（也就是说，是左子树中区间j的右端点)， 那么一定有

否则区间i和j重合，对于右子树中的任意区间k，一定有

所以k与i不重合。

动态规划

散列表中碰撞的解决

由于散列表的元素个数小于关键字的取值集合U, 因此会有两个不同的关键字映射到散列表的同一个槽上， 这时就发生了碰撞。发生了碰撞时， 书上给出了两种方法来解决， 而且保证此时的散列表平均情况下的查找复杂度是O(1)。

链接法

在链接法中，关键字映射到同一个槽上的元素通过一个链表来保存， 此时散列表T[0..m-1]的任意元素T[j]是一个链表， 当插入一个元素时，将元素放在它所对应的槽所指向链表的头部。 下面对链接法的性能进行分析。

定义散列表T的装载因子$\alpha = n / m$, 其中n是元素个数，m是散列表槽数, 我们假设元素满足简单一致散列的条件： 任何元素散列到m个槽中的每一个的可能性是相同的。

用$n_j$表示链表T[j]的长度，有 $$ E[n_j] = \alpha = n/m $$

有如下性质成立：

1. 链接方式散列表在简单一致假设下，查找一个不存在元素所需时间的期望为$\Theta (1 + \alpha)$

   假设查找的元素是k, 它所对应的槽为h(k)，链表T[h(k)]的长度$E[n_{h(k)}] = \alpha$， 所以平均情况下需要遍历一个长度为$\alpha$的链表，外加常数的散列函数时间和寻址T[h(k)]的时间， 总共为$\Theta (1 + \alpha)$

2. 链接方式散列表在简单一致假设下，平均查找一个已存在的元素所需的时间为$\Theta (1 + \alpha)$

   对于任意元素x，检查的元素个数等于x所在链表中，出现在x之前的元素个数加1。 设$x_i$是第i个插入的元素，i=1,2,..,n, 定义：

   $$X_{ij} = \begin{cases} 1 & x_i\text{和}x_j\text{在同一槽中} \\ 0 & \text{否则} \end{cases}$$

   由简单一致性假设，$E[X_{ij}] = 1/m$，所以检查元素个数的期望为：

   $$\begin{array} {lcl} E[\frac{1}{n} \sum_{i=1}^{n} (1 + \sum_{j=0}^{i-1}X_{ij})] &=& 1 + \frac{n-1}{2m} \\ &=& 1 + \frac{\alpha}{2} - \frac{\alpha}{2n} \end{array}$$

   所以平均查找时间为: $\Theta (2 + \frac{\alpha}{2} - \frac{\alpha}{2n}) = \Theta (1 + \alpha)$

比较排序的时间下界

合并排序和堆排序在最坏情况下能够在O(nlgn)时间内排序n个数， 而快速排序则能够在平均情况下达到这个上界。 这些算法在确定元素的次序时， 都是基于元素间的比较。 这类排序算法称为__比较排序__。

比较排序的时间下界是O(nlgn)， 这意味着所有的基于比较的排序算法，在最坏情况下都要用$\Omega (n \lg n)$ 次比较来完成排序。

这是因为比较排序可以被抽象为__决策树__， 决策树是一棵满二叉数， 它的每一条从根节点到叶节点的路径都对应于比较排序的一次执行过程， 达到叶节点时，叶节点确定了这次排序的结果。 所以比较排序算法的最坏情况的比较次数等于决策树的高度。 n个数的排列总数有n!，每一种排列都必须在决策树的叶节点中出现， 高度为h的决策树的叶节点个数最多为$2^h$，故有：

所以比较排序的时间下界是O(nlgn)。

正如上一篇所说，我这几天都在学习《算法导论》这本书， 也终于是下定决心要好好把这本书看出个所以然来。 这几天看下来，发现最大的困扰并不是知识的难度， 而是克服自己内心的浮躁。因为这本书并不像其他的工科教材， 它讲得东西是比较偏理论一些，里面充满了各种数学公式，数学定理, 包括一个算法正确性的证明，都采取了形式化的证明手段， 力求证明的数学严格性。 如果只是需要粗粗理解各种算法是什么样的以及如何实现的话， 那么看这本书有点不太合适， 因为这方面的东西并不是这本书的重点。

而我，也是在粗粗了解了各种算法和实现的基础上学习这本书的， 一开始扫了一下书的第一章，第二章和第六章， 发现和其他的算法书还差不多嘛， 直到看到第七章快速排序， 看到作者在大概描述完快速排序算法之后 （这个快速排序的划分函数还和我以前见过的都不一样，更加容易理解和实现）， 转而开始分析快速排序的性能和随机化版本，我才明白， 我不能再这么浮躁地只是抱着了解了解算法的目的来学习这本书了。 于是我又回过去仔仔细细地从头看到了第7章， 虽然说这本书里的定理和数学公式很多，但是并不难理解， 因为作者总是把每一个步骤解释地十分细致和透彻， 每一步的证明没有很大的跨越， 每一个结论的得出都会指明依据的定理或者是前面的结论。 所以说好好看下去其实并没有很大难度， 关键是要能够静得下心。

下面是1～7章中我的几点体会：

这几天好好地研究了一下mysql,认真地看了《High Performance MySQL》的几章， 才发现，要能够精通mysql真的是一个长期的工程，有效地管理mysql, 使它能够具有很强的稳定性同时具有很快的相应速度， 这其中涉及的东西远远不是数据库的课上写几条sql语句那么简单。 而在这篇博客中，我也仅就mysql的一些基本优化知识谈谈我的看法， 待以后更加深入研究之后，再继续分享。

MySQL的表的设计

Normalized Schema Or Denormalized Schema?

在一般的数据库教材中，讲到设计库表结构的设计， 都是将数据库设计范式作为设计的准则，因为这样设计的数据库表重复很少， 这样就会减少存储空间， 同时因为重复的内容少，维护起来也很方便， 因为如果很多的重复的话一个信息的更改可能会需要在多处进行更改才能保证数据的一致性。 然而，数据库范式并不是万能的，这样设计出来的数据库会造成查找时间的加长， 因为要查找一些数据往往需要将多个表join起来，而join是比较费时间的数据库操作， 同时，一些有关系的列被分散到各个表中，不好组合在一起建成一个索引， 这样也会减低查找的速度。 所以在设计数据库的表的结构时，要结合应用的实际情况，平衡考虑。

作为一个天朝的程序员，总是会在编程的时候与中文打交道。一开始对于编码不是很熟悉，也没有弄明白它里面的原理， 在处理中文的时候总是会遇到各种各样的问题，特别是在用python处理中文的时候， 所以特地花时间研究了一下中文编码，并通过python来熟悉一些概念。

废话不多说，先上干货，中文编码杂谈， 这篇文章是淘宝搜索技术团队写的，深入浅出，基本上将中文编码的各个方面讲得十分细致，而且十分通俗易懂。 我很难讲得比这篇文章更好了，我主要从几个侧面来阐述一下我对于中文编码的理解。

中文编码是什么

中文编码其实就是将中文转化为二进制比特串的过程，而不同的编码方式会把同一个中文字符转化为不同的二进制表示， 比如“中”这个字，通过utf-8编码会转化为二进制E4B8AD，而在计算机中，所有的数据都是通过二进制保存，这样我们就可以 通过二进制E4B8AD来保存“中”字，然后我们如果需要读取保存的这个字，我们首先需要知道编码方式是utf-8，然后就能将 E4B8AD转化为“中”。

python的中文处理

python提供了对unicode很好的支持，同时也能将unicode转化为其他的各种编码。

下面通过代码来对解释一下pytho中的编码问题。

    >>>a = "我是123"
    >>>a
    '\xe6\x88\x91\xe6\x98\xaf123'
    >>>type(a)
    str
    >>>len(a)
    9

来由

这段时间真的很忙，忙得都没时间好好看书，好好写博客。

每天都要上班，还要忙着保研的各种事情，有时还在保研和直接工作中纠结， 导致一有一点空闲时间，就什么事情也没想干了。

还好，现在这些事情也终于告一段落，也不用再去纠结什么了，终于可以静下心来 去做自己喜欢做的事，踏踏实实地学习某些东西了。

但是总结一番还是有点必要的，不然这些日子的纠结不是白费了吗。