Shell's Home

May 14, 2012 - 2 minute read - Comments

语言的效率差异1

问题

为了测试语言的效率,做一个正则解析。

预先说好,正则解析的问题是老板正在做的一个实际问题,我把其他和效率无关的部分去了。因此我接受“用法不正确”这样的反驳理由,但是不接受“这不是典型用例”的理由。我欢迎你指正我的用法错误,或者对语言不了解导致的效率低下,但是别来和我吵吵这种例子太特殊。另外,在调整代码和评估速度的时候,顺便注意一下代码行数。我知道用汇编逐行写和优化会很优秀,但是这对实际工作基本没有帮助。

问题是这样的:

有一个文本文件,每行两个数,要求解析出来这两个数。

我用python生成了数据,代码是这样的

with open(sys.argv[1], 'w') as fo:
    for i in xrange(500000):
        fo.write('%d %dn' % (i, random.randint(0, 10000)))

正则分析速率,是个典型的CPU密集操作。对于非编译型语言而言(这里的编译是指正则表达式的解析预编译,实际上除了lisp还真没有编译型的,即使是go也是现场拿到正则进行解析的),这主要是看正则库的实现效率。很多时候,语言的效率问题并不取决于语言本身,还取决于语言的库的实现。大部分情况下我们都不可能砍掉系统的库重新来一个,那还不如换一门语言。

python

我首先贴出python语言的解答。

reline = re.compile('(d+) (d+)')
def main():
    with open(sys.argv[1], 'r') as fi:
        for line in fi: reline.match(line).groups()

这是性能

real  0m0.466s
user  0m0.436s
sys   0m0.012s

common lisp

我找了N个正则包,实际能用的只有ppcre。有些包号称很快,实际测试下来还不如ppcre。

(require :cl-ppcre)

(defun grepfile (filename)
  (let*
      ((cl-ppcre:*use-bmh-matchers* t)
       (cl-ppcre:*regex-char-code-limit* 256)
       (scanner
    (cl-ppcre:create-scanner "d+ d+")))
    (with-open-file (in filename)
      (loop
     for line = (read-line in nil) while line do
       (cl-ppcre:split scanner line)))))

代码在slime里面测试(time (grepfile “data.dat”)),下面是结果

CL-USER> (time (main))
Evaluation took: 0.398 seconds of real time 0.392025 seconds of total run time (0.384024 user, 0.008001 system)
[ Run times consist of 0.016 seconds GC time, and 0.377 seconds non-GC time. ]
98.49% CPU 1,188,481,425 processor cycles 72,242,256 bytes consed

go

go的代码是现学现卖的,不知道是不是哪里写出问题了。

func main()
{
    f, _ := os.Open("data.txt")
    r := bufio.NewReader(f)
    rex, _ := regexp.Compile("(d+) (d+)")
    for line, isPrefix, err := r.ReadLine();err == nil && !isPrefix; line, isPrefix, err = r.ReadLine() {
        rex.FindSubmatch(line)
    }
}

结果居然要差一个数量级!

real 0m8.699s
user 0m8.593s
sys 0m0.036s

这太出乎我的意料了。google的v8引擎赫赫有名,我猜想也应当用到了go上面才是,怎么会性能差成这样?gary说过正则在他那里很快,我希望是我用错了。

lua

lua没有使用正则包,更准确的说,lua内置的字符串处理函数可以处理这个情况。以下是我的代码:

for line in io.lines("data.txt") do
    for w in string.gmatch(line, "%d+") do
        print(w)
    end
end

以下是执行结果:

real 0m0.796s
user 0m0.792s
sys  0m0.000s

lua的代码的却很好看,但是效率上却不见得高。这是当然的,gmatch可是每工作一次就要解析一次阿。

lua-rex-pcre

装一个支持pcre的正则包,lua-rex-pcre。

r = require "rex_pcre".new("(d+) (d+)", 0)
for line in io.lines("data.txt") do
    r.match(r, line)
end

OK,速度一下就快了不少:

real 0m0.643s
user 0m0.632s
sys  0m0.008s