关于如何代替nth问题？

vectra

nth的目的在于随机访问指定元素，受限于list数据结构，算法复杂度为O(n)，效率自然是差的。

数组（Array）或字典（Map,DICT）是随机访问比较有效的结构，复杂度为O(1)，可惜lisp没有直接提供这类对象

可参考
http://bbs.mjtd.com/thread-177140-1-1.html LISP中使用数组
http://bbs.mjtd.com/thread-177087-1-1.htmlLISP缓存类
http://bbs.mjtd.com/thread-170324-1-1.html打造随机访问的LISP可变长数组

通过.net扩展c#的相关数据结构供LISP使用也不失为一个比较好的想法

vectra

另外猫大的测试比较极端，基本不可能用nth来做表的遍历，比较公平一点是比较随机访问指定数据的效率，代码如下

1. (setq biglist nil
   
2.       i -1
   
3. )
   
4. 
   
5. (repeat 10000
   
6.   (setq biglist (cons (setq i (1+ i)) biglist))
   
7. )
   
8. (setq biglist (reverse biglist))
   
9. 
   
10. 
    
11. (defun test (func count)
    
12.   (setq t0 (getvar "MILLISECS"))
    
13.   (repeat count
    
14.     (setq x (eval func))
    
15.   )
    
16.   (strcat "\n返回值" (itoa x) ", 用时" (itoa (- (getvar "MILLISECS") t0)) "ms")
    
17. )
    
18. 
    
19. ;;nth方式遍历表
    
20. (defun ra-nth (lst index /)
    
21.   (nth index lst)
    
22. )
    
23. 
    
24. ;;car cdr 方式遍历表
    
25. (defun ra-car (lst index /)
    
26.   (repeat index
    
27.     (setq lst (cdr lst))
    
28.   )
    
29.   (car lst)
    
30. )
    
31. 
    
32. _$ (test '(ra-nth biglist 5000) 10000)
    
33. "\n返回值5000, 用时407ms"
    
34. _$ (test '(ra-car biglist 5000) 10000)
    
35. "\n返回值5000, 用时24813ms"
    
36. _$ (test '(ra-nth biglist 1) 10000)
    
37. "\n返回值1, 用时234ms"
    
38. _$ (test '(ra-car biglist 1) 10000)
    
39. "\n返回值1, 用时234ms"

(setq biglist nil<br />       i -1<br /> )<br /> <br /> (repeat 10000<br />   (setq biglist (cons (setq i (1+ i)) biglist))<br /> )<br /> (setq biglist (reverse biglist))<br /> <br /> <br /> (defun test (func count)<br />   (setq t0 (getvar "MILLISECS"))<br />   (repeat count<br />     (setq x (eval func))<br />   )<br />   (strcat "\n返回值" (itoa x) ", 用时" (itoa (- (getvar "MILLISECS") t0)) "ms")<br /> )<br /> <br /> ;;nth方式遍历表<br /> (defun ra-nth (lst index /)<br />   (nth index lst)<br /> )<br /> <br /> ;;car cdr 方式遍历表<br /> (defun ra-car (lst index /)<br />   (repeat index<br />     (setq lst (cdr lst))<br />   )<br />   (car lst)<br /> )<br /> <br /> _$ (test '(ra-nth biglist 5000) 10000)<br /> "\n返回值5000, 用时407ms"<br /> _$ (test '(ra-car biglist 5000) 10000)<br /> "\n返回值5000, 用时24813ms"<br /> _$ (test '(ra-nth biglist 1) 10000)<br /> "\n返回值1, 用时234ms"<br /> _$ (test '(ra-car biglist 1) 10000)<br /> "\n返回值1, 用时234ms"

可见数据的位置严重影响结论，当访问表中第一个元素时，nth与car是等效的，当位置越靠近表的后端，则car的效率严重下降（car来实现nth的功能的额外代码开销）。

尘缘一生

vectra 发表于 2021-8-19 09:38
另外猫大的测试比较极端，基本不可能用nth来做表的遍历，比较公平一点是比较随机访问指定数据的效率，代码 ...

对，我就是想，如何解决后部分的快速访问问题。看来目前没好办法啊。

如果：先访问一半，把后半部分倒过来，再从前访问，不知有没有快的可能性。

vectra

尘缘一生 发表于 2021-8-19 10:19
对，我就是想，如何解决后部分的快速访问问题。看来目前没好办法啊。

如果：先访问一半，把后半部分倒 ...

不可能。

可以了解一下vlax-make-safearray 及相关函数

baitang36

不死猫 发表于 2021-8-17 22:47
循环几万次为了读一个值的程序实际应用没有这么写的。
楼主问的也是对整个表的读取遍历，只是楼主的代码 ...

换个思路，把list先转化成vector，从vector中随机取数要快，因为它不需要遍历链表。
测试了一下，和你的t2差不多

zm880928

ADFASDFADSFASDF

不死猫

baitang36 发表于 2021-8-19 13:31
换个思路，把list先转化成vector，从vector中随机取数要快，因为它不需要遍历链表。
测试了一下，和你的 ...

之前找代替append函数的时候测试过vector，
vector-append比append快一倍多的速度，但还是不能满足对效率的需求。

前生

NTH用起来简单。

不死猫

(defun c:t3 (/ i lstx y)         (setq i 0 y nil)         (setq lstx nil)         (repeat 10000 (setq i(1+ i) lstx(cons i lstx)));;生成100万个元素的表         (setq t0 (getvar "TDUSRTIMER"));计时开始         (setq i 0 y nil)         (repeat 10000                 (setq x (nth i lstx))                 (setq i (1+ i))         )         (princ (strcat "\n 程序共用时" (rtos (* (- (getvar "TDUSRTIMER") t0) 86400) 2 4) "秒")) ) (defun c:t4 (/ i lstx y vlst)         (setq i 0 y nil)         (setq lstx nil)         (repeat 10000 (setq i(1+ i) lstx(cons i lstx)));;生成100万个元素的表         (setq i 0 y nil)         (setq t0 (getvar "TDUSRTIMER"));计时开始         (setq vlst (list->vector lstx))         (repeat 10000                 (setq x (vector-elt vlst i))                 (setq i (1+ i))         )         (princ (strcat "\n 程序共用时" (rtos (* (- (getvar "TDUSRTIMER") t0) 86400) 2 4) "秒")) )

yu411038522

都像你们这样研究，电脑还需要大内存，高配置么，商家要饿死了。