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>