返回表第N个元素之后的所有元素（不包括N）

sicky111

确实有些复杂，用个cdr就可以了。

Lispboy

sicky111 发表于 2013-6-13 02:40
确实有些复杂，用个cdr就可以了。

复杂自有复杂的道理，确定看懂了代码了吗？

wowan1314

Free-Lancer 发表于 2013-6-12 23:33
经测试，分治算法确实可以提高效率，不过差在毫秒级

不知道用满足条件就退出循环的mapcar方法比楼主的函数会不会更优秀？！

2. ;;=============={ 返回表第N个元素之后的所有元素 }===================
   
3. ;;测试: (T33 3  '(2334 556 33 44 66 77 22))==> (44 66 77 22)
   
4. (DEFUN T33 (n LST / A)
   
5.   (setq A 0)
   
6.   (vl-catch-all-apply
   
7.     'mapcar
   
8.     (LIST '(lambda (x)
   
9.        (SETQ A (1+ A))
   
10.        (if (< N A)
    
11.          (EXIT)
    
12.          (setq lst (cdr lst))
    
13.        )
    
14.      )
    
15.     lst
    
16.     )
    
17.   )
    
18.   lst
    
19. )

;;=============={ 返回表第N个元素之后的所有元素 }===================<br /> ;;测试: (T33 3  '(2334 556 33 44 66 77 22))==> (44 66 77 22)<br /> (DEFUN T33 (n LST / A)<br />   (setq A 0)<br />   (vl-catch-all-apply<br />     'mapcar<br />     (LIST '(lambda (x)<br />        (SETQ A (1+ A))<br />        (if (< N A)<br />          (EXIT)<br />          (setq lst (cdr lst))<br />        )<br />      )<br />     lst<br />     )<br />   )<br />   lst<br /> )

Lispboy

wowan1314 发表于 2013-6-13 09:49
不知道用满足条件就退出循环的mapcar方法比楼主的函数会不会更优秀？！

葛老，测试是你的强项，你测试下，找个100万的表。

我猜，如果你要找99万以后的表，肯定是我的快:D

Lispboy

wowan1314 发表于 2013-6-13 09:49
不知道用满足条件就退出循环的mapcar方法比楼主的函数会不会更优秀？！

其实，你可以改造下，也分两个分支做，大于1/2用一个MAPCAR, 小于1/2 用另外一个MAPCAR，那样肯定你的快。

不过，我一见到程序里面有(EXIT)就感觉不好，个人原因。

牢固

Lispboy 发表于 2013-6-13 10:08
其实，你可以改造下，也分两个分支做，大于1/2用一个MAPCAR, 小于1/2 用另外一个MAPCAR，那样肯定你的快 ...

返回表第N个元素之后的所有元素的算法和删除表第N个元素的算法基本差不多，删除表第N个元素的最快算法曾经在明经论坛有过大讨论，集成了很多优秀算法代码，大家可以去看看！

ll_j

Lispboy 发表于 2013-6-13 10:08
其实，你可以改造下，也分两个分支做，大于1/2用一个MAPCAR, 小于1/2 用另外一个MAPCAR，那样肯定你的快 ...

其实不要太过纠结于repeat、append、mapcar、cons等函数的效率。
就如本例，repeat可能是最直观的，在n大约一半表长的时候，的确循环的次数太多，那么就reverse？肯定错了，reverse的效率如何？再构建列表的效率如何？
mapcar似乎公认是最有效率的循环，但如果加一个判断情况又如何？
每个函数都有自己的最佳使用范围，如果使用不当，函数本身再有效率也是徒然。

Free-Lancer

ll_j 发表于 2013-6-13 10:50
其实不要太过纠结于repeat、append、mapcar、cons等函数的效率。
就如本例，repeat可能是最直观的，在n ...

测试过 10W 的表，Reverse 的效率是高的

wowan1314

测了下，数据90W的整数表！
参与测试的函数：VL-member及另类mapcar.与楼主的函数。

2. (defun C:1 ()
   
3. (setq time1 (get-utime))
   
4. (T2 700000 LL)
   
5. (setq time2 (get-utime))
   
6. (princ "\nVL-member方法:")
   
7. (princ (- time2 time1))
   
8. (princ "s")
   
9. )
   
10. (defun C:2 ()
    
11. (setq time1 (get-utime))
    
12. (T3 700000 LL)
    
13. (setq time2 (get-utime))
    
14. (princ "\n另类mapcar方法:")
    
15. (princ (- time2 time1))
    
16. (princ "s")
    
17. )
    
18. (defun C:3 ()
    
19. (setq time1 (get-utime))
    
20. (XD::List:N+ LL 700000)
    
21. (setq time2 (get-utime))
    
22. (princ "\n分支方法:")
    
23. (princ (- time2 time1))
    
24. (princ "s")
    
25. )
    
26. (defun c:t1 ()
    
27.   (setq i 0)
    
28.   (setq ll nil)
    
29.   (repeat 900000
    
30.     (setq ll (cons (setq i (1+ i))
    
31.                    ll
    
32.              )
    
33.     )
    
34.   )
    
35. )
    
36. (defun get-utime () (* 86400.0 (getvar "tdusrtimer")))
    
37. 
    
38. ;;=============={ 返回表第N个元素之后的所有元素 }===================
    
39. ;;测试: (T2 3  '(2334 556 33 44 66 77 22))==> (44 66 77 22)
    
40. (DEFUN T2 (n LST / A)
    
41. (setq A 0)
    
42. (vl-member-if '(lambda(x)(setq A (1+ A)) (< n A) ) lst)
    
43. )
    
44. ;;测试: (T3 3  '(2334 556 33 44 66 77 22))==> (44 66 77 22)
    
45. (DEFUN T3 (n LST / A)
    
46. (setq A 0)
    
47. (vl-catch-all-apply 'mapcar (LIST'(lambda(x)(SETQ A (1+ A))(if (< N A) (quit) (setq lst (cdr lst)) ))lst))
    
48. lst
    
49. )
    
50. 
    
51. ;|
    
52. 
    
53.    返回表第N个元素之后的所有元素（不包括N）
    
54. 
    
55.    参数：
    
56.        LST ---- 表
    
57.        N   ---- 序号（从1开始）
    
58. |;
    
59. (defun XD::List:N+ (lst n / lst1 i l)
    
60.   (setq l (length lst))
    
61.   (cond
    
62.     ((< n 1)
    
63.       lst
    
64.     )
    
65.     ((= n 1)
    
66.       (cdr lst)
    
67.     )
    
68.     ((= n 2)
    
69.       (cddr lst)
    
70.     )
    
71.     ((= n 3)
    
72.       (cdddr lst)
    
73.     )
    
74.     ((= n 4)
    
75.       (cddddr lst)
    
76.     )
    
77.     ((and
    
78.        (>= n 5)
    
79.        (<= l)
    
80.      )
    
81.       (if (< n 1)
    
82.         (setq n 1)
    
83.       )
    
84.       (setq i 0)
    
85.       (if (< n (/ l 2.0))
    
86.         (progn
    
87.           (while (and
    
88.                    (setq a (car lst))
    
89.                    (< i n)
    
90.                  )
    
91.             (setq lst (cdr lst)
    
92.                   i (1+ i)
    
93.             )
    
94.           )
    
95.           lst
    
96.         )
    
97.         (progn
    
98.           (setq lst (reverse lst))
    
99.           (while (and
    
100.                    (setq a (car lst))
     
101.                    (< i (- l n))
     
102.                  )
     
103.             (setq lst1 (cons a lst1)
     
104.                   lst (cdr lst)
     
105.                   i (1+ i)
     
106.             )
     
107.           )
     
108.           lst1
     
109.         )
     
110.       )
     
111.     )
     
112.   )
     
113. )
     

(defun C:1 ()<br /> (setq time1 (get-utime))<br /> (T2 700000 LL)<br /> (setq time2 (get-utime))<br /> (princ "\nVL-member方法:")<br /> (princ (- time2 time1))<br /> (princ "s")<br /> )<br /> (defun C:2 ()<br /> (setq time1 (get-utime))<br /> (T3 700000 LL)<br /> (setq time2 (get-utime))<br /> (princ "\n另类mapcar方法:")<br /> (princ (- time2 time1))<br /> (princ "s")<br /> )<br /> (defun C:3 ()<br /> (setq time1 (get-utime))<br /> (XD::List:N+ LL 700000)<br /> (setq time2 (get-utime))<br /> (princ "\n分支方法:")<br /> (princ (- time2 time1))<br /> (princ "s")<br /> )<br /> (defun c:t1 ()<br />   (setq i 0)<br />   (setq ll nil)<br />   (repeat 900000<br />     (setq ll (cons (setq i (1+ i))<br />                    ll<br />              )<br />     )<br />   )<br /> )<br /> (defun get-utime () (* 86400.0 (getvar "tdusrtimer")))<br /> <br /> ;;=============={ 返回表第N个元素之后的所有元素 }===================<br /> ;;测试: (T2 3  '(2334 556 33 44 66 77 22))==> (44 66 77 22)<br /> (DEFUN T2 (n LST / A)<br /> (setq A 0)<br /> (vl-member-if '(lambda(x)(setq A (1+ A)) (< n A) ) lst)<br /> )<br /> ;;测试: (T3 3  '(2334 556 33 44 66 77 22))==> (44 66 77 22)<br /> (DEFUN T3 (n LST / A)<br /> (setq A 0)<br /> (vl-catch-all-apply 'mapcar (LIST'(lambda(x)(SETQ A (1+ A))(if (< N A) (quit) (setq lst (cdr lst)) ))lst))<br /> lst<br /> )<br /> <br /> ;|<br /> <br />    返回表第N个元素之后的所有元素（不包括N）<br /> <br />    参数：<br />        LST ---- 表<br />        N   ---- 序号（从1开始）<br /> |;<br /> (defun XD::List:N+ (lst n / lst1 i l)<br />   (setq l (length lst))<br />   (cond<br />     ((< n 1)<br />       lst<br />     )<br />     ((= n 1)<br />       (cdr lst)<br />     )<br />     ((= n 2)<br />       (cddr lst)<br />     )<br />     ((= n 3)<br />       (cdddr lst)<br />     )<br />     ((= n 4)<br />       (cddddr lst)<br />     )<br />     ((and<br />        (>= n 5)<br />        (<= l)<br />      )<br />       (if (< n 1)<br />         (setq n 1)<br />       )<br />       (setq i 0)<br />       (if (< n (/ l 2.0))<br />         (progn<br />           (while (and<br />                    (setq a (car lst))<br />                    (< i n)<br />                  )<br />             (setq lst (cdr lst)<br />                   i (1+ i)<br />             )<br />           )<br />           lst<br />         )<br />         (progn<br />           (setq lst (reverse lst))<br />           (while (and<br />                    (setq a (car lst))<br />                    (< i (- l n))<br />                  )<br />             (setq lst1 (cons a lst1)<br />                   lst (cdr lst)<br />                   i (1+ i)<br />             )<br />           )<br />           lst1<br />         )<br />       )<br />     )<br />   )<br /> )<br />

wowan1314

测试结果！ 90W数据的表，差别都只在毫秒级。楼主函数两头快中间慢，不过只有一头快过vl-member-if函数.

当N<70W，楼主的函数，搞不赢那两个函数。
当N>70W，楼主的函数才显示出其优势。
当N>80W，函数的差别才达到一百毫秒以上。

测试同时发现，VL-member-if 函数性价比极高。比另类的mapcar的表现还好些.
如果是10W的表。差别仅在几十毫秒之间。实际工程中不晓得数据会在什么级别上。

wowan1314

跟据实际测试,调整代码！

此函数为最优函数

2. ;;=============={ 返回表第N个元素之后的所有元素 }===================
   
3. ;;测试: (T6 3  '(2334 556 33 44 66 77 22))==> (44 66 77 22)
   
4. (DEFUN T6 (n LST / A NLST L)
   
5. (setq A 0 L (LENGTH LST))
   
6. (IF (< N (* L 0.65))
   
7. (SETQ NLST (vl-member-if '(lambda(x)(setq A (1+ A)) (< n A) ) lst))
   
8. (vl-member-if '(lambda(x)(SETQ L (1- L) Nlst (CONS X NLST)) (<= L N) ) (reverse lst))
   
9. )
   
10. NLST
    
11. )

;;=============={ 返回表第N个元素之后的所有元素 }===================<br /> ;;测试: (T6 3  '(2334 556 33 44 66 77 22))==> (44 66 77 22)<br /> (DEFUN T6 (n LST / A NLST L)<br /> (setq A 0 L (LENGTH LST))<br /> (IF (< N (* L 0.65))<br /> (SETQ NLST (vl-member-if '(lambda(x)(setq A (1+ A)) (< n A) ) lst))<br /> (vl-member-if '(lambda(x)(SETQ L (1- L) Nlst (CONS X NLST)) (<= L N) ) (reverse lst))<br /> )<br /> NLST<br /> )

Lispboy

wowan1314 发表于 2013-6-13 15:38
测试结果！ 90W数据的表，差别都只在毫秒级。楼主函数两头快中间慢，不过只有一头快过vl-member-if函数.

...

两头快是肯定的，中间所谓的“慢”也是相对自己，和你们的中间比，是一个数量级的，因为都是都表头到中间。差别也就在FOREACH,WHILE之间的效率差别。这个就是算法体现作用的时候，在机器硬件，函数基本固定情况下，考虑优化的算法是有作用的。当然对今天的硬件来说，只是毫秒级的差距。

看过一个帖子的讨论，对于中间插入，删除这样的操作，VL-REMOVE-IF 这样的函数效率是低的，因为他要遍历所有表，还附带删除操作。

所以，对于必须要遍历所有节点的应用，可以用VL-REMOVE-IF这样的。 对于中间操作然后就结束的，尽量别用。

Lispboy

wowan1314 发表于 2013-6-13 17:22
跟据实际测试,调整代码！

此函数为最优函数

VL-MEMBER-IF 对重复量很大的表，表现如何，葛老测试测试。

wowan1314

Lispboy 发表于 2013-6-13 17:53
VL-MEMBER-IF 对重复量很大的表，表现如何，葛老测试测试。

函数及测试函数都给你了。你都懒的运行下看看哦？

100W相同元素表。N=90W。
命令: 1
VL-member方法:0.375s"s"
命令: 3
分支方法:0.125s"s"
命令: 6
分支方法:0.094s"s"
N=50W
命令: 1
VL-member方法:0.203s"s"
命令:
命令: 3
分支方法:0.469s"s"
命令:
命令: 6
分支方法:0.219s"s"
N=10W
速度一样

wowan1314

ll_j 发表于 2013-6-13 10:50
其实不要太过纠结于repeat、append、mapcar、cons等函数的效率。
就如本例，repeat可能是最直观的，在n ...

长老说的对！ 加if判断后，速度有点影响,不如vl-member-if函数了