论坛标准nth和where及cdddr实现的三种nth效率问题

newer

前几天大家讨论了求子表效率的问题，得到了结论，就是在循环里面获取连续的子表的时候尽量不要用nth函数，而是通过cdr和where结合取得各个位置的元素，这样效率最好，得到的结论好像是nth效率不高，

下面通过测试，来看看

下面函数是取得大表前n 项的子表
(l-where  3 '(1 2 3 4 5 6 7)) =>'(1 2 3)

1. ;;通过WHERE和CDR结合，通过取得表头元素获得当前位置的元素
   
2. (defun l-where (n lst / a i v)
   
3.   (setq i 0)
   
4.   (while (and (< i n)
   
5.               (setq v (car lst))
   
6.          )
   
7.     (setq a   (cons v a)
   
8.           lst (cdr lst)
   
9.           i   (1+ i)
   
10.     )
    
11.   )
    
12.   a
    
13. )
    
14. ;;直接通过NTH得到具体位置的元素，构建连续的表
    
15. (defun l-nth (n lst / a)
    
16.   (if (< n (length lst))
    
17.     (progn
    
18.       (setq i 0)
    
19.       (while (< i n)
    
20.         (setq a (cons (nth i lst) a)
    
21.               i (1+ i)
    
22.         )
    
23.       )
    
24.     )
    
25.   )
    
26.   a
    
27. 
    
28. )
    

;;通过WHERE和CDR结合，通过取得表头元素获得当前位置的元素<br /> (defun l-where (n lst / a i v)<br />   (setq i 0)<br />   (while (and (< i n)<br />               (setq v (car lst))<br />          )<br />     (setq a   (cons v a)<br />           lst (cdr lst)<br />           i   (1+ i)<br />     )<br />   )<br />   a<br /> )<br /> ;;直接通过NTH得到具体位置的元素，构建连续的表<br /> (defun l-nth (n lst / a)<br />   (if (< n (length lst))<br />     (progn<br />       (setq i 0)<br />       (while (< i n)<br />         (setq a (cons (nth i lst) a)<br />               i (1+ i)<br />         )<br />       )<br />     )<br />   )<br />   a<br /> <br /> )<br />

测试结果：



可以看出，用where实现的nth取得子表效率要高于用nth, 但是什么时候用nth都会慢吗？

下面通过用where,cdddr实现的nth和nth 就单个取一个元素来看看效率。

1. ;;标准nth
   
2. (defun nth-nth(n lst)
   
3.   (nth n lst)
   
4. )
   
5. ;;where实现nth
   
6. (defun nth-where (n lst)
   
7.   (setq i 0)
   
8.   (while (and (< i n)
   
9.               (setq v (car lst))
   
10.          )
    
11.     (setq i   (1+ i)
    
12.           lst (cdr lst)
    
13.     )
    
14.   )
    
15.   v
    
16. )
    
17. ;;cdddr实现nth
    
18. (defun nth-cdddr (n lst)
    
19.   (repeat (/ n 4)
    
20.     (setq lst (cddddr lst))
    
21.   )
    
22.   (repeat (rem n 4)
    
23.     (setq lst (cdr lst))
    
24.   )
    
25.   (car lst)
    
26. )
    
27. 
    

;;标准nth<br /> (defun nth-nth(n lst)<br />   (nth n lst)<br /> )<br /> ;;where实现nth<br /> (defun nth-where (n lst)<br />   (setq i 0)<br />   (while (and (< i n)<br />               (setq v (car lst))<br />          )<br />     (setq i   (1+ i)<br />           lst (cdr lst)<br />     )<br />   )<br />   v<br /> )<br /> ;;cdddr实现nth<br /> (defun nth-cdddr (n lst)<br />   (repeat (/ n 4)<br />     (setq lst (cddddr lst))<br />   )<br />   (repeat (rem n 4)<br />     (setq lst (cdr lst))<br />   )<br />   (car lst)<br /> )<br /> <br />

上面测试表明，单独去一个具体位置的元素，nth 要 秒杀 用 cdddr,where实现的两个函数，差的数量级不是一点半点，表越长，取得的位置越靠后，nth 快的越多。

所以，nth不是什么时候都慢的，结论：
1、如果是只取得一个元素，标准的nth函数是最快的。
2、如果是在循环里面，要取得很多元素，这时候nth才慢于用cdr和where实现的，所以循环里面取得很多元素的时候，不建议用nth。


下面我们来单独测试下cdddr实现的nth 和 标准的 nth 自己和自己，取得不同位置元素的效率比较：




上面测试结果表明：


1、nth 函数在取得各个不同位置的元素，时间差别很小，所以ALISP的nth函数，绝不是顺序遍历内部表，一定是表在ALISP内部进行了特别的处理。绝不是从头遍历到指定位置。 90000的数据和1000的数据时间只是相差3秒多。


2、CDDDR和WHERE CDR实现的比较，都是从头往后面遍历顺序读取，因为CDDDR步幅是CDR的四倍，所以CDDDR要快了2倍多，但是90000和1000的时间差距是上百倍。

炫翔

楼主分析的很透彻，nth本身就是效果很多的循环

炫翔

楼主分析的很透彻
nth本身就是效果很高的循环
要在表中取出多个值的时候，如果还用nth的话，哪么就是 外层循环 * nth循环 的次数，自然慢了

marting

炫翔 发表于 2017-6-11 16:43

从上面测试最后的结论1看， nth取一个数，不是循环，基本上直接就定位了。有高级语言数组或VECTOR的类似的查询方式。

ll_j

应该就是“指针”吧，直接按索引读地址，在一般情况下都要快，关键是不太受表大小影响。
虽然AutoLisp不支持用户级的读写地址，但不能确定其内核不能读写，我想，除了所谓的七个基本函数外，现在公开的这些函数效率也都是无法用用户函数能取代的（当然，也有效率高于系统函数的情况，但也只是特例），所以，编程时，使用最合适函数应该是提高效率的关键。

aeo

应该是交互的越少越快。
比如求p1 p2点的距离,或者p1往某方向移动，
用distance 和 polar
要比mapcar 代数求要快很多，
因为mapcar 要向lisp输入的数据次数多好几次.

xinxirong

弄个arx版的nth吧，估计比nth慢1倍。