尝到一次扩展性的甜头

最近几天工作比较忙，却尝到一次扩展性的甜头。就是去年的一块我当时经过思想斗争，留下一个扩展的可能。并且在当时没用上的地方粗略的填了代码，整体也一直维护着这个扩展性。其实我一直很烦莫名其妙没有需求的过度扩展，所以当时心理还有点打鼓。后来仔细分析觉得还是有必要。结果这几天发现这个扩展非常有用，如果要加这个新的需求，可能重构很多地方并且有大的梳理。所以比较顺利。

设计的时候，能考虑到哪些是需要扩展的，那些是过度的设计是很难的，一方面是设计人员的经验，另外现在软件经常受到需求不明确的干扰。需求似乎一直是变化的。虽然重构等手法能拥抱这种变化，但是简洁不应该成为设计不作为的借口，那就是过度的简洁。至少在设计的时候，能预料到不明确的地方，即便不实现，如果将来有重构的可能，重构的成本也应该在设计时候考虑进去，而不是一句：没事，到时候再重构。

我为什么写Blog

貌似每个写Blog的人都有经常问自己为什么写Blog.如网上这篇我为什么要Blog。以前我也经常问自己写blog干嘛。回头看看历史，竟然5年了。2004年开始写Blog，那时候有一个小圈子，现在这个小圈子还在，只是我不再使用Blog和这个圈子交流了。从2006年左右搬到Blogger，或者说Blogspot， 就基本上很少去公开现在的这个Blog,除非和人交流时候互相交换。如今这个Blog的读者是非常少的，目前我知道的只有两个，哈哈。也就是说，2006年之后，我的Blog就是相当于主要只是写给自己看了。

中国环难题和格雷码（二）

继续笔记，上次提到的格雷码的一个迭代规则，在实际编程中，这个算法在计算后置0的时候带有一个循环，因此效率并非最好。TAOCP上提到计算后置0的算法是可以不循环的，这个在TAOCP的前册有提到，不过我没有。但是有一本书，《Hacker's Delight》，上面应该有。不过这些算法可能依赖机器字长，书上提到一个通用的算法，速度很快。
算法的本质和上次提到的一样，快得原因是是找到k的进位不需要循环，而是维护一个长度一致的数组f,其中f[i]表示:

1 如果找到一个块 a[j + 1] = 0, a[j] = a[j - 1] ... = a[i] = 1, a[i - 1] = 0. 那么a[i] = j + 1
2 否则 f[i] = i;

显然，对于一个原始码的一次进位，那个进位的位置就是f[0]指向的位置。(f[-1] = 0)
算法每次都拿f[0]的位置，确定需要修改的g(k)中的变化的位，上次说过了，这个进位的位置和格雷码的变化位是对应的。另j = f[0]，进位发生后, 需要修改一些f，保持f的含义:

         j
         |
         v
..011..11011...11
         |
..011..11100...00

首先f[0] = 0，然后上面可以看出刚刚取出的变化的j,则

f[j] = f[j + 1]       /*这是为了把f[j + 1]指向的块向右扩展一个，因为当前的块变成了 f[j + 1] ~ j */ 
f[j + 1] = j + 1      /*把以前的f[j + 1]清为指向j,规则2*/

书上说这个算法是“眼花缭乱”的快。而且这种算法是很有启发性的，他的意义不仅仅在于这个问题上面，通用性可能应用到其他类似的地方。

过年归来

初五来到合肥，又要开始枯燥的上班生活了。

年过得很开心，虽然现在年味是很淡了。还了了一个大事情，就是父母和LP的父母见面，之前和LP都很害怕，不知道会不会尴尬，结果他们4个人一见如故，相谈甚欢。我的恋爱之路终于步过新的里程碑了。

在家看到五舅，小舅的小孩已经长很大了，还有表姐的小孩也长大了。



=== 华丽分界线 ================================

回家看了些电影，把一直没完整看的教父1 和 2都补全了。另外看了大烟枪等喜剧，然后看了悲情城市，不少人觉得悲情城市里面有亲日和悲伤的结局，但是我觉得这是一部充满希望和美好的电影，政治的苦难只是背景，并不是表现的主题，主题还是台湾的人，无论是日统，国统，228，族人相残这些政治之难之后，他们仍然吸收和保有自己的文化，孕育自己的家庭。所以看完挺感动的，这才是一种真正的坚强。如果只有悲伤，怎么会有最后的一家吃饭的长镜头，几个小孩已经长大，香火不断，坚强不息。

小年，假期，春节

今年农历年挺早的，下个周一是我农历生日了--小年。灶神在古人的书中是个帅哥啊。“男不拜月，女不祭灶”，为啥，灶王爷帅啊。昨天去买了车票准备回家，结果以前常坐的那次车停运了，这次得很晚才能回到家。。。离家不过两个小时的火车，真晕，铁路就是霸王啊。上面通知了，要配合几个老美，估计得在假期要几天来加班。本来今年经济危机，假期比以往的长，结果发现不但加班，连付费加班都没了。不过经济危机就是这样，台湾那边好多同事还有很多在国外出差，而且是过年期间。

去年回家之前是雪灾，今年看来没有这个担心了吧。经济上的雪灾，至少不能阻断回家之路，父母，家庭，才是温暖的所在啊。祝天下所有父母新年快乐，身体健康，家庭幸福。虽然现在的社会年味越来越淡，要不就是商家为了赚钱营造的那些浮华的气氛。但是一年的辛苦之后，我们总要有个休息。推杯换盏之间，热气腾腾的饭菜，让我们忘记那些不如意的事情，尽情的爱身边的人。

中国环难题和格雷码

最近在翻TAOCP的第四卷第2册。看到格雷码问题的一个产生方式是与一个叫做中国环问题相关（作为中国人，我竟然不知道这个东西）。而这个问题我去年在做ACM题目的时候，刚好也有个类似的题目，关于一个囚犯解脱的问题规则和这个一模一样。当时我仅仅得到结论就是每一个步骤只能做一种动作，因为任何动作都是自反的，就是再做就回到上一步了。那么问题就是如何选择第一步，选完第一步，后面的计算是确定的。我当时的程序列出那些数据，那时候并不太明白格雷码的相关知识，也就作罢了。因为需要一个公式才能做那个题，否则就需要硬迭代，范围太大了。
那个格雷码的公式就是格雷码与他的索引之间的关系。就是TAOCP的g(k)与k的公式，是一个总结的结论然后用数学归纳法证明的。

g(k) = (b[n], b[n - 1], ... b[1])
k = (a[n], a[n - 1], ... a[1])
则对 j <= n 有 b[j] = a[j] XOR a[j + 1] 

这个公式就能解释这个中国环问题为什么是格雷码问题，不过高大爷写的过程的不太直接。其实就是找出k ++的格雷码增加的规律。
当 a[1] = 0的时候， k + 1不产生进位，则g(k)的最后一位取反(1 XOR a[2] =NOT(0 XOR a[2])
当 a[1] = 1的时候， k + 1产生一个传递的进位，另（假设n无范围） a[j + 1] = 0, a[j] = a[j - 1] = ... = a[1] = 1有

 X011...11                    Y10...00
+        1     
----------  k   对应 g(k)   ------------
 X100...00                    Z10...00

可以看出，这个进位使得g(k)的0最右0不变，并且第一个1不变，然后紧接这个1的位取反，Z = 1 XOR X = NOT(0 XOR X) = NOT(Y)
这样两个g(k)的变化规律刚好就是中国环的取环和下环规则:
1 最右一个环可随时取下和放上
2 可以取下或放上一个环，这个环的右边的环是放上的，右边的右边到最右边的环都是取下的。
再回到刚才的情况a[1] = 0 或者1的判断其实就是一个简单奇偶判断。
那么一个k可以求出g(k)，反过来g(k)求k就是 （利用第一个公式联j到n + 1位得到的式子,然后XOR这些式子消去中间的式子,这种推导在书上是不会写的，连一个习题都不算）

 
a[j] = b[j] XOR b[j + 1] ... XOR b[n]

上面这个公式对于编程的时候，是可以简单的动态规划的，就是求得a[j] = b[j] XOR a[j + 1],a[n] = b[n]. 于是当面对一个环的状态时，可以转换到对应的自然数索引k，根据k的奇偶这样就可以确定该如何往下走了。 PS,我看得这个书是双语版的，翻译有一些不妥的地方，坚定了我在豆瓣建了一个翻译勘误小组，因为有些翻译还是很容易误导别人的。还有上面的[]索引有些地方看上去超出了范围，其实本没有范围，对于自然数，超出就是0。

2009展望

新年将至，想明年开始一个自己的project，目前还没有想好要做什么。用业余时间。继续打乒乓球。继续Blog.继续看书。其他的没想到了。

2008年终总结

2008年即将过去，雪灾，地震，奥运，藏独，经济危机... ... 真是多事之秋，而且很多都和我直接相关，即便不再身上发生，也会强烈的撼动我。所以觉得2008年过得很快，一个悲伤的年份。

今年没有出去玩，和lp一起把旅游经费都捐给灾区了。租的房子也搬了，因为以前的房子卖了。我自己买的房子还没到手，于是又换了一个房子。这个房子房租贵些，但是离上班比较近一些。并且，新房子有网络上，虽然网络质量一开始非常差。于是我又开始玩游戏。到年底房子已经好了，还没开始装修。

今年看了一些书，做了大概几十题的PKU ACM题库的题目。有不少收获，实际做题的帮助还是挺大的，只看不练也不行。但是再做下去也不想做了，因为感觉能做的能做，不能做的还是不太好做。还是多看看书吧。今年买了不少书，不过很多都没时间看，都是马桶上翻翻，上班的间隙翻翻。

工作今年很忙，加入这个组之后。对于linux内核方面有不少收获，不过并不是那么完整。工作其实更多的时间在做很烦人的事情。这两年都没闲下来过。

打乒乓球换了一段时间直板，最后又改回来，现在是oc横版但是不贴满，却发现这样非常好用，解决了我手小捏版问题，哈哈。

2008，没什么可写的了。

让自己快乐起来！

基于染色DFS下的拓扑排序算法

拉屎的时候翻算法导论，无意停在图的DFS，然后到拓扑排序，发现这里的拓扑排序算法是基于DFS的。以前在群里还和讨论过依赖关系的算法，当时我知道的就是那个最简单的不断删除入度0顶点的算法。因为认为DFS(注：普通的DFS）算法可能需要辅助一些特殊的手段来做，不是很方便。
其实删除顶点算法并不是很好用，虽然渐近意义上是o(v+e)，实际使用中和存储结构很相关，而且不好用。然而算法导论上的基于染色的DFS算法很容易做拓扑排序：因为染色使得很容易知道回路，（灰色节点的重入代表回路）。接下来就简单了：

For each v in V do DFS
    If a child is Gray , Fail.
    If v is finished (to be black), insert v onto the font of list L.
return L.

这个算法的复杂度也是o(v+e),但是执行起来效率很高，因为删除顶点的算法需要维护“可删除性”，就是入度的维护。DFS维护一个染色信息，和顶点数相同。但是删除顶点算法可能需要临时的栈/队列来暂存计算出来的入度为0的节点。。
以前老觉得DFS多老生常谈，什么书到那都翻过去，其实发现《导论》上的染色并且维护时间戳的DFS是非常有用的。（记得以前有段时间研究GC遇到过，但是没有在意在别的上面的应用）。看来很多书还要再仔细的多翻翻。

ps，惊闻饭岛爱去世的消息，沉痛悼念！

又到年末

今天是12月13号。。。明天凌晨又是皇马对巴萨，突然又想起四年前的皇马对巴萨，那时只有小罗和齐达内，没有梅西，更没有柏杨。。又是年末，圣诞将至，元旦将至，尾牙将至，春节将至。。。。

到年末就是要写年终总结的，我把07年的总结翻出来，看着觉得好熟悉，觉得近在咫尺，不能想象过了一年了。。今年也是看上去波澜不惊的一年，只是2008年对于身边的环境，的确是一个多事之秋。

准备准备，写一篇总结。。。