我是个很无趣的人

最近身边很多人在学车，还有很多人也在搞装修，，前段时间还有很多人在炒股，为什么我对这些一点兴趣都没有呢。貌似除了吃喝，真的没有什么 共同的东西了。我真是个很无趣的人。

“背”算法和写代码

高中的时候第一次接触快排的时候，发现即便知道了算法的思想和基本过程，自己写出一个完整的代码，并不是容易的事情。不像做上学题目一样，基本思路有了，基本也就做出来了。当时真的很沮丧，发现写出一个一定程度上可以证明是正确的，都是很难的。当时发现不仅仅是快排，很多程序都不是那么好写，或者说只能写出个样子，却无法放心这样写是不是对的，包括后来的著名的2分查找。当时我就有个疑问，难道学编程，这些基本的东西要背下来么？不会的，不会的。

再后来的日子里，一直伴随着这种失落感，编程接触的也越来越多。有些很容易写出代码，比如动态规划的程序，或者逻辑非常清晰的程序，比如大部分递归的算法。有些很麻烦，基本上要写的时候还要debug，比如一些复杂的数据结构的操作代码，但是这些还算容易从代码上证明基本上正确。最难写的，还是上面提到的某些“短”的代码，比如二分查找和快排之类，如果不知道里面的变量在循环等结构里保持何种关系，所谓循环不变式，只有每次写的时候，从书上认真再去复查，才敢心安。

于是后来开始思考，我要依赖代码重用还是依赖书籍，甚至自己背下来？重用也许是最合理的想法，所以不要再去造轮子。不过，总有一些情况你无法重用曾经的代码，使用一些标准库，然而在很多语言，标准库对于基础算法的封装，并不总是够用的。（Knuth对传统黑箱式的重用就说"有偏见"）。另外，从某个意义上，不会造基本的轮子的程序员估计在很多人眼里算不上合格的程序员。 其实大部分情况下都是复制粘贴吧，也许。本质上还是依赖书籍。不过，即便如此，不理解为什么代码这么写，复制粘贴不能解决心中的问题！于是乎，还得把代码的一些关键的地方“背”下来，记下隐藏在i，j后的循环不变式，可能发生的边界问题等等。去年做acm题目的时候，发现大量的时间还是费在一些基本算法的使用上，后来才知道，真正参赛的选手都是要把那些基本算法背的很熟才行的。不过，如何写好算法的代码本身也是个值得思考的问题。一个代码写的好不好，缩进和命名都是表面的，关键是，是不是很尽量能被理解和证明正确性。可读性并不仅仅是文本上的。现实中，我们可能经常看到一些代码，看上去也是工作的，有些复杂，然而，很难看到其中一种条理性：这一段之后，会是什么样的，这个循环每次的入口是个什么样的，我能控制得了。失控的代码，结果总是等到debug的时候修修补补。其实是和自己过不去，代码基本上没办法证明是对的。

我平时写代码还算认真，也喜欢仔细思考每一小段代码的前后（广义上，都算入口和出口）是不是可控的。但是项目一忙，而且很多事情本身就是一个比较让人烦闷的事情，比如merge code，人总是来不及思考，结果让更多的时间给了将来去浪费。

PS，后来，终于在算法导论上看到了快排的一个更优良的划分方式，这个比以前的霍尔的快排要容易理解和证明的多，当时感到十分惊艳，也觉得终于拿掉了当年心中的一个石头。这个算法，好“背”多了。

无论如何，做一个心中合格的程序员还是很难得，还有很长的路。很多人看不起Coder,可是，做一个合格的coder, 也许比很多角色要难很多！而做一个合格的coder，也许是很多所谓光鲜角色的基础，然后，现在看上去很多都是本末倒置。

一个字

黨

来源

可恶的Blog css，装修

有段时间没更新了，其实我每天都在更新这个可恶的Blog的Html模板。我本来css就不懂，烦死了，好不容易搞了一个满意的，在IE6下面显示有问题，而且问题还都不一样.最后只好还是选择这个最初用的，稍微改改，不敢再改了。

======分界线===============================

装修开始了，目前顺利。我负责验收，LP负责买东西。

======分界线================================

尝到一次扩展性的甜头

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

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

我为什么写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。