设为首页收藏本站CAD论坛CAD教程CAD下载明经币充值
切换到宽版

明经CAD社区

 找回密码
 注册

QQ登录

只需一步，快速开始

搜索
明经CAD社区»社区 › 开发篇 › AutoLISP/Visual LISP 编程技术 › [讨论]->征求最佳答案：删除表中第 n 个元素的最快算 ...
12345678下一页
返回列表 发新帖
楼主: caoyin

[讨论]->征求最佳答案：删除表中第 n 个元素的最快算法

  [复制链接]
elitefish
发表于 2011-11-12 15:21 | 显示全部楼层
补充下 member 方法的测试结果  与 递归算法对比

测试对象 lst 元素 共2000个

  2. 测试函数(EF:LIST-INDEXDEL-递归 200 LST) 10000次,共耗时:2.75671秒
  3. 测试函数(EF:LIST-INDEXDEL-递归 400 LST) 10000次,共耗时:5.10737秒
  4. 测试函数(EF:LIST-INDEXDEL-递归 600 LST) 10000次,共耗时:7.47293秒
  5. 测试函数(EF:LIST-INDEXDEL-递归 800 LST) 10000次,共耗时:9.84967秒
  6. 测试函数(EF:LIST-INDEXDEL-递归 1000 LST) 10000次,共耗时:12.2062秒
  7. 测试函数(EF:LIST-INDEXDEL-递归 1200 LST) 10000次,共耗时:12.4276秒
  8. 测试函数(EF:LIST-INDEXDEL-递归 1400 LST) 10000次,共耗时:10.0993秒
  9. 测试函数(EF:LIST-INDEXDEL-递归 1600 LST) 10000次,共耗时:7.58469秒
  10. 测试函数(EF:LIST-INDEXDEL-递归 1800 LST) 10000次,共耗时:5.19305秒

  12. 测试函数(REMOVENTH 200 LST) 10000次,共耗时:5.02542秒
  13. 测试函数(REMOVENTH 400 LST) 10000次,共耗时:5.15953秒
  14. 测试函数(REMOVENTH 600 LST) 10000次,共耗时:5.37404秒
  15. 测试函数(REMOVENTH 800 LST) 10000次,共耗时:5.47245秒
  16. 测试函数(REMOVENTH 1000 LST) 10000次,共耗时:5.56558秒
  17. 测试函数(REMOVENTH 1200 LST) 10000次,共耗时:5.67362秒
  18. 测试函数(REMOVENTH 1400 LST) 10000次,共耗时:5.78538秒
  19. 测试函数(REMOVENTH 1600 LST) 10000次,共耗时:5.89341秒
  20. 测试函数(REMOVENTH 1800 LST) 10000次,共耗时:6.04615秒
复制代码
从上可以看出 member 的方法 当没有重复项时 速度相当快，但前提是 列表中无重复项
在测试对象为2000个重复项时    速度就非常慢了  达到80+s 以上

以下为 递归算法 测试 ，可以看出 递归算法计算时间基本与 列表项数 成正比

  2. 测试对象 lst 元素 共1000个
  3. 测试函数(EF:LIST-INDEXDEL-递归 500 LST) 1000次,共耗时:0.625849秒

  5. 测试对象 lst 元素 共2000个
  6. 测试函数(EF:LIST-INDEXDEL-递归 1000 LST) 1000次,共耗时:1.27777秒

  8. 测试对象 lst 元素 共3000个
  9. 测试函数(EF:LIST-INDEXDEL-递归 1500 LST) 1000次,共耗时:2.64496秒

  11. 测试对象 lst 元素 共4000个
  12. 测试函数(EF:LIST-INDEXDEL-递归 2000 LST) 1000次,共耗时:4.62309秒

  14. 测试对象 lst 元素 共5000个
  15. 测试函数(EF:LIST-INDEXDEL-递归 2500 LST) 1000次,共耗时:5.80028秒

  17. 测试对象 lst 元素 共6000个
  18. 测试函数(EF:LIST-INDEXDEL-递归 3000 LST) 1000次,共耗时:6.94022秒

  20. 测试对象 lst 元素 共7000个
  21. 测试函数(EF:LIST-INDEXDEL-递归 3500 LST) 1000次,共耗时:8.0727秒

  23. 测试对象 lst 元素 共8000个
  24. 测试函数(EF:LIST-INDEXDEL-递归 4000 LST) 1000次,共耗时:9.29832秒

  26. 测试对象 lst 元素 共9000个
  27. 测试函数(EF:LIST-INDEXDEL-递归 4500 LST) 1000次,共耗时:10.4457秒

  29. 测试对象 lst 元素 共10000个
  30. 测试函数(EF:LIST-INDEXDEL-递归 5000 LST) 1000次,共耗时:11.5766秒

  32. 测试对象 lst 元素 共11000个
  33. 测试函数(EF:LIST-INDEXDEL-递归 5500 LST) 1000次,共耗时:12.5803秒

  35. 测试对象 lst 元素 共12000个
  36. 测试函数(EF:LIST-INDEXDEL-递归 6000 LST) 1000次,共耗时:13.9177秒

  38. 测试对象 lst 元素 共13000个
  39. 测试函数(EF:LIST-INDEXDEL-递归 6500 LST) 1000次,共耗时:14.9161秒

  41. 测试对象 lst 元素 共14000个
  42. 测试函数(EF:LIST-INDEXDEL-递归 7000 LST) 1000次,共耗时:16.2184秒

  44. 测试对象 lst 元素 共15000个
  45. 测试函数(EF:LIST-INDEXDEL-递归 7500 LST) 1000次,共耗时:17.3859秒

  47. 测试对象 lst 元素 共16000个
  48. 测试函数(EF:LIST-INDEXDEL-递归 8000 LST) 1000次,共耗时:18.727秒

  50. 测试对象 lst 元素 共17000个
  51. 测试函数(EF:LIST-INDEXDEL-递归 8500 LST) 1000次,共耗时:19.5913秒

  53. 测试对象 lst 元素 共18000个
  54. 测试函数(EF:LIST-INDEXDEL-递归 9000 LST) 1000次,共耗时:20.7297秒

  56. 测试对象 lst 元素 共19000个
  57. 测试函数(EF:LIST-INDEXDEL-递归 9500 LST) 1000次,共耗时:21.8973秒

  59. 测试对象 lst 元素 共20000个
  60. 测试函数(EF:LIST-INDEXDEL-递归 10000 LST) 1000次,共耗时:22.9984秒
复制代码

评分

参与人数 1金钱 +10 收起 理由
yjr111 + 10 很给力!

查看全部评分

回复 支持 反对

使用道具 举报

elitefish
发表于 2011-11-12 15:45 | 显示全部楼层
再来个 Member 方法的 测试数据
测试 LST  为‘（ 1 2 3 4 5 6 7 8 9 0 1 2 3 4...)  中元素重复率 为10%
从下面测试结果可以看出  Member 方法 随 列表元素的数目增加 计算时间是非线形的     时间消耗量 急剧增加

  2. 测试对象 lst 元素 共1000个
  3. 测试函数(EF:LIST-INDEXDEL-MEMBER 500 LST) 1000次,共耗时:0.566244秒

  5. 测试对象 lst 元素 共2000个
  6. 测试函数(EF:LIST-INDEXDEL-MEMBER 1000 LST) 1000次,共耗时:1.546秒

  8. 测试对象 lst 元素 共3000个
  9. 测试函数(EF:LIST-INDEXDEL-MEMBER 1500 LST) 1000次,共耗时:3.06063秒

  11. 测试对象 lst 元素 共4000个
  12. 测试函数(EF:LIST-INDEXDEL-MEMBER 2000 LST) 1000次,共耗时:5.34579秒

  14. 测试对象 lst 元素 共5000个
  15. 测试函数(EF:LIST-INDEXDEL-MEMBER 2500 LST) 1000次,共耗时:7.94977秒

  17. 测试对象 lst 元素 共6000个
  18. 测试函数(EF:LIST-INDEXDEL-MEMBER 3000 LST) 1000次,共耗时:10.8927秒

  20. 测试对象 lst 元素 共7000个
  21. 测试函数(EF:LIST-INDEXDEL-MEMBER 3500 LST) 1000次,共耗时:14.3498秒

  23. 测试对象 lst 元素 共8000个
  24. 测试函数(EF:LIST-INDEXDEL-MEMBER 4000 LST) 1000次,共耗时:18.2278秒

  26. 测试对象 lst 元素 共9000个
  27. 测试函数(EF:LIST-INDEXDEL-MEMBER 4500 LST) 1000次,共耗时:22.4992秒

  29. 测试对象 lst 元素 共10000个
  30. 测试函数(EF:LIST-INDEXDEL-MEMBER 5000 LST) 1000次,共耗时:27.515秒

  32. 测试对象 lst 元素 共11000个
  33. 测试函数(EF:LIST-INDEXDEL-MEMBER 5500 LST) 1000次,共耗时:32.7475秒

  35. 测试对象 lst 元素 共12000个
  36. 测试函数(EF:LIST-INDEXDEL-MEMBER 6000 LST) 1000次,共耗时:38.5344秒

  38. 测试对象 lst 元素 共13000个
  39. 测试函数(EF:LIST-INDEXDEL-MEMBER 6500 LST) 1000次,共耗时:44.728秒

  41. 测试对象 lst 元素 共14000个
  42. 测试函数(EF:LIST-INDEXDEL-MEMBER 7000 LST) 1000次,共耗时:51.2845秒

  44. 测试对象 lst 元素 共15000个
  45. 测试函数(EF:LIST-INDEXDEL-MEMBER 7500 LST) 1000次,共耗时:59.6254秒

  47. 测试对象 lst 元素 共16000个
  48. 测试函数(EF:LIST-INDEXDEL-MEMBER 8000 LST) 1000次,共耗时:66.5508秒

  50. 测试对象 lst 元素 共17000个
  51. 测试函数(EF:LIST-INDEXDEL-MEMBER 8500 LST) 1000次,共耗时:74.0758秒

  53. 测试对象 lst 元素 共18000个
  54. 测试函数(EF:LIST-INDEXDEL-MEMBER 9000 LST) 1000次,共耗时:82.9777秒

  56. 测试对象 lst 元素 共19000个
  57. 测试函数(EF:LIST-INDEXDEL-MEMBER 9500 LST) 1000次,共耗时:93.0487秒

  59. 测试对象 lst 元素 共20000个
  60. 测试函数(EF:LIST-INDEXDEL-MEMBER 10000 LST) 1000次,共耗时:104.655秒
复制代码

评分

参与人数 1明经币 +1 收起 理由
yjr111 + 1 很给力!

查看全部评分

回复 支持 反对

使用道具 举报

elitefish
发表于 2011-11-12 16:03 | 显示全部楼层
再来个 Mermber 方法的测试结果
和上面不同的是 LST 为 字符串表 '("1" "2" "3"...) 其余条件相同  排除误差的话  可以看出  两种计算时间基本相同   所以 Member 方法 与数据类型无关

  2. 测试对象 lst 元素 共1000个
  3. 测试函数(EF:LIST-INDEXDEL-MEMBER 500 LST) 1000次,共耗时:0.569969秒

  5. 测试对象 lst 元素 共2000个
  6. 测试函数(EF:LIST-INDEXDEL-MEMBER 1000 LST) 1000次,共耗时:1.58697秒

  8. 测试对象 lst 元素 共3000个
  9. 测试函数(EF:LIST-INDEXDEL-MEMBER 1500 LST) 1000次,共耗时:3.03239秒

  11. 测试对象 lst 元素 共4000个
  12. 测试函数(EF:LIST-INDEXDEL-MEMBER 2000 LST) 1000次,共耗时:4.96209秒

  14. 测试对象 lst 元素 共5000个
  15. 测试函数(EF:LIST-INDEXDEL-MEMBER 2500 LST) 1000次,共耗时:7.4096秒

  17. 测试对象 lst 元素 共6000个
  18. 测试函数(EF:LIST-INDEXDEL-MEMBER 3000 LST) 1000次,共耗时:10.1834秒

  20. 测试对象 lst 元素 共7000个
  21. 测试函数(EF:LIST-INDEXDEL-MEMBER 3500 LST) 1000次,共耗时:13.5005秒

  23. 测试对象 lst 元素 共8000个
  24. 测试函数(EF:LIST-INDEXDEL-MEMBER 4000 LST) 1000次,共耗时:17.561秒

  26. 测试对象 lst 元素 共9000个
  27. 测试函数(EF:LIST-INDEXDEL-MEMBER 4500 LST) 1000次,共耗时:21.5455秒

  29. 测试对象 lst 元素 共10000个
  30. 测试函数(EF:LIST-INDEXDEL-MEMBER 5000 LST) 1000次,共耗时:26.1292秒

  32. 测试对象 lst 元素 共11000个
  33. 测试函数(EF:LIST-INDEXDEL-MEMBER 5500 LST) 1000次,共耗时:31.2813秒

  35. 测试对象 lst 元素 共12000个
  36. 测试函数(EF:LIST-INDEXDEL-MEMBER 6000 LST) 1000次,共耗时:36.7112秒

  38. 测试对象 lst 元素 共13000个
  39. 测试函数(EF:LIST-INDEXDEL-MEMBER 6500 LST) 1000次,共耗时:42.884秒

  41. 测试对象 lst 元素 共14000个
  42. 测试函数(EF:LIST-INDEXDEL-MEMBER 7000 LST) 1000次,共耗时:49.746秒

  44. 测试对象 lst 元素 共15000个
  45. 测试函数(EF:LIST-INDEXDEL-MEMBER 7500 LST) 1000次,共耗时:56.444秒

  47. 测试对象 lst 元素 共16000个
  48. 测试函数(EF:LIST-INDEXDEL-MEMBER 8000 LST) 1000次,共耗时:63.9989秒

  50. 测试对象 lst 元素 共17000个
  51. 测试函数(EF:LIST-INDEXDEL-MEMBER 8500 LST) 1000次,共耗时:73.4016秒

  53. 测试对象 lst 元素 共18000个
  54. 测试函数(EF:LIST-INDEXDEL-MEMBER 9000 LST) 1000次,共耗时:79.9767秒

  56. 测试对象 lst 元素 共19000个
  57. 测试函数(EF:LIST-INDEXDEL-MEMBER 9500 LST) 1000次,共耗时:91.6278秒

  59. 测试对象 lst 元素 共20000个
  60. 测试函数(EF:LIST-INDEXDEL-MEMBER 10000 LST) 1000次,共耗时:107.608秒
复制代码

点评

fsxm
member，是遍历到“相等”停止，你测试的字串太短当然速度差不多，长字串是否“相等”，也是很慢的！  发表于 2011-11-12 17:25
Gu_xl
如果表为点表的话，对member方法速度影响很大！几乎会慢一半！具体测试结果见42楼  发表于 2011-11-12 17:08
yjr111
虽然实际中各种方法对小程序来说影响不大，但知道道理后应该还是会挑选适合的函数了  发表于 2011-11-12 16:55
回复 支持 反对

使用道具 举报

Gu_xl
发表于 2011-11-12 17:12 | 显示全部楼层
本帖最后由 Gu_xl 于 2011-11-12 17:25 编辑

重新对三种表类型（纯数字表、字符串表、点表）做了测试！测试结果如下：



对于数字表和字符串表来说，各种方法相对本身来说区别不大，如果是点表的话，member方法影响会大一点，Gu_xl方法4和xianaihua  递归改进方法对表类型敏感度不大！几种表速度相差不太大！
发现一个很有意思的现象，Caoyin和xshrimp 的Member方法再编译以后的运算速度居然比没编译的运算速度慢！特别是纯数字表，前后居然差了3秒！（5.34766  秒 对 8.48047  秒）！


本帖子中包含更多资源

您需要 登录 才可以下载或查看，没有账号？注册

x

点评

fsxm
递归20000次，达到最大堆栈出错！用个5Ｗ的表，删除第2.5Ｗ测试下就知道  发表于 2011-11-12 17:28
回复 支持 反对

使用道具 举报

cabinsummer
发表于 2011-11-12 17:39 | 显示全部楼层
试过嵌套表吗？
回复 支持 反对

使用道具 举报

shalei021647
发表于 2011-11-13 11:18 | 显示全部楼层
问题太高深了
回复 支持 反对

使用道具 举报

xiaxiang
发表于 2011-11-13 17:46 | 显示全部楼层
纯粹凑个热闹，不懂如何提速。如果能知道是正向提取还是逆向提取，会不会好些。
递归法，从1开始，不能为0，为负数则逆向提取

  3. (defun ntht ( n l)
  4. (cond ((= n 0) nil)
  5.           ((> n 0)
  6.        (repeat (1- n) (setq l(cdr l)))
  7.        (car l)
  8.           ) ;返回第n个元素
  9.           (T(ntht(1+ (+ (length l) n)) l)) ;返回倒数第n个元素
  10. )
  11. )

回复 支持 反对

使用道具 举报

byghbcx
发表于 2011-11-14 00:29 | 显示全部楼层
本帖最后由 byghbcx 于 2011-11-14 21:12 编辑

  1. (defun tt (n lst)
  2.   (setq lst_r (reverse lst) lt lst)
  3.   (repeat n (setq lt (cdr lt)))
  4.   (repeat (- (length lst_r) (- n 1)) (setq lst_r (cdr lst_r)))
  5.   (setq lst_r (reverse lst_r))
  6.   (append lst_r lt)
  7.   )
  8. (defun tt( n lst / t1 t2 m temp)
  9.   (setq m 0 temp '())
  10.   (mapcar '(lambda(x) (setq m (1+ m)) (if (= n m) t (setq temp (cons x temp )))) lst)
  11.   (reverse temp)
  12.   )
  13. (defun tt (n lst)
  14.   (setq lst_r (reverse lst) lt lst nn (nth (1- n) lst))
  15.   (while (/= (length lt) (- (length lst) n))
  16.     (setq lt (cdr (member nn lt))))
  17.   (while (/= (length lst_r) (1- n))
  18.     (setq lst_r (cdr (member nn lst_r))))
  19.   (append (reverse lst_r) lt)
  20.   )
我用了几种方法，用MEMBER还是较快

点评

Gu_xl
第一个速度很快！后两个不行！  发表于 2011-11-16 19:42
回复 支持 反对

使用道具 举报

NetBee
发表于 2011-11-16 17:23 | 显示全部楼层
本帖最后由 NetBee 于 2011-11-16 17:26 编辑

我也来凑热闹，我的函数库中的：
  2. (defun NBTF_LST_Delnth1        (Num# OldList@)
  3.   (setq Num# (1+ Num#))
  4.   (vl-remove-if
  5.     '(lambda (x) (zerop (setq Num# (1- Num#))))
  6.     OldList@
  7.   )
  8. )
从没有考虑过这个问题，哪位测试一下看看，怕是最慢的。

点评

Gu_xl
速度不错！  发表于 2011-11-16 19:41
回复 支持 反对

使用道具 举报

vormittag
发表于 2011-11-16 19:20 | 显示全部楼层
cnks 发表于 2011-11-11 15:21
不好意思，g版，你的没错，查了查cons也是内部函数

请教cnks一下，哪些函数属于内部函数？autocad的帮助里好像没有找到信息，您能给点资料么？
回复 支持 反对

使用道具 举报

12345678下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则

小黑屋|手机版|CAD论坛|CAD教程|CAD下载|联系我们|关于明经|明经通道 ( 粤ICP备05003914号 )  
©2000-2023 明经通道 版权所有 本站代码，在未取得本站及作者授权的情况下，不得用于商业用途

GMT+8, 2024-5-17 18:13 , Processed in 0.208707 second(s), 20 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表