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

fsxm

为夺取最后胜利冲刺！

1. (defun fsxm-RemoveN (lst n / i slst tmp len)
   
2.   (setq i 0)
   
3.   (setq len (length lst))
   
4.   (if (< n (/ len 2))
   
5.     (progn
   
6.       (setq slst (vl-member-if-not
   
7.                    (function (lambda (a)
   
8.                                (if (/= i n)
   
9.                                  (setq tmp (cons a tmp)
   
10.                                        i   (1+ i)
    
11.                                  )
    
12.                                )
    
13.                              )
    
14.                    )
    
15.                    lst
    
16.                  )
    
17.       )
    
18.       (append (reverse tmp) (cdr slst))
    
19.     )
    
20.     (progn
    
21.       (setq lst         (reverse lst)
    
22.             n         (- len n 1)
    
23.             slst (vl-member-if-not
    
24.                    (function (lambda (a)
    
25.                                (if (/= i n)
    
26.                                  (setq tmp (cons a tmp)
    
27.                                        i   (1+ i)
    
28.                                  )
    
29.                                )
    
30.                              )
    
31.                    )
    
32.                    lst
    
33.                  )
    
34.       )
    
35.       (append (reverse (cdr slst)) tmp)
    
36.     )
    
37.   )
    
38. )

(defun fsxm-RemoveN (lst n / i slst tmp len)<br />   (setq i 0)<br />   (setq len (length lst))<br />   (if (< n (/ len 2))<br />     (progn<br />       (setq slst (vl-member-if-not<br />                    (function (lambda (a)<br />                                (if (/= i n)<br />                                  (setq tmp (cons a tmp)<br />                                        i   (1+ i)<br />                                  )<br />                                )<br />                              )<br />                    )<br />                    lst<br />                  )<br />       )<br />       (append (reverse tmp) (cdr slst))<br />     )<br />     (progn<br />       (setq lst         (reverse lst)<br />             n         (- len n 1)<br />             slst (vl-member-if-not<br />                    (function (lambda (a)<br />                                (if (/= i n)<br />                                  (setq tmp (cons a tmp)<br />                                        i   (1+ i)<br />                                  )<br />                                )<br />                              )<br />                    )<br />                    lst<br />                  )<br />       )<br />       (append (reverse (cdr slst)) tmp)<br />     )<br />   )<br /> )

Gu_xl

我的方法三代码优化一下，快多了！

1. (defun gxl-removeNth2  (index lst / c rtn len)
   
2.   (if (< -1 index (setq len (length lst)) )
   
3.     (if (<= index (/ len 2)) ;_ index位于前半截
   
4.       (progn
   
5. (setq c -1)
   
6. (while (/= index (setq c (1+ c)))
   
7.    (setq rtn (cons (car lst) rtn)
   
8.   lst (cdr lst)
   
9.   )
   
10.    )
    
11. (append (reverse rtn) (cdr lst))
    
12. )
    
13.       (progn ;_ index位于后半截
    
14. (setq index (- len index 1)
    
15.        lst   (reverse lst)
    
16.        c     -1
    
17.        )
    
18. (while (/= index (setq c (1+ c)))
    
19.    (setq rtn (cons (car lst) rtn)
    
20.   lst (cdr lst)
    
21.   )
    
22.    )
    
23. (reverse (append (reverse rtn) (cdr lst)))
    
24. )
    
25.       )
    
26.         lst ;_ index 越界
    
27.     )
    
28.   )
    
29.   )
    

(defun gxl-removeNth2  (index lst / c rtn len)<br />   (if (< -1 index (setq len (length lst)) )<br />     (if (<= index (/ len 2)) ;_ index位于前半截<br />       (progn<br /> (setq c -1)<br /> (while (/= index (setq c (1+ c)))<br />    (setq rtn (cons (car lst) rtn)<br />   lst (cdr lst)<br />   )<br />    )<br /> (append (reverse rtn) (cdr lst))<br /> )<br />       (progn ;_ index位于后半截<br /> (setq index (- len index 1)<br />        lst   (reverse lst)<br />        c     -1<br />        )<br /> (while (/= index (setq c (1+ c)))<br />    (setq rtn (cons (car lst) rtn)<br />   lst (cdr lst)<br />   )<br />    )<br /> (reverse (append (reverse rtn) (cdr lst)))<br /> )<br />       )<br />         lst ;_ index 越界<br />     )<br />   )<br />   )<br />

几种方法测试结果：
命令: tt
Gu_xl 方法一:
  用时  0.113281  秒
Gu_xl 方法二:
  用时  0.078125  秒
Gu_xl 方法三:
  用时  0.0117188  秒
duotu007 方法:
  用时  0.03125  秒
xshrimp 方法:
  用时  0.0195313  秒
yjr111 test2方法:
  用时  0.417969  秒
fsxm 方法:
  用时  0.015625  秒

全部测试代码:

xshrimp

命令: test1
测试程序名.....流逝时间(毫秒) / 相对速度 (重复: 1024 次)
    (FSXM-REMOVEN 300 LST1)............1078 / 28.87 <fastest>
    (GXL-REMOVENTH2 300 LST1)..........1188 / 26.2
    (XSHRIMP-REMOVENTH 300 LST1).......3109 / 10.01
    (DUOTU007-REMOVENTH 300 LST1)......4250 / 7.32
    (GXL-REMOVENTH1 300 LST1)..........8313 / 3.74
    (GXL-REMOVENTH 300 LST1)...........8813 / 3.53
    (YJR111-REMOVEN 300 LST1).........31125 / 1 <slowest>

命令: test2
测试程序名.....流逝时间(毫秒) / 相对速度 (重复: 512 次)
(FSXM-REMOVEN 1900 LST1)............1203 / 62.97 <最快>
(GXL-REMOVENTH2 1900 LST1)..........1375 / 55.09
(XSHRIMP-REMOVENTH 1900 LST1).......1765 / 42.92
(DUOTU007-REMOVENTH 1900 LST1)......2172 / 34.88
(GXL-REMOVENTH1 1900 LST1)..........4219 / 17.95
(GXL-REMOVENTH 1900 LST1)...........4547 / 16.66
(YJR111-REMOVEN 1900 LST1).........75750 / 1 <最慢>

命令:
命令: test3
测试程序名.....流逝时间(毫秒) / 相对速度 (重复: 65536 次)
(GXL-REMOVENTH2 6 LST2).........1938 / 5.02 <最快>
(FSXM-REMOVEN 6 LST2)...........1953 / 4.98
(XSHRIMP-REMOVENTH 6 LST2)......4031 / 2.41
(DUOTU007-REMOVENTH 6 LST2).....5016 / 1.94
(GXL-REMOVENTH1 6 LST2).........8469 / 1.15
(GXL-REMOVENTH 6 LST2)..........9031 / 1.08
(YJR111-REMOVEN 6 LST2).........9734 / 1 <最慢>

命令:
命令: test4
测试程序名.....流逝时间(毫秒) / 相对速度 (重复: 32768 次)
(FSXM-REMOVEN 16 LST2)...........1187 / 4.38 <最快>
(GXL-REMOVENTH2 16 LST2).........1250 / 4.16
(XSHRIMP-REMOVENTH 16 LST2)......2031 / 2.56
(DUOTU007-REMOVENTH 16 LST2).....2516 / 2.07
(GXL-REMOVENTH1 16 LST2).........4219 / 1.23
(GXL-REMOVENTH 16 LST2)..........4531 / 1.15
(YJR111-REMOVEN 16 LST2).........5203 / 1 <最慢>

xshrimp

Mp的Benchmark.lsp测试程序

这个测试应该相对准确点.测试结果见楼上
根据Gu_xl修改的测试程序

highflybird

建议把测试次数放大100倍，这样才能较准确反映其效率.

VBALISPER

N大高手齐出手!精彩!

yjr111

唉，最慢也要慢得有点面子，又搞一个，又快了一点，应该不会第一名了哈

2. (defun test3(n lst / )
   
3.   (setq   lst_2 '() len (length lst))
   
4.   (cond ((< n (/ len 2))
   
5.          (setq  i 0)
   
6.          (setq lst_1(vl-remove-if (function(lambda(x)
   
7.           (if(= i n) nil (progn(setq i (1+ i)lst_2 (cons x lst_2)) ))))lst))
   
8.          (append (reverse lst_2) (cdr lst_1))
   
9.         )
   
10.         ((> n (/ len 2))
    
11.          (setq lst (reverse lst) n (- len n) i 1)         
    
12.          (setq lst_1(vl-remove-if (function(lambda(x)
    
13.          (if(= i n) nil (progn(setq i (1+ i)lst_2 (cons x lst_2)) ))))lst))
    
14.          (reverse(append  (reverse lst_2)  (cdr lst_1)))
    
15.         )
    
16.   )       
    
17.          
    
18.   )

(defun test3(n lst / )<br />   (setq   lst_2 '() len (length lst))<br />   (cond ((< n (/ len 2))<br />          (setq  i 0)<br />          (setq lst_1(vl-remove-if (function(lambda(x)<br />           (if(= i n) nil (progn(setq i (1+ i)lst_2 (cons x lst_2)) ))))lst))<br />          (append (reverse lst_2) (cdr lst_1))<br />         )<br />         ((> n (/ len 2))<br />          (setq lst (reverse lst) n (- len n) i 1)         <br />          (setq lst_1(vl-remove-if (function(lambda(x)<br />          (if(= i n) nil (progn(setq i (1+ i)lst_2 (cons x lst_2)) ))))lst))<br />          (reverse(append  (reverse lst_2)  (cdr lst_1)))<br />         )<br />   )        <br />          <br />   )

按题意放大10倍检测：
命令: tt
第一次。。。。。。。。。。
Gu_xl 方法一:
  用时  11.3594  秒
Gu_xl 方法二:
  用时  11.1406  秒
Gu_xl 方法三:
  用时  1.67188  秒
duotu007 方法:
  用时  6.9375  秒
xshrimp 方法:
  用时  2.57813  秒
yjr111 test3方法:
  用时  6.15625  秒
fsxm 方法:
  用时  1.54688  秒

命令: tt
第二次。。。。。。。。
Gu_xl 方法一:
  用时  14.5625  秒
Gu_xl 方法二:
  用时  15.6094  秒
Gu_xl 方法三:
  用时  2.04688  秒
duotu007 方法:
  用时  9.59375  秒
xshrimp 方法:
  用时  3.01563  秒
yjr111 test3方法:
  用时  8.375  秒
fsxm 方法:
  用时  1.90625  秒

xianaihua

2. ;;;递归法
   
3. (defun RemoveNth1 (index lst)
   
4.   (if (and lst (< 0 index))
   
5.     (cons (car lst) (RemoveNth1 (1- index) (cdr lst)))
   
6.     (cdr lst)
   
7.   ) ;_ 结束if
   
8. ) ;_ 结束defun
   
9. 
   
10. 
    
11. ;;;迭代法
    
12. (defun RemoveNth2 (index lst / i)
    
13.   (setq i -1)
    
14.   (vl-remove-if '(lambda (x) (= (setq i (1+ i)) index)) lst)
    
15. ) ;_ 结束defun

;;;递归法<br /> (defun RemoveNth1 (index lst)<br />   (if (and lst (< 0 index))<br />     (cons (car lst) (RemoveNth1 (1- index) (cdr lst)))<br />     (cdr lst)<br />   ) ;_ 结束if<br /> ) ;_ 结束defun<br /> <br /> <br /> ;;;迭代法<br /> (defun RemoveNth2 (index lst / i)<br />   (setq i -1)<br />   (vl-remove-if '(lambda (x) (= (setq i (1+ i)) index)) lst)<br /> ) ;_ 结束defun

xianaihua

xianaihua 发表于 2011-11-11 12:01

__$
正在进行处理 ..............运行的毫秒数 / 迭代2048次的相对速度:

    (REMOVENTH1 300 LST1).........1656 / 2.86 <最快>
    (FSXM-REMOVEN LST1 300).......2422 / 1.95
    (GXL-REMOVENTH2 300 LST1).....2563 / 1.85
    (REMOVENTH2 300 LST1).........4734 / 1 <最慢>
$
正在进行处理 .................运行的毫秒数 / 迭代16384次的相对速度(s):

    (GXL-REMOVENTH2 1900 LST1)......1063 / 65.92 <最快>
    (REMOVENTH2 1900 LST1).........38078 / 1.84
    (FSXM-REMOVEN LST1 1900).......69750 / 1
    (REMOVENTH1 1900 LST1).........70078 / 1 <最慢>
;
_$
正在进行处理 .................运行的毫秒数 / 迭代16384次的相对速度:

    (REMOVENTH1 16 LST2).........1500 / 1.92 <最快>
    (GXL-REMOVENTH2 16 LST2).....1719 / 1.67
    (FSXM-REMOVEN LST2 16).......1765 / 1.63
    (REMOVENTH2 16 LST2).........2875 / 1 <最慢>

正在进行处理 .................运行的毫秒数 / 迭代16384次的相对速度:

    (REMOVENTH1 6 LST2).........1125 / 2.6 <最快>
    (GXL-REMOVENTH2 6 LST2).....1219 / 2.4
    (FSXM-REMOVEN LST2 6).......1406 / 2.08
    (REMOVENTH2 6 LST2).........2922 / 1 <最慢>

3527188

最后的结果是，什么方法最快呢？