明经CAD社区

 找回密码
 注册

QQ登录

只需一步,快速开始

搜索
楼主: caoyin

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

  [复制链接]
发表于 2011-11-11 19:05 | 显示全部楼层
为准确的测试removenth函数的运算速度,我将测试函数的测试规则做了下修改:
表1长20000,分10组取n,均匀分布,分别取1000、3000...19000,不同位置点计算10次
           表2长200,分10组取n,均匀分布,分别取10、30...190,不同位置点计算10次
,这样就考验了removenth函数对长短表的不同位置删除数据的综合能力!
测试函数经过编译后和不经过编译运行,各位的函数计算速度不尽相同!
测试函数:
编译后测试函数:
测试函数未经编译的测试结果:
Gu_xl 方法一:
  用时  2.03125  秒
Gu_xl 方法二:
  用时  3.42969  秒
Gu_xl 方法三:
  用时  1.32031  秒
Gu_xl 方法四repeat:
  用时  1.23828  秒
duotu007 方法:
  用时  2.29688  秒
xshrimp 方法:
  用时  0.804688  秒 (最快)
fsxm 方法:
  用时  1.07422  秒
yjr111 test3方法:
  用时  2.17969  秒
xianaihua  递归方法:
  用时  2.21094  秒
xianaihua  递归改进方法:
  用时  1.20703  秒
xianaihua  迭代方法:
  用时  0.882813  秒
测试函数经编译的测试结果:
Gu_xl 方法一:
  用时  1.59375  秒
Gu_xl 方法二:
  用时  1.43359  秒
Gu_xl 方法三:
  用时  0.605469  秒
Gu_xl 方法四repeat:
  用时  0.453125  秒 (最快)
duotu007 方法:
  用时  0.839844  秒
xshrimp 方法:
  用时  0.734375  秒
fsxm 方法:
  用时  0.519531  秒
yjr111 test3方法:
  用时  1.03125  秒
xianaihua  递归方法:
  用时  0.851563  秒
xianaihua  递归改进方法:
  用时  0.539063  秒
xianaihua  迭代方法:
  用时  0.863281  秒

本帖子中包含更多资源

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

x

点评

好像不稳定,前面几位的可能速度之间差距极小,每次位次都有变化,后面的几位可能速度之间相差较大,位次没有变化。。。  发表于 2011-11-11 19:36
 楼主| 发表于 2011-11-11 19:16 | 显示全部楼层
我的也是member方法,估计对于超长的表稍快,短表稍慢
(defun LT:LIST-REMOVE-NTH (LST N / X LST2 LE)
  (if (setq X (nth N LST))
    (progn
      (setq LST2 (reverse LST)
            LE   (- (length LST) N 1)
      )
      (while (/= (length (setq LST2 (cdr (member X LST2)))) N))
      (while (/= (length (setq LST (cdr (member X LST)))) LE))
      (append (reverse LST2) LST)
    )
  )
)

点评

member方法的速度还取决于表元素的内容,若表元素各不相同,还是非常快!若是n位置表元素相同的很多,就很影响速度了!yjr111 说测试好像不稳定,原因大概就在这里了,因为表是随机产生的,每次都会不同  发表于 2011-11-11 20:04
发表于 2011-11-11 19:56 来自手机 | 显示全部楼层
Gu_xl 测试次数太少啦,
用时都0.几秒
至少达到5s才好些!
发表于 2011-11-11 20:19 | 显示全部楼层
本帖最后由 Gu_xl 于 2011-11-11 20:30 编辑
fsxm 发表于 2011-11-11 19:56
Gu_xl 测试次数太少啦,
用时都0.几秒
至少达到5s才好些!


循环100此结果:
未编译测试结果:
Gu_xl 方法一:
  用时  50.4609  秒
Gu_xl 方法二:
  用时  59.7148  秒
Gu_xl 方法三:
  用时  22.1914  秒
Gu_xl 方法四repeat:
  用时  20.5664  秒
duotu007 方法:
  用时  39.2773  秒
xshrimp 方法:
  用时  9.99219  秒
fsxm 方法:
  用时  18.0234  秒
yjr111 test3方法:
  用时  37.375  秒
xianaihua  递归方法:
  用时  39.0898  秒
xianaihua  递归改进方法:
  用时  21.0  秒
xianaihua  迭代方法: (最快)
  用时  9.71094  秒
Caoyin的Member方法:
  用时  10.0625  秒

测试程序编译后测试结果:
Gu_xl 方法一:
  用时  17.1406  秒
Gu_xl 方法二:
  用时  15.3086  秒
Gu_xl 方法三:
  用时  6.77344  秒
Gu_xl 方法四repeat:  (最快)
  用时  5.31641  秒
duotu007 方法:
  用时  9.06641  秒
xshrimp 方法:
  用时  8.48438  秒
fsxm 方法:
  用时  6.0  秒
yjr111 test3方法:
  用时  11.4727  秒
xianaihua  递归方法:
  用时  9.08984  秒
xianaihua  递归改进方法:
  用时  5.6875  秒
xianaihua  迭代方法:
  用时  9.19141  秒
Caoyin的Member方法:
  用时  8.57422  秒
******************************
再次测试结果:
编译测试结果:
命令: tt
Gu_xl 方法一:
  用时  18.0156  秒
Gu_xl 方法二:
  用时  14.8789  秒
Gu_xl 方法三:
  用时  6.26563  秒
Gu_xl 方法四repeat:
  用时  4.75391  秒 (还是最快)
duotu007 方法:
  用时  8.42578  秒
xshrimp 方法:
  用时  7.53125  秒
fsxm 方法:
  用时  5.35156  秒
yjr111 test3方法:
  用时  10.6133  秒
xianaihua  递归方法:
  用时  8.66406  秒
xianaihua  递归改进方法:
  用时  5.44531  秒
xianaihua  迭代方法:
  用时  8.82422  秒
Caoyin的Member方法:
  用时  7.69922  秒
命令:
未编译后测试结果:
命令:
命令: tt
Gu_xl 方法一:
  用时  39.7617  秒
Gu_xl 方法二:
  用时  42.2461  秒
Gu_xl 方法三:
  用时  16.082  秒
Gu_xl 方法四repeat:
  用时  14.9961  秒
duotu007 方法:
  用时  27.7383  秒
xshrimp 方法:
  用时  9.13281  秒 (最快)
fsxm 方法:
  用时  13.0352  秒
yjr111 test3方法:
  用时  26.7266  秒
xianaihua  递归方法:
  用时  27.5  秒
xianaihua  递归改进方法:
  用时  14.9492  秒
xianaihua  迭代方法:
  用时  9.34375  秒
Caoyin的Member方法:
  用时  9.21484  秒
发表于 2011-11-11 21:33 | 显示全部楼层
刚测试了编译后,Gu_xl 方法四快些~
Caoyin,xshrimp,的member方法不稳定~,相同元素个数是个问题~
还有member可能只是对数字快些,对string或point类型的表做member可能更慢
递归对小表非常快,表大了会慢,有时还导致堆栈出错
发表于 2011-11-11 23:51 | 显示全部楼层
希望G版、飞版及其他大师们能对此次测试情况进行讲解一下,比如程序的结构或函数等对速度或效率的影响,应该怎样写程序才是正确的。。。我等新手必将获益匪浅!
发表于 2011-11-12 12:17 | 显示全部楼层
对列表 从起始到结束 1/10的表长为步进  分别计算5000次

方法1 采用 vl-remove-if 的方法  程序简洁  速度稳定   idx取中间值时 速度较快
方法2 采用 两头 cdr 再合并的方法 程序简洁 速度稳定   最慢
方法3 采用 GU_XL 的方法4  区分前后段计算   速度波动大 两头快 中间慢 平均速度较快
方法4  采用递归法  同样速度波动大  两头快 中间慢 平均速度最快,但递归算法系统开销应该也比较大

测试函数【(EF:LIST-INDEXDEL-1 164 LST)】5000次共耗时:6.50808秒
测试函数【(EF:LIST-INDEXDEL-1 328 LST)】5000次共耗时:8.41916秒
测试函数【(EF:LIST-INDEXDEL-1 493 LST)】5000次共耗时:8.19936秒
测试函数【(EF:LIST-INDEXDEL-1 657 LST)】5000次共耗时:8.18819秒
测试函数【(EF:LIST-INDEXDEL-1 822 LST)】5000次共耗时:8.13603秒
测试函数【(EF:LIST-INDEXDEL-1 986 LST)】5000次共耗时:8.23133秒
测试函数【(EF:LIST-INDEXDEL-1 1150 LST)】5000次共耗时:8.18074秒
测试函数【(EF:LIST-INDEXDEL-1 1315 LST)】5000次共耗时:8.15094秒
测试函数【(EF:LIST-INDEXDEL-1 1479 LST)】5000次共耗时:8.09878秒

测试函数【(EF:LIST-INDEXDEL-2 164 LST)】5000次共耗时:12.7628秒
测试函数【(EF:LIST-INDEXDEL-2 328 LST)】5000次共耗时:12.4983秒
测试函数【(EF:LIST-INDEXDEL-2 493 LST)】5000次共耗时:12.6831秒
测试函数【(EF:LIST-INDEXDEL-2 657 LST)】5000次共耗时:12.7442秒
测试函数【(EF:LIST-INDEXDEL-2 822 LST)】5000次共耗时:13.2024秒
测试函数【(EF:LIST-INDEXDEL-2 986 LST)】5000次共耗时:13.2136秒
测试函数【(EF:LIST-INDEXDEL-2 1150 LST)】5000次共耗时:13.2248秒
测试函数【(EF:LIST-INDEXDEL-2 1315 LST)】5000次共耗时:12.9438秒
测试函数【(EF:LIST-INDEXDEL-2 1479 LST)】5000次共耗时:13.1167秒

测试函数【(EF:LIST-INDEXDEL-3 164 LST)】5000次共耗时:3.02866秒
测试函数【(EF:LIST-INDEXDEL-3 328 LST)】5000次共耗时:5.10365秒
测试函数【(EF:LIST-INDEXDEL-3 493 LST)】5000次共耗时:6.7316秒
测试函数【(EF:LIST-INDEXDEL-3 657 LST)】5000次共耗时:8.55327秒
测试函数【(EF:LIST-INDEXDEL-3 822 LST)】5000次共耗时:10.5053秒
测试函数【(EF:LIST-INDEXDEL-3 986 LST)】5000次共耗时:9.75125秒
测试函数【(EF:LIST-INDEXDEL-3 1150 LST)】5000次共耗时:8.00565秒
测试函数【(EF:LIST-INDEXDEL-3 1315 LST)】5000次共耗时:6.1132秒
测试函数【(EF:LIST-INDEXDEL-3 1479 LST)】5000次共耗时:4.2133秒

测试函数【(EF:LIST-INDEXDEL-递归 164 LST)】5000次共耗时:2.51457秒
测试函数【(EF:LIST-INDEXDEL-递归 328 LST)】5000次共耗时:4.7721秒
测试函数【(EF:LIST-INDEXDEL-递归 493 LST)】5000次共耗时:6.72787秒
测试函数【(EF:LIST-INDEXDEL-递归 657 LST)】5000次共耗时:9.13814秒
测试函数【(EF:LIST-INDEXDEL-递归 822 LST)】5000次共耗时:11.3308秒
测试函数【(EF:LIST-INDEXDEL-递归 986 LST)】5000次共耗时:10.2073秒
测试函数【(EF:LIST-INDEXDEL-递归 1150 LST)】5000次共耗时:8.05035秒
测试函数【(EF:LIST-INDEXDEL-递归 1315 LST)】5000次共耗时:5.8338秒
测试函数【(EF:LIST-INDEXDEL-递归 1479 LST)】5000次共耗时:3.72902秒

本帖子中包含更多资源

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

x

点评

刚开始我也是测试递归最快,但表元素太多的话话递归是很慢的还可能出错,你测试的用的表可能很短!  发表于 2011-11-12 12:57
发表于 2011-11-12 12:21 | 显示全部楼层
以下为上述结果的 测试程序部分    计算函数 详见上面的附件 Test.lsp
  1. ;测试函数
  2. (defun C:TT ( / lst i n idxs idx funs fun)
  3.   (setq i 5000)                        ;测试次数
  4.   (setq lst lst1)        ;测试函数列表
  5.   (setq n (length lst))
  6.   (setq idxs '(0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9)        ;测试位置
  7.         funs '("EF:List-IndexDel-1"
  8.                "EF:List-IndexDel-2"
  9.                "EF:List-IndexDel-3"
  10.                "EF:List-IndexDel-递归"
  11.                );测试函数名
  12.         )
  13.   
  14.   (princ "\n测试对象 lst 元素共")
  15.   (princ n)
  16.   (princ "个")
  17.   
  18.   (mapcar '(lambda (fun)
  19.              (mapcar '(lambda (idx)
  20.                         (EF:TimeTest
  21.                           (read (strcat "(" fun " "(rtos (fix (* idx n)) 2 0) " lst)"))
  22.                           i)
  23.                         ) idxs
  24.                      )
  25.              )funs
  26.           )
  27.   (princ)
  28.   )

  29. ;获取当前时间
  30. (defun EF:GetTime (/ Date H M S)
  31.   (setq Date (getvar "CDATE"))
  32.   (setq H (* (- Date (fix Date)) 100))
  33.   (setq M (* (- H (fix H)) 100))
  34.   (setq H (fix H))
  35.   (setq        S (* (- M (fix M)) 100))
  36.   (setq M (fix M))
  37.   (+ (* (+ (* H 60) M) 60) S)
  38.   )

  39. ;函数运行时间测试
  40. (defun EF:TimeTest (fun n / time)
  41.   (princ "\n测试函数【")
  42.   (princ fun)
  43.   (princ "】")
  44.   (setq time (EF:GetTime))
  45.   (repeat n (eval fun))
  46.   (princ (strcat (rtos n 2 0) "次共耗时:"))
  47.   (princ (- (EF:GetTime) time))
  48.   (princ "秒")
  49.   (princ)
  50. )
发表于 2011-11-12 15:21 | 显示全部楼层
补充下 member 方法的测试结果  与 递归算法对比

测试对象 lst 元素 共2000个

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

评分

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

查看全部评分

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

评分

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

查看全部评分

您需要登录后才可以回帖 登录 | 注册

本版积分规则

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

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

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

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