Less is more

Google Protocol Buffer（简称protobuf）是Google内部混合语言数据标准，protobuf是一种紧凑的可扩展的二进制消息格式，适合做网络数据传输、数据存储的消息格式。

protobuf作为网络传输的消息格式，有两个问题需要解决：

• 消息长度。protobuf打包的数据没有自带长度信息，需要应用程序自己在发送和接收消息的时候做切分。
• 消息类型。protobuf打包的数据没有自带消息类型，需要由发送方把类型信息传给接收方，接收方再根据收到的消息类型创建具体的Message对象。
  第一个问题很好解决，可以在protobuf消息的前面附加一个固定长度的HeaderLen即可。

第二个问题可能很多人会想到在HeaderLen和protobuf消息之间再加上一个消息类型数据段，由接收方根据不同的类型创建相应的Message对象。但其实protobuf已经自带了消息类型反射的功能。

自动反射

Google Protocol Buffer具有reflection的功能，可以根据type name创建相应的类型的Message对象。（下图引用自陈硕的blog）

protobuf自动反射功能的关键所在就是Descriptor了，每个Message对象对应一个相应Descriptor。尽管创建Mesasge对象的过程中没有直接调用Descriptor，但是它却在其中起到了关键桥梁的作用。

在密码学中，「凯撒密码」是一种最简单且最广为人知的加密技术。它是一种替换加密技术，明文中所有字母都在字母表上向后或向前按照一个固定数目进行偏移后被替换成密文。例如当偏移量为3时，所有的A被替换为D，B被替换为E。这个加密方法是以凯撒的名字命名的，因为当年凯撒用此方法与将军们进行联络。

方法

凯撒密码的替换方法是通过排列明文和密文字母表，密文字母通过将明文字母向左或向右移动一个固定数目的位置。例如当偏移量是左移3时（解密是密钥就是3）：

明文：ABCDEFGHIJK
密文：DEFGHIJKLMN

明文：HELLO WORLD
密文：EBIIL TLOIA

f(x) = (x + n) mod 26

g(x) = (x - n) mod 26

在上一篇文章《八皇后问题之回溯算法》中介绍了如何使用「回溯算法」解决八皇后问题。关于八皇后问题，还有一种巧妙的解法，那就是本文将要介绍的「全排列」算法了。

全排列

学过高中数学的都知道，n个数字的全排列一共有n的阶乘个排列方法，即n!。例如数列{1, 2, 3, 4, 5}，一共有5×4×3×2×1=120个排列方法，那么对于计算机程序语言来说，如何实现这种全排列呢？

对于数列12345来说，可以看成是1和2345这两个数字的全排列，即12345和23451。而对于2345来说又可以看成是2和345这两个数字的全排列，即2345和3452，依次类推。当1和2345的排列组合算出后，再依次算2和1345，3和1245……

在计算机算法层面上来讲，这是一种递归的思想。我们把一组数分解成2部分，其中一部分只有1个数，另一部分有多个数。然后把这个有多个数的部分再分解，这样依次分解下去，当最终分解的2部分都是1个数的情况时就得到了全排列的一个解。然后原路返回至之前状态的下一种情况，再按这样的思想进行分解，最终得到所有全排列的解。整个过程，其实就是所谓的「递归」。

下面是全排列基本思想的实现，在实际算法中，每次分解2部分时，总是把当前数组的第一个数当做两部分中的其中一部分。这样当需要不同的数字充当只有一个数的那部分时，只需将它和数组的第一个数交换即可。当本次分解计算完成后，再交换回来，恢复原状态。

void print(int* data, int size)
{
    static int count = 0;
    printf("The %d solution:\n", ++count);
    for (int i = 0; i < size; ++i)
    {
        printf("%2d ", data[i]);
    }
    printf("\n");
}

void permutation(int* data, int size, int position)
{
    if (size == position)
    {
        print(data, size);
    }
    else if (size > position)
    {
        for (int i = position; i < size; ++i)
        {
            std::swap(data[position], data[i]);
            permutation(data, size, position + 1);
            std::swap(data[position], data[i]);
        }
    }
}

八皇后问题是一个以国际象棋为背景的问题：如何能在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任何两个皇后都不能处于同一条横线、纵线或斜线上。其中一种解法如下图所示。

思路

使用「回溯算法」求解八皇后问题是一种常见的思路。如上图中，从上到下依次在每一行放置一个皇后并检验是否满足要求，若某一行的每一列均不能符合要求，则回溯至有其他可放置列的行中进行放置。然后继续向下搜索，直至搜索到最后一行，即找到一个可行的解。

具体思路如下：

1. 初始化棋盘，当前行为第一行，当前列为第一列。
2. 在当前行，当前列的位置上检查是否满足条件（经过这一点的行、列和斜线上均没有其他皇后）。若满足条件则进行步骤3，否则跳到步骤4。

3. 在满足条件的当前位置放置一个皇后：

   • 若当前行是最后一行，则输出棋盘，记录一个解。
   • 若当前行不是最后一行，则将当前行设为下一行，当前列设为下一行的第一列，返回步骤2。

4. 此时，当前位置不满足条件：

   • 若当前列不是最后一列，则当前列设为下一列，返回步骤2。
   • 若当前列是最后一列，则进行回溯，即设当前行为上一行，当前列设为上一行中尚未经过的下一列，返回步骤2。
     阅读全文 »

花了2个晚上终于把这个独立博客弄起来了。

其实之前一直想弄一个有自己域名的独立博客，但是由于懒的原因一直没有付诸行动。将就的在博客园的blog上写写技术方面的文章。在别人的管制下，总是感觉不那么自由，有时候想改一下页面HTML结构，但是博客园只给开放了给公告栏、页首、页尾插入HTLM代码的权限，要大改的话只能上传JS脚本动态加载了，其中的限制还是颇多。最受不了的就是blog文章下面的广告了，但是这个也怪不得人家，作为一个运营网站总是要赚钱的。

直到前几天在知乎上看到了Belleve、Karbo Kuo的个人博客后，就越发觉得这事不能再拖了，作为一个喜欢写代码的人却没有自己的独立博客总是说不过去的，于是开始去godaddy上买域名了。果不其然，心中所想的liyuan.com这个域名被人买走了，就算没有人买估计这种短域名的价格也是很贵的。找了半天最终找到了liyuanbox.com和liyuanlife.com两个域名，都是2.5刀一年，但是想想liyuanbox这名字总觉得哪里不对劲，所以就选择了后者。可能因为刚好搜到的那会是在做活动吧，因为代理不给力的关系支付页面好多次都打不开，到最后打开的时候已经涨到了10刀一年了，还好可以接受，就欣然付款了。然后就租了个美国的虚拟主机，系统选的是ubuntu 12.04，服务端嘛，必须是Linux了。

博客暂时是用wordpress搭起来的，找了一个主题框架，然后自己现学了一点css和php把页面、排版大致的改了一下。不过wordpress因为历史的缘故比较臃肿，而且如果访问量大的话对系统的消耗也是挺大的。如果以后有需要的话，抽些空闲时间自己再从头写个博客吧。

或许是因为今天春节放假的原因，才6点钟整栋办公楼就剩下几个人了。回去收拾收拾东西，明天也该回家了。

傍晚6点，公司停车场的余晖。