2012年5月30日星期三

@shell909090: 语言的效率差异2

 
 

satan 通过 Google 阅读器发送给您的内容：

 
 


# 问题 #
为了更深入的测试语言，我做了一个经典问题——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

 
 

可从此处完成的操作：

 
 
发帖者 时间：

没有评论:

发表评论

订阅： 博文评论 (Atom)