关于如何代替nth问题？

尘缘一生 · 发表于 2021-8-16 21:58

nth 函数比较慢，为了解决这个问题
car cadr caddr cadddr 可以解决4个，那么多的表格，还是需要它。

这几天再考虑，是不是可以弄个函数出来，把多的表格也一并处理了。。。。。

tryhi · 发表于 2021-8-17 21:56

本帖最后由 tryhi 于 2021-8-17 22:08 编辑

不死猫发表于 2021-8-17 16:43
不用测了，组合car cdr比nth快的多

不对吧，我觉得无法写出一个能替代nth的函数，只有在某些特定情况的算法可以用car cdr来代替nth，但是想要在一个100万个元素的表里面取出其第50万个元素的值，我觉得nth没有可替代性

;;测试用cdr取第50万个时间(repeat版)  结果79毫秒
(defun c:t1 (/ i lstx)
      (setq lstx nil i 0)
      (repeat 1000000 (setq i(1+ i) lstx(cons i lstx)));;生成100万个元素的表
      (try-time-be);计时开始
      (repeat 500000
            (setq lstx(cdr lstx))
      )
      (setq r(car lstx));第50万个的值
      (try-time-end nil t);计时结束
)

;;测试用cdr取第50万个时间(while版)  结果83毫秒
(defun c:t2 (/ j i lstx)
      (setq lstx nil i 0 j 0)
      (repeat 1000000 (setq i(1+ i) lstx(cons i lstx)));;生成100万个元素的表
      (try-time-be);计时开始
      (while (< j 500000)
            (setq lstx(cdr lstx)
                     j(1+ j)
            )
      )
      (setq r(car lstx));第50万个的值
      (try-time-end nil t);计时结束
)

;;测试用nth的时间  结果2毫秒
(defun c:t3 (/ i lstx)
      (setq lstx nil i 0)
      (repeat 1000000 (setq i(1+ i) lstx(cons i lstx)));;生成100万个元素的表
      (try-time-be);计时开始
      (setq r(nth 500000 lstx));第50万个的值
      (try-time-end nil t);计时结束
)
结果是nth完胜，顺带回答题主的问题，nth具有不可替代性，任何可以通过不使用nth来优化的算法，都具有一定特殊性或局限性

baitang36 · 发表于 2021-8-17 06:45

本帖最后由 baitang36 于 2021-8-17 06:59 编辑

lisp的表在内存中的数据结构是cons，也就是一个链表。每个节点包含下一节点的地址和本节点的内容。表的每个元素在内存中都是不连续的。链表只能从从头开始查询，遍历起来速度慢。
字符串在内存中是连续存放的，你可以试试改成字符串，然后用substr来处理，速度应该能快。
你的测试有问题，(princ (nth 4 lst))这句中的princ速度很慢，你测的是它的速度，不是nth的速度。

尘缘一生 · 发表于 2021-8-17 00:10

本帖最后由尘缘一生于 2021-8-17 01:36 编辑

弄了个，似乎可以，然而。。。。。。？？？

;;nth替代函数--------（一级）----------
(defun nnth (i lst / k)
  (setq loop t k 0)
  (while loop
(setq numlis (car lst))
(if (/= k i)
   (setq lst (cdr lst) k (1+ k))
   (setq loop nil)
)
  )
  numlis
)
;测试-------13秒
(defun c:tt1 ()
  (setq t0 (getvar "TDUSRTIMER"))
  (setq lst (list "1" "2" "3" "4" "5") i 1)
  (while (< i 90000)
(princ (nnth 4 lst))
(setq i (1+ i))
  )
  (princ "\n 程序共用时")
  (princ (rtos (* (- (getvar "TDUSRTIMER") t0) 86400) 2 4))
  (princ "秒")
)
;;测试------------12秒
(defun c:tt2 ()
  (setq t0 (getvar "TDUSRTIMER"))
  (setq lst (list "1" "2" "3" "4" "5") i 1)
  (while (< i 90000)
(princ (nth 4 lst))
(setq i (1+ i))
  )
  (princ "\n 程序共用时")
  (princ (rtos (* (- (getvar "TDUSRTIMER") t0) 86400) 2 4))
  (princ "秒")
)
;;测试------------12秒与nth 相同
(defun c:tt3 ()
  (setq t0 (getvar "TDUSRTIMER"))
  (setq lst (list "1" "2" "3" "4" "5") i 1)
  (while (< i 90000)
(princ (cadr lst))
(setq i (1+ i))
  )
  (princ "\n 程序共用时")
  (princ (rtos (* (- (getvar "TDUSRTIMER") t0) 86400) 2 4))
  (princ "秒")
)
;;测试------------13秒
(defun c:tt4 ()
  (setq t0 (getvar "TDUSRTIMER"))
  (setq lst (list "1" "2" "3" "4" "5") i 1)
  (while (< i 90000)
(princ (cadddr lst))
(setq i (1+ i))
  )
  (princ "\n 程序共用时")
  (princ (rtos (* (- (getvar "TDUSRTIMER") t0) 86400) 2 4))
  (princ "秒")
)
结论：还没有nth 快，失败了。。。。。。。无语
lisp 快慢顺序测试为： car < cadr < caddr < cadddr
对这一结论严重怀疑，不应该是cadddr < caddr < cadr < car 吗？

尘缘一生 · 发表于 2021-8-17 07:21

本帖最后由尘缘一生于 2021-8-17 08:07 编辑

baitang36 发表于 2021-8-17 06:45
lisp的表在内存中的数据结构是cons，也就是一个链表。每个节点包含下一节点的地址和本节点的内容。表的每个 ...

奥，有道理，我重新试试，

;;nth替代函数--------（一级）----------
(defun nnth (i lst / k)
(setq loop t k 0)
(while loop
(setq numlis (car lst))
(if (/= k i)
(setq lst (cdr lst) k (1+ k))
(setq loop nil)
)
)
numlis
)
;测试-------12秒
(defun c:tt1 ()
(setq t0 (getvar "TDUSRTIMER"))
(setq lst (list "1" "2" "3" "4" "5") i 1)
(while (< i 4400000)
(nnth 4 lst)
(setq i (1+ i))
)
(princ (strcat "\n 程序共用时" (rtos (* (- (getvar "TDUSRTIMER") t0) 86400) 2 4) "秒"))
)
;;测试------------9秒
(defun c:tt2 ()
(setq t0 (getvar "TDUSRTIMER"))
(setq lst (list "1" "2" "3" "4" "5") i 1)
(while (< i 20000000)
(nth 4 lst)
(setq i (1+ i))
)
(princ (strcat "\n 程序共用时" (rtos (* (- (getvar "TDUSRTIMER") t0) 86400) 2 4) "秒"))
)
;;测试------------7秒
(defun c:tt3 ()
(setq t0 (getvar "TDUSRTIMER"))
(setq lst (list "1" "2" "3" "4" "5") i 1)
(while (< i 20000000)
(cadr lst)
(setq i (1+ i))
)
(princ (strcat "\n 程序共用时" (rtos (* (- (getvar "TDUSRTIMER") t0) 86400) 2 4) "秒"))
)
;;测试------------9秒
(defun c:tt4 ()
(setq t0 (getvar "TDUSRTIMER"))
(setq lst (list "1" "2" "3" "4" "5") i 1)
(while (< i 20000000)
(cadddr lst)
(setq i (1+ i))
)
(princ (strcat "\n 程序共用时" (rtos (* (- (getvar "TDUSRTIMER") t0) 86400) 2 4) "秒"))
)
;;; 结论：取单独字符速度 car < cadr < caddr < cadddr < nth

不死猫 · 发表于 2021-8-17 16:43

不用测了，组合car cdr比nth快的多

自贡黄明儒 · 发表于 2021-8-17 21:30

晓东上有现成的函数，跟老猫方法同

不死猫 · 发表于 2021-8-17 22:47

tryhi 发表于 2021-8-17 21:56
不对吧，我觉得无法写出一个能替代nth的函数，只有在某些特定情况的算法可以用car cdr来代替nth，但是想 ...

循环几万次为了读一个值的程序实际应用没有这么写的。
楼主问的也是对整个表的读取遍历，只是楼主的代码测试的不太对，效率损失了。
正确的测试方式是对一个大表进行循环读取，查看耗时。

;nth方式遍历表
(defun c:t1 (/ i lstx)
      (setq lstx nil i 0)
      (repeat 10000 (setq i(1+ i) lstx(cons i lstx)));;生成100万个元素的表
      (setq t0 (getvar "TDUSRTIMER"));计时开始
(setq i 0)
      (repeat (length lstx)
         (setq x (nth i lstx))
   (setq i (1+ i))
      )
      (princ (strcat "\n 程序共用时" (rtos (* (- (getvar "TDUSRTIMER") t0) 86400) 2 4) "秒"));计时结束
)
;car cdr 方式遍历表
(defun c:t2 (/ i lstx)
      (setq lstx nil i 0)
      (repeat 10000 (setq i(1+ i) lstx(cons i lstx)));;生成100万个元素的表
      (setq t0 (getvar "TDUSRTIMER"));计时开始
      (while lstx
(setq x (car lstx))
(setq lstx (cdr lstx))
)
      (princ (strcat "\n 程序共用时" (rtos (* (- (getvar "TDUSRTIMER") t0) 86400) 2 4) "秒"));计时结束
)

我电脑不够快，100万数据太久，所以用1万数据测试。
命令: t1
程序共用时0.1740秒"\n 程序共用时0.1740秒"
命令:
命令: t2
程序共用时0.0010秒"\n 程序共用时0.0010秒"

nth增加序号有损失效率，所以组合car cdr比nth快的多

tryhi · 发表于 2021-8-17 22:50

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

原来如此，因为我看楼主的标题写的是“替代nth”，所以指出nth不具备完全可替代性，在遍历这个问题上我的看法倒是跟猫老师一致

xj6019 · 发表于 2021-8-17 22:52

大佬们玩的好深，不用太多，就取二三十个元素的时候，不用nth 能有啥好法子吗，总不能一堆dddd吧

账号		自动登录	找回密码
密码			注册

[讨论] 关于如何代替nth问题？

本帖子中包含更多资源