【挑战】获取子表

st788796

sublist3和 mt:sublist 差了 三个 cdr相当于
for (int i= 4;0…

先抢跑了

newer

wowan1314 发表于 2017-6-9 13:31

很佩服你的观察和统计能力

且听风吟09

重新写了一个
不太清楚reverse和遍历列表哪个效率更高，通过判断三段子列表长度，对最短的两段子列表进行循环操作

[C] 纯文本查看 复制代码

(defun kaka-list-Sub2 (lst start len / l sublst)
  (setq start (max start 0))
  (if (null len)
    (setq len (- (length lst) start))
  )
  (setq l (- (length lst) start len))
  (if (and (> start l) (> start (* 2 len)))
    (progn
      (setq lst (reverse lst))
      (repeat l
	(setq lst (cdr lst))
      )
      (repeat len
	(setq sublst (cons (car lst) sublst)
	      lst    (cdr lst)
	)
      )
      sublst
    )
    (progn
      (repeat start
	(setq lst (cdr lst))
      )
      (if (< (* 2 len) l)
	(progn
	  (repeat len
	    (setq sublst (cons (car lst) sublst)
		  lst	 (cdr lst)
	    )
	  )
	)
	(progn
	  (setq sublst (reverse lst))
	  (repeat l
	    (setq sublst (cdr sublst))
	  )
	)
      )
      (reverse sublst)
    )
  )
)

newer

且听风吟09 发表于 2017-6-9 14:34

1、中间测试



2、NIL测试



新的KAKA 中间段测试有提升， 但NIL处理还是慢，再完善完善。

Lisphk

newer 发表于 2017-6-9 14:49

1. (defun HK:SubList2 (lst left lgth / _trim)
   
2.   (defun _trim (l i)
   
3.     (if (> i 0)
   
4.       (_trim (cdr l) (1- i))
   
5.       l
   
6.     )
   
7.   )
   
8.   (if lgth
   
9.     (reverse (_trim (reverse (_trim lst left)) (- (length lst) left lgth)))
   
10.     (_trim lst left)
    
11.   )
    
12. )
    

(defun HK:SubList2 (lst left lgth / _trim)<br />   (defun _trim (l i)<br />     (if (> i 0)<br />       (_trim (cdr l) (1- i))<br />       l<br />     )<br />   )<br />   (if lgth<br />     (reverse (_trim (reverse (_trim lst left)) (- (length lst) left lgth)))<br />     (_trim lst left)<br />   )<br /> )<br />

newer

Lisphk 发表于 2017-6-9 22:23

1、中间测试



2、NIL测试

Lispboy

newer 发表于 2017-6-9 22:57

1. (defun LB:sublist2 (lst s l / i)
   
2.   (if (not l)
   
3.     (setq l (- (length lst) s))
   
4.   )
   
5.   (repeat 2
   
6.     (setq i   0
   
7.           lst (reverse (vl-member-if (function (lambda (e) (< s (setq i (1+ i))))) lst))
   
8.           s   (- (length lst) l)
   
9.     )
   
10.   )
    
11.   lst
    
12. )
    

(defun LB:sublist2 (lst s l / i)<br />   (if (not l)<br />     (setq l (- (length lst) s))<br />   )<br />   (repeat 2<br />     (setq i   0<br />           lst (reverse (vl-member-if (function (lambda (e) (< s (setq i (1+ i))))) lst))<br />           s   (- (length lst) l)<br />     )<br />   )<br />   lst<br /> )<br />

newer

Lispboy 发表于 2017-6-9 23:50

1、中间测试



2、NIL测试

ll_j

marting 发表于 2017-6-9 13:10

使用了cadr系列函数最巧妙的，无疑也是最快的。
有个建议，就是在开始前对总长、开始、截取长做一个比较，即把总表分为三段，这样可以先截掉首或尾最短的一段，然后在比较剩下的两端长度确定斩头或截留。这样做对某个表来说或许不是最快的，但可以保证在超大表时有最高的整体效率。
基本代码还是你的代码，我也不想掺和了，如果有兴趣，你不妨再组织一下。

st788796

ll_j 发表于 2017-6-10 08:38

对 mt:sublist 的任何优化基本都是多余，大家可以测试下。用通俗语言分析下程序

repeat (/ s 4)  ---- 循环次数是 while cdr 的1/4
  (setq l (cons ...  --- 一次构造四个元素，相当于四档 起步
          l (cddddr l) ----  又是一个四档
...
repeat (rem s 4) --- 其余的一档，最多循环3次
...
if (and s l) .... 如果到尾部就不执行此段，直接返回
(progn
    (repeat (/ n 4) ---- 循环是 while + cdr 的 1/4
       (setq s (cons ...    一次构造4个元素，相当于 四档 起步
                l (cddddr l)   ----- 又一个四挡前进
     )
     (repeat (rem n 4) ----- 其余的 一档 ，最多 3 次
         (setq s (cons ... ------ 三档构造
                l  (cdr l) ------ 一档档前进
    )

去头部的时候，循环次数减少 约 3/4 ，去的过程 四档 前进，构造的时候同理，效率就提高在这里，至于还有没有必要 reverse 后用相同方法按去头部方法，其实是多余的，大家可以看到前面的构造表，(repeat 200000 (setq lst (cons i lst))) 这样构造表的时间基本可以忽略，中间部分用 三档 构造，和加判断 reverse 去头部所用时间不会差多少

作为函数整体，alisp 对内存是自动管理的，无从知道堆栈是如何分配的，但是表的迅速收敛在实际应用中可以看到效率整体的明显提升

另外一个函数 nth ，不管是多大的表，单独使用都是首选，循环中使用效率会大打折扣

ll_j

st788796 发表于 2017-6-10 09:10

使用现在的mt:sublist，设想一个30000元素的大表，(mt:sublist lst 1000 2000)无疑是速度最快的，先斩头1000元素，再截取2000元素，成把抓，速度几乎达到极致，但如果是在尾部抓一小截呢，比如(mt:sublist lst 27000 2000)，是不是要把表倒过来“抓”更合适一些？再有，(mt:sublist lst 2000 26000)，是不是把头尾都“抓”扔掉更好呢？
我是这个意思，先判断一下，看看这个次序。因为使用了判断和翻转，或许对某种情况不是最优的，但总体效率应该算最高的。

st788796

ll_j 发表于 2017-6-10 09:30

我用mt:sublist方法修改sublist3，改造的效率仍然不及mt:sublist

newer

ll_j 发表于 2017-6-10 09:30

确实如长老的分析，MT:SUBLIST 唯一的一个弱点的地方被发现了

1、START 接近结尾 分析



2、START接近开头



可见，MT在START接近开头表现开始中庸了。

还是上面的数据，NIL分析：





在START接近开头，MT的数据还是逆天的。
接近结尾，MT还是保持第一，但数据下来了。

通过这两个测试，MT在大多数情况下表现都是优异的，只有一种情况中庸，
长老继续分析分析，MT的代码，在START接近开头NIL的逆天数据，在哪个地方改进下，会提升START接近开头时候非NIL的表现？

ll_j

newer 发表于 2017-6-10 17:24

如我39楼分析，非nil的情况，实际上是留中段，就是要分析先斩头还是先去尾，去掉一截以后再分析是截留，还是斩头去尾。这里涉及判断和表翻转（reverse），所以会影响一部分效率，但总体有一个取舍会更平衡一点。
我前几天测试了一下表反转，使用while＋cdr自己构造的函数不尽人意，而reverse虽然表现好很多，但同样需要时间，使用时也是要注意的。

marting

感谢上面各位的支持，根据大家的意见，修改了mt:sublist的代码，请测试

1. (defun mt:sublist-1 (l s n)
   
2.     (repeat (/ s 4) (setq l (cddddr l)))
   
3.     (repeat (rem s 4) (setq l (cdr l)))
   
4.     (setq s nil)
   
5.     (if (and l n)
   
6.         (cond ((>= n (length l)) l)
   
7.               ((< n (- (length l) n))
   
8.                (repeat (/ n 4)
   
9.                    (setq s (cons (cadddr l)
   
10.                                  (cons (caddr l) (cons (cadr l) (cons (car l) s)))
    
11.                            )
    
12.                          l (cddddr l)
    
13.                    )
    
14.                )
    
15.                (repeat (rem n 4)
    
16.                    (setq s (cons (car l) s)
    
17.                          l (cdr l)
    
18.                    )
    
19.                )
    
20.                (reverse s)
    
21.               )
    
22.               (t
    
23.                (setq l (reverse l)
    
24.                      s (- (length l) n)
    
25.                )
    
26.                (repeat (/ s 4) (setq l (cddddr l)))
    
27.                (repeat (rem s 4) (setq l (cdr l)))
    
28.                (reverse l)
    
29.               )
    
30.         )
    
31.         l
    
32.     )
    
33. )
    
34. 
    

(defun mt:sublist-1 (l s n)<br />     (repeat (/ s 4) (setq l (cddddr l)))<br />     (repeat (rem s 4) (setq l (cdr l)))<br />     (setq s nil)<br />     (if (and l n)<br />         (cond ((>= n (length l)) l)<br />               ((< n (- (length l) n))<br />                (repeat (/ n 4)<br />                    (setq s (cons (cadddr l)<br />                                  (cons (caddr l) (cons (cadr l) (cons (car l) s)))<br />                            )<br />                          l (cddddr l)<br />                    )<br />                )<br />                (repeat (rem n 4)<br />                    (setq s (cons (car l) s)<br />                          l (cdr l)<br />                    )<br />                )<br />                (reverse s)<br />               )<br />               (t<br />                (setq l (reverse l)<br />                      s (- (length l) n)<br />                )<br />                (repeat (/ s 4) (setq l (cddddr l)))<br />                (repeat (rem s 4) (setq l (cdr l)))<br />                (reverse l)<br />               )<br />         )<br />         l<br />     )<br /> )<br /> <br />