Topic: Split big list...

[ribarm]

Here are the results on my PC...

Code - Auto/Visual Lisp: [Select]

1. (defun c:test ( / extremum l t0 t1 )
2.  
3.   (defun extremum ( cmp lst / rtn )
4.      (setq rtn (car lst))
5.      (foreach itm (cdr lst)
6.          (if (apply cmp (list itm rtn)) (setq rtn itm))
7.      )
8.      rtn
9.   )
10.    
11.   (setq l (atoms-family 1))
12.   (setq t0 (car (_vl-times)))
13.   (repeat 10
14.     (extremum '(lambda ( a b ) (<= (strlen a) (strlen b))) l)
15.   )
16.   (setq t1 (car (_vl-times)))
17.   (prompt "\nElapsed time for (extremum) : ") (princ (rtos (- t1 t0) 2 20)) (prompt " milliseconds...")
18.   (setq t0 (car (_vl-times)))
19.   (repeat 10
20.     (car (vl-sort l '(lambda ( a b ) (<= (strlen a) (strlen b)))))
21.   )
22.   (setq t1 (car (_vl-times)))
23.   (prompt "\nElapsed time for (car (vl-sort)) : ") (princ (rtos (- t1 t0) 2 20)) (prompt " milliseconds...")
24.   (princ)
25. )
26.  
27. ;|
28. Command: TEST
29. Elapsed time for (extremum) : 5265.000000000000 milliseconds...
30. Elapsed time for (car (vl-sort)) : 1391.000000000000 milliseconds...
31. |;
32.  

So (car (vl-sort)) is still unbeatable...

[Marc'Antonio Alessi]

I didn't understand your problem well, but maybe this can help you:

Code: [Select]

(defun vl-sortT (lst func)
   (mapcar
     '(lambda (x) (nth x lst))
      (vl-sort-i lst func)
   )
)


Code: [Select]

;-----------------------------------------------------------------------------------

(vl-sort '((3) (2) (1) (3) (1) (2) (2) (2)) '(lambda (E1 E2) (< (car E1) (car E2))))
=> ((1) (1) (2) (2) (2) (2) (3) (3))

(vl-sortT '((3) (2) (1) (3) (1) (2) (2) (2)) '(lambda (E1 E2) (< (car E1) (car E2))))
=> ((1) (1) (2) (2) (2) (2) (3) (3))

;-----------------------------------------------------------------------------------

(vl-sort '(3 2 1 3 1 2 2 2) '<)
=> (1 2 3)                           <<<<<<<<<<<<<<

(vl-sortT '(3 2 1 3 1 2 2 2) '<)
=> (1 1 2 2 2 2 3 3)                           <<<<<<<<<<<<<<

;-----------------------------------------------------------------------------------

(vl-sort  '(3 2 1 3 1 2 2 2 1.0 1.0 1.0 1.0) '<)
=> (1 1.0 1.0 1.0 1.0 2 3)                           <<<<<<<<<<<<<<

(vl-sortT  '(3 2 1 3 1 2 2 2 1.0 1.0 1.0 1.0) '<)
=> (1.0 1.0 1.0 1.0 1 1 2 2 2 2 3 3)                           <<<<<<<<<<<<<<

;-----------------------------------------------------------------------------------

(vl-sort  '("a" "A" "a") '<)
=> ("A" "a" "a")

(vl-sortT  '("a" "A" "a") '<)
=> ("A" "a" "a")

;-----------------------------------------------------------------------------------

(vl-sort  '("a" "A" "a" "A") '<)
=> ("A" "A" "a" "a")

(vl-sortT  '("a" "A" "a" "A") '<)
=> ("A" "A" "a" "a")

;-----------------------------------------------------------------------------------

[JohnK]

TEST: Can anyone see my posts?

[gile]

The goal : You need to split big list into 2 or more smaller lists, but without using iteration and recursion - in the fastest way possible...

As LISP list are linked lists (i.e. recursive data structure) you can only acces them from the left in a recursive (or iterative) way. All built-in functions (cdr, nth, member, ...) internally recurse (or iterate) from the left to the right of the list.

[hmspe]

TEST: Can anyone see my posts?

Yes.

[JohnK]

TEST: Can anyone see my posts?

Yes.

Thank you. I was starting to worry. 

[ribarm]

The goal : You need to split big list into 2 or more smaller lists, but without using iteration and recursion - in the fastest way possible...

As LISP list are linked lists (i.e. recursive data structure) you can only acces them from the left in a recursive (or iterative) way. All built-in functions (cdr, nth, member, ...) internally recurse (or iterate) from the left to the right of the list.

Gilles, can you explain then why single iteration through whole list is slower in Lee's sub than (vl-sort) which by my opinion is sorting all elements unnecessary if we need only single extremum... If (vl-sort) is also iterating, then why this iteration is faster then normal foreach with testing only 2 items for comparison in each step of foreach...

[gile]

The goal : You need to split big list into 2 or more smaller lists, but without using iteration and recursion - in the fastest way possible...

As LISP list are linked lists (i.e. recursive data structure) you can only acces them from the left in a recursive (or iterative) way. All built-in functions (cdr, nth, member, ...) internally recurse (or iterate) from the left to the right of the list.

Gilles, can you explain then why single iteration through whole list is slower in Lee's sub than (vl-sort) which by my opinion is sorting all elements unnecessary if we need only single extremum... If (vl-sort) is also iterating, then why this iteration is faster then normal foreach with testing only 2 items for comparison in each step of foreach...

I do not know exactly how built-in functions are implemented, but I guess vl-sort is a C implementation of quick sort which is much more faster than any LISP implementation. Anyway, you certainly know that to sort a list (or any other collection) you have to iterate at least one time the collection.

What I wanted to say was: to split a singly linked list of n items into 2 lists of n/2 items, there's no other way than recurse or iterate the (n/2) first items. This is exactly what does (cdr (cdr (cdr ...))).

[JohnK]

Could be any number of reasons why. It's far more complicated then just comparing speeds of functions. In C/C++ you pass byref or byval (pointers or not pointers) and/or any number of different methods used. For example: prefix-increment is faster then post-increment  (++i is better then i++) because post-increment makes a copy of the element (which is slower). Meaning, foreach is almost guaranteed to be just a simple for loop in the source code (making a new list and passing that back) and the developer could have used post-increment instead of pre-increment (to give a dumb multi-pronged example).
for (i=0; i<list; i++) { ...

Where as vl-sort is most probably using QuickSort (like gile suggests) or some other sorting method but is passing byref instead of making a new list in memory.

[ribarm]

Thanks, although I don't quite understand why LISP in overall is so programmed that it's way too slower than other languages... It looks to me that with such lacks of speed in comparison with other faster languages it's pretty dumb job to do anything useful in LISP - it finally looks well programmed, but in fact it's toy for loosing time...
To me this : http://www.theswamp.org/index.php?topic=30434.msg600027#msg600027
looks like total waste of time and has no purposes at all... Only bright light in it is actual usage of (vl-sort) on several places... And because of that now I don't believe it's useful to convert it to faster language at all (probably the gain in speed would be so low that it would be even bigger waste of time if someone would actually do it)... So it's just pretty language with not much overall purpose in terms of doing things efficiently the fastest way possible... IMHO (foreach) function should be the fastest way of performing tasks like iterations - why copying list in each step into memory - this should be comparable with iterations used in C/C++ API... I just can't still understand why things are implemented such badly... About recursion I don't even want to speak...

[gile]

From what I experienced, the same AutoCAD routine works about 2 to 10 times faster if written in C# (.NET) instead of LISP, but writing and and debugging this routine taked about 2 to 10 more times with .NET...

[JohnK]

Auto/Visual lisp is an interpreted language--in other words, it needs something to convert the language to instructions before they are run. C, C++, C# are compiled languages; compiled languages get converted to machine instructions (for your actual computer).

Converting an interpreted language to a low level language can happen (algorithm maybe) but not the actual operation because things just aren't done the same. For example, in C (the lowest of the C based languages) you don't have strings; you have char arrays. And you cannot just create a variable like you do in AutoLisp.

Lisp
(setq MyVariable "some text")
C
char MyVariable[10];
MyVariable = "some text";

But the variable is only 10 items big meaning you cant just add to it like you can in AutoLisp.
(setq MyVarialbe (strcat MyVariable " and some more text")

In C you'd need to reallocate more memory for that variable and re-assign it. Things like this get easier the more you step up. C++ being easier to deal with strings, and C# being the easiest.

Obviously, this is just another dumb example; and what I'm trying to say is that you "design" differently in compiled languages then you do in languages like AutoLisp.

Recursion is the easiest form of a loop to understand/use. You really should read at least the first two chapters of Structure and Interpretation of Computer Programs.

[gile]

More seriously, this topic is quite interesting about speed performances.
It shows the importance of the algorithm. The best LISP implementations were faster than than my first 'brute force' C# implementations.
Anyway, for the same algorithm LISP will always be slower because it's a quite old interpreted language which uses dynamic typing and has only one data structure (linked list).

VisualLISP is for ObjectARX what windsurfing is for ocean racing yachts: lighter, more fun but less powerful, especially with large tasks.

PS: I really do like LISP.

[VovKa]

why LISP in overall is so programmed that it's way too slower than other languages...

because modern computers are way behind the lisp philosophy

p.s. at least they tried https://en.wikipedia.org/wiki/Lisp_machine

[Marc'Antonio Alessi]

Sorry for my ignorance (I don't know many languages and I'm not a programmer...) just out of curiosity: with other languages can a list long 4190208 strings be processed much faster?

> Test on AutoCAD 2013 and my old PC...

Code: [Select]

(length (setq aList (atoms-family 1)))
(progn (repeat 10 (setq aList (append aList aList))) (princ))
(prompt "\nLength: ") (princ (setq   aLeng   (length aList))) (princ "\n")
(setq   aMLen  (fix (/ (length aList) 2.0)))

(setq t0 (car (_vl-times)))
(prompt "\nLength ALE_List_FirstN: ")(princ (length (ALE_List_FirstN   aMLen aList)))
(setq t1 (car (_vl-times)))
(prompt "\nElapsed time for ALE_List_FirstN : ") (princ (rtos (- t1 t0) 2 20)) (prompt " milliseconds...")

(setq t0 (car (_vl-times)))
(prompt "\nLength ALE_List_LastN: ")(princ (length (ALE_List_LastN   aMLen aList)))
(setq t1 (car (_vl-times)))
(prompt "\nElapsed time for ALE_List_LastN : ") (princ (rtos (- t1 t0) 2 20)) (prompt " milliseconds...")



Code: [Select]

Length: 4190208
Length ALE_List_FirstN: 2095104
Elapsed time for ALE_List_FirstN : 188 milliseconds...
Length ALE_List_LastN: 2095104
Elapsed time for ALE_List_LastN : 78 milliseconds...