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

0 Members and 1 Guest are viewing this topic.

ribarm

  • Gator
  • Posts: 3225
  • Marko Ribar, architect
Split big list...
« 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...
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: Split big list...
« Reply #1 on: May 27, 2020, 07:57:12 AM »
Post a sample list (short) and results...

ribarm

  • Gator
  • Posts: 3225
  • Marko Ribar, architect
Re: Split big list...
« Reply #2 on: May 27, 2020, 08:06:06 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)...
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

JohnK

  • Administrator
  • Seagull
  • Posts: 10605
Re: Split big list...
« 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]
  1. ( (lambda ()
  2.     (setq a_lst '(0 1 2 3 4 5 6 7)
  3.           opperator "d"
  4.           num (length a_lst)
  5.           int 1
  6.           temp "c")
  7.     (while (<= int (/ num 2))
  8.            (setq temp (strcat temp opperator)
  9.                  int (+ int 1)))
  10.     (setq temp (strcat temp "r"))
  11.     (eval (list (read temp) (quote a_lst)))
  12.     )
  13.  )

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".
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

ribarm

  • Gator
  • Posts: 3225
  • Marko Ribar, architect
Re: Split big list...
« 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...
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

JohnK

  • Administrator
  • Seagull
  • Posts: 10605
Re: Split big list...
« Reply #5 on: May 27, 2020, 08:33:08 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?
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: Split big list...
« 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

  • Gator
  • Posts: 3225
  • Marko Ribar, architect
Re: Split big list...
« 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)
)
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

ribarm

  • Gator
  • Posts: 3225
  • Marko Ribar, architect
Re: Split big list...
« 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]
  1. (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 )
  2.  
  3.   (defun ALE_List_NthCdr (n l) 
  4.     (repeat (/       n              1000) (setq l (Cd1000r l)))
  5.     (repeat (/ (setq n (rem n 1000)) 100) (setq l (Cd100r  l)))
  6.     (repeat (/ (setq n (rem n  100))  10) (setq l (Cd10r   l)))
  7.     (repeat (/ (setq n (rem n   10))   4) (setq l (cddddr  l)))
  8.     (repeat (rem n 4)                     (setq l (cdr     l)))
  9.     l  
  10.   )
  11.   ;
  12.   (defun ALE_List_LastN (n l)  
  13.     (ALE_List_NthCdr (- (length l) n) l)
  14.   )
  15.   (defun ALE_List_FirstN (n l) 
  16.     (reverse (ALE_List_NthCdr (- (length l) n) (reverse l)))
  17.   )
  18.   ;
  19.   (defun Cd10r (l)
  20.     (cddddr(cddddr(cddr l)))
  21.   )
  22.   (defun Cd100r (l)
  23.     (cddddr(cddddr(cddddr(cddddr l)))))))))))))))))))))))))
  24.   )
  25.   (defun Cd1000r (l)
  26.     (cddddr(cddddr(cddddr(cddddr(cddddr l))))))))))))
  27.     )))))))))))))))))))))))))))))))))))))))))))))))))
  28.     )))))))))))))))))))))))))))))))))))))))))))))))))
  29.     )))))))))))))))))))))))))))))))))))))))))))))))))
  30.     )))))))))))))))))))))))))))))))))))))))))))))))))
  31.     ))))))))))))))))))))))))))))))))))))))))))
  32.   )
  33.    
  34.   (setq pos (fix (/ (setq len (length l)) 2.0)))
  35.   (setq l1 (ALE_List_FirstN (- len pos) l))
  36.   (setq l2 (ALE_List_LastN pos l))
  37.  
  38.   (cond
  39.     ( (and l1 l2)
  40.       (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))
  41.       (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))
  42.       (if (apply f (list a1 a2))
  43.         a1
  44.         a2
  45.       )
  46.     )
  47.     ( t
  48.       (car l)
  49.     )
  50.   )
  51. )
  52.  
  53. ;;; (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 '<
  54. ;;; (car-sort '(2 4 1 3 5 1) '<=) => 1
  55.  

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]
  1. (defun car-sort ( l f / removenth r k )
  2.  
  3.   (defun removenth ( l n / k )
  4.     (setq k -1)
  5.     (vl-remove-if '(lambda ( x ) (= (setq k (1+ k)) n)) l)
  6.   )
  7.  
  8.   (setq k -1)
  9.   (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)
  10.   r
  11. )
  12.  
  13. ;;; (car-sort '(2 4 1 3 5 1) '<) => nil
  14. ;;; (car-sort '(2 4 1 3 5 1) '<=) => 1
  15.  

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

Thanks, M.R.
« Last Edit: May 27, 2020, 09:53:35 AM by ribarm »
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: Split big list...
« 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

  • Gator
  • Posts: 3225
  • Marko Ribar, architect
Re: Split big list...
« 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...
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: Split big list...
« 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]
  1. (defun extremum ( cmp lst / rtn )
  2.    (setq rtn (car lst))
  3.    (foreach itm (cdr lst)
  4.        (if (apply cmp (list itm rtn)) (setq rtn itm))
  5.    )
  6.    rtn
  7. )

(Previously posted here.)

ribarm

  • Gator
  • Posts: 3225
  • Marko Ribar, architect
Re: Split big list...
« 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]
  1. (defun c:test ( / car-sort-old car-sort-new l t0 t1 )
  2.  
  3.   (defun car-sort-old ( l f / removenth r k )
  4.  
  5.     (defun removenth ( l n / k )
  6.       (setq k -1)
  7.       (vl-remove-if '(lambda ( x ) (= (setq k (1+ k)) n)) l)
  8.     )
  9.  
  10.     (setq k -1)
  11.     (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)
  12.     r
  13.   )
  14.  
  15.   ;;; (car-sort '(2 4 1 3 5 1) '<) => nil
  16.   ;;; (car-sort '(2 4 1 3 5 1) '<=) => 1
  17.  
  18.   (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 )
  19.  
  20.     (defun ALE_List_NthCdr (n l)       
  21.       (repeat (/       n              1000) (setq l (Cd1000r l)))      
  22.       (repeat (/ (setq n (rem n 1000)) 100) (setq l (Cd100r  l)))      
  23.       (repeat (/ (setq n (rem n  100))  10) (setq l (Cd10r   l)))      
  24.       (repeat (/ (setq n (rem n   10))   4) (setq l (cddddr  l)))      
  25.       (repeat (rem n 4)                     (setq l (cdr     l)))      
  26.       l
  27.     )
  28.     ;
  29.     (defun ALE_List_LastN (n l)
  30.       (ALE_List_NthCdr (- (length l) n) l)
  31.     )
  32.     (defun ALE_List_FirstN (n l)       
  33.       (reverse (ALE_List_NthCdr (- (length l) n) (reverse l)))
  34.     )
  35.     ;
  36.     (defun Cd10r (l)
  37.       (cddddr(cddddr(cddr l)))
  38.     )
  39.     (defun Cd100r (l)
  40.       (cddddr(cddddr(cddddr(cddddr l)))))))))))))))))))))))))
  41.     )
  42.     (defun Cd1000r (l)
  43.       (cddddr(cddddr(cddddr(cddddr(cddddr l))))))))))))
  44.       )))))))))))))))))))))))))))))))))))))))))))))))))
  45.       )))))))))))))))))))))))))))))))))))))))))))))))))
  46.       )))))))))))))))))))))))))))))))))))))))))))))))))
  47.       )))))))))))))))))))))))))))))))))))))))))))))))))
  48.       ))))))))))))))))))))))))))))))))))))))))))
  49.     )
  50.      
  51.     (setq pos (fix (/ (setq len (length l)) 2.0)))
  52.     (setq l1 (ALE_List_FirstN (- len pos) l))
  53.     (setq l2 (ALE_List_LastN pos l))
  54.  
  55.     (cond
  56.       ( (and l1 l2)
  57.         (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))
  58.         (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))
  59.         (if (apply f (list a1 a2))
  60.           a1
  61.           a2
  62.         )
  63.       )
  64.       ( t
  65.         (car l)
  66.       )
  67.     )
  68.   )
  69.  
  70.   ;;; (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 '<
  71.   ;;; (car-sort '(2 4 1 3 5 1) '<=) => 1
  72.  
  73.   (setq l (atoms-family 1))
  74.   (setq t0 (car (_vl-times)))
  75.   (repeat 10
  76.     (car-sort-old l '(lambda ( a b ) (<= (strlen a) (strlen b))))
  77.   )
  78.   (setq t1 (car (_vl-times)))
  79.   (prompt "\nElapsed time for (car-sort-old) : ") (princ (rtos (- t1 t0) 2 20)) (prompt " milliseconds...")
  80.   (setq t0 (car (_vl-times)))
  81.   (repeat 10
  82.     (car-sort-new l '(lambda ( a b ) (<= (strlen a) (strlen b))))
  83.   )
  84.   (setq t1 (car (_vl-times)))
  85.   (prompt "\nElapsed time for (car-sort-new) : ") (princ (rtos (- t1 t0) 2 20)) (prompt " milliseconds...")
  86.   (setq t0 (car (_vl-times)))
  87.   (repeat 10
  88.     (car (vl-sort l '(lambda ( a b ) (<= (strlen a) (strlen b)))))
  89.   )
  90.   (setq t1 (car (_vl-times)))
  91.   (prompt "\nElapsed time for (car (vl-sort)) : ") (princ (rtos (- t1 t0) 2 20)) (prompt " milliseconds...")
  92.   (princ)
  93. )
  94.  
  95. ;|
  96. Command: TEST
  97. Elapsed time for (car-sort-old) : 392688.0000000000 milliseconds...
  98. Elapsed time for (car-sort-new) : 52968.99999999999 milliseconds...
  99. Elapsed time for (car (vl-sort)) : 1406.000000000000 milliseconds...
  100. |;
  101.  
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

JohnK

  • Administrator
  • Seagull
  • Posts: 10605
Re: Split big list...
« 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).
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

ribarm

  • Gator
  • Posts: 3225
  • Marko Ribar, architect
Re: Split big list...
« Reply #14 on: May 27, 2020, 11:11:12 AM »
Unless I'm overlooking something about car-sort, why not just:
Code - Auto/Visual Lisp: [Select]
  1. (defun extremum ( cmp lst / rtn )
  2.    (setq rtn (car lst))
  3.    (foreach itm (cdr lst)
  4.        (if (apply cmp (list itm rtn)) (setq rtn itm))
  5.    )
  6.    rtn
  7. )

(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...
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube