Topic: list of first n elements from list

[Kerry]

 I was cleaning up some code and noticed the date on this. I use this routine and a few of it's brothers daily.

Makes me laugh a little when I see this stuff re-invented and published as new and revolutionary.

Code - Auto/Visual Lisp: [Select]

1.  ;;; "list of first n elements", iterative version
2. ;;; with safety check:
3. ;;;   (std-firstn 1 '(0 1 2)) => '(0)
4. ;;;   (std-firstn 0 '(0 1 2)) => nil
5. ;;;   (std-firstn 4 '(0 1 2)) => '(0 1 2)
6. ;;; O(n+i)
7. ;;  http://autocad.xarch.at/stdlib/html/func6hgu.htm
8. ;;  circa 1998 from STDLIST
9. (defun std-firstn (i lst / out)
10.   (repeat (min i (length lst))
11.     (setq out (cons (car lst) out)
12.           lst (cdr lst)
13.     )
14.   )
15.   (reverse out)
16. )

In my opinion Tony T and Reini Urban should be thanked every day for their individual contribution to out industry.

[MP]

True (tho I don't know if Tony would care to share praise in the same breath as Reini), tho even in '98 chances are a variant of that algorithm was about 40 years old.

While I have my own (defun _GetNItems ...) function it's often more convenient to simply use ...

(mapcar 'set '(varΉ var² var³ ... varⁿ) lst)

(pre) Nulling the target vars if applicable (e.g. child of iterative code).

[Kerry]

< .. >  tho even in '98 chances are a variant of that algorithm was about 40 years old.

yep.

[divtiply]

std-firstn uses (length) function, therefore it _always_ runs till the end of a list. This behaviour can be slow with a large lists.

[MP]

std-firstn uses (length) function, therefore it _always_ runs till the end of a list. This behavior can be slow with a large lists.

Disagree, std-firstn is fine as is and its performance negligibly impacted by the size of the list it processes.

[Kerry]

divtiply,
Have another look at the code.
The iteration is for the MIN of n or list length. If the list has a thousand elements and we want the first 10 the REPEAT will execute the code block 10 times.

http://autocad.xarch.at/stdlib/html/func6hgu.htm

[Lee Mac]

std-firstn uses (length) function, therefore it _always_ runs till the end of a list. This behavior can be slow with a large lists.

Disagree, std-firstn is fine as is and its performance negligibly impacted by the size of the list it processes.

Agree that the use of length has negligible affect on performance, but feel that std-firstn could be better optimised when n>length/2, e.g.:

Code - Auto/Visual Lisp: [Select]

1. (defun firstn ( n l / r )
2.     (if (< n (/ (length l) 2))
3.         (progn
4.             (repeat n
5.                 (setq r (cons (car l) r)
6.                       l (cdr l)
7.                 )
8.             )
9.             (reverse r)
10.         )
11.         (progn
12.             (setq l (reverse l))
13.             (repeat (- (length l) n)
14.                 (setq l (cdr l))
15.             )
16.             (reverse l)
17.         )
18.     )
19. )

(reverse is quick IIRC, even for large lists)

[Kerry]

I'd need to see some compelling evidence to warrant that sort of algorithm for the general usage 

[Lee Mac]

I'd need to see some compelling evidence to warrant that sort of algorithm for the general usage

Sample list:

Code - Auto/Visual Lisp: [Select]

1. _$ (setq lst '(1 2 3 4))
2. (1 2 3 4)
3. _$ (repeat 10 (setq lst (append lst lst)))
4. (1 2 3 ... 1 2 3 4)
5. _$ (length lst)
6. 4096

Benchmarks:

Code - Auto/Visual Lisp: [Select]

1. _$ (benchmark '((std-firstn 10 lst) (firstn 10 lst)))
2. Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):
3.  
4.     (FIRSTN 10 LST).........1123 / 1.00 <fastest>
5.     (STD-FIRSTN 10 LST).....1124 / 1.00 <slowest>
6.  
7. _$ (benchmark '((std-firstn 3000 lst) (firstn 3000 lst)))
8. Benchmarking .............Elapsed milliseconds / relative speed for 1024 iteration(s):
9.  
10.     (FIRSTN 3000 LST).........1373 / 3.17 <fastest>
11.     (STD-FIRSTN 3000 LST).....4352 / 1.00 <slowest>
12.  
13. _$ (benchmark '((std-firstn 4000 lst) (firstn 4000 lst)))
14. Benchmarking ..............Elapsed milliseconds / relative speed for 2048 iteration(s):
15.  
16.     (FIRSTN 4000 LST)..........1498 / 7.91 <fastest>
17.     (STD-FIRSTN 4000 LST).....11856 / 1.00 <slowest>

[MP]

It's easy to dismiss improvements that aren't revealed until list lengths are rather high but consider that the items might represent data originating from a file -- easily realized in day to day programming. Thanks for the mod Lee.

[Kerry]

Yes it does make a difference for large quantities on large data lists.

My testing shows the difference is not as significant as shown by your test .. interesting.

Thanks for the option Lee.

Code - Auto/Visual Lisp: [Select]

1.  
2. (setq list4 nil
3.       list20 nil
4.       list100 nil
5.       list4000 nil
6. )
7. (setq list4    '(1 "alpha" 2 "bravo")
8.       list20   (repeat 5 (setq list20 (append list20 list4)))
9.       list100  (repeat 5 (setq list100 (append list100 list20)))
10.       list4000 (repeat 40 (setq list4000 (append list4000 list100)))
11. )
12.  
13.  
14.  
15. (benchmark '((std-firstn 2 list4) (firstn 2 list4)))
16. (benchmark '((std-firstn 3 list4) (firstn 3 list4)))
17.  
18. (benchmark '((std-firstn 5 list20) (firstn 5 list20)))
19. (benchmark '((std-firstn 15 list20) (firstn 15 list20)))
20.  
21. (benchmark '((std-firstn 20 list100) (firstn 20 list100)))
22. (benchmark '((std-firstn 75 list100) (firstn 75 list100)))
23.  
24. (benchmark '((std-firstn 50 list4000) (firstn 50 list4000)))
25. (benchmark '((std-firstn 3000 list4000) (firstn 3000 list4000)))
26.  
27. (benchmark '((std-firstn 3990 list4000) (firstn 3990 list4000)))
28.  

Code - Text: [Select]

1.  Benchmarking [M.P. 2005 < revised kdub 2005>] ................
2. Elapsed milliseconds for 8192 iteration(s)/ relative Timing :
3.  
4.     (STD-FIRSTN 2 LIST4).....219 / 1.0788 <slowest>
5.     (FIRSTN 2 LIST4).........203 / 1.0000 <fastest>
6.  
7.  Benchmarking [M.P. 2005 < revised kdub 2005>] ................
8. Elapsed milliseconds for 8192 iteration(s)/ relative Timing :
9.  
10.     (FIRSTN 3 LIST4).........218 / 1.0000 <slowest>
11.     (STD-FIRSTN 3 LIST4).....218 / 1.0000 <fastest>
12.  
13.  Benchmarking [M.P. 2005 < revised kdub 2005>] ................
14. Elapsed milliseconds for 8192 iteration(s)/ relative Timing :
15.  
16.     (FIRSTN 5 LIST20).........234 / 1.0734 <slowest>
17.     (STD-FIRSTN 5 LIST20).....218 / 1.0000 <fastest>
18.  
19.  Benchmarking [M.P. 2005 < revised kdub 2005>] ................
20. Elapsed milliseconds for 8192 iteration(s)/ relative Timing :
21.  
22.     (STD-FIRSTN 15 LIST20).....280 / 1.2844 <slowest>
23.     (FIRSTN 15 LIST20).........218 / 1.0000 <fastest>
24.  
25.  Benchmarking [M.P. 2005 < revised kdub 2005>] ................
26. Elapsed milliseconds for 8192 iteration(s)/ relative Timing :
27.  
28.     (FIRSTN 20 LIST100).........312 / 1.0000 <slowest>
29.     (STD-FIRSTN 20 LIST100).....312 / 1.0000 <fastest>    
30.  
31.  Benchmarking [M.P. 2005 < revised kdub 2005>] ................
32. Elapsed milliseconds for 8192 iteration(s)/ relative Timing :
33.  
34.     (STD-FIRSTN 75 LIST100).....609 / 1.7755 <slowest>
35.     (FIRSTN 75 LIST100).........343 / 1.0000 <fastest>
36.  
37.  Benchmarking [M.P. 2005 < revised kdub 2005>] ...............
38. Elapsed milliseconds for 4096 iteration(s)/ relative Timing :
39.  
40.     (FIRSTN 50 LIST4000).........281 / 1.0036 <slowest>
41.     (STD-FIRSTN 50 LIST4000).....280 / 1.0000 <fastest>
42.  
43.  Benchmarking [M.P. 2005 < revised kdub 2005>] ...........
44. Elapsed milliseconds for 256 iteration(s)/ relative Timing :
45.  
46.     (STD-FIRSTN 3000 LIST4000).....609 / 2.4360 <slowest>
47.     (FIRSTN 3000 LIST4000).........250 / 1.0000 <fastest>
48.  
49.  Benchmarking [M.P. 2005 < revised kdub 2005>] ...........
50. Elapsed milliseconds for 256 iteration(s)/ relative Timing :
51.  
52.     (STD-FIRSTN 3990 LIST4000).....812 / 4.0000 <slowest>
53.     (FIRSTN 3990 LIST4000).........203 / 1.0000 <fastest>
54.  
55.  

[Lee Mac]

Yes it does make a difference for large quantities on large data lists.

My testing shows the difference is not as significant as shown by your test .. interesting.

I'd hazard a guess that the difference in the benchmarking is perhaps a result of different hardware specs, as the number of iterations performed in your tests are also different from mine (especially when processing the tail-end of the list).

Thanks for the option Lee.

Thanks for the mod Lee.

Cheers guys 

[Lee Mac]

Here is a recursive variant for 'fun':

Code - Auto/Visual Lisp: [Select]

1. (defun firstn-rec ( n l )
2.     (if (and l (< 0 n))
3.         (cons (car l) (firstn-rec (1- n) (cdr l)))
4.     )
5. )

At the expense of performance of course 

[Marc'Antonio Alessi]

Also depends on the type of list...

(setq aList '(1 2 3 4))
(repeat 10 (setq aList (append aList aList)))

(setq Alist2 (atoms-family 1)) ;len 3986

Code: [Select]

;another approach with member 03-19-2008
(defun ALE_List_ReverseMember (NthPos In_Lst / InRLst NthItm)
  (cond
    ( (> NthPos (length In_Lst)) In_Lst)
    ( (> NthPos 500)
      (setq InRLst (reverse In_Lst)  NthItm (nth NthPos In_Lst))
      (while
        (/=
          NthPos
          (length (setq InRLst (cdr (member NthItm InRLst))))
        )
      )
      (reverse InRLst)
    )
    ( T
      (repeat NthPos
        (setq
          InRLst (cons (car In_Lst) InRLst)
          In_Lst (cdr In_Lst)
        )
      )
      (reverse InRLst)
    )
  )
)

Code: [Select]

(ALE_LIST_REVERSEMEMBER 10 ALIST).........3869 / 61.53 <fastest>
(FIRSTN 10 ALIST).........................4743 / 50.19
(FIRSTN 4000 ALIST)......................44492 / 5.35
(ALE_LIST_REVERSEMEMBER 4000 ALIST)......60419 / 3.94
(FIRSTN 3000 ALIST)......................74568 / 3.19
(ALE_LIST_REVERSEMEMBER 3000 ALIST).....238073 / 1 <slowest>     

(FIRSTN 10 ALIST2).....................1887 / 1.19 <fastest>
(ALE_LIST_REVERSEMEMBER 10 ALIST2).....2246 / 1 <slowest>

(ALE_LIST_REVERSEMEMBER 3000 ALIST2).....3042 / 1.19 <fastest>
(FIRSTN 3000 ALIST2).....................3619 / 1 <slowest>

(ALE_LIST_REVERSEMEMBER 3980 ALIST2).....1684 / 1.16 <fastest>
(FIRSTN 3980 ALIST2).....................1950 / 1 <slowest>


Merry Christmas to all.

[MP]

[Edited] Ugly but performs reasonably, gnerally better as the size of the list increases (some code lifted, some code new) ...

Code: [Select]

(defun FirstN_MP ( n lst / len foo boo bar )
    (defun foo ( n lst / result )
        (repeat n
            (setq
                result (cons (car lst) result)
                lst    (cdr lst)
            )
        )
        (reverse result)
    )
    (defun boo ( n k lst func )
        (repeat (/ (- (length lst) n) k)
            (setq lst (func lst))
        )
        lst
    )
    (defun bar ( n lst / result )
        (setq result (reverse lst))
        (foreach pair '((4 cddddr)(3 cdddr)(2 cddr)(1 cdr))
            (setq result (boo n (car pair) result (eval (cadr pair))))
        )
        (reverse result)           
    )
    (if (< (setq n (min n (setq len (length lst)))) (/ len 5))
        (foo n lst)
        (bar n lst)
    )
)
Test results for n samples of 10, 33, 50, 66 and 90 % of the list lengths, for list lengths of 100, 1000 and 10000.

List length = 100, n = 10

    (FIRSTN_STD N LST).....1373 / 1.13 <fastest>
    (FIRSTN_LM N LST)......1389 / 1.11
    (FIRSTN_ALE N LST).....1404 / 1.10
    (FIRSTN_MP N LST)......1545 / 1.00 <slowest>

List length = 100, n = 33

    (FIRSTN_ALE N LST).....1045 / 1.10 <fastest>
    (FIRSTN_STD N LST).....1045 / 1.10
    (FIRSTN_LM N LST)......1045 / 1.10
    (FIRSTN_MP N LST)......1154 / 1.00 <slowest>

List length = 100, n = 50

    (FIRSTN_LM N LST)......1061 / 1.24 <fastest>
    (FIRSTN_MP N LST)......1138 / 1.15
    (FIRSTN_ALE N LST).....1310 / 1.00
    (FIRSTN_STD N LST).....1311 / 1.00 <slowest>

List length = 100, n = 66

    (FIRSTN_LM N LST)......1856 / 1.67 <fastest>
    (FIRSTN_MP N LST)......2246 / 1.38
    (FIRSTN_STD N LST).....3089 / 1.00
    (FIRSTN_ALE N LST).....3104 / 1.00 <slowest>

List length = 100, n = 90

    (FIRSTN_LM N LST)......1436 / 2.68 <fastest>
    (FIRSTN_MP N LST)......2153 / 1.79
    (FIRSTN_STD N LST).....3853 / 1.00
    (FIRSTN_ALE N LST).....3854 / 1.00 <slowest>

List length = 1000, n = 100

    (FIRSTN_ALE N LST).....1077 / 1.04 <fastest>
    (FIRSTN_STD N LST).....1077 / 1.04
    (FIRSTN_LM N LST)......1092 / 1.03
    (FIRSTN_MP N LST)......1124 / 1.00 <slowest>

List length = 1000, n = 330

    (FIRSTN_MP N LST)......1061 / 1.43 <fastest>
    (FIRSTN_LM N LST)......1497 / 1.01
    (FIRSTN_ALE N LST).....1513 / 1.00
    (FIRSTN_STD N LST).....1513 / 1.00 <slowest>

List length = 1000, n = 500

    (FIRSTN_MP N LST)......1014 / 2.22 <fastest>
    (FIRSTN_LM N LST)......1701 / 1.32
    (FIRSTN_STD N LST).....2231 / 1.01
    (FIRSTN_ALE N LST).....2247 / 1.00 <slowest>

List length = 1000, n = 660

    (FIRSTN_MP N LST)......1981 / 2.95 <fastest>
    (FIRSTN_ALE N LST).....2044 / 2.86
    (FIRSTN_LM N LST)......2824 / 2.07
    (FIRSTN_STD N LST).....5850 / 1.00 <slowest>

List length = 1000, n = 900

    (FIRSTN_ALE N LST).....1669 / 4.72 <fastest>
    (FIRSTN_LM N LST)......1856 / 4.24
    (FIRSTN_MP N LST)......1872 / 4.21
    (FIRSTN_STD N LST).....7878 / 1.00 <slowest>

List length = 10000, n = 1000

    (FIRSTN_LM N LST)......1154 / 5.12 <fastest>
    (FIRSTN_STD N LST).....1155 / 5.12
    (FIRSTN_MP N LST)......1170 / 5.05
    (FIRSTN_ALE N LST).....5912 / 1.00 <slowest>

List length = 10000, n = 3300

    (FIRSTN_MP N LST)......1155 / 2.31 <fastest>
    (FIRSTN_STD N LST).....1825 / 1.46
    (FIRSTN_LM N LST)......1826 / 1.46
    (FIRSTN_ALE N LST).....2668 / 1.00 <slowest>

List length = 10000, n = 5000

    (FIRSTN_MP N LST)......1139 / 2.40 <fastest>
    (FIRSTN_LM N LST)......2153 / 1.27
    (FIRSTN_ALE N LST).....2371 / 1.15
    (FIRSTN_STD N LST).....2730 / 1.00 <slowest>

List length = 10000, n = 6600

    (FIRSTN_MP N LST)......1108 / 3.30 <fastest>
    (FIRSTN_LM N LST)......1732 / 2.11
    (FIRSTN_ALE N LST).....1981 / 1.84
    (FIRSTN_STD N LST).....3651 / 1.00 <slowest>

List length = 10000, n = 9000

    (FIRSTN_MP N LST)......1061 / 4.69 <fastest>
    (FIRSTN_LM N LST)......1170 / 4.25
    (FIRSTN_ALE N LST).....1295 / 3.84
    (FIRSTN_STD N LST).....4976 / 1.00 <slowest>

[Lee Mac]

@Marc, great idea to use member to skip large sections of the list! 


@MP, nicely coded - I've seen that method being used quite a lot recently - on the same theme, this may offer some marginal performance enhancements:

Code - Auto/Visual Lisp: [Select]

1. (defun firstn_LM2 ( n l / r )
2.     (if (< n (/ (length l) 2))
3.         (progn
4.             (repeat (/ n 4)
5.                 (setq r (vl-list* (cadddr l) (caddr l) (cadr l) (car l) r)
6.                       l (cddddr l)
7.                 )
8.             )
9.             (repeat (rem n 4)
10.                 (setq r (cons (car l) r)
11.                       l (cdr l)
12.                 )
13.             )
14.             (reverse r)
15.         )
16.         (progn
17.             (setq n (- (length l) n)
18.                   l (reverse l)
19.             )
20.             (repeat (/ n 4)
21.                 (setq l (cddddr l))
22.             )
23.             (repeat (rem n 4)
24.                 (setq l (cdr l))
25.             )
26.             (reverse l)
27.         )
28.     )
29. )

[Marc'Antonio Alessi]

LM>>> this may offer some marginal performance enhancements:

Yes...

Code: [Select]

(setq Alist2 (atoms-family 1))
(length Alist2) 3983


    (FIRSTN_LM2 10 ALIST2).................1373 / 1.48 <fastest>
    (ALE_LIST_REVERSEMEMBER 10 ALIST2).....2028 / 1 <slowest>

    (FIRSTN_LM2 1000 ALIST2).................1529 / 1.86 <fastest>
    (ALE_LIST_REVERSEMEMBER 1000 ALIST2).....2839 / 1 <slowest>

    (FIRSTN_LM2 2000 ALIST2).................1263 / 1.1 <fastest>
    (ALE_LIST_REVERSEMEMBER 2000 ALIST2).....1389 / 1 <slowest>

    (ALE_LIST_REVERSEMEMBER 3000 ALIST2).....1341 / 1.11 <fastest>
    (FIRSTN_LM2 3000 ALIST2).................1482 / 1 <slowest>

    (ALE_LIST_REVERSEMEMBER 3980 ALIST2).....1341 / 1.01 <fastest>
    (FIRSTN_LM2 3980 ALIST2).................1357 / 1 <slowest>


[MP]

Cool thread guys; interesting results --

Code: [Select]

(defun FirstN_MP2 ( n lst )
    (reverse
        (   (lambda ( lst n f ) (f n 1 (f n 4 lst cddddr) cdr))
            (reverse lst)
            (min n (length lst))
            (lambda ( n i lst f )
                (repeat (/ (- (length lst) n) i)
                    (setq lst (f lst))
                )
                lst
            )
        )
    )
)
List length = 100, n = 10

    (FIRSTN_LM2 N LST).....1326 / 1.34 <fastest>
    (FIRSTN_ALE N LST).....1435 / 1.24
    (FIRSTN_MP2 N LST).....1779 / 1.00 <slowest>

List length = 100, n = 25

    (FIRSTN_LM2 N LST).....1560 / 1.22 <fastest>
    (FIRSTN_MP2 N LST).....1731 / 1.10
    (FIRSTN_ALE N LST).....1903 / 1.00 <slowest>

List length = 100, n = 40

    (FIRSTN_MP2 N LST).....1622 / 1.44 <fastest>
    (FIRSTN_LM2 N LST).....1794 / 1.30
    (FIRSTN_ALE N LST).....2340 / 1.00 <slowest>

List length = 100, n = 50

    (FIRSTN_LM2 N LST).....1544 / 1.72 <fastest>
    (FIRSTN_MP2 N LST).....1607 / 1.65
    (FIRSTN_ALE N LST).....2652 / 1.00 <slowest>

List length = 100, n = 75

    (FIRSTN_LM2 N LST).....1436 / 2.40 <fastest>
    (FIRSTN_MP2 N LST).....1482 / 2.33
    (FIRSTN_ALE N LST).....3447 / 1.00 <slowest>

List length = 100, n = 90

    (FIRSTN_LM2 N LST).....1389 / 2.77 <fastest>
    (FIRSTN_MP2 N LST).....1466 / 2.63
    (FIRSTN_ALE N LST).....3853 / 1.00 <slowest>

List length = 1000, n = 100

    (FIRSTN_LM2 N LST).....1420 / 2.72 <fastest>
    (FIRSTN_ALE N LST).....2152 / 1.80
    (FIRSTN_MP2 N LST).....3869 / 1.00 <slowest>

List length = 1000, n = 250

    (FIRSTN_LM2 N LST).....1358 / 1.69 <fastest>
    (FIRSTN_MP2 N LST).....1857 / 1.23
    (FIRSTN_ALE N LST).....2293 / 1.00 <slowest>

List length = 1000, n = 400

    (FIRSTN_MP2 N LST).....1748 / 2.03 <fastest>
    (FIRSTN_LM2 N LST).....2028 / 1.75
    (FIRSTN_ALE N LST).....3541 / 1.00 <slowest>

List length = 1000, n = 500

    (FIRSTN_LM2 N LST).....1622 / 2.75 <fastest>
    (FIRSTN_MP2 N LST).....1670 / 2.67
    (FIRSTN_ALE N LST).....4462 / 1.00 <slowest>

List length = 1000, n = 750

    (FIRSTN_LM2 N LST).....1482 / 1.16 <fastest>
    (FIRSTN_MP2 N LST).....1513 / 1.13
    (FIRSTN_ALE N LST).....1716 / 1.00 <slowest>

List length = 1000, n = 900

    (FIRSTN_LM2 N LST).....1357 / 1.11 <fastest>
    (FIRSTN_MP2 N LST).....1419 / 1.07
    (FIRSTN_ALE N LST).....1513 / 1.00 <slowest>

List length = 10000, n = 1000

    (FIRSTN_LM2 N LST)......1326 / 8.60 <fastest>
    (FIRSTN_MP2 N LST)......4446 / 2.57
    (FIRSTN_ALE N LST).....11404 / 1.00 <slowest>

List length = 10000, n = 2500

    (FIRSTN_LM2 N LST).....1529 / 3.50 <fastest>
    (FIRSTN_MP2 N LST).....2152 / 2.49
    (FIRSTN_ALE N LST).....5351 / 1.00 <slowest>

List length = 10000, n = 4000

    (FIRSTN_MP2 N LST).....2013 / 2.41 <fastest>
    (FIRSTN_LM2 N LST).....2402 / 2.02
    (FIRSTN_ALE N LST).....4852 / 1.00 <slowest>

List length = 10000, n = 5000

    (FIRSTN_LM2 N LST).....1918 / 2.32 <fastest>
    (FIRSTN_MP2 N LST).....1997 / 2.23
    (FIRSTN_ALE N LST).....4446 / 1.00 <slowest>

List length = 10000, n = 7500

    (FIRSTN_LM2 N LST).....1732 / 1.84 <fastest>
    (FIRSTN_MP2 N LST).....1778 / 1.79
    (FIRSTN_ALE N LST).....3183 / 1.00 <slowest>

List length = 10000, n = 9000

    (FIRSTN_LM2 N LST).....1622 / 1.38 <fastest>
    (FIRSTN_MP2 N LST).....1654 / 1.36
    (FIRSTN_ALE N LST).....2246 / 1.00 <slowest>

[Lee Mac]

Code: [Select]

(defun FirstN_MP2 ( n lst )
    ...
)

Very elegantly coded Michael 
Its a shame that the code processing the front of the list can't be implemented quite as cleanly...

Cool thread guys; interesting results --

Interesting indeed - thank you for running the benchmarks!

The results for 40% would confirm that it is slightly more efficient to remove items from the tail-end of the list than to construct a new list, which leads me to think that my function would probably perform better if (< n (/ (length l) 2)) was instead changed to (< n (/ (length l) 3))

[Kerry]

Would have been nice if lisp had list slicing and stepping similar to Python.
This lack in functionality has always sort of surprised me considering lisps list based structure.

Code - Python: [Select]

1. seq = L[start:stop:step]

[gile]

Would have been nice if lisp had list slicing and stepping similar to Python.
This lack in functionality has always sort of surprised me considering lisps list based structure.

Code - Python: [Select]

1. seq = L[start:stop:step]

It seems to me the main lack of AutoLISP is that the only data structure it uses is the linked list which is cheap to access from the left end (car) but inefficient for random access lookup because it must be traversed from the left at each lookup.

I don't know much about Python, but there's something similar in F# for slicing arrays (which works with array data structures only):

Code - F#: [Select]

1. let arr = [| "0"; "1"; "2"; "3"; "4"; "5"; "6"; "7"; "8"; "9" |]
2. arr.[3 .. 7]  // -> [| "3"; "4"; "5"; "6"; "7" |]
3. arr.[.. 4] // -> [| "0"; "1"; "2"; "3"; "4" |]
4. arr.[7 ..] // -> [| "7"; "8"; "9" |]

[Kerry]

yes gile, that's the sort of thing.

for lists JavaScript has

Code - Javascript: [Select]

1. var newList = list.slice(begin, end);

and I've seen several slice implementations in C# , usually implementing Linq or the Enumerable.Skip and Enumerable.Take extension methods.

I really should resurrect my F# books.

[gile]

Yes, the thing I wanted to point is the lack of other data structure than linked list in AutoLISP. With JavaScript, the slice method works on arrays too.

[Kerry]

Yes, I understand.

[divtiply]

Would have been nice if lisp had list slicing and stepping similar to Python.

The lisp way is:

Code: [Select]

(defun sublist (lst start len)
    (firstn len (nthcdr start lst)))


Yes, the thing I wanted to point is the lack of other data structure than linked list in AutoLISP.

There are safearray and sometimes string also.

[ribarm]

Would have been nice if lisp had list slicing and stepping similar to Python.

Another lisp way (with elements):

Code: [Select]

(defun sublist ( lst stel enel )
  (reverse (member enel (reverse (member stel lst))))
)

With numbers:

Code: [Select]

(defun sublist ( lst st en )
  (reverse (member (nth (- en 1) lst) (reverse (member (nth (- st 1) lst) lst))))
)

Of course, list must be constituted of all different elements, otherwise result is incorrect

Correct version, but more robust - not elegant like Python

Code: [Select]

(defun sublist ( lst st en / n )
  (setq n (length lst))
  (repeat (- st 1)
    (setq lst (cdr lst))
  )
  (setq lst (reverse lst))
  (repeat (- n en)
    (setq lst (cdr lst))
  )
  (reverse lst)
)


[Marc'Antonio Alessi]

Just for fun... other demential approaches...

Code: [Select]

(defun ALE_List_MapcarToLength (LstLen In_Lst / Countr OutLst)
  (setq Countr 1)
  (vl-catch-all-apply
    'mapcar
    (list
     '(lambda (x)
        (if (> Countr LstLen)
          (exit)
          (setq OutLst (cons x OutLst) Countr (1+ Countr))
        )
      )
      In_Lst
    )
  )
  (reverse OutLst)
)
; perhaps problems for excess length of string...
(defun ALE_List_CdrToLength2 (n l / s p)
  (setq n (- (length l) n)  s "" c 0  p "")
  (repeat (/   n 4) (setq s (strcat "(cddddr " s)  c (1+ c)))
  (repeat (rem n 4) (setq s (strcat "(cdr "    s)  c (1+ c)))
  (repeat (1+ c)    (setq p (strcat ")" p)))
  (eval (read (strcat "(reverse " s "(reverse l)" p)))
)
;--------
(defun ALE_List_Cd100r (l)
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr l)))))))))))))))))))))))))
)
;
(defun ALE_List_CdrToLength (n l / s p c)
  (setq l (reverse l)  n (- (length l) n)  s ""  c 0  p "")
  (repeat (/ n 100) (setq l (ALE_List_Cd100r l)))
  (repeat (rem n 100) (setq s (strcat "(cdr " s)  c (1+ c)))
  (repeat (1+ c) (setq p (strcat ")" p)))
  (eval (read (strcat "(reverse " s " l" p)))
)

[Marc'Antonio Alessi]

under certain conditions can be interesting ...

Code: [Select]

(setq aList2 '(1 2 3 4 5 6 7 8 9 0 11))
(repeat 20 (setq aList2 (append aList2 aList2)))
Comando: (length Alist2)
11534336

(ALE_LIST_CDRTOLENGTH 5767100 ALIST2).....2871 / 1.73 <fastest>
(FIRSTN_MP2 5767100 ALIST2)...............3120 / 1.59
(FIRSTN_LM2 5767100 ALIST2)...............4961 / 1 <slowest>


[Lee Mac]

Interesting approach Marc 

This may be slightly more efficient:

Code: [Select]

(defun ale_list_cdrtolength2 ( n l / s p )
    (setq l  (reverse l)
          n  (- (length l) n)
          s '(" l)")
    )
    (repeat (/   n 100) (setq l (ale_list_cd100r l)))
    (repeat (rem n 100) (setq s (cons "(cdr" s) p (cons ")" p)))
    (eval (read (apply 'strcat (cons "(reverse " (append s p)))))
)

[Marc'Antonio Alessi]

Interesting approach Marc 
...

Thanks Lee, yes:
    (ALE_LIST_REVERSECDRBYLENGTH 180200 ...).....1279 / 1.51 <fastest>
    (ALE_LIST_REVERSECDRBYLENGTH1 180200...).....1935 / 1 <slowest>

Perhaps it might be an idea for sublist functions... (I changed the name because it was not coherent):

Code: [Select]

(defun ALE_List_CdrByLength ( n l / s p )
  (setq n  (- (length l) n)
        s '(" l")
  )
  (repeat (/   n 100) (setq l (ale_list_cd100r l)))
  (repeat (rem n 100) (setq s (cons "(cdr" s) p (cons ")" p)))
  (eval (read (apply 'strcat (append s p))))
)
(defun ALE_List_ReverseCdrByLength ( n l / s p )
  (setq l  (reverse l)
        n  (- (length l) n)
        s '(" l)")
  )
  (repeat (/   n 100) (setq l (ale_list_cd100r l)))
  (repeat (rem n 100) (setq s (cons "(cdr" s) p (cons ")" p)))
  (eval (read (apply 'strcat (cons "(reverse " (append s p)))))
)
(defun ALE_List_Sub (l i n)
  (ALE_List_CdrByLength i (ALE_List_ReverseCdrByLength (+ i n) l))
)

[Marc'Antonio Alessi]

On very long list:

Code: [Select]

(setq aList '(1 2 3 4 5 6 7 8 9 0 11))(repeat 18 (setq aList (append aList aList)))
(length Alist) > 2883584

(defun ALE_List_Cd1000r (l)
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr l))))))))))))
  )))))))))))))))))))))))))))))))))))))))))))))))))
  )))))))))))))))))))))))))))))))))))))))))))))))))
  )))))))))))))))))))))))))))))))))))))))))))))))))
  )))))))))))))))))))))))))))))))))))))))))))))))))
  ))))))))))))))))))))))))))))))))))))))))))
)
(defun ALE_List_CdrByLength ( n l / s p )
  (setq n  (- (length l) n)
        s '(" l")
  )
  (repeat (/  n 1000)                    (setq l (ALE_List_Cd1000r l)))
  (repeat (/ (setq n (rem  n 1000)) 100) (setq l (ALE_List_Cd100r  l)))
  (eval (read (apply 'strcat (append s p))))
)
(defun ALE_List_ReverseCdrByLength ( n l / s p )
  (setq l  (reverse l)
        n  (- (length l) n)
        s '(" l)")
  )
  (repeat (/  n 1000)                    (setq l (ALE_List_Cd1000r l)))
  (repeat (/ (setq n (rem  n 1000)) 100) (setq l (ALE_List_Cd100r  l)))
  (repeat (rem n 100) (setq s (cons "(cdr" s) p (cons ")" p)))
  (eval (read (apply 'strcat (cons "(reverse " (append s p)))))
)


Code: [Select]

(ALE_LIST_REVERSECDRBYLENGTH 1441700...).....1311 / 1.9 <fastest>
(FIRSTN_MP2 1441700 ALIST)...................1810 / 1.38
(FIRSTN_LM2 1441700 ALIST)...................2496 / 1 <slowest>

[Marc'Antonio Alessi]

These are pretty good also in short lists:

Code: [Select]

(defun ALE_List_CdrByLen (n l)
  (setq n (- (length l) n))
  (repeat (/  n 1000)                   (setq l (Cd1000r l)))
  (repeat (/ (setq n (rem n 1000)) 100) (setq l (Cd100r  l)))
  (repeat (/ (setq n (rem n  100))  10) (setq l (Cd10r   l)))
  (repeat (/ (setq n (rem n   10))   4) (setq l (cddddr  l)))
  (repeat (rem n 4)                     (setq l (cdr     l)))
  l
)
(defun ALE_List_RevCdrByLen (n l)
  (setq l  (reverse l) n  (- (length l) n))
  (repeat (/  n 1000)                   (setq l (Cd1000r l)))
  (repeat (/ (setq n (rem n 1000)) 100) (setq l (Cd100r  l)))
  (repeat (/ (setq n (rem n  100))  10) (setq l (Cd10r   l)))
  (repeat (/ (setq n (rem n   10))   4) (setq l (cddddr  l)))
  (repeat (rem n 4)                     (setq l (cdr     l)))
  (reverse l)
)
(defun Cd10r (l)
  (cddddr(cddddr(cddr l)))
)
(defun Cd100r (l)
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr l)))))))))))))))))))))))))
)
(defun Cd1000r (l)
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr(cddddr(cddddr
  (cddddr(cddddr(cddddr(cddddr(cddddr l))))))))))))
  )))))))))))))))))))))))))))))))))))))))))))))))))
  )))))))))))))))))))))))))))))))))))))))))))))))))
  )))))))))))))))))))))))))))))))))))))))))))))))))
  )))))))))))))))))))))))))))))))))))))))))))))))))
  ))))))))))))))))))))))))))))))))))))))))))
)
(defun ALE_List_Sub (l i n)
  (ALE_List_CdrByLen i (ALE_List_RevCdrByLen (+ i n) l))
)

Code: [Select]

(setq Alist (atoms-family 1))
(length aList) > 4005

Elapsed milliseconds / relative speed for 4096 iteration(s):
    (FIRSTN_LM2 3800 ALIST)...............2043 / 1.5 <fastest>
    (FIRSTN_MP2 3800 ALIST)...............2996 / 1.02
    (ALE_LIST_REVCDRBYLEN 3800 ALIST).....3058 / 1 <slowest>

Elapsed milliseconds / relative speed for 2048 iteration(s):
    (ALE_LIST_REVCDRBYLEN 3000 ALIST).....1840 / 1.48 <fastest>
    (FIRSTN_LM2 3000 ALIST)...............2652 / 1.02
    (FIRSTN_MP2 3000 ALIST)...............2714 / 1 <slowest>

Elapsed milliseconds / relative speed for 2048 iteration(s):
    (ALE_LIST_REVCDRBYLEN 2000 ALIST).....1950 / 1.75 <fastest>
    (FIRSTN_MP2 2000 ALIST)...............2387 / 1.43
    (FIRSTN_LM2 2000 ALIST)...............3417 / 1 <slowest>

Elapsed milliseconds / relative speed for 4096 iteration(s):
    (ALE_LIST_REVCDRBYLEN 1000 ALIST).....1638 / 1.76 <fastest>
    (FIRSTN_LM2 1000 ALIST)...............2074 / 1.39
    (FIRSTN_MP2 1000 ALIST)...............2886 / 1 <slowest>

Elapsed milliseconds / relative speed for 32768 iteration(s):
    (FIRSTN_LM2 10 ALIST)................3245 / 10.88 <fastest>
    (ALE_LIST_REVCDRBYLEN 10 ALIST).....13182 / 2.68
    (FIRSTN_MP2 10 ALIST)...............35319 / 1 <slowest>

[Marc'Antonio Alessi]

Code: [Select]

;20140107 - Mixed version for short lists
(defun ALE_List_RevCdrByLen (n l / r)
  (cond
    ( (> n 1000)
      (setq l  (reverse l) n  (- (length l) n))
      (repeat (/       n              1000) (setq l (Cd1000r l)))
      (repeat (/ (setq n (rem n 1000)) 100) (setq l (Cd100r  l)))
      (repeat (/ (setq n (rem n  100))  10) (setq l (Cd10r   l)))
      (repeat (/ (setq n (rem n   10))   4) (setq l (cddddr  l)))
      (repeat (rem n 4)                     (setq l (cdr     l)))
      (reverse l)
    )   
    ( T
      (repeat (/ n 10)
        (setq
          r
          (vl-list*
            (cadddr (cddddr (cddr l))) (cadddr (cddddr (cdr l)))
            (cadddr (cddddr l)) (cadddr (cdddr l)) (cadddr (cddr l))
            (cadddr (cdr l)) (cadddr l) (caddr l) (cadr l) (car l) r
          )
          l (cddddr (cddddr (cddr l)))
        )
      )
      (repeat (rem n 10) (setq r (cons (car l) r) l (cdr l) ))
      (reverse r)
    )
  )
)

[MP]

Would have been nice if lisp had list slicing and stepping similar to Python.

I had need to do this very thing this week (to sample values within a list), ergo:

Code: [Select]

(defun _Slice ( n1 n2 lst / prune normal a b n )

    ;;  Normal result order:
    ;;  (_Slice 2 5 '(0 1 2 3 4 5 6 7 8 9))
    ;;      >> (2 3 4 5)
    ;;
    ;;  Reversed result order:
    ;;  (_Slice 5 2 '(0 1 2 3 4 5 6 7 8 9))
    ;;      >> (5 4 3 2)
    ;;
    ;;  Boundary safe:
    ;;  (_Slice -5 100 '(0 1 2 3 4 5 6 7 8 9))
    ;;      >> (0 1 2 3 4 5 6 7 8 9)

    (defun prune ( n lst )
        (repeat (/ n 4) (setq lst (cddddr lst)))
        (repeat (rem n 4) (setq lst (cdr lst)))
        lst
    )
   
    (setq
        a (max 0 (if (setq normal (< n1 n2)) n1 n2))
        b (min (1- (length lst)) (if normal n2 n1))
        n (1- (- (length lst) b))   
    )
   
    (if normal
        (reverse (prune n (reverse (prune a lst))))
        (prune n (reverse (prune a lst)))
    )
)
If one is taking relatively small slices the conventional approach:

Code: [Select]

(defun _Slice ( n1 n2 lst / a b normal result )

    (setq
        a (max 0 (if (setq normal (< n1 n2)) n1 n2))
        b (min (1- (length lst)) (if normal n2 n1))
    )

    (repeat (- b (setq a (1- a)))
        (setq result
            (cons
                (nth (setq a (1+ a)) lst)
                result
            )
        )
    )
   
    (if normal
        (reverse result)
        result
    )       

)
Executes faster, but as a general, all purpose slicer I found the first one performs quite well.

Cheers.

[Lee Mac]

Good stuff MP 

The only change I'd be inclined to make to your excellent code is changing:

Code: [Select]

(setq
    a (max 0 (if (setq normal (< n1 n2)) n1 n2))
    b (min (1- (length lst)) (if normal n2 n1))
    n (1- (- (length lst) b))   
)

(if normalTo:

Code: [Select]

(setq
    a (max 0 (min n1 n2))
    b (min (length lst) (1+ (max n1 n2)))
    n (- (length lst) b)
)

(if (< n1 n2)
    ...Or, more compactly:

Code: [Select]

(setq
    a (max 0 (min n1 n2))
    n (- (length lst) (min (length lst) (1+ (max n1 n2))))
)

(if (< n1 n2)
    ...

[Marc'Antonio Alessi]

...needs to be optimized, but it can stand comparison.

Code: [Select]

(defun ALE_List_Slice (i n l)
  (ALE_List_CdrByLen (1+ (- n i)) (ALE_List_RevCdrByLen (1+ n) l))
)
(defun ALE_List_CdrByLen (n l / r g)
  (setq g (- (length l) n))
  (cond
    ( (> g 1000)
      (repeat (/       g              1000) (setq l (Cd1000r l)))
      (repeat (/ (setq g (rem g 1000)) 100) (setq l (Cd100r  l)))
      (repeat (/ (setq g (rem g  100))  10) (setq l (Cd10r   l)))
      (repeat (/ (setq g (rem g   10))   4) (setq l (cddddr  l)))
      (repeat (rem g 4)                     (setq l (cdr     l)))
       l
    )   
    ( T
      (setq l  (reverse l))
      (repeat (/ n 10)
        (setq
          r
          (vl-list*
            (cadddr (cddddr (cddr l))) (cadddr (cddddr (cdr l)))
            (cadddr (cddddr l)) (cadddr (cdddr l)) (cadddr (cddr l))
            (cadddr (cdr l)) (cadddr l) (caddr l) (cadr l) (car l) r
          )
          l (cddddr (cddddr (cddr l)))
        )
      )
      (repeat (rem n 10) (setq r (cons (car l) r) l (cdr l) ))
      r
    )
  )
)


Code: [Select]

Benchmark.lsp | © 2005 Michael Puckett | All Rights Reserved
List > '(0 1 2 3 4 5 6 7 8 9)
Elapsed milliseconds / relative speed for 32768 iteration(s):
    (_SLICE 2 6 (QUOTE (0 1 2 3 4 5 6 7 ...).....1248 / 1.06 <fastest>
    (ALE_LIST_SLICE 2 6 (QUOTE (0 1 2 3 ...).....1326 / 1 <slowest>

> (setq Alist (atoms-family 1))
> (length aList) > 4005

Elapsed milliseconds / relative speed for 1024 iteration(s):
    (_SLICE 101 4000 ALIST).............1061 / 3.22 <fastest>
    (ALE_LIST_SLICE 101 4000 ALIST).....3417 / 1 <slowest>

Elapsed milliseconds / relative speed for 1024 iteration(s):
    (_SLICE 101 3000 ALIST).............1076 / 2.67 <fastest>
    (ALE_LIST_SLICE 101 3000 ALIST).....2870 / 1 <slowest>

Elapsed milliseconds / relative speed for 1024 iteration(s):
    (_SLICE 101 2000 ALIST).............1123 / 1.89 <fastest>
    (ALE_LIST_SLICE 101 2000 ALIST).....2121 / 1 <slowest>

Elapsed milliseconds / relative speed for 1024 iteration(s):
    (_SLICE 101 1000 ALIST).............1045 / 1.28 <fastest>
    (ALE_LIST_SLICE 101 1000 ALIST).....1342 / 1 <slowest>

Elapsed milliseconds / relative speed for 2048 iteration(s):
    (ALE_LIST_SLICE 101 800 ALIST).....1919 / 1.07 <fastest>
    (_SLICE 101 800 ALIST).............2059 / 1 <slowest>

Elapsed milliseconds / relative speed for 4096 iteration(s):
    (ALE_LIST_SLICE 101 400 ALIST).....1857 / 2.31 <fastest>
    (_SLICE 101 400 ALIST).............4290 / 1 <slowest>

Elapsed milliseconds / relative speed for 8192 iteration(s):
    (ALE_LIST_SLICE 101 200 ALIST).....1763 / 4.68 <fastest>
    (_SLICE 101 200 ALIST).............8252 / 1 <slowest>

Elapsed milliseconds / relative speed for 8192 iteration(s):
    (ALE_LIST_SLICE 10 101 ALIST).....1155 / 7.24 <fastest>
    (_SLICE 10 101 ALIST).............8362 / 1 <slowest>

Elapsed milliseconds / relative speed for 2048 iteration(s):
    (_SLICE 1010 3000 ALIST).............1935 / 1.14 <fastest>
    (ALE_LIST_SLICE 1010 3000 ALIST).....2199 / 1 <slowest>

Elapsed milliseconds / relative speed for 2048 iteration(s):
    (ALE_LIST_SLICE 1010 2000 ALIST).....1856 / 1.06 <fastest>
    (_SLICE 1010 2000 ALIST).............1966 / 1 <slowest>

Elapsed milliseconds / relative speed for 2048 iteration(s):
    (_SLICE 1000 1010 ALIST).............1825 / 1.03 <fastest>
    (ALE_LIST_SLICE 1000 1010 ALIST).....1872 / 1 <slowest>

Elapsed milliseconds / relative speed for 2048 iteration(s):
    (_SLICE 800 1010 ALIST).............1981 / 1.09 <fastest>
    (ALE_LIST_SLICE 800 1010 ALIST).....2153 / 1 <slowest>

Elapsed milliseconds / relative speed for 2048 iteration(s):
    (_SLICE 400 1010 ALIST).............1997 / 1.16 <fastest>
    (ALE_LIST_SLICE 400 1010 ALIST).....2309 / 1 <slowest>

Elapsed milliseconds / relative speed for 1024 iteration(s):
    (_SLICE 200 1010 ALIST).............1014 / 1.29 <fastest>
    (ALE_LIST_SLICE 200 1010 ALIST).....1311 / 1 <slowest>

Elapsed milliseconds / relative speed for 1024 iteration(s):
    (_SLICE 10 1010 ALIST).............1123 / 1.36 <fastest>
    (ALE_LIST_SLICE 10 1010 ALIST).....1529 / 1 <slowest>


[Marc'Antonio Alessi]

on very big lists:

Code: [Select]

(setq Alist (atoms-family 1))
(repeat 10 (setq Alist (append Alist Alist)))
(length aList) > 4100096

Elapsed milliseconds / relative speed for 2 iteration(s):
    (ALE_LIST_SLICE 101 4000 ALIST).....1217 / 1.59 <fastest>
    (_SLICE 101 4000 ALIST).............1935 / 1 <slowest>

Elapsed milliseconds / relative speed for 2 iteration(s):
    (ALE_LIST_SLICE 101 3000 ALIST).....1092 / 1.76 <fastest>
    (_SLICE 101 3000 ALIST).............1919 / 1 <slowest>

Elapsed milliseconds / relative speed for 2 iteration(s):
    (ALE_LIST_SLICE 101 2000 ALIST).....1092 / 1.76 <fastest>
    (_SLICE 101 2000 ALIST).............1919 / 1 <slowest>

Elapsed milliseconds / relative speed for 2 iteration(s):
    (ALE_LIST_SLICE 101 1000 ALIST).....1139 / 1.68 <fastest>
    (_SLICE 101 1000 ALIST).............1919 / 1 <slowest>

Elapsed milliseconds / relative speed for 128 iteration(s):
    (ALE_LIST_SLICE 101 800 ALIST).......1030 / 168.01 <fastest>
    (_SLICE 101 800 ALIST).............173052 / 1 <slowest>

Elapsed milliseconds / relative speed for 1024 iteration(s):
    (ALE_LIST_SLICE 101 400 ALIST)........1248 / 1171.02 <fastest>
    (_SLICE 101 400 ALIST).............1461433 / 1 <slowest>

Elapsed milliseconds / relative speed for 2048 iteration(s):
    (ALE_LIST_SLICE 101 200 ALIST)........1685 / 1423.59 <fastest>
    (_SLICE 101 200 ALIST).............2398750 / 1 <slowest>
Benchmarking ..............; errore: Funzione annullata