Topic: list of first n elements from list

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