罕见地在雪夜看到红色的闪电，听到轰隆的雷声，这在汉乐府中描述的奇景不知道算不算是帝都的特色？在这样的夜里，会有几个人像我一样望着窗外的雪景，想着心中的愁绪呢？

唉，问题在，感叹也于事无补，还是洗洗睡吧。

您可能对这些感兴趣：

• 兄弟写的不是博客，是失败感 (14)
• 窗外皓月当空 (5)
• Snow And Sun (2)
• 明天和永远 (0)
• The Real World (0)
• 熙熙攘攘，利来利往 (0)

我不会公开写什么面经，也不会炫耀自己拿了多少 offer，相反，我拿到的并不多，因为结束地太早。我的要求并不高，百度给了我很满意的 offer，而且在接触的过程中，我以及我的朋友们都感到百度的 HR 以及面试官对人非常 nice。因此在接受百度 offer 后，我就推掉了其它所有公司的笔试和面试邀请——我并不是那种在求职过程中享受到很多乐趣的人，世界上还有很多有意义的事情可以做。

在整个求职的过程中，我得到了很多朋友的无私帮助，让我非常感激。这里面有的推荐我参加面试，有的直接给我面试机会，有的给我讲解面试技巧，有的和我讨论笔试面试中遇到的难题，有的帮我打探内部消息，不一而足。能得到这么多好人的帮助，我觉得自己非常幸运。希望能借我的博客这互联网的小小一隅，表达对诸君的谢意（以拼音序）：

百度的杨帆师弟、张弦小姐（《IT 小小鸟》作者）和赵柏敏师兄（曾经的面试官，现在的朋友）；
和我一起奋斗的北大小伙蔡白银和曹磊；
博文视点的周筠老师；
HP 的 Shin-Ming Liu；
IBM 的甘志博士和李获鼎师兄；
以前的老板 Intel 的 Sun Chan；
MSRA 的刘未鹏师兄(《IT 小小鸟》作者)；
纳拓软件的 Yong Liu；
农行的高飞师兄；
Opera 咨询的吴新雨师弟；
Synopsys 的陈怀兴先生；
泰为科技的 John Zhao；
淘宝网的马震先生和章文嵩博士；
腾讯的王信文师弟；
新浪网的刘立先生和张慧聪先生；
和我一起奋斗的中科院同学王捷。

您可能对这些感兴趣：

• 长假之购物 (6)
• 毛毛生日 (0)
• 孤独 (0)
• 生勿有负，死愿无撼 (1)
• 一个人的精彩 (0)
• 写在一个电闪雷鸣的雪夜 (4)

Problem:

1. Boot from livecd, select install. After a glowing ubuntu Symbol, screen shows nothing, even no CLI.

2. After installation with "text mode", boot from HD. After a glowing ubuntu Symbol, screen shows nothing, even no CLI.

Solution:

I am not very sure whether this problem is caused by the NV 185 driver(nvidia-glx-185). Installing or removing this package gave no help. I googled a lot, found many people encountered the same problem. However, no answer could work on my laptop. Then I tried to install NV driver manually...it works! So, here is the fix:

1. When you get the GRUB boot menu screen, press 'e' to edit the fist entry. Add a word 'single' after 'linux /boot/vmlinuz..... quiet splash', then press 'Ctrl+x' to boot. (I cannot enable networking in recovery mode, so I tried with the single mode.)

2. Select the 'netroot' entry. You will get a root command line with network support.

3. Download the latest NV driver for linux (2010-11-3):

# wget http://us.download.nvidia.com/XFree86/Linux-x86/190.42/NVIDIA-Linux-x86-190.42-pkg1.run

[You can visit http://www.nvidia.com/object/unix.html for the latest NV driver.]

4. Install development tools to build NV driver on you os.

# apt-get update
# apt-get install build-essential

5. Install the NV driver:

# chmod u+x NVIDIA-Linux-x86-190.42-pkg1.run
# ./NVIDIA-Linux-x86-190.42-pkg1.run

6. Reboot.

If you are using a livecd, please use the "text mode" to install Ubuntu 9.10. After installation, try the solution above.

Ubuntu 9.10 启动后黑屏的解决方法

平台： Dell Latitude D630, Nvidia NVS 135M, Intel CPU, Ubuntu 9.10

问题描述：

1. 从 livecd 启动后，选择安装，在白色 Ubuntu 图标闪烁结束之后，无任何屏显，连命令行都没有。

2. 用文本模式安装完成后，从硬盘启动，在白色 Ubuntu 图标闪烁结束之后，无任何屏显，连命令行都没有。

解决方法：

我不太清楚是不是 NV 的 185 驱动有问题(nvidia-glx-185)，安装或者删除它对状况没有任何帮助。我搜索了一下，发现很多人遇到和我类似的问题，不过没有任何解决方法可以在我的电脑上工作。无奈下我尝试手动安装了一下 NV 的最新驱动——居然解决了！下面是我的解决方法：

1. 当你进入 grub 启动菜单选择屏幕时，在第一条上按 e 进入编辑状态，在 'linux /boot/vmlinuz..... quiet splash' 这一行最后添加一个单词 single，然后按 Ctrl+x 启动。其实 recovery mode 能做类似的事，但是 9.10 的 recovery mode 好像不能启动网络，所以只好自己进入 single 模式了。

2. 启动后选择 'netroot' 选项，进入带网络的 root 命令行。

3. 下载最新的 NV 驱动(2010-11-3)：

# wget http://us.download.nvidia.com/XFree86/Linux-x86/190.42/NVIDIA-Linux-x86-190.42-pkg1.run

[你可以先访问 http://www.nvidia.com/object/unix.html 查看 NV 最新驱动的地址。]

4. 安装编译 NV 驱动需要的编译工具：

# apt-get update
# apt-get install build-essential

5. 安装 NV 驱动：

# chmod u+x NVIDIA-Linux-x86-190.42-pkg1.run
# ./NVIDIA-Linux-x86-190.42-pkg1.run

6. 重启

如果您使用 livecd 安装 Ubuntu 9.10 的话，您应该选择 "text mode" 进行安装。成功安装完成后，仍然遇到黑屏问题，请尝试上述方法。

您可能对这些感兴趣：

• Ubuntu 9.04 安装手记 (8)
• Install EIOffice 2007 on Ubuntu Linux 8.04 (6)
• 在 Dell Latitude D630 上硬盘安装 Ubuntu Linux 8.04 (18)
• Ubuntu 7.10 on my Dell Latitude D630 (1)
• Using Windows Fonts in Linux on Duo-System-Installed Computer (4)
• Writing x86 PC Bootloader With Free Software (3)

随便一本《近世代数》或者《抽象代数》书上在讲到置换群的时候，应该都会讲到这样一个定理：
任何一个置换都可以表示为不相交轮换的乘积，若不计因子的顺序，其分解式是唯一的。

一、简单解释

没有数学背景的人，这句话很难读懂，下面我们来看一个简单的例子。假设我们有这样一个置换 P：

1, 2, 3, 4, 5
2, 5, 4, 3, 1

那么这个置换是什么样的轮换的乘积呢？我们先从 1 出发，1 被换到 2，2 被换到 5，5 又被换到 1，这就是一个轮换；然后再从 3 出发，3 被换到 4，4 又被换到 3，这又是一个轮换。也就是说 P 是两个不相交轮换 (1, 2, 5) 和 (3,4) 的乘积。

二、一个应用：全排列判断问题

下面我们来看这个定理有什么作用，考虑下面这道题目[1][2]：

给一个 n 长的数组，判断它是否为一个 1, 2, ..., n 的全排列，要求在线性时间，常数空间内实现。

我们可以容易看到，每个全排列都可以视为 1, 2, ..., n 上的一个置换。问题就转化为检测该数组是不是一个 1, 2, ..., n 的置换。由本文开头提到的定理可知，我们只需要检查该置换是不是由不相交的轮换构成的即可。

还是上面那个例子，怎么检查

1, 2, 3, 4, 5
2, 5, 4, 3, 1

是不是一个置换呢？首先从 1 开始，a[1]=2，那么再检查 a[a[1]]=a[2]=5，然后再检查a[a[a[1]]]=a[5]=1，这样就发现了一个轮换 (1, 2, 5)。然后接下来检测第二个，第三个轮换...

如何保证检查的高效以及所有轮换都不相交呢？我们每次检查完一个数，就将它置负，这样遇到负值，循环就终止了。如果终止前检查的那个数与起始的数相同，那么我们就发现了一个轮换，否则它就不是一个轮换，说明 P 不是一个置换。由于检查过的轮换中的数字都被置为负值，所以第二个轮换肯定不会与第一个轮换相交。如果到最后所有的数都被置为负值，且循环正常终止，那么说明它们都在不相交的轮换里，那么 P 就是一个置换。

如果想要查找过程不影响最终数组的值，到最后把所有置负的元素都重新置正即可。

代码实现如下[2]：

/* We use a n+1 elements array a[n+1] for convenience. a[0] is used to store
 * the return value, thus is not part of the permutation.  */
int test_perm(int *a, int n)
{
  int i, j;
  if (a == NULL)  return 0;     /* Test input */
  a[0] = 1;
  for (i = 1; i <= n; ++i)      /* Test input */
    if (a[i] < 1 || a[i] > n) { /* Is a[i] in the range 1~n? */
      a[0] = 0;
      return a[0];
    }

  for (i = 1; i <= n; ++i)
    if (a[i] > 0) {
      j = i;
      while (a[j] > 0) {        /* Follow the cycle */
        a[j] = -a[j];
        j = -a[j];
      }
      if (j != i)  a[0] = 0;    /* Test the cycle */
    }

  for (i = 1; i <= n; ++i)
    a[i] = a[i] > 0 ? a[i] : -a[i];

  return a[0];
}

三、另一个应用：100 囚徒碰运气问题

那么这个定理还有其它的用处没有呢？考虑下面这道题目[3][4]：

100 个囚犯，每人有一个从 1 到 100 的不重复不遗漏的号码，国王把这些号码收集起来，打乱放进 100 个箱子里，每个箱子里有且仅有一个号码。囚犯们一个一个地来到 100 个箱子面前，每人可以打开至多 50 个箱子来寻找自己的号码，可以一个一个打开（即可以根据之前箱子里看到的号码来决定后面要打开的箱子）。如果有一个囚犯没有找到自己的号码，那么这 100 个人一起被处死；只有当所有的囚犯都找到了自己的号码，他们才会被国王全部释放。

囚犯们可以在没开箱子前商量对策，但是一但打开了箱子，他就不能告诉别人箱子和号码的对应关系。问他们应该用什么样的策略以保证最大的存活概率？

显然，每个人随机选 50 个箱子打开，100 个人的存活概率会是 1/2 的 100 次方，即1/1267650600228229401496703205376，可以小到忽略不计。但是事实上有一种极简单的办法，其存活概率高达 30% 。至于有没有更好的办法？我不知道。

存活率达 30% 的策略就是：

囚犯打开自己号码对应的箱子，就按照箱子中的号码打开另一个箱子，一直到找到自己号码或者选50 次为止，这样就能保证整体有 30% 的存活概率。

这个策略背后的数学原理是什么呢？其实国王所作的事情，就是一个 1 到 100 元素集合的置换，囚犯所做的事情，就是顺着自己号码所在的轮换找自己号码。那么什么时候所有人都不用死呢？就是这个置换中所有的轮换长度都不大于 50，因为每个囚犯号码的轮换都不大于 50，那么他总能在 50 次以内找到自己的号码。

怎么计算这个概率 P 呢？{这个置换中所有的轮换长度都不大于 50 的概率}，就是 1 - {存在轮换长度大于 50 的概率}，进而 1 - {存在轮换长度为 51, 52, ..., 100 的概率}，由此，我们可以得到下面的等式：

其中，Hn 代表调和数（Harmonic Number）。虽然调和数没有精确的公式，但是我们知道调和数和自然对数有着密切的联系[5]，那么我们就可以用自然对数来近似：

[6]

因此，我们可以得到，使用这种策略 100个囚犯的存活概率 P 约为 30%。

[1] http://yueweitang.org/bbs/topic/22
[2] http://fayaa.com/tiku/view/84/
[3] http://tydsh.spaces.live.com/Blog/cns!435F1A315756AD5D!833.entry
[4] http://fayaa.com/tiku/view/141/
[5] http://en.wikipedia.org/wiki/Harmonic_number#Calculation
[6] 求和得到的更精确的结果是：0.31182782068980479698，Bash 代码：

STR="1-("
for i in `seq 51 99`; do
  STR+="1/$i+"
done
STR+="1/100)"
echo $STR | bc -l

您可能对这些感兴趣：

• Cygwin GCC qsort 函数错误（续） (0)
• Cygwin GCC qsort 函数错误 (5)
• 将文本文件读入数组-C语言实现 (7)
• vasprintf 会将空间分配到栈上吗？ (11)
• 多余的逗号？ (11)
• Something About Scanf() In C (1) (0)

有 25 匹马和 1 个赛场，但赛场只有 5 条赛道，即一次只能给最多 5 匹马提供比赛机会，并且不能计时。请问如何设计比赛策略得到最快的 3/5 匹马，使得使用赛道的次数最少。

我想了一下，下面尝试给出我的分析，如果不对的话，还请指正。

一、决出前三名的策略

决出前 3 名网上有很多讨论，答案是 7 次，没有见过更少的，策略如下：

1. 将 25 匹马分成 5 组，分别赛一轮，得出一个先后顺序，共 5 轮。
2. 将每组的头马组成一组，再赛一轮，得出一个先后顺序。这第 6 轮能确定第一名。
3. 将最快一组的二三名，第二那组的一二名，以及第三那组的第一名五匹马放在一起，再赛一轮。这第 7 轮的前两名就是最终的二三名。总共赛 7 轮。

下面是分析。不失一般性，在赛 6 次之后，我们假设这 25 匹马的序号为：

A1 A2 A3 A4 A5  // 1 <-------
B1 B2 B3 B4 B5  // 2  |     |
C1 C2 C3 C4 C5  // 3 Main   |
D1 D2 D3 D4 D5  // 4  |  Extended
E1 E2 E3 E4 E5  // 5 <--    |
--------------  //          |
A1 B1 C1 D1 E1  // 6  {A1} <-

其中主矩阵列出了 25 匹马的序号，扩展矩阵的每行是每轮比赛的结果。我们可以看到主矩阵的行有序，第一列有序，那么现在我们知道第一名是 A1。

由于已知 A1 是第一名，第二名肯定是在每轮中紧挨在 A1 后面的，因此第二名的候选集为 {A2, B1}。

它们两个占不满 5 个赛道，我们再来看第三名的候选集。第三名在每轮中只可能是挨在第一或第二名的后面，也就是说在 {A1} U {A2, B1} 的后面，那么第三名的候选集就是 {A2, A3, B1, B2, C1}，正好 5 匹马（第二名的候选集肯定包含在第三名候选集中）。那么第二三名只可能在这 5 匹马中，因此我们只需要让 {A2, A3, B1, B2, C1} 这 5 匹马再比一次，得到前两名，与 {A1} 合起来就是总的前三名。这样总共的比赛次数是 7 次。

2. 决出前五名的策略

决出前 5 名，就比较复杂了，我们按照同样策略再往下思考：

{A2, A3, B1, B2, C1} 决出前两名，有几种可能呢？如果它们没有比过，可能性就是从 5 个中取 2 个后的排列数，20 种可能。但是我们前面的比赛已经得到了一些快慢信息，我们就可以发现，第 7 轮 {A2, A3, B1, B2, C1} 决出前两名只有 5 种可能情况：

A2 A3 B1       B2/C1 * // 7  {A1, A2, A3}
B1 B2 A3/C1    *     * // 7  {A1, B1, B2}
B1 C1 A2/B2    *     * // 7  {A1, B1, C1}
A2 B1 A3/B2/C1 *     * // 7  {A1, A2, B1}
B1 A2 A3/B2/C1 *     *

去掉可交换的 A2 B1，其实只有 4 种情况。我们分别来考虑这 4 种情况：

1. {A1, A2, A3}

第四名肯定是 {A1, A2, A3} 之后的马，候选集为 {A4, B1}；元素不足 5，再推一下第五名，即{A1, A2, A3} U {A4, B1} 之后的马，候选集为 {A4, B1, A5, B2, C1}，只有 5 匹马。就是说第四、五名可以从这五匹马中产生，那么我们只需要再比一轮，取前两名，与 {A1, A2, A3} 并起来就能得到整个的前 5 匹马。那么最少的比赛次数是 8 次。

2. {A1, B1, B2}

这种情况下，同理，第四名候选集为 {A2, B3, C1} ，第五名候选集为 {A2, A3, B3, B4, C1, C2, D1}，元素多于 5 个。因此我们必须先让 {A2, B3, C1} 比赛得到第 4 名，才能将第五名候选集的元素个数减少到 5 个以内。穷举：第 8 轮 A2 第一，可以消去 {C2, D1, B4, A2}；B3 第一，可以消去 {B3, A3, C2, D1}；C1 第一，可以消去 {C1, A3, B4}，均能保证第五名的取值集合减少到 5 以内，因此只需要再一轮，就可以得到第五名。总的比赛次数是 9 次。

3. {A1, B1, C1}

同理，第四名候选集为 {A2, B2, C2, D1}，第五名候选集为{A2, A3, B2, B3, C2, C3, D1, E1}。第四名无论取哪个，都会消去四个第五名候选集中的元素，总的比赛次数仍然是 9 次。

4. {A1, A2, B1}

同理，第四名候选集为{A3, B2, C1}，第五名候选集为{A3, A4, B2, B3, C1, C2, D1}。第四名无论取哪个，至少消去第五名候选集中的 3 个元素，总的比赛次数也是 9 次。

穷举结束了，现在我们可以得出结论：最坏情况下该策略决出前 5 匹马的最少比赛次数是 9 次。

三、扩展问题

我有一个问题是：这种策略下取3, 5名比赛次数一定是最少的吗？有没有数学证明？

再扩展一点儿，如果需要求前 n 名，最少需要比赛几次？

在我们的这种策略下，因为主矩阵只有 5 行，每行还是有序的，那么求下一名的候选集最多有 5 个元素。也就是说多求一名，至多需要增加一轮比赛。什么情况下可以少于一轮呢？当已经确定第 n 名的情况时，第 n+2 名的候选集元素少于 5 个，我们就可以一轮比赛确定两个名次了。

我还比较好奇的是，如果需要决出所有 25 匹马的快慢顺序，最坏情况下至少需要比赛几次？

在我们这种策略下，假设 f(n) 是第 n 名最坏情况下的最少比赛次数，我们已知 f(1) = 6, f(2) = f (3) = 7, f(4) = 8, f(5) = 9，f(n) <= (n-5)+9 = n+4。那么 f(25) = f(20)+1 <= (20-5)+9 + 1 = 25 次，其上界应该是 25。但其准确值怎么确定？穷举就太困难了。

但是如果题目要求是确定 25 个的全部顺序，我们这种策略未必是最好的。这时候这题可以看成 n 路归并排序，并且可同时比较 n 个数的优化问题。过程中有很多可优化的可能。比如我们预处理时可以对每行和每列都排一下序，能否可以得到一些额外的信息？当主矩阵（去掉已确定顺序的元素）显得不那么平衡时，用扩展矩阵中的比较信息是否可以将主矩阵平衡一下，或者消去某些行列，这样做是否有帮助？

您可能对这些感兴趣：

• Math in CS：置换的轮换分解 (2)
• Cygwin GCC qsort 函数错误（续） (0)
• 统计二进制中 1 的个数 (6)
• 从一个数列中取具有最小和的子序列 (11)
• 用两个非门和任意的与、或门构造三个非门 (3)
• 薄弱的算法基础 (4)

这个错误直接导致了快排算法失效。

但是为什么在 Linux 下的 gcc 可以输出正确的排序结果呢？我想了很久，最终还是把 glibc 的代码看了一下，才发现，原来当数组规模比较小时时（数组大小小于物理内存的四分之一），glibc 的 qsort 其实不使用 quick sort(_quicksort)，而是使用 merge sort(msort_with_tmp)。而且在 msort_with_tmp 中，对 compare 的处理是比较其返回值是否 <=0，这样排序的结果就是正确的了。[1]

事实上最简单的快排算法是只使用 '<' 号或者 '<='的，比如 Wikipedia 上给出的快排算法，那么我们的 compare 只返回 -1 和 0 行吗？这取决于实现，比如对快排算法的优化中有一个就是对数组中有大量相等元素情况下的优化，其中一种实现 Three-way partition， 就需要使用到三种情况：大于、小于或等于。原始的快排 partition 是将数组按照与 pivot 的比较分为两段，Three-way partition 则是将数组分为三段，中间增加一段与 pivot 值相等的子数组。C 玩具代码的实现如下：

void qsort_3way(int a[], int lo, int hi)
{
  if (hi <= lo) return;
  int lt = lo, gt = hi, i = lt;
  int v = a[lo], t;
  while (i <= gt) {
    if (a[i] < v) {
      t = a[i]; a[i] = a[lt]; a[lt] = t;
      ++i; ++lt;
    } else if (a[i] > v) {
      t = a[i]; a[i] = a[gt]; a[gt] = t;
      --gt;  
    } else i++;
  }
  qsort_3way(a, lo, lt - 1);
  qsort_3way(a, gt + 1, hi);
}

但是 '<' 和 '>' 真的都需要吗？理论上来讲，'>' 是不需要的，我们显然可以将 a[i] > v 改成 v < a[i]。这也是 C++ 里面做的，C++ 中的 sort 函数只需要类重载 '< ' 运算符。但是 C 中并没有这种约定，我们不能预设 qsort 如何拿 compare() 的返回值与 0 比较。因此让 compare() 按照 C 的约定，返回大于、小于和等于 0 的三种情况是绝对正确的而且必要的。

我了解了正确的结果怎么得来的，但是我仍然不知道错误的结果是怎么得来的。看起来 Cygwin 使用的 libc 中没有采取类似 Linux 下 gcc 的策略（比如无法取到物理内存大小？）。quick sort 算法有很多优化的技巧和实现：有的使用 '< ' 符号比较，有的在分支数组足够小时采用插入排序，有的同时使用 '<', '> 两个符号，有的随机取 pivot，有的取三点中值作为 pivot。[2] 没有看到代码和调试，很难判断 Cygwin 的 libc 使用了什么算法（当然，尝试分析不同的输入输出是可以得到规律的，比密码分析还是要简单一些）。

[1] glibc/stdlib/msort.c.
[2] Jon Bentley and M. Douglas McIlroy, "Engineering a sort function", Software - Practice and Experience, Vol. 23 (11), 1249-1265, 1993.

您可能对这些感兴趣：

• Math in CS：置换的轮换分解 (2)
• Cygwin GCC qsort 函数错误 (5)
• 将文本文件读入数组-C语言实现 (7)
• vasprintf 会将空间分配到栈上吗？ (11)
• 多余的逗号？ (11)
• Something About Scanf() In C (1) (0)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *p, const void *q)
{
  return *(const char *)p > *(const char *)q;
}

int main()
{
  char a[] = "1312515";
  printf("%sn", a);
  qsort(a, strlen(a), sizeof(char), compare);
  printf("%sn", a);
  return 0;
}

按说它应该输出：

1312515
1112355

但是我用 Cygwin gcc 编译后，它居然运行出这样的结果：

1312515
2111355

太诡异了。我尝试调试它，结果 gdb 无法步入 qsort 代码中。谁能告诉我是为什么？

附 Cygwin gcc 信息：

$ gcc -v
Using built-in specs.
Target: i686-pc-cygwin
Configured with: /gnu/gcc/package/gcc4-4.3.2-2/src/gcc-4.3.2/configure --srcdir=/gnu/gcc/package/gcc4-4.3.2-2/src/gcc-4.3.2 --prefix=/usr --exec-prefix=/usr --bindir=/usr/bin --sbindir=/usr/sbin --libexecdir=/usr/sbin --datadir=/usr/share --localstatedir=/var --sysconfdir=/etc --infodir=/usr/share/info --mandir=/usr/share/man --datadir=/usr/share --infodir=/usr/share/info --mandir=/usr/share/man -v --with-gmp=/usr --with-mpfr=/usr --enable-bootstrap --enable-version-specific-runtime-libs --with-slibdir=/usr/bin --libexecdir=/usr/lib --enable-static --enable-shared --enable-shared-libgcc --enable-__cxa_atexit --with-gnu-ld --with-gnu-as --with-dwarf2 --disable-sjlj-exceptions --enable-languages=ada,c,c++,fortran,java,objc,obj-c++ --disable-symvers --enable-libjava --program-suffix=-4 --enable-libgomp --enable-libssp --enable-libada --enable-threads=posix AS=/opt/gcc-tools/bin/as.exe AS_FOR_TARGET=/opt/gcc-tools/bin/as.exe LD=/opt/gcc-tools/bin/ld.exe LD_FOR_TARGET=/opt/gcc-tools/bin/ld.exe
Thread model: posix
gcc version 4.3.2 20080827 (beta) 2 (GCC)

我犯了一个愚蠢的错误，感谢来自 Stephen 的评论：

你的compare函数有问题，你的compare函数不会返回负数。修改compare为：
int compare(const void *p, const void *q)
{
return *(const char *)p - *(const char *)q;
}
再编译运行就正确了。

您可能对这些感兴趣：

• Math in CS：置换的轮换分解 (2)
• Cygwin GCC qsort 函数错误（续） (0)
• 将文本文件读入数组-C语言实现 (7)
• vasprintf 会将空间分配到栈上吗？ (11)
• 多余的逗号？ (11)
• Something About Scanf() In C (1) (0)

十一长假不愿好好在食堂吃饭，出去吃些麻辣烫之类的食品，发现了一些关于麻辣烫小店的有趣现象，闲聊一下。

第一种风格，我称为“京城麻辣烫”，因为我是在京城第一次见这种风格的麻辣烫，而且它在京城很流行。其特点是：长槽形的锅具，煮着各式串串，相熟或不相熟的食客都围坐锅具一圈，拿起便吃，吃完数签结帐。据我观察，京城麻辣烫颇受学生青睐，在北京可谓有大学的地方就有京城麻辣烫。我有印象的比如北航南门外、清华照澜院、中科院青年公寓门口成都小吃外、中科院玉泉校区附近麦当劳门口。

第二种风格，我称为“南京麻辣烫”，也是因为第一次相熟是在南京。其特点是：串串都放在一个架子状冷柜上，按价格分别，食客先用饭筐挑选串串，店主数串付钱，然后由厨师抽掉竹签，煮好送上饭桌，食客自己加辣椒等调味品。汤水比较多，并且汤水的味道比较不错。以前在北京没怎么见过，只是最近发现我们玉泉校区超市发旁边小巷子中有一家，中关村地下广场肯德基对面有一家，依稀记得北大某个食堂也有提供。

第三种风格，我称为“川味麻辣烫”，主要是因为它很辣。其特点是：串串或者食品放在一个服务台上供食客挑选，但食客不用自己动手，按串或者按斤计算价钱，付钱后煮好送上饭桌。但与“南京麻辣烫”不同的是，“川味麻辣烫”送上的锅比较干，没什么汤水，而且默认加很多辣椒。丸子和肉类味道尚可，稠糊糊的粉丝可不敢恭维。像京城很流行(也很贵)的“麻辣香锅”，还有复兴路上五棵松附近有家“林静小吃”，就是此种风格的麻辣烫。

我个人来说，比较偏好于“南京麻辣烫”，因为汤水比较好喝，还可以泡点儿饼馕什么的，而且默认并不辣；“京城麻辣烫”一般还是吃得了的，但太大排档了，不好当作饭吃；“川味麻辣烫”对我并不友好，默认的辣椒我不太喜欢，只能凑合吃吃，而且必须有酒水佐食，不然实在是太干了。这些名字都是我自己起的，要是哪位知道该风格的麻辣烫到底起源于哪里或者哪家店铺，我愿意更正过来。

谈到麻辣烫，不得不说我在南京非常喜欢的一家叫做“傣妹”的火锅店。虽然“傣妹”号称是火锅店，但我认为它其实是披着火锅外皮的麻辣烫。傣妹的一大特色就是食品种类多，每份小且便宜。但凡你能在麻辣烫摊位上找到的东西，以及在火锅店能找到的东西，傣妹几乎都有。比如说牛丸，一份三块五，只有八九个；肥羊肉，一小盘，四五块钱。一顿饭吃下来能吃不少样菜，要比真正的火锅实惠很多。我一直期望能在北京找到类似的火锅店，但目前来讲还没有发现。

您可能对这些感兴趣：

• 春游戒台寺 (1)
• Class Member Function as pthread_create Argument (1)
• 写在一个电闪雷鸣的雪夜 (4)
• 骑行卢沟桥 (5)
• 窗外皓月当空 (5)
• Golden Week 200810 (3)

这次国庆假期我没有回南京，不过不要误会，我不是为了看阅兵 。我表姐已经在北京工作，租的住处离我学校不远，住的问题比较好解决，所以就让女朋友来北京玩了。

我女友学的是统计学专业，找工作的方向和我这种技术类的不同，很多公司面试都要求穿正装。学生能负担起的正装品牌本来就不多，女装就更少了。貌似一个叫做 G2000 的品牌在学生中比较流行，我们身边好多女同学都买的它，所以我女友也倾向于选择这个牌子。

在南京看了几家 G2000 专卖店之后，发现折扣太少，因此就寄希望于北京国庆期间可以能多打些折扣。后来真是费了很多周折，逛了很多地方，西单、中关村和几个上品折扣，发现最大的折扣才能 7 折，而上品都没有合适的号码和款式，都快失望了。最后在我爱打折网上翻到一条很简略的回帖，说天虹百货有大约 4 折，于是第二天又赶到从来没去过的广安门。总算功夫不负有心人，找到了合适的款式和号码，最后算下来折扣大约 4.2 左右。God bless Internet!

之所以特别提这个购物经历，是因为这大概是我们买过最贵的衣服了，一套下来将近两千块。我原来在 NJULUG 的朋友蒸鱼曾经写过一篇博客“奢侈品”，我当时看了印象很深刻，于我心有戚戚焉。蒸鱼在文中所说的“奢侈品”列表很有趣，G2000 的衣服对现在的我来说，肯定是在奢侈品列表里的。

这也让我想起我从小到大的购物观念，哪些是奢侈品，哪些不是。

我小时候住在乡下时，当时我们家还没有在县城盖房子，所以我的零食开销还算比较多。在记忆里经常可以买烧饼、糖包和冰棍吃。但自从 95 年在县城盖房子之后，烧饼、糖包和冰棍于我就变成了奢侈品，罕有一吃，更别提其它东西了。我还记得我觊觎了书店里 6 块钱一本的作文集大约一年，才买了下来，不过现在那本书已经不知道被我扔哪里去了。那个时候，除了一毛钱一包的糖豆，其它东西基本上都是奢侈品，去县城 2 块钱的车费，5 毛钱一包的三鲜伊面，让我看来都是了不得的贵哦！（可能也包括我的父母，因为他们都是骑自行车去县城）

家搬到县城之后，生活好了很多。那时候烧饼已经不算奢侈品了，初中上晚自习的时候还有点儿钱买点儿吃的，也第一次穿上了所谓的“旅游鞋”。不过那时候一块钱五个的游戏币，对我来说仍然有些奢侈，所以我对街机只好完全免疫，天天放学踢足球到天黑才回去。记得当时足球鞋有两种：一种是荣光的， 18 块一双，一种是双星的，30 一双，我直到上高中才穿上双星牌的足球鞋。

我的高中是在市高上的，多数同学是市里的，消费水平和我大不一样。那时候我才知道世界上还有超薄随身听和 CD 机这种东西，真高科技呀。和同学交流也让我初识了不少品牌，比如我总算知道了“麦当劳”不是“麦当娜”的别名。当时本地商店里的杂牌衣服和鞋子已经被我从奢侈品列表中剔除了，只不过文曲星、超薄随身听、CD 机变成了我梦寐以求的奢侈品，当时觉得包里放一个带线控的 Sony 随身听没事儿听着玩玩该多酷呀！

到了大学，其实转变并不明显。一方面因为大学里攀比并不明显，另一方面因为我们呆在浦口那个荒凉的地方，也没什么可消费的。在大学里我才发现，原来我一直认为挺奢侈的品牌，比如班尼路、真维斯等，打折起来还是比较便宜的，因此就养成习惯趁过节打折时候买衣服，直到现在。真正有较大改变是大学毕业实习时，实习单位的经理很欣赏我，实习的报酬还算比较好，第一次能自己养活自己。出了校园一看，天地真不一样啊——还有吃饭好贵呀，那时候起才把奢侈品列表中的麦当劳、肯德基等快餐厅列入平价饭店的行列。

但是直到读研究生，火车卧铺和出租车仍然在我的奢侈品列表中。当然这是指比较长的火车卧铺和北京的出租车，比如北京到南京的卧铺就比硬座贵一百来块，我仍然不舍得多花这个钱。其实总的来看，我比较偏执的是拒绝那些有廉价替代品的物品。

我曾经仔细考虑过我对金钱的态度，发现在目前阶段我对金钱仍然是非常的执着，这表现在我和朋友在一起时会经常讨论到赚钱的问题，而且我无法理解那些让人忽略金钱问题的劝告，比如这篇文章 。看到这个问题：钱重要还是梦想重要？我就想发笑，一般提出这种问题的往往是功成名就后，站着说话不腰疼的同志。我不是说梦想不重要，但是梦想之所以是梦想，就在于其不确定性，而选择工作是一个很确定的过程。一个单位只能用比较确定的东西来吸引人才，比如工作内容和项目前景，好的团队和人才培养计划，以及体面的收入，而不是告诉申请者：“来到我们公司应该是你的梦想，其它的你不应该考虑。”为了申请一个公司，一个申请者需要填那么多乱七八糟的表格，提供项目实习关系证件，那么为了表示互相尊重，招聘者也理应提供给申请者一个体面工作的具体描述。当然，像阿里这种大公司，薪酬水平也基本上是公开的，HR确实也没有必要多谈，这另当别论。

天那，本来想写轻松的一小篇，居然扯了那么多。总结一下吧，无论是个人、公司还是国家，每个都在努力着去减少奢侈品列表中的物品数量，公司的奢侈品可能是研究部门或者顶尖人才，国家的奢侈品可能是全民福利或者枪炮。希望这世界能真按克鲁格曼所说：Greedy people, make the world go round.

您可能对这些感兴趣：

• 为求职事谢诸君 (15)
• 写在一个电闪雷鸣的雪夜 (4)
• 博客被搬家 (13)
• 工行网银：用9个月的时间修正一个错误 (8)
• 灭蟑记 (2)
• 兄弟写的不是博客，是失败感 (14)

#include <iostream>
#include <typeinfo>
#include <vector>
#include <string>
using namespace std;

template<typename T>
void foo(const T& t)
{
  cout << "foo: generic(" << t << ") " << typeid(t).name() << endl;
}

template<typename T>
void bar(const T t)
{
  cout << "bar: generic(" << t << ") " << typeid(t).name() << endl;
}

/*
$ c++filt [-t] A1_c A2_c A3_c Ss PKc
char [1]
char [2]
char [3]
std::basic_string<char, std::char_traits<char>, std::allocator<char> >
char const*
*/
int main()
{
  foo("");                              // foo: generic() A1_c
  foo("0");                             // foo: generic(0) A2_c
  foo("01");                            // foo: generic(01) A3_c
  foo(static_cast<string>(""));         // foo: generic() Ss
  foo(static_cast<string>("0"));        // foo: generic(0) Ss
  foo(static_cast<string>("01"));       // foo: generic(01) Ss
  foo(static_cast<const char *>(""));   // foo: generic() PKc
  foo(static_cast<const char *>("0"));  // foo: generic(0) PKc
  foo(static_cast<const char *>("01")); // foo: generic(01) PKc
  foo(*(new string("")));               // foo: generic() Ss
  foo(*(new string("0")));              // foo: generic(0) Ss
  foo(*(new string("01")));             // foo: generic(01) Ss
  bar("");                              // foo: generic() PKc
  bar("0");                             // foo: generic(0) PKc
  bar("01");                            // foo: generic(01) PKc
  bar(static_cast<string>(""));         // foo: generic() Ss
  bar(static_cast<string>("0"));        // foo: generic(0) Ss
  bar(static_cast<string>("01"));       // foo: generic(01) Ss
  bar(static_cast<const char *>(""));   // foo: generic() PKc
  bar(static_cast<const char *>("0"));  // foo: generic(0) PKc
  bar(static_cast<const char *>("01")); // foo: generic(01) PKc
  bar(*(new string("")));               // foo: generic() Ss
  bar(*(new string("0")));              // foo: generic(0) Ss
  bar(*(new string("01")));             // foo: generic(01) Ss
  return 0;
}

基于前一篇博客的分析，我们知道形如 "hello" 的常量字符串在编译时的类型是 char 数组。不同长度的 char 数组，其类型是不一样的，我们可以使用下面语句：

cout << (typeid(char [1]) == typeid(char [2])) << endl;

来验证这一想法。因此，如果我们使用不同长度的字符串作为参数调用 foo，编译器就会为模板函数 foo 实例化不同的实例函数，这一点已经由 foo 的前三个输出验证。我们还可以通过 readelf 来读取目标文件符号表，或者 objdump 查看目标文件反汇编代码中 foo 的实例函数的数量。

$ readelf -s test.o | c++filt -t | less
$ objdump -S test.o | c++filt -t | less

这也就是说，我们使用原始字符串调用了三次 foo，其实是三个不同的实例函数，这样显然会导致目标代码臃肿。那么怎么避免这种情况出现呢？下面我们使用了三种不同的方法，将字符串 static_cast 成 string 或者 const char * 类型，或者使用字符串构造一个 string 对象作为参数，这三种情况都能保证不同（内容）字符串参数的调用使用的是同一个实例化的模板函数。

有没有方法避免类型转换呢？我们可以使用非引用参数类型作为模板函数的模板参数，如 bar 模板函数所示。如前一篇中的分析，此时 char 数组类型会被隐式转换成 char 指针类型，然后进行模板函数推导。所以我们看到即使传的是原始字符串参数，其调用的实例化函数仍然是 char const * 类型的。由于这里类型 T 被推导为 char const * 类型，所以传递的仍然是指针。

但是下面的 string 类型的实例化模板函数实现的就是值传递了，这在函数运行效率上可能会有一些影响。不过现代的函数库对 string 都实现为 copy-on-write（例如 MFC 的 CString 和 Qt 的 QString），我想 STL 的 string 应该也不例外，而 const T 参数并不允许对参数修改，所以效率上的影响应该还是比较小的。只是在语义上与传一个指针就有不同了，假如不限定 T 是 const，那么值传递 string 时，对 string 的修改就无法反映到原来 string 上了。

最后，到底哪个方法好呢？我不知道，我没有足够的实践经验来评论哪种方法更好。我这两篇文章的目的仅仅是探讨一下使用不同形式字符串作为模板函数参数时可能发生的奇怪现象，以及要注意的方面，至于哪种方法更好，可能要留待实际需求来决定。

附：第一段代码的 VS 2008 编译器编译结果执行的输出：

foo: generic() char const [1]
foo: generic(0) char const [2]
foo: generic(01) char const [3]
foo: generic() class std::basic_string,class std::allocator >
foo: generic(0) class std::basic_string,class std::allocator >
foo: generic(01) class std::basic_string,class std::allocator >
foo: generic() char const *
foo: generic(0) char const *
foo: generic(01) char const *
foo: generic() class std::basic_string,class std::allocator >
foo: generic(0) class std::basic_string,class std::allocator >
foo: generic(01) class std::basic_string,class std::allocator >
bar: generic () char const *
bar: generic (0) char const *
bar: generic (01) char const *
bar: generic () class std::basic_string,class std::allocator >
bar: generic (0) class std::basic_string,class std::allocator >
bar: generic (01) class std::basic_string,class std::allocator >
bar: generic () char const *
bar: generic (0) char const *
bar: generic (01) char const *
bar: generic () class std::basic_string,class std::allocator >
bar: generic (0) class std::basic_string,class std::allocator >
bar: generic (01) class std::basic_string,class std::allocator >

您可能对这些感兴趣：

• 字符串参数的模板函数推导问题 (1)
• 多余的逗号？ (11)
• Math in CS：置换的轮换分解 (2)
• Cygwin GCC qsort 函数错误（续） (0)
• Cygwin GCC qsort 函数错误 (5)
• 将文本文件读入数组-C语言实现 (7)

困惑起源于以字符串作为参数，如何匹配到特化的模板函数。代码如下，其中注释部分是该句对应的输出（使用 VS2008 编译器，一会儿再讨论 g++ 的问题）：

#include <iostream>
#include <typeinfo>
using namespace std;

template<typename T>
void foo(const T& t)
{
  cout << "foo: generic " << typeid(t).name() << endl;
}

template<>
void foo<const char *>(const char * const& t)
{
  cout << "foo: special " << typeid(t).name() << endl;
}

template<typename T>
void bar(const T t)
{
  cout << "bar: generic " << typeid(t).name() << endl;
}

template<>
void bar<const char *>(const char * t)
{
  cout << "bar: special " << typeid(t).name() << endl;
}

int main()
{
  char str[] = "hello";
  const char con_str[] = "hello";
  const char * const p = "hello";
  foo("hello");                                  // foo: generic char const [6]
  foo(static_cast<const char * const>("hello")); // foo: special char const *
  foo(static_cast<const char *>("hello"));       // foo: special char const *
  foo(str);                                      // foo: generic char const [6]
  foo(con_str);                                  // foo: generic char const [6]
  foo(p);                                        // foo: special char const *
  bar("hello");                                  // bar: special char const *
  bar(str);                                      // bar: generic char *
  bar(con_str);                                  // bar: special char const *
  bar(p);                                        // bar: special char const *
  cout << typeid("hello").name() << endl;        // char const [6]
  cout << typeid(str).name() << endl;            // char [6]
  cout << typeid(con_str).name() << endl;        // char const [6]
  cout << typeid(p).name() << endl;              // char const *
  return 0;
}

首先让我奇怪的问题是，第一个 foo 函数调用 foo("hello")，为什么实际调用的不是特化的 foo 函数？

其实这个例子是有起源的，《C++ Primer》第四版 Section 16.6.1 的最后给出这样一个例子：

// define the general compare template
template <class T>
int compare(const T& t1, const T& t2) { /* ... */ }

int main() {
    // uses the generic template definition
    int i = compare("hello", "world");
    // ...
}

// invalid program: explicit specialization after call
template<>
int compare<const char*>(const char* const& s1,
                         const char* const& s2)
{ /* ... */ }

并解释说：

This program is in error because a call that would match the specialization is made before the specialization is declared. When the compiler sees a call, it must know to expect a specialization for this version. Otherwise, the compiler is allowed to instantiate the function from the template definition.

那么我认为作者暗含的意思里有，compare("hello", "world") 这个函数调用是 match 特化的 compare 函数的。但是从我们给出的第一段代码输出来看，并不是这个样子的，所以我谨慎地怀疑，《C++ Primer》给出的这个例子是有错的。虽然这段程序的确有错，但是即使将特化函数提到前面，compare("hello", "world") 仍然不会调用该特化函数。

请教了别人、书本和标准之后，下面我试着对上面每句的输出做一下解释（当然，可能有错，请指正）：

1.   foo("hello");                                  // foo: generic char const [6]

"hello"具有类型 char const [6]，由于 foo 模板使用的是引用参数，因此数组实参不会被转换成指针，而是追求一个较为精确的匹配，因此编译器实例化一个 void foo<char const [6]>(const char (& t)[6]) 模板函数（VS2008），这也是为什么我们能看到参数的类型输出是 char const [6]；

2.   foo(static_cast<const char * const>("hello")); // foo: special char const *

"hello"被 cast 成了 const char * const 类型，自然与特化的函数 void foo<const char *>(const char * const& t) 能够精确匹配，因此调用的是特化的 foo；

3.   foo(static_cast<const char *>("hello"));       // foo: special char const *

"hello"被 cast 成了 const char * 类型，虽然少了一个 const，但是 C++ 标准中有这样的说法：

14.8.2.3
If the orignial A is a reference type, A can be more cv-qualified than the deduced A

这种 cv-qualifier 并不影响推导，最终仍然是匹配到特化的 foo 函数；

4.   foo(str);                                      // foo: generic char const [6]

str 和 "hello" 也是仅仅相差一个 cv-qualifier，也不影响推导，其结果与 1 是一致的；

5.   foo(con_str);                                  // foo: generic char const [6]

con_str 和 "hello" 的类型一样，显然其结果与 1 应是一致的；

6.   foo(p);                                        // foo: special char const *

p 的类型其实就是 2 中参数被 cast 之后的类型，显然其结果应该与 2 一致；

7.   bar("hello");                                  // bar: special char const *

乍一看就有些奇怪，为什么把模板参数换成值（而不是引用），特化的情况就与 foo 不同了呢？C++ 标准中有这样的规定：

14.8.2.3
If A is not a reference type:
-- If P is an array type, the pointer type produced by the array-to-pointer standard conversion (4.2) is used in place of P for type deduction;

因此，这里 "hello" 原本是一个数组类型，由于模板的参数不是引用类型，所以 "hello" 的类型被转换为指针类型 char const * 参加推导，正好与特化的 bar 函数匹配；

8.   bar(str);                                      // bar: generic char *

由于模板参数不是引用类型，没有 const 限定的 str 无法匹配特化的 bar，因此编译器实例化一个 void bar<char *>(char * t) 模板函数；

9.   bar(con_str);                                  // bar: special char const *

由于 con_str 与 "hello" 的类型一样，因此其结果与 7 是一致的；

10.   bar(p);                                        // bar: special char const *

这里 p 的类型本身就是特化函数的参数类型，显然要被推导为调用特化函数。

解释完了字符串参数的模板函数推导问题，下面来讨论一下 g++ 和 VS2008 的不同。上面同样的代码，使用 g++ 编译之后，输出是这个样子的：

foo: generic A6_c
foo: special PKc
foo: special PKc
foo: generic A6_c
foo: generic A6_c
foo: special PKc
bar: special PKc
bar: generic Pc
bar: special PKc
bar: special PKc
A6_c
A6_c
A6_c
PKc

当然，需要解释的是 g++ 内部对符号的字面做了一些变化，我们可以使用 c++filt demangle 这些符号：

$ c++filt [-t] A6_c PKc Pc
char [6]
char const *
char *

与 VS2008 的输出相比，我有一个疑问，为什么 g++ 没有为 const char [6] 输出正确的 const 类型名呢？

还有，我们提到了第 1 种情况下，编译器为 foo("hello") 调用实例化了一个 void foo<char const [6]>(const char (& t)[6]) 类型的函数。假如我们提供了一个类似的特化函数，那么 foo("hello") 会调用该特化函数；但是，使用 g++ 编译器时，特化函数的类型必须是 void foo<char [6]>(const char (& t)[6]) 而不是 void foo<char const [6]>(const char (& t)[6])，这让我感觉非常奇怪。只有不提供模板参数时，比如 void foo(const char (& t)[6])，两个编译器才能都推导出调用特化函数。

需要验证的话，您可以尝试在第一段代码中增加下面两个特化函数，再在两个编译器上编译那段代码：

template<>
void foo<char [6]>(const char (& t)[6])
{
  cout << "foo: special<char [6]> " << typeid(t).name() << endl;
}

template<>
void foo<char const [6]>(const char (& t)[6])
{
  cout << "foo: special<char const [6]> " << typeid(t).name() << endl;
}

您可能对这些感兴趣：

• 字符串参数的模板函数推导问题（续） (0)
• 多余的逗号？ (11)
• Math in CS：置换的轮换分解 (2)
• Cygwin GCC qsort 函数错误（续） (0)
• Cygwin GCC qsort 函数错误 (5)
• 将文本文件读入数组-C语言实现 (7)

要求：使用 C 语言将文本文件的每一行读入为数组的一个元素，返回一个 char ** 指针。

由于行长度和文本文件行数均未知，相当于二维 char 数组的两维长度都未定义。由于 getline 函数可以自动扩充 char 数组长度，我最初的想法是使用 getline 得到每行，然后每次对 char ** 进行 realloc，直到读完整个文件。

但是这种做法并不好，首先 getline 是 glibc 的扩展，而不是 C 语言的标准函数，使用除 gcc 以外的编译器是不一定能编译通过的；其次，每次对 char ** 指针进行 realloc 显得代码很 ugly。可以使用 fgets 替代 getline，但是就要自己来控制一维 char 数组的长度。

后来想想，换了一种思路，首先将整个文件读入内存，然后根据 '\n' 的个数来计算文件的行数，作为二维数组的长度，然后将所有的 '\n' 替换成 '\0'，并将每一行的指针赋给二维 char 数组，代码如下：

char ** text_2_array(const char *filename)
{
  char *p, **array;
  int lines;
  if(filename == NULL) return NULL;

  FILE *fp = fopen(filename, "r");
  if(fp == NULL) return NULL;

  /* Get file size. */
  fseek(fp, 0L, SEEK_END);
  long int f_size = ftell(fp);
  fseek(fp, 0L, SEEK_SET);

  /* Allocate space for file content. */
  char *buf = (char *) calloc(f_size, sizeof(char));
  if(buf == NULL) return NULL;

  fread(buf, sizeof(char), f_size, fp);
  fclose(fp);

  /* Get number of lines. */
  for(p=strchr(buf, '\n'), lines=1; p!=NULL; p=strchr(p, '\n'), lines++) {
    if(*p == '\n') p++;
  }

  /* Allocate space for array; split file buffer to lines by change '\n' to
     '\0'. */
  array = (char **) calloc(lines+1, sizeof(char*));
  array[0] = buf;
  for(p=strchr(buf, '\n'), lines=1; p!=NULL; p=strchr(p, '\n')) {
    if(*p == '\n') *p++ = '\0';
    if(p != NULL) array[lines++] = p;
  }
  /* Add a terminate NULL pointer. */
  array[lines] = NULL;
  return array;
}

其实读文本文件入数组这个功能在很多语言中是很简单的操作，比如 PHP 的 file 函数，或者 Bash 的 (`cat filename`)，都可以直接实现这个功能。但是对 C 这种更低级的语言来说，貌似就没那么简单了。我想要了解的是，除了我上面提到的两种思路，有没有更简单或者直接的方法来解决这个问题？比如一些我不熟悉的函数，或者一些 trick。

您可能对这些感兴趣：

• Math in CS：置换的轮换分解 (2)
• Cygwin GCC qsort 函数错误（续） (0)
• Cygwin GCC qsort 函数错误 (5)
• vasprintf 会将空间分配到栈上吗？ (11)
• 多余的逗号？ (11)
• Something About Scanf() In C (1) (0)

其实也不是第一次发生这种事情，一般情况下我忍一忍也就过去了，不就那么一段时间不能正常访问嘛。但很郁闷地是我现在正在找工作的关键关口，大家也都看到我在 CV 中列出了我的项目和博客，我可不想当 HR 对我简历感兴趣的时候却无法访问我列出的项目主页。因此我紧急搬了次家，至少希望在未来三个月到半年时间内不要出问题。

由于是独立主机，所以搬家过程算是相当无痛吧，把文件打个包再解包，数据库导出再导入，基本上没丢失啥，访问体验也没有任何改变。只是我多句牢骚，记以为志罢了。

最近博客更新频率大幅下降，可以想见我也是在忙碌和踌躇的当口，没什么好说的，祝自己好运吧！

附近照一张，身着 Perl T 恤乃是在 China-Pub 九周年会抽到的奖品——我第一次在活动中抽到奖品。

您可能对这些感兴趣：

• 一些关于博客的小变动 (5)
• Jan 28th, Train 1303 Heading Home (2)
• The Real World (0)
• 写在一个电闪雷鸣的雪夜 (4)
• 为求职事谢诸君 (15)
• 长假之购物 (6)

话说2008年12月中旬，我不慎丢失一张工行信用卡，打电话挂失并补办了一张后，网上银行就出现了问题。按说旧卡丢失后，网上银行账户要么自动切换到新卡，要么随旧卡一同删除，给用户以办新卡的机会。但是我到工行玉泉路支行办理开通网银业务时，却发现了一个诡异的问题：使用我的身份证号开办网银业务时，系统会提示类似用户已注册此项业务；但是拿身份证号去查询已开通网银帐号时，又无法找到。可能是工行的数据库在哪里发生了冲突。

就这么一个技术问题，我却等待了 9 个月，到今天才得以解决。大事时间表如下：

2008 年 12 月 15 日：第一次到营业厅办理网银，未果，营业员记下我的联系方式，承诺问题解决后通知我；
2008 年 12 月 25 日：第二次到营业厅咨询，营业经理打电话给上级部门，让我等候通知，再次留下联系方式；
2009 年 01 月 12 日：第三次到营业厅咨询，营业经理称上级部门曾在 12 月 29 日给他们答复，说批转开发中心处理，近期解决。下午 2 时，我致电 95588 第一次投诉；
2009 年 04 月 09 日：收到玉泉路支行电话，第四次到营业厅咨询，尝试仍无法开通，第二次投诉；

刚开始我很生气，这么简单的问题拖了那么久都无法解决。到4月份我的心态已经放平和了，之后我没有再记录到营业厅的时间，但是基本上一两个月会去咨询一下。然后八九月份工行通知了我两次去尝试开通网银，仍然没有解决。此事拖了那么久，而我还那么不依不饶，大概引起了北京分行领导的重视，最终总算在今天，2009年9月11日，得到了顺利解决。

从 08 年 12 月 15 日发现问题，到 09 年 9 月 11 日解决问题，这么小的一个技术问题拖了居然将近九个月才得以解决。我能说什么呢？是工行给开发部门的工资太低，导致员工都不好好工作？还是工行技术部门的人才策略出现问题，没有技术能人可以解决这么“复杂”的问题？还是工行对用户的投诉漠不关心？

可能会有人问：这世间好的网银多得是，你为什么死认工行一家呢？那是因为我觉得工行于我而言是最方便的。我只有工行和建行两家银行账户，建行的网银口令卡 5 元一张，只能使用 30 次，所以建行肯定不是一个选项。我只好选择工行，而且工行网点比较多，无论是自动还款还是上门还款都是很方便的。虽然很多银行，在网银的易用性方面是有口皆碑的，但是仍有诸多限制。比如招商银行，现在已经不给学生办信用卡了，而招行的储蓄卡日均存款低于 1 万块就要收取小额账户管理费，像我这种穷人肯定没有 1 万块在银行账户里放着呀，其它银行也都有类似的问题。工行的小额账户额度为日均 300 块，显然是更平民化一点儿，而且我的确有工行的信用卡，所以我就只好跟工行死磕了。

虽然处理过程太过漫长，但是我所遇到的工行的业务员还是很好的，至少没有哪个态度恶劣的。由于去玉泉路支行太多趟，某些业务员和经理见了面都能认得出我了。今天解决问题后，营业经理还送了我一个小礼物表示歉意。比较好的服务态度是唯一我觉得还不错的地方。

您可能对这些感兴趣：

• 写在一个电闪雷鸣的雪夜 (4)
• 为求职事谢诸君 (15)
• 长假之购物 (6)
• 博客被搬家 (13)
• 灭蟑记 (2)
• 兄弟写的不是博客，是失败感 (14)

这是一篇受密码保护的文章。您需要提供访问密码：

密码：

您可能对这些感兴趣：

• 为求职事谢诸君 (15)

第一次见到传说中的“小强”，是在南京上大学时。忘记是我的室友还是隔壁室友，打死了只蟑螂，喊大家都去看。但是在 PKU (Pukou University，非 Peking University) 的日子里，宿舍很新也比较干净，活的蟑螂还是没见过。自从搬到了鼓楼校区，住在 7 舍靠厕所的房间，真是什么动物都有呀。有大得吓人的蜘蛛、到处窜的蟑螂、半夜在床底下悉悉窣窣的耗子，还有那拉上蚊帐仍然要开着电筒在里面屠杀一阵的蚊子。南方的蟑螂，个儿都挺大的，和蛐蛐儿差不多，但是比蛐蛐儿要宽一些。

我在南京时，一直以为蟑螂是南方的动物，北方不会有。后来到了北京，才发现不是那么回事。因为供暖的缘故，北京的冬天里都会有蟑螂活动。尤其是我住过的那种出租屋，租住的人比较多，东西也堆得多，打扫也比较不仔细，自然有很多空间供蟑螂生存。但是北京的蟑螂有个特点，就是个儿很小，乍一看上去不太像蟑螂，但是一观察到它那快速的跑动和钻缝隙的功夫，就知道肯定是蟑螂了。

住在中关村的时候，偶尔会发现一两只蟑螂，不过公寓一年发了两次灭蟑饵料，效果貌似也不错。再加上住的那个楼是新生楼，每年都会被清空一次，蟑螂不是很猖獗。搬到玉泉来之后，刚开始也没有蟑螂的痕迹，不过最近一段时间，发现卫生间里蟑螂特别多。尤其是晚上，上厕所时一开灯，洗手台上好几只蟑螂往缝隙里钻，很多比蚂蚁大一点儿的蟑螂幼虫，看来是哪窝蟑螂在这安家了。

一年来玉泉这面都没有发灭蟑饵料，去楼管那里要了一袋，有些受潮，好像快过期的样子。在屋里撒了一圈，尤其是卫生间，撒得更多，发现部分饵料确实被吃光了，有那么一两天没看到蟑螂，以为起效果了。到了第三天，又发现了好几只蟑螂，看来是没什么用。幸好翻出来从上次离京朋友那里拾回来的垃圾，发现了一瓶灭蟑喷雾剂。于是每次见到蟑螂就对着它们喷一气，喷了几天，发现就剩下些特别小的蟑螂，看来效果还不错。

我很怀疑这些蟑螂是生活在洗脸池的防溢泄水口里面，但是那个口只有一条缝，也看不进去。不知道有没有什么有效的方法确定蟑螂巢穴的位置，这样就可以斩草除根了，不像现在只能见到一只杀一只。唉，看来维持宿舍的清洁还是很重要的，只是住集体宿舍的话，有时候会懒，别人的东西也不好动，总是尴尬。

您可能对这些感兴趣：

• Jan 28th, Train 1303 Heading Home (2)
• 写在一个电闪雷鸣的雪夜 (4)
• 为求职事谢诸君 (15)
• 长假之购物 (6)
• 博客被搬家 (13)
• 工行网银：用9个月的时间修正一个错误 (8)

AutoHotKey 是一个编辑和管理 Windows 热键的开源软件，SciTEAutoHotkey 是编辑 AutoHotKey 脚本的开源软件。（也许某些人会惊讶，AutoHotKey 居然不自带脚本编辑器，还要别人帮它写，我想这也许是受到 Unix 哲学的影响：Do one thing and do it well.)

AutoHotKey 脚本的基本语法是很简单的，前面是热键，后面是执行的命令，启动脚本后热键就会起作用了。键盘上每个特殊键对应的符号在热键列表中有列出，像我前面替换热键 Win+E 为打开“我的电脑”且无左侧栏的语句是：

#e::Run ::{20D04FE0-3AEA-1069-A2D8-08002B30309D}

::{20D04FE0-3AEA-1069-A2D8-08002B30309D} 是“我的电脑”的 CLSID(多谢 IronFeet 的提示)，如果需要打开非特种文件夹，就不需要这么麻烦了，直接类似于 #e::Run C:WINDOWS 即可。同理，设置用 Win+C 打开控制面板可以写成：

#c::Run ::{20D04FE0-3AEA-1069-A2D8-08002B30309D}::{21EC2020-3AEA-1069-A2DD-08002B30309D}

利用 AutoHotKey 可以做很强大的事情。比如我在 Linux 下使用 Evince 查看 pdf，可以使用 vim 的习惯，jkhl 上下左右移动 pdf 文档，那么我们可以在 Windows 下用 AutoHotKey 来实现对 Adobe Reader 同样的操控，语句如下：

#IfWinActive ahk_class AcrobatSDIWindow
j::Send {Down}
k::Send {Up}
h::Send {Left}
l::Send {Right}
#IfWinActive

这几句话的意思是，如果 AcrobatSDIWindow 这个 ahk_class 窗口在激活状态下的话，那么 jkhl 就被换成键盘上的上下左右键。AutoHotKey 的高级使用还是很麻烦的，它网站上的 Tutorial 是一个不错的入门教程。其实一般我都是用 Launchy 启动程序，对 AutoHotKey 的需求不是那么多，简单的几个组合键就够了。

我昨天才发现 Windows XP 家庭版和专业版的一个大区别：家庭版没有“组策略”编辑器。我电脑的“所有程序”->"启动"目录不知道被什么安全软件设置成只读了，我以为 ATTRIB 命令是修改文件权限的，却发现无法修改“启动”文件夹的权限。后来找到 CACLS 命令，可以用来指定特定用户对文件的访问权限，才把"启动"文件夹访问权限修改成了完全控制：

cacls 启动 /G Solrex:F

设置可写以后就可以把 AutoHotKey 脚本的快捷方式拖到“启动”文件夹，随系统一起启动了。

您可能对这些感兴趣：

• 跨平台音乐播放软件 Songbird (9)
• 谈谈 CoolSIP (7)
• 应用程序打包技术之四（exe篇） (0)
• 《使用开源软件-自己动手写操作系统》Rev 2发布 (24)
• Fix Black Screen After Boot Problem of Ubuntu 9.10 on D630 (5)
• 几种不得已时的上网办法 (4)

1. 手机作为 modem，使用 GPRS 拨号上网

这个一般受到手机版本影响，三星这方面做得非常不错。将手机使用数据线连接到电脑，打开 Samsung PC studio，选择 Network Wizard(网络向导?)，创建连接，连接名称随便写，比如“中国移动”，下一步调制解调器选择“Samsun Mobile USB Modem”，下一步国家选择中国，网络供应商选择“China Mobile(Beijing)”（其实选择哪个好像无所谓），用户ID选择“cmnet”，密码也是“cmnet”，创建完成后就可以拨号了。因网络状况或者 GPRS 版本不同，连接速度可能是 153.5 kbps，或者 460 kbps。

GPRS 资费是非常贵的，不在不得已或者包月流量用不完时，最好不要用 GPRS 上网；即使用 GPRS 拨号上网时，也要切记关掉所有自动联网的软件，比如禁用杀毒软件和操作系统的自动更新，禁用浏览器插件等等，这样才能将有限的网速使用在优先的程序上。

2. 使用 201 卡进行古老的 modem 拨号上网

使用 201 卡拨号上网可能会受到运营商的限制。经过我多次咨询 10010 和动手尝试，北京网通（联通）的“阳光心语普通快捷卡”拨号上网方式是这样的：首先将电话线插到笔记本的 modem 口（一般台式机已经没有这个口了）。创建一个新的连接，“连接到 Internet”->“手动设置我的连接”->“用拨号调制解调器连接”->选择笔记本电脑自带的调制解调器（我从来没想过我会有使用它的一天...）->ISP 名称，随便填，比如“201”->电话号码：“2012,语言种类,卡号#,密码#,16911#”，语言种类为打201电话时选择的数字->用户名：169，密码：169。设置完后就可以拨号了，刚开始会听到愉悦的 201 拨号机器回复，最后就要忍受一会儿嘈杂的拨号音了。201 拨号上网的速度大概为 46.6 kpbs...

使用 16911 拨号上网资费大概是 0.07 元一分钟，所以也是相当贵的，只是在 201 卡快过期或者不得已时才能为之。

3. 借用 IPv6 上的 Google App Engine 上网

这个大概只适用于高校使用教育网的学生了。Google，作为一间牛逼闪闪的公司，当其他互联网公司还在 IPv4 上晃悠时，Google 已经将其几乎所有服务部署在 IPv6 互联网上了。作为 IPv6 网络用户，您只需要将所有 Google 相关的域名在 hosts 文件(C:\WINDOWS\system32\drivers\etc, /etc/hosts)中映射到 2001:4860:c004::68 这个 IPv6 地址即可，格式例如：

2001:4860:c004::68 www.google.com mail.google.com clients1.google.com talk.google.com ssl.goo飞gle-analytics.com

就可以使用浏览器访问 IPv6 上的 Google 服务了。目前中国的 IPv6 网络上是没有审查制度的，所以在 Google 搜索时，您可以放心地搜索任意关键词，以及查看网页快照了。

但是目前只解决了访问 Google 的问题，如何访问其它网站呢？就不得不提到我前段时间发布的 Tohr 项目了。Tohr router 可以运行在 Google App Engine 上，所以您只需要将您的 Google App Engine 的域名，比如 example.appspot.com 照上面格式添加到 hosts 文件中，就可以利用 Tohr 结合 GAE 作为一个 IPv4 over IPv6 通道来上网了。当然，GAE 有很多限制，所以有些网站是铁定上不了的。为了实现浏览器自动选择直连 IPv6 的 Google 服务和使用 Tohr 代理访问其他网站，强烈推荐您阅读一下我的这篇博客文章《浏览器自动选择 Proxy 配置案例》。

使用这种方法起码在访问只需要阅读的网站还是 OK 的，Twitter 也可以直接登陆。部分在登录时检查 HTTP 请求 Referer 的网站是无法登录的，比如豆瓣、开心网、Facebook 等，这些时候不要责怪我，因为这是 GAE 的限制，不许用户自定义 Referer；或者 gmail, google reader 等，这也可能是 GAE 限制访问的网站。

但比较遗憾的是，除了第3种方法在 Linux 一样好用以外，前两种方法我都不知道如何在 Linux 上使用。

您可能对这些感兴趣：

• 用 Wireshark 分析 RTP 流 (6)
• Fix Black Screen After Boot Problem of Ubuntu 9.10 on D630 (5)
• Windows Tips: 修改热键和文件访问权限 (3)
• SVN 技巧：GUI 版本比较和可执行属性 (1)
• JPerf Single Jar with UDP BW Unit Fixed (0)
• qRFCview Proxy Patch (7)

$ more svndiff
#!/bin/bash
sed -i -e 's/^# diff-cmd.*$/diff-cmd=meld/' ~/.subversion/config
svn diff
sed -i -e 's/^diff-cmd.*$/# diff-cmd = meld/' ~/.subversion/config

其实就是用一个脚本 svndiff 来做 GUI 比较的工作。svndiff 执行时首先将 svn 配置文件中的比较工具改为 meld，然后进行比较，比较完后再将修改注释掉，这样就不会影响正常 svn diff 的功能。这样一来，svndiff 是 GUI diff，svn diff 就是命令行 diff。

设置文件可执行属性对 Windows 用户来说可能没什么用，可是对 Linux 用户来说用处就大了。没人希望每次一 update，就要重新对需要执行的脚本 chmod 一下。svn 修改文件可执行属性的命令太长了，我老记不住，所以放在这里做个笔记吧：

svn propset svn:executable ON filename

您可能对这些感兴趣：

• 使用 kdiff3 进行 svn 版本比较 (7)
• 在 Ubuntu 9.04 上安装 Kscope (4)
• 跨平台音乐播放软件 Songbird (9)
• Vim 中文输入法插件 Vimim (6)
• Ubuntu 9.04 安装手记 (8)
• 应用程序打包技术之三（rpm 篇） (0)

1. 我的朋友王聪的博客

... 谁知道这人怎么回复？第一条回复是问我是不是在说判断endian的技巧？扯淡！你自己的留言什么意思你自己不知道？！第二条回复中他似乎意识到自己前一个回复很白痴，于是补了一句Linux内核中没有。放屁！它有才怪呢！它凭什么要有？！貌似他们家的C语言技巧都是出自Linux内核！一个人能傻到这种地步真的挺不容易的！

别慌。他还能继续向我们证明他更傻呢！这个人在链接中给出了这么个地址，稍微有常识的人都看的出来，那是一个patch，那个patch的作者是Changli Gao，我review了这补丁，认为可以接受，然后Linus回复了，回复的意思也很简单，他不喜欢那个patch，他解释说如果用户程序能触发这个问题就说明你那程序是一坨shit。稍微有常识的人都明白这话什么意思：Linus只不过是借虚构的“你那程序”来说明这个问题不应该在内核中修复。而精彩的事情这时发生了！lovecreatesbeauty@gmail.c0m同学成功地把这话联想到了Linus所说的“你那程序”就是我写的程序！太伟大了！真不知道这人上小学时语文怎么学的？！估计他的语文老师看了都会气得跳楼自杀了！唉，语文没学好也就罢了，你找找整个邮件的存档，看看里面到底有没有shit程序啊。问题是他连找到没找就脑残式地下结论了。没找就没找吧，你仔细看看patch不行么？很不幸，他连patch是谁发的到看不出来！所以这个人不光脑残，眼也有问题，那么大大的一行Signed-off-by他看不到！！...more

2. Ubuntu 的 BUG tracker: Kubuntu 9.04 alpha6 panel corruption

#46 dotancohen wrote on 2009-06-14:

Are you trying to piss him off by any way that you can? You are not a developer, and you go around confirming and invalidating components, and playing ping pong confirmed/invalid with a dev. Then you make a remark like that?!? I personally am angry at you right now. I need this bug fixed, and you are going to piss off the developer so that he leaves us _both_ here to rot.

Go away. File a different bug, you have every right to as the dev implies that your issue is not the same as the OP (yes, that's me). Piss the devs off there. But let them do their work here and help those of us who appreciate it. ...more

简单地来说，就是开发者把该 BUG 标记为 Invalid，说该 BUG 应该是属于 Driver 的 BUG，有个用户不满意开发者对 BUG 的处理，就跟开发者对着干，开发者标记为 Invalid，他重新标记成 Confirmed，开发者开启一个新 BUG 报告，他去给人家改成 Invalid。一般来说修改 BUG 的状态应该是开发者来做，用户可以提交 BUG，assign 给某个开发者，但是不应该修改 BUG 状态，这是一种非常不礼貌的行为。一个用户一般情况下不可能比开发者对目标系统了解更多。

3. Wordpress 2.8.x(x<4) 的一个密码重设漏洞

From: laurent gaffie < laurent.gaffie_at_gmail.com >
Date: Tue, 11 Aug 2009 01:11:07 -0400

Mr Fabio,

You dont even understand the bug, so please shut the hell up.

2009/8/11 Fabio N Sarmento [ Gmail ] < fabior2_at_gmail.com >

> if this is an bug, please close Twitter.com, MSN.com and other services,
> because they have the same stupid "Reset password" service.
>
> So please make my day, and create a stupid script to flood with mutiple
> request to reset password. ...more

翻译过来就是，某个人发现了一个 Wordpress 2.8.x(x<4) 的密码重设漏洞，报告了出来。有个人评论说：“如果密码重设是 BUG 的话，那么所有网站都有 BUG 了，你没事干就写点儿傻逼程序去到处重设别人的密码吧。”然后报告漏洞的人就无奈了：“你根本没有理解这个 BUG，那么就请闭上你的臭嘴吧。”过了两天，Wordpress 就紧急发布了新版本 2.8.4，fix 了这个 BUG。

于是，我现在非常理解为什么 Linus 大神说话经常那么难听了，要是我成天跟这种人打交道，我也会抓狂。

有些人根本不了解和别人交流、在社区中交流应该遵循什么样的礼仪，应该使用什么样的方法。我遇到过的不礼貌行为包括（但不限于）：不去搜索 BUG 列表和邮件列表，一遍又一遍地提出重复的问题；有 BUG 列表和邮件列表时，还直接与开发者联系，或者只 reply 开发者，不知道 reply all 到邮件列表；提交 patch 时，不知道如何使用 diff 和 patch 工具，而是直接提交整个文件；描述 BUG 时，不提供 BUG 出现的环境和步骤，就来一句“xx出问题了”。尽管有时候我都懒的搭理这些人，但是我不想被别人认为是一个没礼貌的人，所以我都尽量回复，但的确心中很不爽。

我希望那些想要在社区中和别人讨论、交流并想赢得别人尊重的朋友能够多了解点儿社区交往的礼仪，起码应该去了解点儿入门的知识，免得遭受挫折打击积极性，反倒以为别人非常不友好不礼貌。推荐的基本资料包括：

1. 如果您想在邮件列表或者社区中提问，那么请首先阅读 “How To Ask Questions The Smart Way ”，中文翻译《提问的智慧》

2. 如果您想提交软件 bug, patch, feature request 并想得到开发者的尊重和重视，那么请首先阅读“The Art of Unix Programming” 第 19 章的“Best Practices for Working with Open-Source Developers”。

您可能对这些感兴趣：

• 解决 GAppProxy Set-Cookie 和 HTTPS Cert Bugs (14)
• Windows Tips: 修改热键和文件访问权限 (3)
• JPerf Single Jar with UDP BW Unit Fixed (0)
• qRFCview Proxy Patch (7)
• Wordpress 2.8 和 2.8.1 beta1 毛病真多 (9)
• vasprintf 会将空间分配到栈上吗？ (11)