移山之道

THU – team players 合作精神

关心 — Sun, 24 Jan 2010 14:12:42 GMT

我朝的教育体系虽然时不时灌输“互相帮助”的精神，但是所有小考，中考，大考，无一不是考察个人独立作战的能力。你要互相帮助，不但违反考场纪律，而且其他同学的好成绩对你是一个直接的威胁。在这种价值体系下产出的学生，合作精神如何? 善于合作，对自己是弊大于利么?

在清华大学《现代软件工程》课中，我安排同学们有尽量多的机会和别人合作:

1) 两人一组的结对项目 I (为期两周)

2) 两人一组的结对项目 II (为期两周)

3) 4~5 人一组的团队项目 (为期十周)

我们安排让每个学生在三个项目的合作伙伴都不一样，这样，一个学生在这个课程中有机会和 5 至 6 个人合作。在组员眼中，你是不是一个好的合作伙伴? 我们让他们给各自合作过的同学打分 ( 1.. 5 分，5分最高)，下面是结果。

[第一列：学生学号，按合作精神分值高低排列; 第二列：合作精神得分; 第三列: 学生学号，按最后得分由高到低排列]

以0.5 为区间，得分人数分布如下。

这个投票的结果不计入课程成绩，大家匿名投票，当然还有一些同学没来上课，失去了投票的机会。由于投票者分布在3 个不同的项目中，可以说数据还是挺全面的。可以看出，有得全票满分分 (5.0) 的同学，也有得1.5 分的同学。对比第一列和第三列，绝大部分合作精神得分高的同学，最后课程的得分也相当高。

很多学生并没有自知之明 (self-awareness), 觉得自己已经很了不起了，别人也应该对自己顶礼膜拜, 至少为能有机会和自己合作而庆幸不已... ... 我上课的计划就是把这样的得分公布出来，让同学们看看自己在别人眼中的地位。相信一些人看了数据，会很震惊 - “平时大家都是哥们儿，怎么我才得这么少分数? ”

以后好些年，可以回头看看，“混得好”的人和团队精神高的人，是不是有相关性。

THU - 清华大学现代软件工程成绩统计

关心 — Sat, 23 Jan 2010 05:28:32 GMT

第三年讲这个课。同学们除了完成个人项目，结对项目外，还完成了如下的团队项目:

team 1 (最后评审第二名)

一个日程管理的小软件，名为Lifer，可以与Google Calendar同步的 Todo / Calendar / 便签管理工具。

team 2 (最后评审第五名) 评审时尚未发布软件。

Q三国杀 - 像所有的游戏软件一样，多次推迟后，发布了一个问题多多的版本，他们的总结提到:

什么功能产生的bug 最多，为什么？
规则部分的bug较多。这是因为三国杀本身的设计造成的，其规则比较凌乱复杂，难以用一个清晰的框架描述。比如说:
· 关羽在被借刀的情况下是不能将红色的武器当杀打出
· 关羽在出过杀的情况下不能将红色的的诸葛连弩打出
· 大乔流离的时候，如果用武器或者马流离，则要去掉武器或马的距离

其实，最大的问题出在项目管理上。

team 3 (最后评审第四名)

课程管理助手

team 4 (最后评审第一名)

SmartMe - 用多个搜索引擎同时解决你的任何问题。

team 5 (最后评审第三名)

Cute Reminder -

1.BBS(newsmth,各系bbs等)消息管理、消息提醒； 2.网络学堂信息管理、信息提醒； 3.备忘录功能、日程提醒。

最短摘要生成与多模式匹配（三）

silver — Mon, 04 Jan 2010 09:21:36 GMT

Boyer-Moore算法——“坏后缀规则”？

如前贴所述，BM算法的“好后缀规则”实际上有两种情况：“中缀”和“前缀”。

“前缀”没啥问题，但是我发现“中缀”往往会出现“跳转以后朝向注定的失败匹配”，如下图所示：

如上图，在第6位X处发生了miss match，BM算法会跳转到3位，也就是将pat挪到如上表第三行的样子，再从11位开始比较，假设11～7都匹配成功了，但是X!=B，第6位是注定失败的。

那么可否将“中缀跳表”独立出来，匹配过程中判断”好后缀”加上它的前导字符构成的子串是否在pat中存在？如果不存在就是个“坏后缀”。

例如：上图中的“XXY”实际上是“坏后缀”，而不是“好后缀”，因为在pat中根本不存在这样的子串。

如何考虑“坏后缀规则”？

如果要实现这个规则，需要注意两个问题。

如下图，和前面一样，假设在倒数第三位X处发生了miss match，可以跳转到两个位置（如箭头所示），但是有一个跳转是重复的，A=A。

因此可以看出，如果要独立“中缀跳表”，需要考虑两个问题：

某位置的中缀跳转可能不止一个；
跳转中可能存在重复。如果出现重复，需要取最右边的那个。

很容易想到，满足这两个需求，用个哈希表恰好。

一种实现方法

将（二）贴中的计算中缀跳表的地方用一个函数AddInfixJump(i, j);代替，这个函数如下：

/// <summary>

/// 中缀跳表

/// </summary>

static Dictionary<char, int>[] iJumps;

static void AddInfixJump(int i, int j)

    if (j < m - 1)//最后一位采用坏字符移动，这里不需要

        if (iJumps[ j ] == null) iJumps[ j ] = new Dictionary<char, int>();

        //添加中缀跳 能保证从小到大

        if (!iJumps[ j ].ContainsKey(pat[ i ])) iJumps[ j ].Add(pat[ i ], i);

这样去计算中缀跳表，能够保证没有重复，并且右边的跳转肯定是先计算的，所以保留的也是最右边的。

然后在搜索过程中，如果在pat倒数第1位以前发生了miss match（也就是不用“坏字符规则”）的时候，先设置跳转为原来的那个表（比原来少了中缀跳转而已），然后再看看是否有好的“中缀”：

shift = mJumps[ j ];//设置为前缀和坏后缀混合跳转

if (iJumps[ j ] != null &&//存在中缀

    iJumps[ j ].ContainsKey(text[ i ]))//且跳转以后匹配text[ i ]

    shift = m - 1 - iJumps[ j ][text[ i ]];//设置中缀跳 (m-1-j + j-k)

这样能够避免上面出现“注定的失败”了。

实验结果

通过实验我发现，这样改进以后，在随机字符串和英文文章的匹配中，比较次数能够降低10%～30％，但是总体性能提高却不明显。我估计性能肯定是损失在C#的泛型字典Dictionary<>上面了，“坏后缀”的思路应该很好，但是可能需要别的实现方法：比如字符集小的话可以用数组，或者别的语言实现。有人想到好方法麻烦告诉我：）

后记

这和我一直以来的编程经验是相反的：“一般来说，不应该先考虑太细节的优化，算法思想的优化是最重要的”；但是在字符匹配的程序中不完全是这样，字符比较的消耗很小，稍微复杂的逻辑和数据结构都会损失性能，所以凡事都有例外。

有些细节优化却能够提升性能，例如，原版的BM搜索过程是这样的：

var shift = 0;

var k = (int)text[ i ];

if (k < cJumps.Count) shift = cJumps[ k ];

else shift = m;

i += Math.Max(shift, mJumps[ j ]);

贴（二）中，我将其改为：

if (m - j == 1)//末位不匹配

     var k = (int)text[ i ];

     if (k < cJumps.Count) i += cJumps[ k ];

     else i += m;

 else i += mJumps[ j ];

实际上就是当匹配超过1个字符时候，不用去计算“坏字符跳”。这样小改动一点，在随机字符和英文测试中，性能都提高了10％左右。

当然要说明的是，MB算法总体性能相比最原始的BruteForce算法还是有大幅提高的，pat越长越明显。

编程之美 - 哪个题目最美?

关心 — Sat, 02 Jan 2010 15:42:00 GMT

编辑部搞的活动，请大家帮个忙，来投票吧，看看《编程之美》第1章“游戏之乐——游戏中碰到的题目”大家最喜欢哪个题目，或者大家认为哪个题目最有趣。
　　
　　
　　可以选择以下任何网址参与投票：
　　CSDN：http://vote.csdn.net/VotePost.aspx?voteid=6419

　　开心网：http://www.kaixin001.com/~vote/detail.php?vid=6324994&uid=57936198

　　QQ空间：http://user.qzone.qq.com/80754098/vote/1021116304

最不美的题目说不定以后就不要了 :)

最短摘要生成与多模式匹配（二）

silver — Fri, 01 Jan 2010 07:24:00 GMT

Boyer-Moore算法

通过学习和借鉴之后，感觉这个算法思想挺精妙，同时也比较复杂。我根据自己的理解写了一个算法，望大家指教。

前面提到过，这个算法是从右往左匹配，根据“坏字符规则”和“好后缀规则”来跳转，避免无谓的比较。

坏字符规则

这个规则比较简单，首先看pat的末位是不是和要查找的文本匹配，如果不匹配，pat里面又没有这个字符，则可以完全跳过这个字符，如下图：

如果pat里面有这个字符，则跳到pat里面最右的这个字符（当然排除自己），如下图中pat的第二个T:

可见这个规则是在末位就不匹配的时候用的，如果已经匹配了几位了，这几位就是“好后缀”了。

好后缀规则

个人觉得，如果要清晰理解这个规则，应该再明确两个概念，一个是“中缀”、一个是“前缀”。

中缀

如下图，在pat＝wowwow中，第3位的w就是中缀，它有两个特点：一是和后缀匹配；二是它前面的字符不能和“后缀”前面的字符一样，否则跳转过去没意义。

下图中，如果匹配到4的时候发生miss match，就跳到2，换个w来比。

另外要注意的是，中缀可能很多，在BM算法中就考虑移动到最右边的这个中缀，如下图，x y 的中缀出现了好多次，如果在8出现mis match，就跳到5，而不考虑2了。

注意，最前面的x y不算中缀，而算“前缀”。

前缀

和后缀匹配的前缀这里简称“前缀”。如果pat＝wowwow，其前缀是w 和wow，长度分别为1 和 3，这说明前缀长度可以是跳跃的，长度为2的前缀不存在。

如AAAcAAAAAAcAAA的前缀长度就有7、3、2、1。

最后，在前缀跳转和中缀跳转中，应该取小的，避免遗漏（中缀跳<前缀跳）。

如果中缀、前缀都不存在，就可以直接跳过整个已经匹配的部分。

算法实现

坏字符表构造

坏字符表理论上可以用哈希表来做，不过我实验了下，字符比较本来运算量就小，用哈希有点费，还是改用数组了，cJump 是坏字符跳表，由于不知道字符集的大小，这里用动态扩展策略。

其中，m = pat.Length;

static List<int> cJump = new List<int>();
static void BuildCharJump()
{
    cJump.Clear();
    for (int i = 0; i < m - 1; i++)
    {
        var k = (int)pat[ i ];
        while (k >= cJump.Count) cJump.Add(m);
        cJump[k] = m - 1 - i;
    }
}

好后缀表构造

好后缀表又称为match jump，可以通过上次帖子介绍的“逆向的MP fail links”来构造，因为是倒着匹配的。

为了便于理解，这里给出一个“逆向MP fail links”的构造过程：

static int[] mJumps;

static void BuildMatchJump()

    if (m < 2) return;//少于一个字符，不存在后缀

    //一、初始化

    var n = m - 1;

    mJumps = new int[ n ];

    for (int k = 0; k < n; k++)

        mJumps[ k ] = (n - k) + m;//初始化为最大移动数

    //二、构造逆向 MP fail links，并计算中缀跳表

    var fails = new int[ m ];//逆向 MP fail links

    int i = n;

    int j = fails[ n ] = m;

    while (true)

        while (j < m && pat[ i ] != pat[ j ])

            if (j < n)// 已匹配长度 +  移动数

                mJumps[ j ] = Math.Min(mJumps[ j ], (n - j) + (j - i));//计算中缀跳，记录最右的中缀

            j = fails[ j ];

        if (i == 0) break;

        fails[--i] = --j;

    //三、计算前缀跳表

    var s = 0;

    while (j < m)//顺着最后一个箭头往前可找到所有前缀

        if (pat[ i ] == pat[ j ])

            var L = m - j;//前缀长度

            for (int k = s; k < m - L; k++)//已匹配长度 + 移动数

                mJumps[ k ] = Math.Min(mJumps[ k ], (n - k) + (m - L));

            s = m - L;

        j = fails[ j ];

查找算法

最后的查找算法再用两个表就好了：

static public int IndexOf(string pattern, string text, int index)

    if (pat != pattern)

        pat = pattern;

        BuildCharJump();

        BuildMatchJump();

    int i = index + m - 1, j = m - 1;

    while (i < text.Length)

        if (j < 0) return i + 1;//找到

        if (pat[ j ] == text[ i ]) { i--; j--; }

        else

            if (m - j == 1)//末位不匹配

                var k = (int)text[ i ];

                if (k < cJumps.Count) i += cJumps[ k ];

                else i += m;

            else i += mJumps[ j ];

            j = m - 1;

    return -1;

后记

个人觉得MB算法还可以有改进的地方：可以提出一个“坏后缀规则”，因为MB算法构造跳表的时候没有考虑text的内容，所以没办法知道“坏后缀”，明天咱们继续分析这个改进。

最短摘要生成与多模式匹配（一）

silver — Thu, 31 Dec 2009 06:21:00 GMT

问题

《编程之美》有一道题目“最短摘要生成”：若输入“微软亚洲研院使命”三个关键字，查找最短的摘要：

微软研究院的使命是使未来的计算机能够看、听、学，能用自然语言与人类进行交流。 ... 微软亚洲工程院将以微软亚洲研究院的科研成果为依托，创造关键技术、为微软亚洲研究院核心技术的孵化提供有力保证。 ... 微软亚研院的科研环境编辑本段回目录…

书中给出的解法是基于“分词”后的数组的。

那么，如果是客户端蜘蛛临时抓的网页，或者是在一堆文件中查找，这时候没有分词、没有建立倒排表，如何直接生成呢？再加上有中英文混杂的情况（查找某种表达的翻译）？

冰山一角

这时我想到了基于“多模式匹配”改进原书中算法，因此决定研究下经典的AC_BM算法。查阅了很多文献后，意外的发现：小小的“字符串匹配”居然有这么多学问～：），引用一段文献——

“String-matching is a very important subject in the wider domain of text processing. String-matching algorithms are basic components used in implementations of practical software existing under most operating systems. Moreover, they emphasize programming methods that serve as paradigms in other fields of computer science (system or software design). Finally, they also play an important role in theoretical computer science by providing challenging problems…”

这段文字出自 http://www-igm.univ-mlv.fr/~lecroq/string/node1.html ，这个网站上竟有35个单模式匹配算法的详细分析、例子、代码、java动画演示…

多模式匹配在：入侵检测、数据挖掘、DNA配对、文本处理（查找替换）等方面都有广泛的应用。

算法发展简要回顾

先简要回顾下经典的AC_BM算法是怎么来的：

1. 1977年，这三个人改进Morris-Pratt 算法提出了Knuth-Morris-Pratt 算法——将“有限状态自动机”＋“递归/递推”思想用得很精妙。

2. 同年，Stanford和Palo Alto研究院的两个人提出了经典的Boyer-Moore算法，主要思想为：

a) 提出了从右往左匹配的思路；

b) 通过“坏字符移动”＋“好后缀移动”避免无谓的比较；

c) “好后缀移动”借鉴了Knuth-Morris-Pratt 算法。

题外话：这个BM算法就是大家日常“查找替换”时候用的：）

3. 1980年，Horspool简化了Boyer-Moore算法：用实验证明了只采用“坏字符移动”在一般情况下性能足够了。这是因为“好后缀”出现的概率并不大，除非是DNA一类的“小字符集”中的匹配，类似AGTCAAGGTTTC…

4. 1975年，Bell Labs的两个人提出了Aho_Corasick算法，主要思想是构造了“多模式”（多关键字）的“有限状态自动机”（是一棵多关键字树，Knuth-Morris-Pratt 算法是单模式的“有限状态自动机”）

5. 2001年，Silicon Defense的三个人将Aho_Corasick算法和Boyer-Moore算法思想结合起来（因为AC算法没有如BM算法一样很好的跳转，还有优化的空间），就成了AC_BM算法。

由此可以看出，要想搞懂AC_BM算法，得从头一个个来。

引用一个题外话：

AC 算法被用于fgrep1.0（在UNIX中通过-f使用）

BM_AC算法在gre中应用，并被fgrep2.0收用。

Knuth-Morris-Pratt 算法

在单模式匹配中，可把要匹配的关键字看成一个“有限状态自动机”：

例如上图，如要匹配：GCAGAGAG，遇到G就转状态1，再遇到G还是在状态1，遇到C就转状态2… 到8就成功

这个思路挺不错，问题是跳转的条件比较麻烦，于是Morris-Pratt就将其简化为两个：成功s和失败f，如下图所示：

要匹配ABABABCB，成功了就向前，失败了就退回来，再失败了递归退后…如下表：

那么构造的时候可以递推构造，思路挺好：）

那么这个算法最关键就是要构造失败的这些箭头：MP fail links，可以用一个int[]保存。

设要匹配的模式是string pattern; m = pattern.Length; 那么MP fail links可以很简洁地构造：

 int[] Morris_Pratt()
    {
        var fails = new int[m];
        int i = 0;
        int j = fails[0] = -1;
        while (i < m - 1)
        {
            while (j >= 0 && pattern[ i ] != pattern[j]) j = fails[j];
            fails[++i] = ++j;
        }
        return fails;
     }

不知道大家有没发现MP fail links 有个问题，假设遇到：

设要匹配的文本是 string text; 如果text中出现了“…ABAY…”，那么按照MP fail links跳转换过来的还是B（如上表最后一行），肯定匹配不上的，所以Knuth-Morris-Pratt算法就改进了这个问题（将上面while里面改了下），构造KMP fail links：

……
while (i < m - 1)
{
        while (j >= 0 && pattern[ i ] != pattern[j]) j = fails[j];
        i++; j++;
        if (pattern[ i ] == pattern[j]) fails[ i ] = fails[j];
        else fails[ i ] = j;
}
…….

就递推地实现了所有首位字符相同的跳转都合并的效果，如下图所示：

那么在查找的时候，就可以利用 KMP fail links 实现跳转，而且思路和构造的时候类似：

 ……
 int i = index, j = 0;
 while (i < text.Length)
 {
       while (j >= 0 && pattern[j] != text[ i ]) j = fails[j];
       i++; j++;
       if (j == pattern.Length) return i - pattern.Length;//找到
 }

 return –1

后记

今天先写到这里，明天咱们继续研究BM算法，感觉挺巧妙的是利用简短的MP fail links可以找到所有的“中缀”和“后缀”。

需要说明的是，直接利用KMP 搜索效率提高并不明显，因此“查找替换”一般用BM算法。

顶级程序员的心得 Coders at Work (IV)

关心 — Sat, 26 Dec 2009 04:12:11 GMT

( 第一，第二，第三部分 )

“Coders at Work”, 对15 位顶级程序员的采访，总共600页。看似冗长的问答中有不少精辟的言论。我摘录了一些关于挑选，面试程序员，优秀程序员的特点，和程序设计的句子。下面是最后 3 个程序员的心得，和我的几句解释：

Coder

What they say about good programmer, interview, and design

My interpretation

Fran Allen

first woman winner of Turing Award

Software process:

did software-development process save the IBM/360 project?

it's was absolutely necessary, but it was painful for the software people to [adjust to] design reviews, design specs, all of this stuff.

good programmer:

basic threshold: find out what they're excited about.

if they can't get enthusiastic about something, they're not going to get charged up in a group.

软件流程:

因为IBM/360 项目的软件部分遇到了很大的困难，那时候还没有什么成文的 "软件工程"， Fred Brooks 把管硬件的经理们调来，让他们来管软件部门，因为硬件是一个相对成熟的产业 - 芯片设计，测试，等等。这些“不懂软件”的同志们参考硬件产业，建立了软件工程的基本流程。

从一个成熟的产业中学习，是很有效的办法。现在我们还可以从软件工程的一些术语中看到硬件的影子 - 例如 smoke test 冒烟测试。

好的程序员:

热情 (前面 Ken 同学也谈到了这一点)

Bernie Cosell

czar of PDP-1

pioneer of APPANET, the core of the later internet

advice to programmer:

write a lot of programs.

there is very few inherently hard programs. if the code looks very hard, that's almost always an indication that it was poorly thought thruough. if you have complicated code, put it in an encapulated place.

programs are meant to be read.

avoid premature optimization

find talented programmers:

whether they have the kind of inquiring, curious, precise kind of mind. quickness of learning, interested in lots of different things, and kind of broadly based.

[carefully chosen] puzzle can gives you a glimmer as to how they organized something to approach it.

给程序员的建议:

写很多程序。

世界上难的问题/程序很少，如果一个人的代码看起来很难，这通常意味着程序员没有想清楚。如果你必须用很复杂的代码，把它包装起来。

程序是用来给人读的。

避免过早优化。

优秀程序员:

应聘者有没有刨根问底，好奇心, 准确的思维? 能快速地学习么? 是否对很多东西都有兴趣? 是否有很广泛的基础?

[仔细挑选的] 智力题能让你看到应聘者是如何组织材料，解决问题的。

Donald Knuth

TAOCP, TeX and METAFONT, literate programming

Knuth 在学术界的影响

How I learn programming – basically taking one program that i made up myself and sitting at a machine over a period of some weeks, and kept getting it to work a little better and a little better.

Q: Should every programmer be able to read TAOCP?

A: I sometimes wonder if I can read them.

but even an algorithm like a balanced tree ot AVL tree, i don't use it in m own programs unless i know that it's going t obe a really big tree.

what do you use?

i use an ordinary binary search tree with a little trick for randomizing it that i just put it.

...

顶级程序员的心得 Coders at Work (III)

关心 — Fri, 25 Dec 2009 15:37:02 GMT

这是第三部分（第一，第二部分），非常有意思的问答，值得仔细琢磨。

这里只是一些和程序员发展，面试，优秀程序员的特点等相关的部分。

有些想法和 MSF 中的原则也很相似（见 <移山之道>）。

Coder	What they say about good programmer, interview, and design	My interpretation
Dan Ingalls Guru of Smalltalk; inventor of BitBlt operation, working on Lively Kernal now.	Tips on a good technical leader: 1) clear vision; 2) trust people; get everything figure out, but leave it open to team member to do it. 3) avoid micromanagement. if you’re worried and you’re insecure, and so you’re feeling like you hve to nail everything down. Alan Kay is a good example for such great leader.	技术带头人: 1) 清楚的远景。没有清楚的远景，只有强大技术能力的团队，就像盲人骑瞎马，还使劲用鞭子抽打，让马快跑。看起来一度非常拉风，但后来免不了人仰马翻。 2）信任团队，把大方向弄清楚之后，把其他事情交给团队成员去搞清楚。如果带头人详细规定了所有细节，那么团队成员干得还有什么劲呢？ 3）避免“微观管理”。当你担心或者没有安全感的时候，你当然会希望把所有细节都搞清楚，但是这样反而会出乱子。
L Peter Deutsch veteran of Xerox PARC, author of Ghostscript; now he is into music composition.	skills of good programmer: intuition – no luck, but experience that had simply gotten internalized so far down that i didn’t have conscious access to the process. programmer – people who feel comfortable swimming around in the world of symbols. programmer vs. coder: "Coder" is strongly associated with the smallest and most narrowly focused part of that whole software building endeavour. "coder" represents such a small corner of the whole processs. a good title should be: software developer. computer science = enginnering + applied mathematics. I would've thought that the internt was inherently uncontrollable, and i no longer think that. China shows that you can do it pretty effectively.	优秀程序员：直觉。但是Peter 说的不是运气，而是长期实践之后成为你思维一部分的东西 - 你不知道推理这些东西出来，正如同你不知道如何推理出直觉。 Peter 认为优秀的程序员必须能在抽象思维 (world of symbols) 中得心应手的人。程序员 vs. 码农: Peter 认为Coder 把程序员的工作定义得太狭隘了。就像IT 民工，翻沙，砌墙。砌墙并不是一个坏工作，但这只是“建筑”这一过程中的一个小部分。 "软件开发者" 应该是一个好名称，虽然并不全面。所谓 "计算机科学" 不过是工程加上应用数学。我原以为互联网是根本上无法控制的。。。
Ken Thompson creator of Unix.	Talented programmers: it's just enthusiasm. you ask them what's the most interesting program they worked on, get them to describe it and its algorthms and what's going on. if the ycan't withstand my questioning on their program, then they are not good. enthusiasm is not something you ask directly, but in the conversation you'll come with the enthusiasm-ometer.	优秀程序员的特点: 就是“热情”，我们有时也说 "passion for technology". 但是在面试的时候你不能问 - 你对计算机技术有热情么? 因为所有回答都是 yes。你要在场景中，对话中感觉对方的“热情”。如果一个念了5-7年计算机专业的人，不能 “两眼放光”地给你讲他自己最得意，最激动人心的项目或算法，不能回答你的深入提问，除了老师的作业和实验室老板叫做的项目之外，没有别的想法。你觉得这种人有多少 “热情”? Ken 还表达了自己对C++ 的意见，几乎所有这本书采访的牛人都不太喜欢C++，很有意思，不过这是另外一个话题了。

顶级程序员的心得 Coders at Work (II)

关心 — Thu, 24 Dec 2009 14:47:10 GMT

正在读 “Coders at Work”, 对15 位顶级程序员的采访，总共600页。这些看似冗长的问答中有不少精辟的言论。我摘录了一些关于挑选，面试程序员，优秀程序员的特点，和程序设计的句子。下面是 3 个程序员的心得，和我的几句解释。 Peter Norvig 讲了NASA 的一个著名事故的一些故事，我也重构了一下，写在后面.

Coder

What they say about good programmer, interview, and design

My interpretation

Simon Peyton Jones

Haskell architect, MSR-Cambridge researcher

Beautiful Code: agrees with Tony Hoare that good code should obviously have no bugs, rather than having no obvious bugs. but “looking at the bare code may not be enough, it’s not a characteristic of beautiful code that you should be able to just look at the bare code and see why it’s right. (AVL tree is one example)

漂亮的代码:

像Tony Hoare 说的那样 – 它们明显没有bug; 而不是没有明显的bug.

但是“漂亮”并不意味着看着源代码就能马上读懂。例如 AVL 树, 光看代码你不懂为什么这些子树要转来转去。但是如果你理解了它的核心思想，看到它维护了这个不变量 (invariant) 从而保证 log 级的访问速度，你就会说，”啊，明显理当如此。”

Peter Norvig

In charge of Research at Google, NASA.

Made fun of PowerPoint AutoContent Wizard

Advice to school:

Teach more on team work. “when I was in school, working as a team was called cheating”.

Successful programmer:

The bravado and willingness to “go ahead” with incomplete but essential info.

Interview:

I don’t like the trick puzzle questions. It’s important to have someone that you can get along with. More, Can they technically do what they said they can do? You really want to have people write code on the board.

XP, pair programming:

10% of the time is to share is important, but if doing it most of the time, it won’t be as effective.

UML:

I never liked any of these UML-type of tools. If you can’t do it in the language itself that’s a weakness of the language.

学校教育:

应该教更多的团队合作，“我上学的时候，团队合作被认为是作弊” (现在有些学校还是这样)。

成功的程序员:

他们更多的是“我只要懂得我需要的，就可以开始干活了”，而不是“我得完全理解某个领域，才能开始”。

面试:

不喜欢用智力题目，要依赖于面对面的问答来判断这个应聘者是否能够和团队合得来，更重要的是，让他们在黑板上写代码，看看他们是否真的能“说到做到”。

XP, 结对编程:

10% 的时间用来交流是很重要的，但是如果大部分时间都用来结对，那效率不会太高。

UML:

我从来不喜欢这类工具，如果你不能在计算机语言中表达(UML 要表达的东西)，那这是这种语言的弱点。

Guy Steele

Help created Common Lisp and Scheme, Emacs

Code writing:

When you are writing code you’re writing as much for human readers as for the computer.

If efficiency is important, I’ll often resort to a trick. And then I realize that will mislead a human. And you have to comment it or do something to flag that, to make it more readable.

代码:

当你写代码的时候，你写给机器看，同时也写给人看。

如果效率很重要，我会用一些小技巧。这些技巧会误导读代码的人，你得加上注释，或者类似的东西标注一下，让它更可读。

Peter Norvig 同学在NASA 工作的时候，参与了NASA 的一个著名事故的调查 ( 1999 年“火星气候卫星” 因导航出现重大错误而坠入火星大气层)。从他在这本书的问答中，我们可以看到一个大略的错误发生过程:

1) 软件外包公司对于 mission-critical 的软件模块有很完备的检查和测试，但是对于其他模块则没有完备的管理。

2) 程序员写了一个不重要的log 功能，其中用英制 (磅* 英尺) 表示力, 但是 NASA 用“牛顿”= 千克*米/(秒*秒)

3) 外包公司接到一个新的工程，他们进行了软件重用，log 功能中记录的力被重用为导航功能的输入参数，成为 mission-critical 的模块。 //错误: 一个模块从 non-mission-critical 变成 mission-critical 没有经历必要的复审和测试。

4) 这个新的工程由发包公司 Lockheed (洛克希德公司) 交给了客户 JPL (喷气推进实验室)

5) 火箭带着卫星发射了，在10个月的飞行中，JPL 可以每天两次启动小推进器，来调整太空船的航向，在这一过程中，有人发现了导航功能的一些不正常现象, 于是 -

a. JPL 发邮件给 Lockheed, 说 – 这个模块有些参数看起来好像不正常…

b. Lockheed 回邮件...

c. JPL 再发邮件…

d. 最后没有人再发邮件了

e. JPL的同志认为， Lockheed 的同志们估计已经搞定了。

f. Lockheed 的同志认为， JPL 的同志们没再追问这个问题，可能已经不是问题了。

错误: 这个问题从来没有收录到NASA 的错误跟踪系统 (Bug tracking system)，只是在email 中交流，导致最后没有人对这个问题负责。在错误跟踪系统中，总得有一个人“拥有”这一个bug，这样可以避免推诿责任。 (MSF 也很重视这一点)

十个月之后， 1999年9月23 日，卫星抵达火星大气层，错误的导航参数造成卫星坠入大气层烧毁。单单卫星的造价就高达一亿两千五百万美元。

顶级程序员的心得 Coders at Work (I)

关心 — Wed, 23 Dec 2009 03:09:33 GMT

正在读 “Coders at Work”, 对15 位顶级程序员的采访，总共600页。从采访的模式看，有点像“艺术人生”，一般都是音乐起，讲小时候的故事，你怎么开始写程序的? (Brad 同学 5 岁开始写) ；不过后来并没有神秘嘉宾上场，也没有声泪俱下的宣泄。无论如何，这些看似冗长的问答中有不少精辟的言论。我摘录了一些关于挑选，面试程序员，优秀程序员的特点，和程序设计的句子。下面是前6个程序员的心得，和我的几句解释：

Coder

What they say about good programmer, interview, and design

My interpretation

Jamie Zawinski,

LISP hacker,

early Netscape developer,

nightclub owner

Stay away from big fan of C++ templates;

Ability to argue their point is important.

Curiosity is a key skill for programmers.

There are people graduating with CS degrees who’d never written C. They started in java and they stayed there. That just seemed bizarre and wrong.

不喜欢过度崇拜C++ 模板的程序员；

程序员的表达能力，说服能力好奇心很重要；

很多学生拿到了CS 学位，但是从来没写过C 程序，他们学了Java，仅此而已。这是非常奇怪和不对的。

Brad Fitzpatrick

creator of memcached, Perlbal, MogileFS.

interview question:

Write a class to do arbitrary, bigint manipulation with multiplication and division

写一个大数的类，可以做乘除法。

Douglas Crockford

creator of JSON

Good Programmer:

They have to read Knuth (TAOCP); they are really literate in whatever language they write to other humans.

I invite the candidate to bring in a piece of code he’s really proud of and walk us thru it.

读过Knuth 的TAOCP;

有很强的文字表达能力和沟通能力。

请应聘者带自己最得意的代码来，给大家看看。

Brendan Eich,

Creator of JavaScript

hiring:

(rely on referral from team member)

Bright people like each other and can judge each other. I don’t give people puzzles to solve. We give them fairly practical problems, Not esoteric puzzles or math-y things.

(他有时通过同事的推荐来招人)

聪明的人会互相欣赏，评价。我不想通过智力题来判断程序员，我们给应聘者相当实际的问题，而不是那些奇怪的智力题或者数学题。

Joshua Bloch

Java Architect, author of “Effective Java”

About programming:

The older I get, the more I realize it isn’t just about making it work; it’s about producing an artifact that is readable, maintainable, and efficient. … it’s easier to optimized correct code than to correct optimized code.

“do you ever use UML as a design tool?”

No. I think it’s nice to be able to make diagrams that other people can understand. But honestly I can’t even remember which components are supposed to be round or square.

关于编程:

我越来越意识到写程序不是仅仅把程序写出来，而是要让你写的程序可读，可维护，并且高效。优化正确的程序要比改正已优化（但是有错）的程序要容易。

“你曾经用过UML 设计工具么?”

没有。能把设计画成图，让别人理解当然很好。但是说实话我记不起来哪些模块应该是圆形，哪些是方形。

Joe Armstrong

creator of Erlang, and OTP.

Interview question:

“what was the most fun project you ever wrote; show me the code for this stuff; how would you solve this problem?”

I’m not so hung up on what they know about language X or Y. they are either good at all languages or good at none.

You have to have a good memory to be a reasonable programmer.

面试问题:

“你写过的最好玩的项目是什么? 让我看看代码，你是怎么解决这个问题的?”

我并不一味要求他们已经知道某一两种语言。好的程序员精通一种语言后，就会触类旁通，能学好所有语言。

好记性对一个好程序员很重要。

IBM 中国研究院 Offer 之感言——能力是一种态度

silver — Tue, 01 Dec 2009 17:11:00 GMT

当我对着远程的大屏，给北京的IBM中国研究院几位面试官汇报完30分钟技术报告之后，心里忐忑不安，这已经是终面了…一关关拼得不容易，但却很精彩!

在之后的几天，很高兴接到了来自IBM两位高级经理的电话，分别给我介绍了他们部门情况和项目情况，表示我的报告“印象深刻”，“能力很突出”…真的是非常感谢他们能给我这个机会！

诀窍

我不是聪明过人的天才，但是我相信自己的研究能力，这来源于一个诀窍——我悟出一条“定律”，那就是：能力是一种态度！

简单解释如下：这世界上不缺乏聪明人，但是缺乏懂得运用自己聪明才智的人。

今天的帖子，我希望通过7个真实的故事，去诠释这条定律——能力是一种态度！

1. 我通过qq在课题组做了一次试验，将同一个问题群发给了6个成员，有3个人回复我：“这个我没遇到过，不会做啊…”；有2个去Google了下，大概告诉了解了应该怎么弄；有一个人，做程序试验了不同方法的优劣，告诉我最好的方法是什么。多年以后，对很多问题都报以“没遇到过，不会啊…”的人，和能力在积累的人，虽然一样聪明，但是差距就很大了。

2. 行人仿真系统研发的初期，我突然发现A*算法和Social Force Model特别有意思，就钻了进去，花了一些时间把它们研究透彻…当我兴致勃勃给老板介绍完各种模型算法之后，老板说：“你去给领导介绍这些模型算法是没用的，他们要的是效果，模型是无止境的…”。当时我也很沮丧，但是后来事实证明，我的“不务正业”是对的！因为智能化的动态寻路能力成为了我们系统的核心创新点，也是每次项目介绍中最得意的内容。

3. 给北京做的“城市轨道交通运营辅助决策系统”是要在08奥运前上线的，时间很紧，临近系统调试的时候，北京测试人员突然打电话说发现某些车站之间候选路径似乎少了一条…当时大家都认为可能就是边界条件问题，稍微改改就好了。我研究了下这个K短路算法(其他人负责开发的)发现竟是理论上的缺陷…

一时半会儿又没办法给领导解释清楚，我就决定重写这个部分，用数据来说明。由于时间太紧，在北京回上海的火车上看这些很多文献，凭借着良好的A*算法基础，很快设计出新的算法。通过测试发现，老算法共丢了500多条路径！（总共十几万条左右），这时候大家总算舒了一口气了…

但我并没有罢休，因为匆忙，算法速度不快。继续花了几天，将北京轨道网络中2万多OD之间清分计算时间优化到10多分钟，最后优化到1分钟（在我笔记本上）。上线调试当天，领导赞叹道：“这算法可真是又快又准啊！”

4. 还是上面这个系统的故事：当时北京路网基础数据是一个硕士负责录入的，他毕业以后，上海路网数据没人弄了，老板叫我去做。虽然只是半天时间的体力活，但是心里很不是滋味…

虽然有人劝说：“花个半天搞定算了哦！”但是我决心不用笨办法——我花了一个星期，凭借曾经开发的“二维矢量图形库”，设计出一个智能化的基础数据管理子系统，只需要在图上简单点击，然后拷入excel中的车站名称和代码，系统自动识别，然后再自动生成区间、换乘关系等等6张数据库表需要的全部数据。后来课题组利用这个工具构建了很多路网，因为非常简单，这个子系统也成为了后来863中网络客流仿真系统的基础。

5. 上物流系统课老师提到一个著名的NP问题——Vehicle Routing Problem，要求大家回去写写系统设计书。我当时就决定要开发这个系统，后来的几个星期，我发现遗传算法和自然界的规律真的是如此的吻合，达到了如痴如醉的地步，被女朋友嘲笑为：“整天关在屋里下崽…”后来结果是，我设计的遗传算法，不但能够求解最少需要多车，还能找到总里程很短的方案。

6. 在斯坦福访学主要是参与一个疏散仿真系统的研究。但是，由于有遗传算法的背景，另外一个教授介绍我参加他们的一个课题——办公大楼改造优化方案的辅助决策系统。

刚开始我认为这是一个确定性问题，因此采用A*算法得到了比较好的效果，已经可以满足项目需求了。我想为了作对比，又设计了遗传算法，居然发现在少数情况下能“变异”到更好解。大量实验后，我发现了两种算法虽然原理差别很大，数据结构上却存在内在联系，能够组合成一种具备通用性的框架，解决大量离散优化问题。

完全出于对科学问题本身的痴迷，我并没有罢手——自行设计了一种数据结构替换哈希表，将两个算法性能同时提升10倍之多（在遗传算法中提出了“花名册”的概念），后来又发明一种“交叉算法”，再次将遗传算法提升十几倍。当时测试案例的人说已经完全跟不上了（已经让他反复做了好多次了），因此最后我们paper里面的数据不是我最快的算法得到的。

7. 利用上面的“离散优化问题搜索框架”，我发现还可以解决《编程之美》中的许多问题。在大家都忙于找工作面试的时候，我却整整花了一个月关在寝室里研究《编程之美》，有时候挑战一个题目整整花去1天时间，当时我身边的人都说我“不务正业”，我自己都有点怀疑了。可是事实证明，这份研究不但证明了兴趣，还证明了我的算法能力，对后来找工作很有帮助。

结论

通过上面的故事，我想已经可以证明我这个定律了——能力是一种态度。如果要问态度是什么，那么我想是一种单纯的，没有任何功利的科学态度，对问题本身的执着。

这7个故事也可以用下面这张图串起来，一面的时候时间很短，我就打印了这个图，凭借它去打动面官。

后记

在我编程之美的学习连载里面，大家看到了很多好的点子。但是，它们都是在平时走路、吃饭、散步的时候想出来的，我这个人从来不擅长考试，女朋友嘲笑我——如果你去微软面试估计危险，因为你没有时间散步…

我曾经想过，对于一个博士，面试不一定能看出其水平，但是，如果给他30分钟PPT时间，介绍他的研究，水平就一目了然了。

真的没想到的是，在IBM的后2轮面试，全部一一印证了我曾经的设想…用PPT去演讲是我最擅长的东西，因为太多次的磨练了：）

微软的技术是我多年研究和喜爱的东西，微软也是我多年梦想的企业。但是，如今却迟疑了，IBM这份《智慧地球赢在中国》的白皮书确实令人震撼——它能够站在世界经济大环境的角度务实考虑中国的未来…

一篇热帖的解剖

关心 — Tue, 24 Nov 2009 15:49:52 GMT

上回提到《结婚相册》的快速流传，其实，不但是结婚相册，有时候网络上出现一篇似是而非，似非而是的热帖，大家就纷纷转贴，大家的朋友看了之后也热气上冲，继续转贴。。。

这篇博客 (http://blog.163.com/hawin2000@126/blog/static/390562922008109112019157/) 分析了一个题为美国兰德公司对中国人的评价的热帖，并指出，它是一篇学术文章(China and Globalization) 和一篇 BBS 帖子(最原始的出处已无此文，有好事者后来贴到了天涯) 的翻译，截肢，并强硬的嫁接。某好事者嫁接之后，给它起了一个抓人眼球的标题，于是此文名声大振，可以想象 - 美国公司，智囊，对咱中国人的评价，赶紧看看。。。真正的学术文章倒是默默无闻地在兰德公司的网站上呆着。

<tipping point / 爆破点> 这本书提到了影响事物流行的诸多因素，在中国的网络里，一个好题目 (某国人对中国人的评论，某地人如何如何)， “过激言论”(例如痛斥贵国的教育) 都能极大加快流行的速度。

偶尔看到这篇帖子和它的解剖，随手记下来。

《我和他的结婚录像和相册集》的快速传播

关心 — Sat, 21 Nov 2009 07:08:05 GMT

当你看到你的一个朋友的 Live Space 有了这个更新，你当然想看.

但是你是点击文字 “我和他的结婚录像和相册集”，还是旁边的 "心形图标"?

很多人，包括我，都点击了"心形图标", 不幸的是，这样就会把这个相册集加入你自己的收集中，然后你的朋友就会看到你的更新：

他们当然很好奇，这哥们不是还没结婚么，怎么和“他”都结婚了还有录像和相册集? 他们可以点击文字，也可以点击 "心形图标"...

于是，在下一个24小时内，更多的朋友，朋友的朋友都不自觉地参与了传播过程，这可能不是当初用户界面设计师希望的。

无独有偶，我们自己的旅游指南有这个问题：

作为一个用户，如果你想进一步了解 “亚龙湾”的情况，你是点击文字呢，还是图片? 这两个看似相似的点击有截然不同的后果。我们在强迫用户想 - 如果我要做这件事，就按图片，如果我要做那件事，就按文字。一个旅游网站，有必要搞得这么复杂么? 拜托， don't make me think!

作为一个附加题，当用户点击 “沙滩”，“潜水”等词汇时，用户期待什么结果，而我们的网站又返回了什么结果呢?

很早以前，我也写过类似的问题。

第二届C++技术大会@ 上海 - 我觉得可以去看看

关心 — Thu, 05 Nov 2009 06:53:25 GMT

[转发的宣传]

大会官方网站www.china-cpp.org。

作为软件开发语言的翘楚，C++对于现代软件的发展功不可没，特别是在系统软件开发领域，C++扮演着关键的角色。中国作为全球软件产业最具潜力的市场，越来越多的企业认识到了C++及相关系统软件技术在软件产业中举足轻重的作用。

为了推动C++及相关系统软件技术在国内的深度应用与发展，提升国内IT企业的研发水平，第二届C++技术大会定于2009年12月3日-4日在上海隆重召开。届时，来自海内外C++技术领域的近20位著名技术专家将就C++及相关系统软件开发技术的热点应用和最新发展，分享技术观点、探讨最佳研发实践。

此次大会开设的主题演讲互动讨论近20场，内容涉及大规模软件开发、程序优化、安全编程、面向对象、泛型编程、网络与服务端开发、多核与并发等多个主题。

大会时间

2009年12月03日-04日

大会地点

上海诺宝中心大酒店上海闵行区漕宝路1688号

大会议题

编号	议题
1	大规模软件开发 Large-Scale Software Development
2	程序优化 Programming Optimization
3	安全编程 Secure Programming

4	面向对象开发 Object-Oriented Development
5	泛型编程与设计 Generic Programming
6	网络与服务端开发Network & Server-Side Development
7	多核与并发编程 Multicore Parallel Programming
8	工具与应用Tools & Applications

参会人员

本届C++技术大会主要面向以下软件开发专业人士：首席技术官（CTO）、研发总监、项目经理、开发主管、系统软件开发工程师等与C++及相关系统软件开发密切相关的专业技术人员。丰富的技术讲演，专业的主题设计、经典的应用案例，软件开发相关专业人士可从大会获得C++及系统软件技术发展的趋势与热点应用，与业界顶尖专家多方位的交流机会。

演讲嘉宾

Stan Lippman
Stan Lippman是全世界公认的C++技术领袖。Stan Lippman先生从1984年开始在Bell实验室从事C++方面的工作。参与开发最初的C++编译器，致力于Cfront的各种实现，包括从1986年的版本1.1到版本3.0，并领导了2.1和3.0版本的开发组。而后又参与了Foundation研究项目中关于程序设计环境的对象模型部分。Stan Lippman先生还曾历任迪士尼动画公司的首席软件设计师、美国宇航局喷气推进实验室(JPL)的著名顾问、微软公司Visual C++开发组系统架构师。Stan Lippman先生撰写了数本享誉全球的经典书籍，包括《C++ Primer》、《Inside the C++ Object Model》、《Essential C++》、《C# Primer》，并编辑了《C++ Gems Programming Pearls from The C++ Report》。

侯捷
侯捷先生是两岸著名技术教育者，计算机图书作者、译者、书评人。著有《深入浅出MFC》、《多型与虚拟》、《STL源码剖析》、《无责任书评》三卷，译有众多脍炙人口的高阶技术书籍，包括Meyers所著的“Effective C++”系列。侯捷先生还兼任教职于元智大学（台湾）、同济大学（大陆）、南京大学（大陆）。

还有很多厉害人物，见官网介绍。

[zz] 钱学森谈大学创新精神

关心 — Wed, 04 Nov 2009 22:08:52 GMT

转贴，并请抄送周济，贵仁同志。

http://www.chinanews.com.cn/gn/news/2009/11-05/1947844.shtml

...

我是在上个世纪30年代去美国的，开始在麻省理工学院学习。麻省理工学院在当时也算是鼎鼎大名了，但我觉得没什么，一年就把硕士学位拿下了，成绩还拔尖。其实这一年并没学到什么创新的东西，很一般化。后来我转到加州理工学院，一下子就感觉到它和麻省理工学院很不一样，创新的学风弥漫在整个校园，可以说，整个学校的一个精神就是创新。在这里，你必须想别人没有想到的东西，说别人没有说过的话。拔尖的人才很多，我得和他们竞赛，才能跑在前沿。这里的创新还不能是一般的，迈小步可不行，你很快就会被别人超过。你所想的、做的，要比别人高出一大截才行。那里的学术气氛非常浓厚，学术讨论会十分活跃，互相启发，互相促进。我们现在倒好，一些技术和学术讨论会还互相保密，互相封锁，这不是发展科学的学风。你真的有本事，就不怕别人赶上来。我记得在一次学术讨论会上，我的老师冯·卡门讲了一个非常好的学术思想，美国人叫“good idea”，这在科学工作中是很重要的。有没有创新，首先就取决于你有没有一个“good idea”。所以马上就有人说：“卡门教授，你把这么好的思想都讲出来了，就不怕别人超过你？”卡门说：“我不怕，等他赶上我这个想法，我又跑到前面老远去了。”所以我到加州理工学院，一下子脑子就开了窍，以前从来没想到的事，这里全讲到了，讲的内容都是科学发展最前沿的东西，让我大开眼界。

我本来是航空系的研究生，我的老师鼓励我学习各种有用的知识。我到物理系去听课，讲的是物理学的前沿，原子、原子核理论、核技术，连原子弹都提到了。生物系有摩根这个大权威，讲遗传学，我们中国的遗传学家谈家桢就是摩根的学生。化学系的课我也去听，化学系主任L·鲍林讲结构化学，也是化学的前沿。他在结构化学上的工作还获得诺贝尔化学奖。以前我们科学院的院长卢嘉锡就在加州理工学院化学系进修过。L·鲍林对于我这个航空系的研究生去听他的课、参加化学系的学术讨论会，一点也不排斥。他比我大十几岁，我们后来成为好朋友。他晚年主张服用大剂量维生素的思想遭到生物医学界的普遍反对，但他仍坚持自己的观点，甚至和整个医学界辩论不止。他自己就每天服用大剂量维生素，活到93岁。加州理工学院就有许多这样的大师、这样的怪人，决不随大流，敢于想别人不敢想的，做别人不敢做的。大家都说好的东西，在他看来很一般，没什么。没有这种精神，怎么会有创新！

加州理工学院给这些学者、教授们，也给年轻的学生、研究生们提供了充分的学术权力和民主氛围。不同的学派、不同的学术观点都可以充分发表。学生们也可以充分发表自己的不同学术见解，可以向权威们挑战。过去我曾讲过我在加州理工学院当研究生时和一些权威辩论的情况，其实这在加州理工学院是很平常的事。那时，我们这些搞应用力学的，就是用数学计算来解决工程上的复杂问题。所以人家又管我们叫应用数学家。可是数学系的那些搞纯粹数学的人偏偏瞧不起我们这些搞工程数学的。两个学派常常在一起辩论。有一次，数学系的权威在学校布告栏里贴出了一个海报，说他在什么时间什么地点讲理论数学，欢迎大家去听讲。我的老师冯·卡门一看，也马上贴出一个海报，说在同一时间他在什么地方讲工程数学，也欢迎大家去听。结果两个讲座都大受欢迎。这就是加州理工学院的学术风气，民主而又活跃。我们这些年轻人在这里学习真是大受教益，大开眼界。今天我们有哪一所大学能做到这样？大家见面都是客客气气，学术讨论活跃不起来。这怎么能够培养创新人才？更不用说大师级人才了。

...

方曲序列——一道有趣的搜索核心研发试题

silver — Wed, 04 Nov 2009 07:44:00 GMT

问题

假设有4×4的方阵（里面可放字符串），给现定一个序列，检查这个序列是否在方阵的“连续对角线”上面：

例如：从左上到右下的连续对角线序列可能是：

1 2 5 9 6 3 4 7 10 13 14 11 8 12 15 16
1 5 2 3 6 9 13 10 7 4 8 11 14 15 12 16

分析

刚刚看到此题目，可能有点晕，“连续对角线”是啥？仔细一看，其实就是方阵里面的曲线序列（如下图），我就叫它“方曲序列”吧。

再一想，这样的序列应该有8条。考试的时候时间紧，只能大概写写思路了，回来用VS08调试着搞感觉好很多:( 不适合应试哈哈

我们来分析下，这个题目的关键是，要把握住曲线运动其实是两个方向：

沿斜线运动
斜线平移

那么，再看这些斜线的长度分别为 1 2 3 4 3 2 1，那么我们在枚举到这个序列之和的这些关键带点的时候：

需要平移斜线
需要翻转斜线上的运动方向

解法

有了思路，借助VS08 强大的调试功能，我写了8个方向，通用的，O(N)（N是序列长度）复杂度的 “方曲序列” 函数：

运行函数：PrintWinding(4);

就可以得到 n=4 的时候8条“方曲序列”：

1 2 5 9 6 3 4 7 10 13 14 11 8 12 15 16
13 14 9 5 10 15 16 11 6 1 2 7 12 8 3 4
4 3 8 12 7 2 1 6 11 16 15 10 5 9 14 13
16 15 12 8 11 14 13 10 7 4 3 6 9 5 2 1
1 5 2 3 6 9 13 10 7 4 8 11 14 15 12 16
13 9 14 15 10 5 1 6 11 16 12 7 2 3 8 4
4 8 3 2 7 12 16 11 6 1 5 10 15 14 9 13
16 12 15 14 11 8 4 7 10 13 9 6 3 2 5 1

代码如下：

        static void PrintWinding(int n)
        {
            var square = new string[n, n];
            for (int i = 0; i < square.Length; i++)
                square[i / n, i % n] = (i + 1).ToString();

            var p = new int[] { 0, n - 1 };
            for (int sign = -1; sign <= 1; sign += 2)
                for (int i = 0; i < p.Length; i++)
                    for (int j = 0; j < p.Length; j++)
                        PrintWinding(square, p[ i], p[j], sign);
        }

其中：

        static void PrintWinding(string[,] square, int x0, int y0, int sign)
        {
            int n = square.GetLength(0);//边长

              int xn = Math.Abs(x0 - n + 1);//目标点x
            int yn = Math.Abs(y0 - n + 1);//目标点y

            int dx = Math.Sign(xn - x0);//平移方向x增量
             int dy = Math.Sign(yn - y0);//平移方向y增量

             int stepX = -dx * sign;//斜线方向x增量
             int stepY = dy * sign;//斜线方向y增量

             int flag = sign == 1 ? 0 : 1;

            int x = x0, y = y0;
            int s = 1, k = 1, sum = 1;
            for (int i = 0; i < square.Length; i++)
            {
                Console.Write(square[y, x] + " ");

                if (i + 1 < sum)
                {
                    x += stepX;
                    y += stepY;//沿斜线方向移动
                  }
                else if (i + 1 == sum)
                {
                    stepX *= -1;
                    stepY *= -1;//斜线方向掉头

                      if (k == n) flag = Math.Abs(1 - flag);

                   if ((k & 1) == flag) x += dx;//平移
                      else y += dy;//平移

                     if (s < n) k++;//前半三角
                     else k--;//后半三角

                     sum += k;
                   s++;
                }
            }
            Console.WriteLine();
        }

讨论

有了8个方向，通用的“方曲序列” 函数，我们就不难写出测试某序列是否在”连续对角线“上面的函数了，可以考虑采用PLINQ写个并行算法，多个核的话每个核测试一个（些）方向的序列，找到就返回true。

编程之美——差之毫厘

silver — Tue, 03 Nov 2009 12:15:00 GMT

问题

不理解计算机底层运作机制，有时候会写出很费的代码，这说明了两个问题：

底层透明性做得还不够好；
在这样的技术条件下，我们还需要去多了解底层。

来看两个有趣的例子，问题需求是：求一个二维整数数组的和，非常简单吧？

本帖通过4个解法（后两个是并行算法），说明微小的改动对程序运行效率的巨大影响。

*注：需要注意的是，测试结果是在release下的，debug下代码未优化。

解法一

        static int SumA(int[,] array, int n)
        {
            int sum = 0;
            for (int x = 0; x < n; x++)
                for (int y = 0; y < n; y++)
                {
                    sum += array[y, x];
                }
            return sum;
        }

运行测试函数：Test(SumA, array, n);

得到结果：

SumA: 1073741824, 20.4777841s

其中：

测试函数为：

        static void Test(SumDele Sum, int[,] array, int n)
        {
            int sum = 0;
            Stopwatch watch = new Stopwatch();
            watch.Start();
            for (int i = 0; i < n; i++) sum += Sum(array, n);
            watch.Stop();
            Console.WriteLine("{0}: {1}, {2}s",

            Sum.Method.Name, sum, watch.Elapsed.TotalSeconds);
        }

        delegate int SumDele(int[,] array, int n);

    初始条件为：

            int n = 1<<10;
            int[,] array = new int[n, n];

            for (int x = 0; x < n; x++)
                for (int y = 0; y < n; y++)
                    array[x, y] = 1;

解法二

就改动一行：

        static int SumB(int[,] array, int n)
        {

            ……
                    sum += array[x, y];

            ……
        }

再看运行结果：

SumB: 1073741824, 4.8847906s

在我的机子上居然提高了近4倍多！！（每次运行稍有差异，一般在3~5倍）有些机器甚至更高。

分析

在现在的经济和技术条件下，计算机中存储设备的容量和速度是”鱼和熊掌“的关系，没办法两全，人们只好采用了多级结构来解决：快的、贵的、小的存储设备靠近CUP，反之远离：

在这种结构中，上层会通过缓存部分下层中数据副本来提高访问速度：CUP要去找一个数据，先从近的找，没有”命中“再往下继续。那么CUP访问到一个数据往往也会将其附近的数据一并缓存，可称为Locality特性，在上面例子中，由于：

二维数组在内存中是按行存放的；
CUP会在其缓存附近的数据。

因此，按行循环的时候利用到了大量缓存数据，效率高。这也说明，如果二维数组是按列存放的机器里面就刚好反过来。

解法三

随着多核处理器的逐渐普，为了充分利用多核的硬件资源，微软正在研发下一代并行系列框架（Parallel FX）。目前微软已经将PLINQ和TPL包含在Parallel Extension中，我们可用并行算法来求解下试试：

        static int SumC(int[,] array, int n)
        {
            int m = Environment.ProcessorCount;
            int[] result = new int[m];

            int step = n / m;
            int leftover = n % m;

            Parallel.For(0, m, (i) =>
            {
                int from = i * step;
                int to = from + step + (i < m - 1 ? 0 : leftover);

                for (int x = from; x < to; x++)
                    for (int y = 0; y < n; y++)
                    {
                        result[ i ] += array[x, y];
                    }
            });

            return result.Sum();
        }

这个算法根据机器处理器的数量将任务分块，最后加总结果。我机器的是双核的，因此分了两块并行算。

运行程序得到结果为：

SumC: 1073741824, 10.8568457s

奇怪的是，为何没有提高？？反而差了？

分析

这是由于False Sharing导致的。由于每个核的L1缓存互相独立，因此CPU必须有一种机制，能够确保一个核在它的L1 Cache中改动一个数据后，其他核内L1 Cache中包含这个数据的整个Line就会过期。这意味着其他核在读取地址相同，或者是接近的数据时会遇到L1 Cache Miss。CPU的这种同步机制就是MESI协议。

由于int[] result很小，会被多个CPU缓存，然而一个CPU改动了其值就会导致其它CPU缓存中的副本过期，下次就需要重新加载，因此损失了很多性能…

解法四

解决这个问题，只需要改动3行，将中间结果另外用一个变量保存：

        static int SumD(int[,] array, int n)
        {

         ……
                int temp = 0;
                for (int x = from; x < to; x++)
                    for (int y = 0; y < n; y++)
                    {
                        temp += array[x, y];
                    }
                result[ i ] = temp;

         ……
        }

运行程序得到结果：

SumD: 1073741824, 2.5991568s

这个例子说明了几个问题：

首先，我们需要理解计算机底层的运作机制。
但是，这并不代表应该“刀耕火种”。利用PLINQ，我们甚至都不需要显式地去关心多线程就可以实现并行求解，看上去是“语法糖”，但是它们会逐步改变我们编程的思维方式。

最后将四个解法结果放一起：

SumA: 1073741824, 20.4777841s
SumB: 1073741824, 4.8847906s
SumC: 1073741824, 10.8568457s
SumD: 1073741824, 2.5991568s

参考资料

计算机体系结构与程序性能

Running Queries On Multi-Core Processors

闲话

最近做了某知名网络公司的笔试题，感觉如果公司实际开发也是这么底层的话，那么个人认为其效率不是很高，原因在于：

很多SDE可能在解决同样的问题；
很多SDE可能在犯着同样的错误；
很多TE可能在查找着同样的BUG；

我遇到的几个例子：其招聘网站录入信息时候出现几个BUG，其软件登录也会弹出个找不到文件错误…

一些常用集合算法——之幂集合生成

silver — Sun, 01 Nov 2009 13:50:00 GMT

问题

在开发过程中常常需要处理集合，因此我写了一些常用算法，贴出大家提提意见。

本帖介绍幂集合生成算法。

解法一

思路为：

构造初始序列00…0
如果全部为11…1，则停止
寻找位置最低的0，将其变1
将刚刚那个0前面的都变0

这里可以用到前面帖子构造的“动态有序集合”——BinHeap，共设置两个：一个用于保存0的位置，一个用于保存1的位置：

    public static List<T[]> Subset<T>(IList<T> list)
        {
            var zeros = new BinHeap<int>(false);//0的位置集合（因为不需要建立索引，传入false)
            var ones = new BinHeap<int>(false);//1的位置集合

            List<T[]> subsets = new List<T[]>();
            for (int i = 0; i < list.Count; i++) zeros.Push(i);//初始状态全0

            while (ones.Count < list.Count)
            {
                var i = zeros.Pop();
                while (!ones.IsEmpty && i > ones.Peek()) zeros.Push(ones.Pop());
                ones.Push(i);

                i = 0;
                var arr = new T[ones.Count];
                foreach (var p in ones) arr[i++] = list[p];
                subsets.Add(arr);
            }
            return subsets;
        }

运行结果

输入abcde，得到2^n – 1 个子集：

1:a 2:b 3:ab 4:c 5:ac 6:bc 7:acb 8:d 9:ad 10:bd 11:adb 12:cd 13:adc 14:bdc 15:abcd 16:e

17:ae 18:be 19:aeb 20:ce 21:aec 22:bec 23:abce 24:de 25:aed 26:bed 27:abde 28:ced 29:acde 30:bcde 31:abdec

讨论

这里也没有用一般算法的“扫描”的办法，而是利用的两个“动态有序集合”解决了问题，效率提高很多。

解法二

当然，这个问题也肯定可以用前面连载里面广泛用到的“分级排列（组合）法”。

    public static List<T[]> Subset2<T>(IList<T> list)
        {
            List<T[]> subsets = new List<T[]>();
            var heap = new List<T[]>[list.Count + 1];//0～n级的组合

            for (int i = 0; i < heap.Length; i++) heap[ i ] = new List<T[]>();
            heap[0].Add(new T[0]);

            for (int i = 0; i < list.Count; i++)
                for (int j = i + 1; j > 0; j--)
                    foreach (var p in heap[j - 1])
                    {
                        var subset = new T[p.Length + 1];
                        p.CopyTo(subset, 0); subset[p.Length] = list[ i ];
                        heap[j].Add(subset);//更新j级

                         subsets.Add(subset);
                    }
            return subsets;
        }

运行结果

1:a 2:ab 3:b 4:abc 5:ac 6:bc 7:c 8:abcd 9:abd 10:acd 11:bcd 12:ad 13:bd 14:cd 15:d

16:abcde 17:abce 18:abde 19:acde 20:bcde 21:abe 22:ace 23:bce 24:ade

25:bde 26:cde 27:ae 28:be 29:ce 30:de 31:e

可以看出，顺序稍微有些差异，但结果相同，解法二效率稍高。

一些常用集合算法——之组合生成

silver — Sun, 01 Nov 2009 13:40:00 GMT

问题

在开发过程中常常需要处理集合，因此我写了一些常用算法，贴出大家提提意见。

本帖介绍组合生成算法。

分析

开一个数组，数组元素的值为1表示其下标代表的数被选中，为0则没选中。

首先初始化，将数组前m个元素置1，表示第一个组合选中前m个元素。

然后找到从左到右的第一个“10”组合，将其变为“01”组合，

同时将其左边的所有“1”全部移动到数组的最左端，例如：

1 1 1 0 0 //1,2,3

1 1 0 1 0 //1,2,4

1 0 1 1 0 //1,3,4

0 1 1 1 0 //2,3,4

1 1 0 0 1 //1,2,5

1 0 1 0 1 //1,3,5

0 1 1 0 1 //2,3,5

1 0 0 1 1 //1,4,5

0 1 0 1 1 //2,4,5

0 0 1 1 1 //3,4,5

解法

具体实现的时候，不需要每次“从左往右扫描”——我们可以这样考虑：每次将“10”变为“01”，可能产生新的翻转位置，那么就只需要记录新的翻转位置。

 public static List<T[]> Combination<T>(IList<T> list, int n)
    {

        n = Math.Min(list.Count, n);

        var combs = new List<T[ ]>();

        var selection = new Dictionary<int>(n);//用于记录被选中元素的位置
         Stack<int> pins = new Stack<int>();//记录翻转位置
         for (int i = 0; i < n; i++) selection.TryAdd(i);//初始的时候选中前n个元素
         if (n < list.Count) pins.Push(n - 1);//初始翻转位置

         while (true)
        {
             <添加生成的组合>

             if (pins.Count == 0) break;

             var i = pins.Pop();
             selection.Remove(i);//去掉i
             var j = i + 1;
             selection.TryAdd(j);//选中j
                
             if (j + 1 < list.Count && !selection.ContainsKey(j + 1))
                pins.Push(j);//增加翻转点

               bool adjusted = false;
             <将i左边这些连续的1全部移动到最左>

             if (!adjusted && i - 1 >= 0 && selection.ContainsKey(i - 1))
               pins.Push(i - 1);//增加翻转点 
         }
       return combs;
   }

其中：

<添加生成的组合>代码为：

        int cnt = 0;
       var newComb = new T[ n ];
       foreach (var index in selection) newComb[cnt++] = list[index];
       combs.Add(newComb);

<将i左边这些连续的1全部移动到最左>代码为：

       if (i >= 2)
      {
          int z = 0;//从左数0的数量
            while (!selection.ContainsKey(z)) z++;
           if (z > 0 && z < i)
           {
              var m = Math.Min(z, i - z);
              for (int k = 0; k < m; k++) selection.TryAdd(k); //选中k
              for (int k = i - 1; k >= i - m; k--) selection.Remove(k); //去掉k
              pins.Push(i - z - 1);
              adjusted = true;
           }
       }

运行结果

输入abcdef，选3个：

1:abc 2:dab 3:dac 4:dbc 5:abe 6:ace 7:bce 8:ade 9:bde 10:cde 11:abf 12:acf 13:bcf 14:adf 15:bdf 16:cdf 17:aef 18:bef 19:cef 20:def

讨论

网上大多是“扫描算法”，这里用“翻转点”做了改进——不断构造新的翻转点，直到没办法再翻转。

一些常用集合算法——之全排列生成

silver — Sun, 01 Nov 2009 13:10:00 GMT

问题

在开发过程中常常需要处理集合，我写了一些常用算法，贴出大家提提意见

本帖是最简单的全排列生成算法，因为全排本来列就很费，所以以简洁为重，没太多考虑效率。

解法

        public static List<T[]> Permutation<T>(IEnumerable<T> list)
        {
            List<T[]> permutations = new List<T[]>();

            Permutation(new List<T>(list), 0, permutations);

            return permutations;
        }
        static void Permutation<T>(List<T> list, int h, List<T[]> permutations)
        {
            if (h == list.Count - 1)
            {
                permutations.Add(list.ToArray());
                return;
            }

            for (int i = h; i < list.Count; i++)
            {
                Swap(list, h, i);
                Permutation(list, h + 1, permutations);
                Swap(list, h, i);//撤销交换

              }
       }
        static void Swap<T>(List<T> list, int i, int j)
        {
            if (i != j)
            {
                var temp = list[ i ];
                list[ i ] = list[j];
                list[j] = temp;
            }
        }

运行结果

输入abcd：

1:abcd 2:abdc 3:acbd 4:acdb 5:adcb 6:adbc 7:bacd 8:badc 9:bcad 10:bcda 11:bdca 12:bdac 13:cbad 14:cbda 15:cabd 16:cadb 17:cdab 18:cdba 19:dbca 20:dbac 21:dcba 22:dcab 23:dacb 24:dabc

讨论

算法思路很简单，就是一位一位去填，和全排列计算的思路一致。

此算法在只需要输出或者测试排列的问题中，可以不去生成所有排列的实例，从而节约大量内存。

不用API构造简单自旋锁

silver — Wed, 28 Oct 2009 23:16:00 GMT

问题

想必大家都记得《编程之美》“双线程下载”的精彩例子。这里我们来看一个类似的例子。

分析

由于采用“挂起/唤醒”线程的方式加锁，往往涉及到“用户态/核心态”切换，导致不小的性能损失，因此人们发明了自旋锁，在一些分布式应用程序中，性能得到了10～1000倍的提升。

解法

这里我们来看一个最简单的，不用API构造的自旋锁：

   class 简单自旋锁
    {
        int c1 = 0, c2 = 0, who_wait;

        void WrokA()
        {
            int taskCnt = 0;
            while (taskCnt++ < 5)
            {
                c1 = 1;//请求进入临界区
                    who_wait = 1;
                while (c2 == 1 && who_wait == 1) ;
                DoSomeWork(taskCnt + "A", ref c1);
            }
        }
        void WrokB()
        {
            int taskCnt = 0;
            while (taskCnt++ < 5)
            {
                c2 = 1;
                who_wait = 2;
                while (c1 == 1 && who_wait == 2) ;
                DoSomeWork(taskCnt + "B", ref c2);
            }
        }
        void DoSomeWork(string who, ref int c)
        {
            try
            {
                DoSomeWork(who);
            }
            catch (Exception e)
            {
                Console.WriteLine(e.Message);
            }
            finally
            {
                c = 0;//离开临界区
               }
        }
        void DoSomeWork(string who)
        {
            Console.WriteLine(who + " enters critical section...");

            Console.Write(who + " is working");
            for (int i = 0; i < 10; i++)
            {
                Thread.Sleep(300);
                Console.Write(".");
            }
            Console.WriteLine();

            Console.WriteLine(who + " leaves critical section... \n");
        }

        public void Test()
        {
            var threadA = new Thread(new ThreadStart(WrokA));
            var threadB = new Thread(new ThreadStart(WrokB));

            threadA.Start();
            threadB.Start();
        }
    }

运行程序，得到如下结果：

1A enters critical section...

1A is working..........

1A leaves critical section...

1B enters critical section...

1B is working..........

1B leaves critical section...

2A enters critical section...

2A is working..........

2A leaves critical section...

2B enters critical section...

2B is working..........

2B leaves critical section...

……

讨论

自旋锁需要解决如下问题：

1. 没有试图进入临界区的线程不得阻止其它线程进入；

2. 不能让某线程“刚好每次都进入临界区”，某线程“刚好每次都等待”；

3. 不能出现互相等待的“死锁”；

4. 不能出现进入临界区之前，线程互相“谦让”，导致不确定谁进入的“活锁”。

5. 某线程出错不能影响其它线程。

这个例子只是双线程，我们以后再研究多线程的例子。

汽车加油问题——一道迷惑的面试题

silver — Wed, 28 Oct 2009 00:05:00 GMT

问题

一辆载油500升的汽车从A开往1000公里外的B，已知汽车每公里耗油量为1升，A处有无穷多的油，其他任何地点都没有油，但该车可以在任何地点存放油以备中转，问从A到B最少需要多少油？

分析

这道题目初一看觉得方案太灵活，有点晕，网上所有对此题目的答案千篇一律的是：

题目可归结为求数列 an=500/(2n+1) n=0,1,2,3......的和Sn什么时候大于等于1000,解得n>6

当n=6时，S6=977.57

所以第一个中转点离起始位置距离为1000-977.57=22.43公里

所以第一次中转之前共耗油 22.43*(2*7+1)=336.50升

此后每次中转耗油500升

所以总耗油量为7*500+336.50=3836.50升

看起来很有道理，但是又没有说明为什么？害我抓破脑皮去想：这是为什么？怎么证明的？

不过我们简单推下：3836.50 - 7*(500 - 2*22.43) ＝ 650.52，也就是说第一次中转跑7次会剩下650.52，证明这个答案是错误的！

后来我猜想出一种解释，首先我们需要抓住几个关键点：

1. 运输距离要尽量短，也就是说，我们的方案肯定是先从起点将所有需要的油搬到第一个x公里外的转运点，然后再以此类推，不能来回奔波于多个转运点。

2. 运输效率要尽可能高，也就是说，尽量以最大运输能力去跑——不要因为1、2公升油再跑一趟。

3. 相邻转运点之间跑的次数一定是奇数次。

由此，我们可以倒过来考虑：

1. 车到1000公里外的终点的时候，只需要放0的油在那里，转运次数1，可以求得距离是500；

2. 车到500公里外的转运点的时候，需要放500的油在那里，转运次数3，那么如何保证3次都是运输效率最高的呢？通过保证运运输效率最高，可以求得转运点的距离。上面也是这样求的。

3. 以此类推… 中转次数 1 3 5 7 …

解法一

        /// <summary>
        ///计算在距离x的地方放a的油，跑2n+1次运输效率最高的距离
        /// </summary>
        double Distance(double a, int n)
        {
            return (tankLimit * (n + 1) - a) / (2 * n + 1);
        }//x为距离，a = k(tankLimit - 2x) + 500 – x

        /// <summary>
        /// 在距离x的地方，存放amount的油需要跑的总次数
        /// </summary>
        int Trip(double x, double amount)
        {
            int n = 0;
            while (true)
            {
                var a1 = 2 * n * (tankLimit - 2 * x);//来回运的油量
                var a2 = tankLimit - x;//最后一次运的油量
                var diff = a1 + a2 - amount;
                if (diff >= 0 || -diff <= 0.0001) return 2 * n + 1;//避免计算误差
                n++;
            }
        }

        void Transport()//倒推中转
        {
            int k = 0;
            double a = 0, d = 0;//a是每次中转的总耗油量，d是距离累计

            while (d < 1000)
            {
                var last_a = a;
                var x = Distance(a, 2 * k);
                if (d + x <= 1000)
                {
                    a += (2 * k + 1) * x;
                    k++;
                }
                else
                {
                    x = 1000 - d;
                    a += Trip(x, a) * x;
                }
                d += x;

            Console.WriteLine("a = {0:F} x = {1:F} Trip = {2}", a, x, Trip(x, last_a));
            }
        }

运行程序，可以求得：

a = 500.00 x = 500.00 Trip = 1

a = 1100.00 x = 200.00 Trip = 3

a = 1877.78 x = 155.56 Trip = 5

a = 2751.28 x = 124.79 Trip = 7

a = 2888.89 x = 19.66 Trip = 7

可以看出，如果采用这种运输方法，已经比上面网上流传的答案3836.50升少了很多了。但是，这种1 3 5 7…的运输方法就是最优的么？

解法二

或许我们并不需要1 3 5 7…这样递增这么快，1 3 3 3 5 5 5也可能是很好的方法，因此将程序小改动下：

        double Transport(int factor)
       {
                …
                var lastA = a;
                var x = Distance(a, 2 * k);
                if (x == 0) { k++; continue; }
                if (d + x <= 1000)
                {
                    a += (2 * k + 1) * x;
                    if (cnt++ % factor == 0) k++;
                }
                …

然后去计算factor从1～100的情况下耗油量分别是：

1 2888.88888888889

2 2507.65432098765

3 2376

4 2350.4

5 2340.16

6 2336.064

7 2334.4256

8 2333.77024

9 2333.508096

10 2333.4032384

11 2333.36129536

12 2333.344518144

13 2333.3378072576

14 2333.33512290304

15 2333.33404916122

可以看出，factor >15以后就趋于稳定了。

讨论

由此可以看出，不可以盲目迷信别人的解法（当然包括我现在的解法：）做到这里我们可以猜测，解法二也不能说就是最优了，可能存在一些更加优秀的序列——哈哈，说到这里，大家应该想到，这种问题最适合遗传算法了！我暂时没时间了，如果有兴趣的同学找到更优秀的解法麻烦通知我：）

时分秒针重合——看似简单的面试题

silver — Tue, 27 Oct 2009 23:06:00 GMT

问题

在一天的24小时之中，时钟的时针、分针和秒针完全重合在一起的时候有几次？都分别是什么时间？你怎样算出来的？

分析

初看此问题觉得很简单，但是网上各种版本的答案都各不相同，那到底谁是对的呢？

我们可以这样考虑——龟兔赛跑，跑得慢的针终归会被快的一圈一圈超过。那么，分别求出时针分针、分针秒针的重合时间，然后再看是否有相同。

这里都不难，关键是有一个陷阱！请问大家，我说“一圈一圈超过”，是不是每圈都被超过？

先求角速度：（度/秒）

1. 时针：w1 = 360 / 12*3600 = 1/120 d/s

2. 分针：w2= 360 / 3600 = 0.1 d/s

3. 秒针：w3 = 360 / 60 = 6 d/s

设3个针当中，快针角速度为wf，慢针角速度为ws。若快针在一天24小时中，转k = 0, 1, 2, 3, … , n圈的时候，重合慢针的时间为t，则：

wf * t - k*360 = ws*t – [ws/wf * k] *360

t = 360*( k - [k*ws/wf] ) / (wf - ws)

代码如下：

        List<double> Times_Overlap(double wf, double ws)
        {
            var n = (int)(24 * 3600 * wf / 360);
            var times = new List<double>(n);
            for (int k = 0; k < n - 1; k++)
            {
                var t = 360 * (k - (int)(k * ws / wf)) / (wf - ws);
                //t = Math.Round(t);
                if (times.Count == 0 || times[times.Count - 1] != t) times.Add(t);
            }
            return times;
        }

运行程序可以得到（显示出來的时间按秒取整了）：

时针分针重合的时间 Times_Overlap(w2, w1)：

(1) 00:00:00, (2) 01:05:27, (3) 02:10:54, (4) 03:16:21, (5) 04:21:49, (6) 05:27:16, (7) 06:32:43, (8) 07:38:10, (9) 08:43:38, (10) 09:49:05, (11) 10:54:32, (12) 12:00:00, (13) 13:05:27, (14) 14:10:54, (15) 15:16:21, (16) 16:21:49, (17) 17:27:16, (18) 18:32:43, (19) 19:38:10, (20) 20:43:38, (21) 21:49:05, (22) 22:54:32,

分针秒针重合的时间 Times_Overlap(w3, w2)：

(1) 00:00:00, (2) 00:01:01, (3) 00:02:02, (4) 00:03:03, (5) 00:04:04, (6) 00:05:05, (7) 00:06:06, (8) 00:07:07, (9) 00:08:08, (10) 00:09:09, (11) 00:10:10, (12) 00:11:11, (13) 00:12:12, …… 23:53:53, (1412) 23:54:54, (1413) 23:55:55, (1414) 23:56:56, (1415) 23:57:57, (1416) 23:58:58,

时分秒针重合的时间：

00:00:00 12:00:00

讨论

通过Times_Overlap(w2, w1) 算出所有时针和分针重合时间；通过Times_Overlap(w3, w2)算出所有分针和秒针重合时间，可以得到总共重合2次：0点和12点。

需要注意的是，快针和慢针每在0点重合，下一圈快针和慢针将不会相遇。因此，时针和分针相遇22次，时针和秒针相遇1438次，分针和秒针相遇1416次。

巧用A*求解大型01规划

silver — Fri, 16 Oct 2009 02:18:00 GMT

A*算法在路径规划中有非常重要的地位，我在很多项目里面都用到了这个算法，下图是我的一个程序，试验大规模Agent实时寻路情况下算法性能：

摘抄一段原来一篇论文对A*介绍：

Pathfinding is a core component of many intelligent agent applications, ranging in diversity from commercial computer games to robotics. Characters should move in some goal-directed manner, and the program must be able to identify a good path from an origin to a goal, which both avoids obstacles and is the most efficient way of getting to the destination.

Despite the fact that the industry as a whole is quite aware of the "magic A* algorithm", it remains perennial problem because implementation is so very game specific.

言归正传，A*如何求解大型01规划？（对需求的描述请参加前面帖子“我在斯坦福”）。

基于A*的改进搜索算法

A*算法是人工智能中一种典型的启发式搜索算法，所谓启发式搜索就是在状态空间中对每一个搜索的位置进行评估，得到当前估计代价最小的位置，再从这个位置进行搜索直到找到目标。因而避免了大量无效的搜索路径，提高了效率。搜索中的估价是用估价函数表示的：

F(n) = G(n) + H(n)

其中F(n)是节点n的估价函数，G(n)实在状态空间中从初始节点到n节点的实际代价，H(n)是从n到目标节点最佳路径的估计代价。A*算法有两个表：Open表，用于存放待访问节点；Close表，用于存放已访问节点。

如果希望A*搜索01规划的解，那么首先需要将解空间定义为树型结构，利用链式二叉堆(LBH, Linked Binary Heap)，或者二叉堆（参加前面帖子）作为Open表，哈希表作为Close表（或者我自己设计的一种数据结构）。

求解的基本思路为：从树根节点开始搜索，不断从Open表中获取当前最好解进行派生，选出符合条件的子节点加入Open，并利用Close表排除重复节点。在搜索过程中动态更新“削枝”条件，以迅速缩小解空间。

1. 解空间的定义

本帖将解空间定义为树型结构（k叉树，本帖k=27，如图 1所示）：

1. 将所有Current condition的Strategies分别按照Score由高到低排列；

2. 将所有Current condition都选择最高Score的方案作为树根Root，此解为解空间中分数最高者；

3. 对于任意一个解Solution，选出其中一个Current condition，按照1中顺序做一次“降级”（即选择相邻的，分数较低的Strategy）——那么本帖将“降级”得到的解定义为Solution的孩子节点。由此可以看出，Root将会有k个孩子节点；这k个孩子中，每个又可能有k个孩子节点（也可能小于），以此类推。

需要说明的是不同的解可能派生出相同的后代，A*在求解过程中通过Close表排除所有重复节点。

图 1案例解空间结构示意图

2. Compare函数的定义

如前文所述，传统A*算法的Open表中节点是按照估价函数F(n)从低到高保持有序的。F(n)做比节点较之用，其绝对值没有物理含义，此特性和遗传算法的适应度函数及罚函数相似。

根据0-1规划求解特点，本帖利用Compare函数替代了A*算法的估价函数和遗传算法的适应度函数，不但避免了复杂的量纲统一问题，并且更精确反应了解的优劣。

令Solution为解的类型(成员Cost为Solution的价格，Score为改进分数)，budget为用户能接受的总预算，比较函数可以定义为：

其中：

max = s1.Cost s2.Cost ? s1 : s2;

其思想为：当两个解都低于budget的时候，分数高的解优；当至少有一个解高于budget的时候，价格低的解优。

在本帖的“改良A*搜索算法”中，Open表根据“比较函数”保持有序，从优到劣。

3. 算法主要步骤

1. 如1所述，将所有Current condition的Strategies分别按照Score由高到低排列；

2. 将树根节点（即总分最高解）加入Open；

3. 若Open非空，则循环执行：

a) 取出当前最优解s = Open.Pop()；

b) 当s .Cost <= budget时：更新当前最优解集合，若找到更好解, 清理Open表CleanUpOpen();

c) 若s可派生后代，即IsExpandable(s, true)返回true，则生成其所有孩子c_i(i=1,2,…,k)，将IsExpandable(c_i, false) 为true者加入Open表；

1.3.1 IsExpandable函数定义

令highestScore为当前解的最高分，则IsExpandable函数可定义为：

bool IsExpandable(Solution s, bool add2Close)

1. 若s.Score < highestScore，返回 false，代表s小于当前最好解的，进行剪枝；

2. 若s已在Close表中，返回 false，忽略已经处理过的解；反之,如果add2Close为true，将s加入Close;

3. 返回true, 此解可派生后代；

1.3.2 CleanUpOpen函数定义

利用Lambda表达式，CleanUpOpen()函数可定义为：

void CleanUpOpen()

1. open.Delete( so => !IsExpandable(so, false) );

2. 返回。

其含义为：根据当前条件，清除Open表中所有不可派生节点。

4. A* 算法求解历程

图 2显示了在用户预算为580,465的条件下，A* 算法从根节点(Score = 43.8, Cost = 812,832)，沿可能最优的分支查找，耗时8秒最终到找到最优解(Score = 40.9, Cost = 527,532)的历程。

图 2 A* 算法求解历程

图2可以近一步说明，A*算法依照Compare函数规则，迭代过程中每次从Open表中取出最优节点进行分支，能够迅速从树根达到用户预算附近的分支进行查找，因而在大多数情况下，它能在短时间内找到最优解。

当然也存在例外，如：某些全局最优解可能比较“隐蔽”，也就是说，它的“前辈节点”都比较差。在这种情况下，A*可能需要花费比较长的时间，以此可以通过遗传算法的变异机制来弥补。

移山之道

THU – team players 合作精神

THU - 清华大学 现代软件工程 成绩统计

最短摘要生成与多模式匹配（三）

Boyer-Moore算法——“坏后缀规则”？

如何考虑“坏后缀规则”？

一种实现方法

实验结果

后记

编程之美 - 哪个题目最美?

最短摘要生成与多模式匹配（二）

Boyer-Moore算法

坏字符规则

好后缀规则

中缀

前缀

算法实现

坏字符表构造

好后缀表构造

查找算法

后记

最短摘要生成与多模式匹配（一）

问题

冰山一角

算法发展简要回顾

Knuth-Morris-Pratt 算法

后记

顶级程序员的心得 Coders at Work (IV)

顶级程序员的心得 Coders at Work (III)

顶级程序员的心得 Coders at Work (II)

顶级程序员的心得 Coders at Work (I)

IBM 中国研究院 Offer 之感言——能力是一种态度

诀窍

结论

后记

一篇热帖的解剖

《我和他的结婚录像和相册集》的快速传播

最近到手的一些书

第二届C++技术大会@ 上海 - 我觉得可以去看看

[zz] 钱学森谈 大学 创新精神

方曲序列——一道有趣的搜索核心研发试题

问题

分析

解法

讨论

编程之美——差之毫厘

问题

解法一

解法二

分析

解法三

分析

解法四

参考资料

闲话

一些常用集合算法——之幂集合生成

问题

解法一

运行结果

讨论

解法二

运行结果

一些常用集合算法——之组合生成

问题

分析

解法

运行结果

讨论

一些常用集合算法——之全排列生成

问题

解法

运行结果

讨论

不用API构造简单自旋锁

问题

分析

解法

讨论

汽车加油问题——一道迷惑的面试题

问题

THU - 清华大学现代软件工程成绩统计

[zz] 钱学森谈大学创新精神