问题

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