前几天,碰到一个题目,因为是racket的练习,很自然的,就是关于递归的。

题目要求实现一个名为lenlen的函数,这个函数的数学定义是下面这样的:

1
2
3
LenLen(0) = 1
LenLen(1) = 2
LenLen(n) = digsum(n) + LenLen(n-1) + len(LenLen(n-1)) + len(len(LenLen(n-1)))

其中,digsum函数是数值n的每位数字之和,len函数是数值n的位数。

对于racket的函数实现,题目提出了性能要求,如果不能在合理时间内完成4位数的计算, 则判定为性能不达标。另外,题目给出了2个已知的结果,lenlen(123456)=3643889lenlen(123457)=3643919。很显然,这是在暗示具体的实现要能跑通这2条结果。

要实现lenlen,首先要实现digsumlen。相对来说,len实现起来更简单, 先写这个,然后再实现digsumlenlen

len函数

这个函数,可以通过检索字符串长度实现,可以写作下面这样:

1
2
(define (len n)
  (string-length (number->string n)))

digsum函数

要实现这个函数,首先就得把数值n的每位数字提取出来,然后才能进行相加。 提取数字,可以通过转换为字符串来实现。因为题目要求不得使用apply、map之类的高阶函数, 所以,求和也只能用递归来实现。

先来写求和函数,可以写作下面这样:

1
2
3
4
(define (mysum lst)
  (cond
    [(null? lst) 0]
    [else (+ (string->number (car lst)) (mysum (cdr lst)))]))

有了求和函数,digsum基本上就算完成了:

1
2
(define (digsum n)
  (mysum (explode (number->string n))))

而之所以不用lambda,也是因为题目不允许使用。

lenlen函数

有了digsumlen之后,写lenlen就很简单了,可以写作下面这样:

1
2
3
4
5
6
(define (lenlen n)
  (cond
    [(zero? n) 1]
    [(= 1 n) 2]
    [else
       (+ (digsum n) (lenlen (- n 1)) (len (lenlen (- n 1))) (len (len (lenlen (- n 1)))))]))

是不是很简单?

只是,上述代码在跑(lenlen 10)的时候,就会卡顿,在这种情况下,验证123456的值肯定是不可能的。 好在,题目后面也给了提示,说应该使用local。那就加上local再试试呗。

加了local之后,上述代码可以写作下面这样:

1
2
3
4
5
6
7
(define (lenlen n)
  (cond
    [(zero? n) 1]
    [(= 1 n) 2]
    [else
     (local [(define n1 (lenlen (- n 1)))]
       (+ (digsum n) n1 (len n1) (len (len n1))))]))

再跑一遍(lenlen 10),几乎是瞬间就有了结果,看来疗效不错。 跑一下123456,也可以在三五秒的时间内,给出与前文一致的准确结果。 由此看来,使用local保存中间结果,十分有必要。

如果再增加一个临时变量,储存len的中间结果呢?

1
2
3
4
5
6
7
8
(define (lenlen n)
  (cond
    [(zero? n) 1]
    [(= 1 n) 2]
    [else
     (local [(define n1 (lenlen (- n 1)))
             (define n2 (len n1))]
       (+ (digsum n) n1 n2 (len n2)))]))

测试下来,好像又变快了一点点。

autolisp能否跑得通题目中的2条测试呢?

因为在Dr racket里边跑1条测试,需要好几秒的时间,就想着试试autocad 的lisp环境, 看看会不会更快一点。

要用autolisp来跑,代码就要稍微改造一下,可以写作下面这样:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
(defun mysum  (lst)
  (cond 
	((null lst) 0)
	(t (+ (atoi (chr (car lst))) (mysum (cdr lst))))))

(defun digsum (n) (mysum (vl-string->list (itoa n))))

(defun len (n) (strlen (itoa n)))

(defun lenlen  (n / n1 n2)
  (cond 
	((zerop n) 1)
	((= 1 n) 2)
	(t
	 (setq n1 (lenlen (1- n))
		   n2 (len n1))
	 (+ (digsum n) n1 n2 (len n2)))))

在autocad 2012的visual lisp ide中进行测试,跑123412345,都是瞬间就给出结果了, 和dr racket的运行速度一样快。然而,很遗憾,123456是跑不通的,提示堆栈溢出了。

经过十几次的测试,发现上述代码能跑通的最大值是19973,跑19974就会溢出。

由此看来,autocad的lisp运行时,性能确实不咋的啊,堂堂一款商业软件,连人家一个教学平台都不如。