TheSwamp

Code Red => AutoLISP (Vanilla / Visual) => Topic started by: Kerry on December 22, 2013, 08:59:14 PM

Title: list of first n elements from list
Post by: Kerry on December 22, 2013, 08:59:14 PM

 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.

Title: Re: list of first n elements from list
Post by: MP on December 22, 2013, 09:09:23 PM

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).

Title: Re: list of first n elements from list
Post by: Kerry on December 22, 2013, 09:15:22 PM

Quote from: MP on December 22, 2013, 09:09:23 PM

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

yep.

Title: Re: list of first n elements from list
Post by: divtiply on December 23, 2013, 01:48:07 PM

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

Title: Re: list of first n elements from list
Post by: MP on December 23, 2013, 02:47:36 PM

Quote from: divtiply on December 23, 2013, 01:48:07 PM

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.

Title: Re: list of first n elements from list
Post by: Kerry on December 23, 2013, 04:12:32 PM

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

Title: Re: list of first n elements from list
Post by: Lee Mac on December 23, 2013, 05:24:24 PM

Quote from: MP on December 23, 2013, 02:47:36 PM

Quote from: divtiply on December 23, 2013, 01:48:07 PM

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)

Title: Re: list of first n elements from list
Post by: Kerry on December 23, 2013, 06:33:12 PM

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

Title: Re: list of first n elements from list
Post by: Lee Mac on December 23, 2013, 06:48:28 PM

Quote from: Kerry on December 23, 2013, 06:33:12 PM

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>

Title: Re: list of first n elements from list
Post by: MP on December 23, 2013, 08:05:35 PM

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.

Title: Re: list of first n elements from list
Post by: Kerry on December 23, 2013, 10:42:37 PM

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.  

Title: Re: list of first n elements from list
Post by: Lee Mac on December 24, 2013, 09:40:00 AM

Quote from: Kerry on December 23, 2013, 10:42:37 PM

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).

Quote from: Kerry on December 23, 2013, 10:42:37 PM

Thanks for the option Lee.

Quote from: MP on December 23, 2013, 08:05:35 PM

Thanks for the mod Lee.

Cheers guys  :-)

Title: Re: list of first n elements from list
Post by: Lee Mac on December 24, 2013, 11:35:40 AM

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  :-)

Title: Re: list of first n elements from list
Post by: Marc'Antonio Alessi on December 24, 2013, 04:54:51 PM

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.

Title: Re: list of first n elements from list
Post by: MP on December 24, 2013, 06:04:54 PM

[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>

Title: Re: list of first n elements from list
Post by: Lee Mac on December 24, 2013, 07:20:26 PM

@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. )

Title: Re: list of first n elements from list
Post by: Marc'Antonio Alessi on December 25, 2013, 03:24:23 PM

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>


Title: Re: list of first n elements from list
Post by: MP on December 25, 2013, 05:45:40 PM

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>

Title: Re: list of first n elements from list
Post by: Lee Mac on December 25, 2013, 08:45:20 PM

Quote from: MP on December 25, 2013, 05:45:40 PM

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...

Quote from: MP on December 25, 2013, 05:45:40 PM

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))

Title: Re: list of first n elements from list
Post by: Kerry on December 25, 2013, 10:11:45 PM

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]

Title: Re: list of first n elements from list
Post by: gile on December 26, 2013, 05:12:05 AM

Quote from: Kerry on December 25, 2013, 10:11:45 PM

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" |]

Title: Re: list of first n elements from list
Post by: Kerry on December 26, 2013, 05:47:53 AM

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.

Title: Re: list of first n elements from list
Post by: gile on December 26, 2013, 06:11:28 AM

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.

Title: Re: list of first n elements from list
Post by: Kerry on December 26, 2013, 06:19:49 AM

Yes, I understand.

Title: Re: list of first n elements from list
Post by: divtiply on December 26, 2013, 01:32:10 PM

Quote from: Kerry on December 25, 2013, 10:11:45 PM

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)))


Quote from: gile on December 26, 2013, 06:11:28 AM

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.

Title: Re: list of first n elements from list
Post by: ribarm on December 26, 2013, 02:32:57 PM

Quote from: Kerry on December 25, 2013, 10:11:45 PM

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)
)


Title: Re: list of first n elements from list
Post by: Marc'Antonio Alessi on January 03, 2014, 01:37:52 PM

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)))
)

Title: Re: list of first n elements from list
Post by: Marc'Antonio Alessi on January 04, 2014, 10:12:13 AM

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>


Title: Re: list of first n elements from list
Post by: Lee Mac on January 04, 2014, 12:06:31 PM

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)))))
)

Title: Re: list of first n elements from list
Post by: Marc'Antonio Alessi on January 04, 2014, 12:50:47 PM

Quote from: Lee Mac on January 04, 2014, 12:06:31 PM

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))
)

Title: Re: list of first n elements from list
Post by: Marc'Antonio Alessi on January 05, 2014, 05:17:07 AM

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>

Title: Re: list of first n elements from list
Post by: Marc'Antonio Alessi on January 05, 2014, 08:59:28 AM

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>

Title: Re: list of first n elements from list
Post by: Marc'Antonio Alessi on January 07, 2014, 04:33:03 AM

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)
    )
  )
)

Title: Re: list of first n elements from list
Post by: MP on January 17, 2014, 10:25:52 AM

Quote from: Kerry on December 25, 2013, 10:11:45 PM

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.

Title: Re: list of first n elements from list
Post by: Lee Mac on January 18, 2014, 02:04:58 PM

Good stuff MP  8-)

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)
    ...

Title: Re: list of first n elements from list
Post by: Marc'Antonio Alessi on January 19, 2014, 05:42:51 AM

...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>


Title: Re: list of first n elements from list
Post by: Marc'Antonio Alessi on January 19, 2014, 11:33:35 AM

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