前几天看到同学写matlab代码时,随手写上tic、toc就记录了时间,甚感震惊——居然计时函数可以如此简洁。
  一般写 C 程序测速时,需要先记录起始时间,然后在结束时再次记录时间,并输出时间差。算起来要3行代码才能完成一个计时任务。一般用起来倒也不算麻烦,但是在寻找程序热点的时候,每几行代码就加入一段冗长的计时代码,会非常的碍眼。
  在此诱惑之下,我写了一个简单的计时器,使用时只需在开始计时时写上“tic”,后面每个需要计时的节点写上“toc”,在需要的时候使用“tictoc(stdout);”就可以输出各部分的运行时间。输出的格式形如“line 12-15: 0.87”。
  经过简单的预判断,程序可以支持 Windows 和 Linux,一般自己写点小程序够用了。
  程序也有一些缺陷,比如只支持单文件,不能在并行的程序快内使用。另外如果需要获得更好的精度及效率,Windows 下应使用 QueryPerformanceCounter(),Linux 下应使用 clock_gettime(),替代 getTime() 的实现。

  P.S. 如果想知道程序的热点,使用 Intel Amplifier 是一个很好的选择,可以看精确到行的耗时,也可以查看程序的并行程度,有针对性地提高性能。在官网上可以下载并免费申请一个月的试用 license。

继续阅读

  很久很久以前,当我想用 C 语言处理中文时,遇到了一些麻烦:C 语言中的 char 只占用 1 字节,但是 GBK 编码的汉字会占用两个字节。如果直接使用 char,会遇到一些非常神奇的问题,比如“页苑估”字符串中含有“吃饭”子串[1]。处理 GBK 编码其实也挺简单,判断一下,如果发现某个 char 的最高位是1,就和下一个 char 合起来考虑。偷懒的办法就是预处理一遍,把合并后的结果存到 short int(其实还有 wchar_t 这种专用的宽字符变量类型,使用时需要注意在 Windows 下是2字节,而在 Linux 下是4字节) 里,这样每个变量就可以表示一个字符了。

  当我知道 C#、Java 的 char 是一个 16 位的存储单元时,我就开始天真的以为“终于一个 char 可以表示一个汉字了”。虽然之后也听说了 C# 和 Java 中的 char 是以 Unicode 的形式存储的(确切的说,是 UTF-16),但是对一个 char 表示一个字符的观念,一直没有改变,直到昨天膝盖中了一箭……

  我在处理维基百科语料时,想统计一下里面出现了多少种不同的字符。随手就写了一个逐 char 的循环,统计之后输出 <char, 出现次数> 的二元组。 结果写文件的时候,抛出了这个异常:

未经处理的异常: System.Text.EncoderFallbackException: 无法将位于索引 551 处的 Unicode 字符 \uD86A 转换为指定的代码页。

  搜索良久,没发现有人遇到这个问题。只好开始猜想,是不是有些字符能用 UTF-16 表示,但不能用 UTF-8 表示?又或许有些 char 不能独立存在?

  第二个猜想在 Unicode 的官网找到了答案[2],同时也否定了第一个猜想:

The Unicode Standard encodes characters in the range U+0000..U+10FFFF, which amounts to a 21-bit code space. Depending on the encoding form you choose (UTF-8, UTF-16, or UTF-32), each character will then be represented either as a sequence of one to four 8-bit bytes, one or two 16-bit code units, or a single 32-bit code unit.

  里面涉及了两个要点。1. Unicode 编码的范围是固定的,Unicode 字符可以选用 UTF-8、UTF-16、UTF-32 这些编码方式来存储,也就是说这三种编码方式可以无损转换。2. 一个 Unicode 字符,在使用 UTF-16 编码方式存储时,会使用1个或两个码元(code unit),也就是 C# 里面的 char。

  于是有些Unicode字符,在 UTF-16 编码方式下,需要用两个码元来表示。在维基百科里找到一个例子:“𪚥”。这个字就需要两个码元来表示。UTF-16 把表示这种字的两个码元称作“代理对(surrogate pair)”,代理对由高位代理和低位代理组合而成,下面的 C# 代码展示了这个分解过程。

var str = "𪚥";
Console.WriteLine(str.Length);
Console.WriteLine(Char.IsHighSurrogate(str[0]));
Console.WriteLine(Char.IsLowSurrogate(str[1]));

  那是不是一个 Unicode 字符就是一个显示字符呢?答案居然是“否”!

  世界上还有“组合字符[4]”这种神一般的存在,最常见的一个肯定很多人都见过“ส้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้”。用来破坏排版的神器。这真的是一个显示字符,不信的话,你可以把它复制下来粘贴到 Word 里,看看是不是占了一个字符的位置。当然,一些比较弱的软件可能不能正常显示这个字符。组合字符一般是用来给拉丁文加重音符号等附加符号的,比如 Ä = A + ¨,也可以在一个字符后面加入一堆附加符号,形成刚才那个神器的效果。

  当然,C#这样的高级语言处理显示字符也是比较方便的,使用 StringInfo [5]类即可,比如下面的代码会输出 39、1。想要逐字符提取可以用 StringInfo 类中的其它方法,非常方便。Java 中应该也有类似的方法,没去调研。

var str = "ส้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้";
Console.WriteLine(str.Length);
StringInfo si = new StringInfo(str);
Console.WriteLine(si.LengthInTextElements);

  最后,在@trouger 的帮助下,我们发现 UTF-8 编码[6]在多字节时,各字节的首位均是 1。利用这一点,如果我想用 C 语言写一个简单的程序,把 UTF-8 编码的文件按照空格分割(或者任意ASCII字符),直接使用 C 语言的 char 就可以完全胜任,无需考虑复杂的编码方式。

[1] 百度之星2007程序设计大赛 两场初赛题目点评 http://www.baiduer.com.cn/2007-06/1207.html
[2] UTF-8, UTF-16, UTF-32 & BOM http://www.unicode.org/faq/utf_bom.html
[3] 码元 – 维基百科 http://zh.wikipedia.org/wiki/码元
[4] 组合字符 – 维基百科 http://zh.wikipedia.org/wiki/组合字符
[5] StringInfo Class http://msdn.microsoft.com/en-us/library/system.globalization.stringinfo.aspx
[6] UTF-8 – 维基百科 http://zh.wikipedia.org/wiki/UTF-8

  重要更新:在@老赵的提醒下,如果在请求中加入“Accept-Encoding: gzip, deflate”,下面的问题就会自动消失。具体见文章末尾。

  两年前我用C#写了一个爬虫类,一直在用。今天终于出错了。让我代码出错的页面是:http://www.hacker.org/challenge/solvers.php?id=1

  这个页面非常之强大,好多简单的爬虫都失效了,比如这段C#代码:

WebClient webClient = new WebClient();
webClient.DownloadData("http://www.hacker.org/challenge/solvers.php?id=1")

  还有php的curl(参考示例),以及Python的opener等,如果直接调用,都会中枪。

  当然,一般的浏览器都能毫无压力正常打开这个页面。

  用上述简易方式下载网页,最后都只能下载到 72k 的内容,但是实际上,这个页面有200多K。剩下的这个内容为什么不能直接抓取到呢?下面来分析一下这朵奇葩,并且给出解决方案。

继续阅读

这三天都在看JavaScript的闭包,终于有点眉目了。

动力

去年在看《黑客与画家》的时候,被里面对不同编程语言描述能力的差异所吸引。
里面描述了if-else、函数递归、闭包、宏等多个语言的抽象层次。
既然闭包是语言的一种重要抽象,我决心要弄清楚是怎么回事。

方法

从JavaScript入手,是因为对js的基础语法还比较熟悉,从这里开始看起容易接受。
按照网上的说法,犀牛书(《JavaScript权威指南》)介绍js的闭包非常清晰易懂,我就从此书看起。主要就看了第四章变量和第八章函数。
但是闭包的最后一个例子不能理解,于是又搜到了一个书评,这个解释很受启发。
另外还有所谓闭包.pptx,这个只是浏览了一下。

认识

花了三天时间,回想起来,从看js的变量作用域,到理解函数作为一个对象,可以被随意传递从而发生的各种“匪夷所思”的事,对闭包逐渐有了脉络。
现在觉得闭包这个称呼也很贴切:一个函数带上它周围的变量包成一团封起来(不过一般习惯上这个函数就叫闭包了,并没把附带周围的变量叫到一起……)。里面的变量逃不出去,不会污染外面的变量名;外面也没法攻入,垃圾回收不能随意收回里面的变量。这团闭包还独立地存在着,携带着里面的东西,帮着别的对象完成一些功能。
犀牛书的前两个例子就是说明了外面没法直接访问闭包内的变量,必须通过指定的方法来访问。相当于class中定义了private的变量。但是这里并不像C++那样,让编译器去识别某个变量外部能不能访问,而是直接通过语言本身的特性,让外面没法访问到。这种设计让语言更为精巧。
第三个例子是利用了闭包可以携带周围变量,构造了一个调试工具。

虽然自认为理解了闭包的原理,不过到灵活运用还有很长的路要走。推崇lisp的人鼓励使用闭包,现在还很难理解那种函数式变成的思考方式。期待有时间进一步学习更抽象的语言。