Author Topic: Split big list... (Read 6410 times)

ribarm · « **on:** May 27, 2020, 07:27:24 AM »

Hi...
Here is the task (small challenge) :
You have big list with elements that are not unique - so there may be repetitions...
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...

If you have some suggestion, please step in...
Cheers...

Marc'Antonio Alessi · « **Reply #1 on:** May 27, 2020, 07:57:12 AM »

Post a sample list (short) and results...

ribarm · « **Reply #2 on:** May 27, 2020, 08:06:06 AM »

Quote from: Marc'Antonio Alessi on May 27, 2020, 07:57:12 AM

Post a sample list (short) and results...

Don't have any particular - can be any but with repeating elements...
For me it's good solution if you could split it at half or approximately at position (nth (fix (/ (length lst) 2.0)) lst)...

JohnK · « **Reply #3 on:** May 27, 2020, 08:23:22 AM »

I got the second half (if the list is short):

Code - Auto/Visual Lisp: [Select]

( (lambda ()
    (setq a_lst '(0 1 2 3 4 5 6 7)
          opperator "d"
          num (length a_lst)
          int 1
          temp "c")
    (while (<= int (/ num 2))
           (setq temp (strcat temp opperator)
                 int (+ int 1)))
    (setq temp (strcat temp "r"))
    (eval (list (read temp) (quote a_lst)))
    )
 )

Why are you splitting lists? When you have large, messy, lists operations on that list can take some time--especially if you are iterating that list several times trying to, unnecessarily "sort it alphabetical".

ribarm · « **Reply #4 on:** May 27, 2020, 08:27:48 AM »

You are iterating with (while) and plus you have a_lst unique elements - elements should repeat randomly...

JohnK · « **Reply #5 on:** May 27, 2020, 08:33:08 AM »

Quote from: ribarm on May 27, 2020, 08:27:48 AM

You are iterating with (while) and plus you have a_lst unique elements - elements should repeat randomly...

My solution wasn't really practical. My question remains though; list operations can be unnecessary so wouldn't a different design approach be better in some cases?

Marc'Antonio Alessi · « **Reply #6 on:** May 27, 2020, 09:07:54 AM »

With long list maybe you can try my ALE_List_NthCdr "demential" solution:

Code: [Select]

(setq   aList '("01" "02" "03" "04" "05" "06" "07" "08" "09" "10" "11" "12" "13" "14" "15")) => ("01" "02" "03" "04" "05" "06" "07" "08" "09" "10" "11" "12" "13" "14" "15")

(setq   aLeng   (length aList)) => 15

(setq   aMLen  (fix (/ (length aList) 2.0))) => 7

(ALE_List_LastN   aMLen aList) => ("09" "10" "11" "12" "13" "14" "15")

(ALE_List_FirstN  (- aLeng aMLen) aList) => ("01" "02" "03" "04" "05" "06" "07" "08")

(length (setq aList (atoms-family 1))) => 4091
(progn (repeat 10 (setq aList (append aList aList))) (princ))

(setq   aLeng   (length aList)) => 4189184

(setq   aMLen  (fix (/ (length aList) 2.0))) => 2094592

(length (ALE_List_LastN   aMLen aList)) => 2094592

(length (ALE_List_FirstN  (- aLeng aMLen) aList)) => 2094592

Code: [Select]

(defun ALE_List_NthCdr (n l)	
  (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_LastN (n l)	
  (ALE_List_NthCdr (- (length l) n) l) 
)
(defun ALE_List_FirstN (n l)	
  (reverse (ALE_List_NthCdr (- (length l) n) (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))))))))))))
  )))))))))))))))))))))))))))))))))))))))))))))))))
  )))))))))))))))))))))))))))))))))))))))))))))))))
  )))))))))))))))))))))))))))))))))))))))))))))))))
  )))))))))))))))))))))))))))))))))))))))))))))))))
  ))))))))))))))))))))))))))))))))))))))))))

ribarm · « **Reply #7 on:** May 27, 2020, 09:23:02 AM »

Thanks Marc' for you input... Actually my attempt is also iteration, similar to yours, but I suppose your is faster-better...

Here is my attempt :

Code: [Select]

(defun c:splitlsthalfs ( / memberpos lst pos len l1 l2 )

  (defun memberpos ( pos lst / k )
    (setq k -1)
    (while (< (setq k (1+ k)) pos)
      (setq lst (cdr lst))
    )
    lst
  )

  (setq lst '(1 2 3 2 1 2 3 2 1 4 5 6 5 4 6))
  (setq pos (fix (/ (setq len (length lst)) 2.0)))
  (setq l2 (memberpos pos lst))
  (setq l1 (if (= (rem len 2) 1) (reverse (cdr (memberpos pos (reverse lst)))) (reverse (memberpos pos (reverse lst)))))
  (princ "\n")
  (princ lst)
  (princ "\n")
  (princ (list l1 l2))
  (princ)
)

ribarm · « **Reply #8 on:** May 27, 2020, 09:49:31 AM »

I hope you don't mind - I steal your subs to make my own - here is where I'll use it :

Code - Auto/Visual Lisp: [Select]

(defun car-sort ( l f / ALE_List_NthCdr ALE_List_LastN ALE_List_FirstN Cd10r Cd100r Cd1000r pos len l1 l2 al1 al2 a1 a2 )
 
  (defun ALE_List_NthCdr (n l)  
    (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_LastN (n l)   
    (ALE_List_NthCdr (- (length l) n) l)
  )
  (defun ALE_List_FirstN (n l)  
    (reverse (ALE_List_NthCdr (- (length l) n) (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))))))))))))
    )))))))))))))))))))))))))))))))))))))))))))))))))
    )))))))))))))))))))))))))))))))))))))))))))))))))
    )))))))))))))))))))))))))))))))))))))))))))))))))
    )))))))))))))))))))))))))))))))))))))))))))))))))
    ))))))))))))))))))))))))))))))))))))))))))
  )
    
  (setq pos (fix (/ (setq len (length l)) 2.0)))
  (setq l1 (ALE_List_FirstN (- len pos) l))
  (setq l2 (ALE_List_LastN pos l))
 
  (cond
    ( (and l1 l2)
      (setq a1 (vl-some (function (lambda ( aa ) (setq al1 (cons aa al1)) (if (vl-every (function (lambda ( xx ) (apply f (list aa xx)))) (append (cdr al1) (setq l1 (cdr l1)))) aa))) l1))
      (setq a2 (vl-some (function (lambda ( aa ) (setq al2 (cons aa al2)) (if (vl-every (function (lambda ( xx ) (apply f (list aa xx)))) (append (cdr al2) (setq l2 (cdr l2)))) aa))) l2))
      (if (apply f (list a1 a2))
        a1
        a2
      )
    )
    ( t
      (car l)
    )
  )
)
 
;;; (car-sort '(2 4 1 3 5 1) '<) => 1, (1 belongs to both l1 and l2) but generally it would be nil if single list processing, so better is '<= than '<
;;; (car-sort '(2 4 1 3 5 1) '<=) => 1
 

For testing use something like :

Code: [Select]

(car-sort (atoms-family 1) '(lambda ( a b ) (<= (strlen a) (strlen b))))

Or opposite :

Code: [Select]

(car-sort (atoms-family 1) '(lambda ( a b ) (>= (strlen a) (strlen b))))

Compare speed with my previous version :

Code - Auto/Visual Lisp: [Select]

(defun car-sort ( l f / removenth r k )
 
  (defun removenth ( l n / k )
    (setq k -1)
    (vl-remove-if '(lambda ( x ) (= (setq k (1+ k)) n)) l)
  )
 
  (setq k -1)
  (vl-some '(lambda ( a ) (setq k (1+ k)) (if (vl-every '(lambda ( x ) (apply f (list a x))) (removenth l k)) (setq r a))) l)
  r
)
 
;;; (car-sort '(2 4 1 3 5 1) '<) => nil
;;; (car-sort '(2 4 1 3 5 1) '<=) => 1
 

It should be much faster-better then it was...

Thanks, M.R.

Marc'Antonio Alessi · « **Reply #9 on:** May 27, 2020, 10:13:20 AM »

Your previous version with length 4.193.280

Benchmark.lsp | © 2005 Michael Puckett | All Rights Reserved

Elapsed milliseconds / relative speed for 8 iteration(s):
(ALE_LIST_FIRSTN AMLEN ALIST).....1281 / 3.15 <fastest>
(MEMBERPOS AMLEN ALIST)...........4031 / 1 <slowest>

Elapsed milliseconds / relative speed for 32 iteration(s):
(ALE_LIST_LASTN AMLEN ALIST)........1797 / 11.05 <fastest>
(MEMBERPOSR AMLEN ALIST ALENG).....19859 / 1 <slowest>

ribarm · « **Reply #10 on:** May 27, 2020, 10:26:04 AM »

It is important to me that (car-sort) is now faster then it was before... This is especially important when you're dealing with routine that repeats inside loops only (car-sort), rather then (car (vl-sort))... In those cases there is no need to sort whole list over and over again and you need only first element of sorting... I believe that now my/your sub is closer to what's called built-in optimized autolisp function - and this one is new one - "congratualtions!!!"...
Can you improve it more?

Thanks for your help...

Lee Mac · « **Reply #11 on:** May 27, 2020, 10:53:21 AM »

Unless I'm overlooking something about car-sort, why not just:

Code - Auto/Visual Lisp: [Select]

(defun extremum ( cmp lst / rtn )
   (setq rtn (car lst))
   (foreach itm (cdr lst)
       (if (apply cmp (list itm rtn)) (setq rtn itm))
   )
   rtn
)

(Previously posted here.)

ribarm · « **Reply #12 on:** May 27, 2020, 10:58:25 AM »

There is still some issues with (car-sort)... Here is my testing function and results on my PC... (car (vl-sort)) should be the worst, but it proved the best... Something's weird going on...

Code - Auto/Visual Lisp: [Select]

(defun c:test ( / car-sort-old car-sort-new l t0 t1 )
 
  (defun car-sort-old ( l f / removenth r k )
 
    (defun removenth ( l n / k )
      (setq k -1)
      (vl-remove-if '(lambda ( x ) (= (setq k (1+ k)) n)) l)
    )
 
    (setq k -1)
    (vl-some '(lambda ( a ) (setq k (1+ k)) (if (vl-every '(lambda ( x ) (apply f (list a x))) (removenth l k)) (setq r a))) l)
    r
  )
 
  ;;; (car-sort '(2 4 1 3 5 1) '<) => nil
  ;;; (car-sort '(2 4 1 3 5 1) '<=) => 1
 
  (defun car-sort-new ( l f / ALE_List_NthCdr ALE_List_LastN ALE_List_FirstN Cd10r Cd100r Cd1000r pos len l1 l2 al1 al2 a1 a2 )
 
    (defun ALE_List_NthCdr (n l)        
      (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_LastN (n l) 
      (ALE_List_NthCdr (- (length l) n) l)
    )
    (defun ALE_List_FirstN (n l)        
      (reverse (ALE_List_NthCdr (- (length l) n) (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))))))))))))
      )))))))))))))))))))))))))))))))))))))))))))))))))
      )))))))))))))))))))))))))))))))))))))))))))))))))
      )))))))))))))))))))))))))))))))))))))))))))))))))
      )))))))))))))))))))))))))))))))))))))))))))))))))
      ))))))))))))))))))))))))))))))))))))))))))
    )
      
    (setq pos (fix (/ (setq len (length l)) 2.0)))
    (setq l1 (ALE_List_FirstN (- len pos) l))
    (setq l2 (ALE_List_LastN pos l))
 
    (cond
      ( (and l1 l2)
        (setq a1 (vl-some (function (lambda ( aa ) (setq al1 (cons aa al1)) (if (vl-every (function (lambda ( xx ) (apply f (list aa xx)))) (append (cdr al1) (setq l1 (cdr l1)))) aa))) l1))
        (setq a2 (vl-some (function (lambda ( aa ) (setq al2 (cons aa al2)) (if (vl-every (function (lambda ( xx ) (apply f (list aa xx)))) (append (cdr al2) (setq l2 (cdr l2)))) aa))) l2))
        (if (apply f (list a1 a2))
          a1
          a2
        )
      )
      ( t
        (car l)
      )
    )
  )
 
  ;;; (car-sort '(2 4 1 3 5 1) '<) => 1, (1 belongs to both l1 and l2) but generally it would be nil if single list processing, so better is '<= than '<
  ;;; (car-sort '(2 4 1 3 5 1) '<=) => 1
 
  (setq l (atoms-family 1))
  (setq t0 (car (_vl-times)))
  (repeat 10
    (car-sort-old l '(lambda ( a b ) (<= (strlen a) (strlen b))))
  )
  (setq t1 (car (_vl-times)))
  (prompt "\nElapsed time for (car-sort-old) : ") (princ (rtos (- t1 t0) 2 20)) (prompt " milliseconds...")
  (setq t0 (car (_vl-times)))
  (repeat 10
    (car-sort-new l '(lambda ( a b ) (<= (strlen a) (strlen b))))
  )
  (setq t1 (car (_vl-times)))
  (prompt "\nElapsed time for (car-sort-new) : ") (princ (rtos (- t1 t0) 2 20)) (prompt " milliseconds...")
  (setq t0 (car (_vl-times)))
  (repeat 10
    (car (vl-sort l '(lambda ( a b ) (<= (strlen a) (strlen b)))))
  )
  (setq t1 (car (_vl-times)))
  (prompt "\nElapsed time for (car (vl-sort)) : ") (princ (rtos (- t1 t0) 2 20)) (prompt " milliseconds...")
  (princ)
)
 
;|
Command: TEST
Elapsed time for (car-sort-old) : 392688.0000000000 milliseconds...
Elapsed time for (car-sort-new) : 52968.99999999999 milliseconds...
Elapsed time for (car (vl-sort)) : 1406.000000000000 milliseconds...
|;
 

JohnK · « **Reply #13 on:** May 27, 2020, 10:59:18 AM »

Confused! I thought we weren't supposed to iterate (I'm not even sure how you would modify a list in any language I know without iteration of some kind).

ribarm · « **Reply #14 on:** May 27, 2020, 11:11:12 AM »

Quote from: Lee Mac on May 27, 2020, 10:53:21 AM

Unless I'm overlooking something about car-sort, why not just:
Code - Auto/Visual Lisp: [Select]
(defun extremum ( cmp lst / rtn )
(setq rtn (car lst))
(foreach itm (cdr lst)
(if (apply cmp (list itm rtn)) (setq rtn itm))
)
rtn
)

(Previously posted here.)

Lee I see your point, I guess you're right... I was carried with my (vl-some) - (vl-every) solution from the first time I constructed (car-sort)... I haven't checked your version in comparison to (car (vl-sort)), but I believe it should perform the quickest... I'll check it once again...

ribarm · « **Reply #15 on:** May 27, 2020, 11:17:32 AM »

Here are the results on my PC...

Code - Auto/Visual Lisp: [Select]

(defun c:test ( / extremum l t0 t1 )
 
  (defun extremum ( cmp lst / rtn )
     (setq rtn (car lst))
     (foreach itm (cdr lst)
         (if (apply cmp (list itm rtn)) (setq rtn itm))
     )
     rtn
  )
    
  (setq l (atoms-family 1))
  (setq t0 (car (_vl-times)))
  (repeat 10
    (extremum '(lambda ( a b ) (<= (strlen a) (strlen b))) l)
  )
  (setq t1 (car (_vl-times)))
  (prompt "\nElapsed time for (extremum) : ") (princ (rtos (- t1 t0) 2 20)) (prompt " milliseconds...")
  (setq t0 (car (_vl-times)))
  (repeat 10
    (car (vl-sort l '(lambda ( a b ) (<= (strlen a) (strlen b)))))
  )
  (setq t1 (car (_vl-times)))
  (prompt "\nElapsed time for (car (vl-sort)) : ") (princ (rtos (- t1 t0) 2 20)) (prompt " milliseconds...")
  (princ)
)
 
;|
Command: TEST
Elapsed time for (extremum) : 5265.000000000000 milliseconds...
Elapsed time for (car (vl-sort)) : 1391.000000000000 milliseconds...
|;
 

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

Marc'Antonio Alessi · « **Reply #16 on:** May 27, 2020, 11:31:47 AM »

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 · « **Reply #17 on:** May 27, 2020, 11:35:57 AM »

TEST: Can anyone see my posts?

gile · « **Reply #18 on:** May 27, 2020, 11:54:43 AM »

Quote from: ribarm on May 27, 2020, 07:27:24 AM

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 · « **Reply #19 on:** May 27, 2020, 12:01:14 PM »

Quote from: John Kaul (Se7en) on May 27, 2020, 11:35:57 AM

TEST: Can anyone see my posts?

Yes.

JohnK · « **Reply #20 on:** May 27, 2020, 12:16:56 PM »

Quote from: hmspe on May 27, 2020, 12:01:14 PM

Quote from: John Kaul (Se7en) on May 27, 2020, 11:35:57 AM
TEST: Can anyone see my posts?
Yes.

Thank you. I was starting to worry.

ribarm · « **Reply #21 on:** May 27, 2020, 12:20:07 PM »

Quote from: gile on May 27, 2020, 11:54:43 AM

Quote from: ribarm on May 27, 2020, 07:27:24 AM
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 · « **Reply #22 on:** May 27, 2020, 01:16:58 PM »

Quote from: ribarm on May 27, 2020, 12:20:07 PM

Quote from: gile on May 27, 2020, 11:54:43 AM
Quote from: ribarm on May 27, 2020, 07:27:24 AM
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 · « **Reply #23 on:** May 27, 2020, 01:30:59 PM »

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 · « **Reply #24 on:** May 27, 2020, 02:02:04 PM »

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 · « **Reply #25 on:** May 27, 2020, 02:40:43 PM »

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 · « **Reply #26 on:** May 27, 2020, 02:58:21 PM »

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 · « **Reply #27 on:** May 27, 2020, 03:04:29 PM »

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 · « **Reply #28 on:** May 27, 2020, 05:10:59 PM »

Quote from: ribarm on May 27, 2020, 02:02:04 PM

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 · « **Reply #29 on:** May 27, 2020, 05:16:00 PM »

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

JohnK · « **Reply #30 on:** May 27, 2020, 06:03:03 PM »

You wouldn't store that much in memory typically. But I've processed the entire "War and Peace" novel in milliseconds in C++ (time values that small are vey hard to get accurate). You can typically get about the same time frames from C and C++. C# is good as well (MS does a good job compiling).

Here was a fun challenge using a snip from "war and peace".
https://www.theswamp.org/index.php?topic=50378.msg555005#msg555005

gile · « **Reply #31 on:** May 28, 2020, 07:15:05 AM »

Quote from: Marc'Antonio Alessi on May 27, 2020, 05:16:00 PM

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?

A quick test with F# and an array (done on VS Code)

Code - F#: [Select]

let arrayFirstN array = 
    let n = (Array.length array) / 2
    array.[.. n - 1]
 
let arrayLastN array = 
    let n = (Array.length array) / 2
    array.[n ..]
 
let benchArray array =
    let sw = System.Diagnostics.Stopwatch()
    printfn "Length: %d" (Array.length array)
    sw.Start()
    let a1 = arrayFirstN array
    sw.Stop()
    printfn "Length arrayFirstN: %d" (Array.length a1)
    printfn "Elapsed time for arrayFirstN: %d milliseconds" sw.ElapsedMilliseconds
    sw.Reset()
    sw.Start()
    let a2 = arrayLastN array
    sw.Stop()
    printfn "Length arrayLastN: %d" (Array.length a2)
    printfn "Elapsed time for arrayLastN: %d milliseconds" sw.ElapsedMilliseconds

Code: [Select]

> benchArray [| 1 .. 4190208 |];;
Length: 4190208
Length arrayFirstN: 2095104
Elapsed time for arrayFirstN: 2 milliseconds
Length arrayLastN: 2095104
Elapsed time for arrayLastN: 2 milliseconds
val it : unit = ()

ribarm · « **Reply #32 on:** May 28, 2020, 08:36:34 AM »

Only to inform... Lee's sub is fastest, but on BricsCAD...

Here is my testing result of (extremum) vs ((car (vl-sort)) :

Code: [Select]

: TEST

Elapsed time for (extremum) : 15 milliseconds...
Elapsed time for (car (vl-sort)) : 171 milliseconds...

Thanks all for participating...
And BTW. If someone would need 2-10 times faster without changing LISP, he/she should just use BricsCAD... For me it worked well on 1 example (32 - depth, 50 solutions, 2 points per (processpt)), but on another one (32 - depth, 100 - solutions, 4 points per (processpt)) it crashed around (unique) - there was probably needed (gc) call while recursing...

Marc'Antonio Alessi · « **Reply #33 on:** May 28, 2020, 05:07:10 PM »

Quote from: gile on May 28, 2020, 07:15:05 AM

A quick test with F# and an array (done on VS Code)
<clip>
Length arrayFirstN: 2095104
Elapsed time for arrayFirstN: 2 milliseconds
Length arrayLastN: 2095104
Elapsed time for arrayLastN: 2 milliseconds
val it : unit = ()

Thanks for sample!

gile · « **Reply #34 on:** May 28, 2020, 05:22:59 PM »

@Marc'Antonio Alessi

The same thing using a list instead of an array gives results similar to those of LISP (F # also uses linked lists like most functional programming languages).
This illustrates what I wanted to say: the problem is less the language itself than the data structures it provides. AutoLISP only provides linked lists which are ineffective when they become too large.

Code - F#: [Select]

let listFirstN lst =
    let n = (List.length lst) / 2
    List.take n lst
 
let listLastN lst =
    let n = (List.length lst) / 2
    List.skip n lst
 
let benchList list =
    let sw = System.Diagnostics.Stopwatch()
    printfn "Length: %d" (List.length list)
    sw.Start()
    let l1 = listFirstN list
    sw.Stop()
    printfn "Length listFirstN: %d" (List.length l1)
    printfn "Elapsed time for listFirstN: %d milliseconds" sw.ElapsedMilliseconds
    sw.Reset()
    sw.Start()
    let l2 = listLastN list
    sw.Stop()
    printfn "Length listLastN: %d" (List.length l2)
    printfn "Elapsed time for listLastN: %d milliseconds" sw.ElapsedMilliseconds

Code: [Select]

> benchList [1 .. 4190208];;
Length: 4190208
Length listFirstN: 2095104
Elapsed time for listFirstN: 141 milliseconds
Length listLastN: 2095104
Elapsed time for listLastN: 14 milliseconds
val it : unit = ()

Marc'Antonio Alessi · « **Reply #35 on:** May 29, 2020, 03:24:37 AM »

@gile Very interesting.

News:

Author Topic: Split big list... (Read 6410 times)