关于 Nth 效率的一个探讨

st788796

C++ 中对数组都是 用 [] 直接取地址，Autolisp 中表数量多的时候用 Nth 虽然可以取，但效率一直被诟病，是不是可以改进下呢？

一般我们表中搜索会用到 assoc ，这个函数好像没有人说过效率慢，那么构造表的时候加上个序号，取第 n 个元素的时候用 assoc 是不是会快些？！

欢迎探讨！

2. 
   
3. 
   
4. (defun c:t1 (/ i l)
   
5.   (setq i -1)
   
6.   (repeat 100000
   
7.     (setq l (cons (setq i (1+ i)) l))
   
8.   )
   
9.   (nth 9000 (reverse l))
   
10. )
    
11. (defun c:t2 (/ i l)
    
12.   (setq i -1)
    
13.   (repeat 100000
    
14.     (setq l (cons (cons (setq i (1+ i)) i) l))
    
15.   )
    
16.   (assoc 9000 l)
    
17. )

<br /> <br /> (defun c:t1 (/ i l)<br />   (setq i -1)<br />   (repeat 100000<br />     (setq l (cons (setq i (1+ i)) l))<br />   )<br />   (nth 9000 (reverse l))<br /> )<br /> (defun c:t2 (/ i l)<br />   (setq i -1)<br />   (repeat 100000<br />     (setq l (cons (cons (setq i (1+ i)) i) l))<br />   )<br />   (assoc 9000 l)<br /> )

LoveArx

不管用哪个函数，归根结底是受LISP表的存储结构影响的，存储结构不变，哪个函数都差不多。LISP表是单向resbuf表，只有从头到尾巴的指针链接起来，没尾巴到头的（双向链表），所以取哪个元素都要从头遍历，不会快。

小龙龙

nth 效率的确低一些，好久没用LISP了

newer

小龙龙 发表于 2016-6-9 09:09
nth 效率的确低一些，好久没用LISP了

1. (defun c:t1 (/ i l)
   
2.   (setq j 0)
   
3.   (repeat 10
   
4.     (xdrx_prompt "\n*********** 第" (setq j (1+ j))
   
5.                  "次 ***********"
   
6.     )
   
7.     (setq i -1)
   
8.     (setq l nil)
   
9.     (xdrx_runtime t)
   
10.     (repeat 100000
    
11.       (setq l (cons (setq i (1+ i))
    
12.                     l
    
13.               )
    
14.       )
    
15.     )
    
16.     (princ "\n")
    
17.     (princ (nth 9000 (reverse l)))
    
18.     (xdrx_prompt "\nnth执行时间:" (xdrx_runtime))
    
19.     (setq i -1 l nil)
    
20.     (xdrx_runtime t)
    
21.     (repeat 100000
    
22.       (setq l (cons (cons (setq i (1+ i))
    
23.                           i
    
24.                     ) l
    
25.               )
    
26.       )
    
27.     )
    
28.     (princ "\n")
    
29.     (princ (assoc 9000 l))
    
30.     (xdrx_prompt "\nassoc执行时间:" (xdrx_runtime))
    
31.   )
    
32. )
    
33. 
    

(defun c:t1 (/ i l)<br />   (setq j 0)<br />   (repeat 10<br />     (xdrx_prompt "\n*********** 第" (setq j (1+ j))<br />                  "次 ***********"<br />     )<br />     (setq i -1)<br />     (setq l nil)<br />     (xdrx_runtime t)<br />     (repeat 100000<br />       (setq l (cons (setq i (1+ i))<br />                     l<br />               )<br />       )<br />     )<br />     (princ "\n")<br />     (princ (nth 9000 (reverse l)))<br />     (xdrx_prompt "\nnth执行时间:" (xdrx_runtime))<br />     (setq i -1 l nil)<br />     (xdrx_runtime t)<br />     (repeat 100000<br />       (setq l (cons (cons (setq i (1+ i))<br />                           i<br />                     ) l<br />               )<br />       )<br />     )<br />     (princ "\n")<br />     (princ (assoc 9000 l))<br />     (xdrx_prompt "\nassoc执行时间:" (xdrx_runtime))<br />   )<br /> )<br /> <br />

看下测试结果：

*********** 第1次 ***********
9000
nth执行时间:0.05
(9000 . 9000)
assoc执行时间:0.054
*********** 第2次 ***********
9000
nth执行时间:0.042
(9000 . 9000)
assoc执行时间:0.051
*********** 第3次 ***********
9000
nth执行时间:0.1
(9000 . 9000)
assoc执行时间:0.06
*********** 第4次 ***********
9000
nth执行时间:0.045
(9000 . 9000)
assoc执行时间:0.064
*********** 第5次 ***********
9000
nth执行时间:0.046
(9000 . 9000)
assoc执行时间:0.059
*********** 第6次 ***********
9000
nth执行时间:0.055
(9000 . 9000)
assoc执行时间:0.056
*********** 第7次 ***********
9000
nth执行时间:0.049
(9000 . 9000)
assoc执行时间:0.061
*********** 第8次 ***********
9000
nth执行时间:0.05
(9000 . 9000)
assoc执行时间:0.06
*********** 第9次 ***********
9000
nth执行时间:0.05
(9000 . 9000)
assoc执行时间:0.052
*********** 第10次 ***********
9000
nth执行时间:0.047
(9000 . 9000)
assoc执行时间:0.06T


执行效果看NTH 要快哦。

newer

分析看，两个函数效率是同一级别的，ASSOC除了要查询，还要判断是否相等，多用了点时间。

st788796

讨论这个的确无意义，alisp传过去的都是 resbuf * ，单链表

小陶

程序稳定就好了，不在乎那几秒钟 :lol