CWYAlpha

Just another WordPress.com site

Thought this was cool: 语言的效率差异2

leave a comment »


# 问题 #
为了更深入的测试语言,我做了一个经典问题——24点。
这个问题主要是测试递归,循环效率,还有数组和树的复制性能。
为了简化问题,方便测试,我的问题是这样描述的:
> 有一个数组,里面有多个正整数。有一个操作数组,其中每个都是双目操作符。找出以两者构成算式,其值等于给定值的所有表达式组合。

> 要求不得遗漏,可以有少量重复。例如可交换算符的交换同构暂不做排重。

实际运行的时候,取+-*/和3 4 6 8,运行100次,查看时间消耗。正确的单次输出结果应当是这样的。
> (((8 + 4) / 3) * 6) = 24
> (6 / (3 / (8 + 4))) = 24

> (((8 + 4) * 6) / 3) = 24

> (((8 / 4) + 6) * 3) = 24
> (((8 – 6) * 3) * 4) = 24
> (((8 – 6) * 4) * 3) = 24
> (((3 * 4) – 8) * 6) = 24
> ((8 – (6 / 3)) * 4) = 24
> (((4 + 8) / 3) * 6) = 24
> (6 / (3 / (4 + 8))) = 24
> (((4 + 8) * 6) / 3) = 24
> (((8 / 4) + 6) * 3) = 24
> (((4 * 3) – 8) * 6) = 24
> (((8 – 6) * 3) * 4) = 24
> (((8 – 6) * 4) * 3) = 24
> ((8 – (6 / 3)) * 4) = 24
# python #
python的解很复杂,长达31行,以下是我写的解。当然,还有更简单的版本,我可以用eval来干这个事情,代码只有24行,但是确实给人很evil的感觉。

from itertools import combinations

class opt(object):
   def __init__(self, name, func, ex=True):
       self.name, self.func, self.exchangable = name, func, ex
   def __str__(self): return self.name
   def __call__(self, l, r): return self.func(l, r)
   def fmt(self, l, r):
       return ‘(%s %s %s)’ % (fmt_exp(l), str(self), fmt_exp(r))
def eval_exp(e):
   if not isinstance(e, tuple): return e
   try: return e[0](eval_exp(e[1]), eval_exp(e[2]))
   except: return None
def fmt_exp(e): return e[0].fmt(e[1], e[2]) if isinstance(e, tuple) else str(e)
def print_exp(e): print fmt_exp(e), eval_exp(e)
def chkexp(target):
   def do_exp(e):
       if abs(eval_exp(e) – target) < 0.001: print fmt_exp(e), ‘=’, target
   return do_exp
def iter_all_exp(f, ops, ns, e=None):
   if not ns: return f(e)
   for r in set(ns):
       ns.remove(r)
       if e is None: iter_all_exp(f, ops, ns, r)
       else:
           for op in ops:
               iter_all_exp(f, ops, ns, (op, e, r))
               if not op.exchangable:
                   iter_all_exp(f, ops, ns, (op, r, e))
       ns.append(r)
opts = [
   opt(‘+’, lambda x, y: x+y),
   opt(‘-‘, lambda x, y: x-y, False),
   opt(‘*’, lambda x, y: x*y),
   opt(‘/’, lambda x, y: float(x)/y, False),]
if __name__ == ‘__main__’:
   for i in xrange(100): iter_all_exp(chkexp(24), opts, [3, 4, 6, 8])
以下是100次的时间:
> real 0m2.259s
> user 0m2.248s
> sys 0m0.004s
# common lisp #

lisp来解这个问题简直是作弊,难怪被叫做人工智能语言。

(defun chkexp (target)
 (lambda (e)
   (if (equal (ignore-errors (eval e)) target) (print e))))
(defun exchangeable (op)
 (not (member op ‘(- /))))
(defun iter-all-exp (f ops ns &optional e)
 (cond
   ((not ns) (funcall f e))
   ((not e) (dolist (r (remove-duplicates ns))
      (iter-all-exp f ops (remove r ns :count 1) r)))
   (t (dolist (r (remove-duplicates ns))
(let ((nss (remove r ns :count 1)))
  (dolist (op ops)
    (iter-all-exp f ops nss `(,op ,e ,r))
    (if (not (exchangeable op))
(iter-all-exp f ops nss `(,op ,r ,e)))))))))
(iter-all-exp (chkexp 24) `(+ – * /) `(3 4 6 8))
只有短短17行。原因在于,lisp本身的ast即是用数据结构表示的,因此根本不需要我做eval函数,也不需要画蛇添足的弄自定义算符,直接用系统算符上。显示,打印,都是现成的。需要写的只有主体逻辑。结果也很特别:
> (* (- (* 3 4) 8) 6) 
> (* (- 8 (/ 6 3)) 4) 
> (* (- (* 4 3) 8) 6) 
> (* (/ (+ 4 8) 3) 6) 
> (/ 6 (/ 3 (+ 4 8))) 
> (/ (* (+ 4 8) 6) 3) 
> (* (+ (/ 8 4) 6) 3) 
> (* (- 8 (/ 6 3)) 4) 
> (* (* (- 8 6) 3) 4) 
> (* (* (- 8 6) 4) 3) 
> (* (/ (+ 8 4) 3) 6) 
> (/ 6 (/ 3 (+ 8 4))) 

> (/ (* (+ 8 4) 6) 3) 

> (* (+ (/ 8 4) 6) 3) 
> (* (* (- 8 6) 3) 4) 
> (* (* (- 8 6) 4) 3) 
不但行数只有一半,速度也很让人吐血,比python快了近一倍,这是100次的结果。
Evaluation took:
 1.379 seconds of real time
 1.372086 seconds of total run time (1.372086 user, 0.000000 system)
 [ Run times consist of 0.012 seconds GC time, and 1.361 seconds non-GC time. ]
 99.49% CPU
 3,628,800 forms interpreted
 4,127,047,350 processor cycles
 102,577,080 bytes consed
# go #
# lua #
lua的代码是所有语言中最罗嗦的,足足长达60行,超过python许多。
function find_item(tbl, obj)
  for i, v in pairs(tbl) do
     if v == obj then return i end
  end
  return nil
end
function remove_duplicates (tbl)
  local newtbl = {}
  for i, v in pairs(tbl) do
     if find_item(newtbl, v) == nil then
table.insert(newtbl, v)
     end
  end
  return newtbl
end
function fmt_exp (e)
  if type(e) ~= ‘table’ then
     return tostring(e)
  else
     return ‘(‘ .. fmt_exp(e[3]) .. e[1] .. fmt_exp(e[4]) .. ‘)’
  end
end
function eval_exp (e)
  if type(e) ~= ‘table’ then
     return tonumber(e)
  else
     return e[2](eval_exp(e[3]), eval_exp(e[4]))
  end
end
function chkexp (target)
  return function (e)
    if eval_exp(e) == target then
print(fmt_exp(e))
    end
 end
end
function iter_all_exp (f, ops, ns, e)
  if table.maxn(ns) == 0 then return f(e) end
  for i, r in pairs(remove_duplicates(ns)) do
     table.remove(ns, find_item(ns, r))
     if e == nil then
iter_all_exp(f, ops, ns, r)
     else
for op, fp in pairs(ops) do
   iter_all_exp(f, ops, ns, {op, fp, e, r})

   if find_item(exchangable, op) == nil then

      iter_all_exp(f, ops, ns, {op, fp, r, e})
   end
end
     end
     table.insert(ns, r)
  end
end
exchangable = {‘+’, ‘*’}
opts = {
  [‘+’] = function (a, b) return a + b end,
  [‘-‘] = function (a, b) return a – b end,
  [‘*’] = function (a, b) return a * b end,
  [‘/’] = function (a, b) return a / b end,
}
iter_all_exp(chkexp(24), opts, {3, 4, 6, 8})
其实lua的代码很好看,自然语言风格,语言写出来后都能看懂。然而lua秉持了最小化内核的方针,死活不提供一些很常用的函数。我上来近15行全在写常用函数,查找某个值在表中的位置,还有除去表中的重复元素。实现下来,效率也不是特别高,基本和python相当。
> real 0m2.222s
> user 0m2.184s
> sys 0m0.000s

from shell's home: http://shell909090.com/blog/2012/05/%e8%af%ad%e8%a8%80%e7%9a%84%e6%95%88%e7%8e%87%e5%b7%ae%e5%bc%822/

Written by cwyalpha

五月 18, 2012 在 5:25 下午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: