Author Topic: Looking for a better way...  (Read 7992 times)

0 Members and 1 Guest are viewing this topic.

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Looking for a better way...
« Reply #30 on: June 26, 2012, 08:23:56 AM »
Exactly! That's the "blank" I was mentioning hitting  ;)
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Looking for a better way...
« Reply #31 on: June 26, 2012, 01:06:55 PM »
OK, I've just figured out how to do this:
Code - Auto/Visual Lisp: [Select]
  1. (defun make-list-from  (size initial-list / lst)
  2.   (if (> size 0)
  3.     (cond ((> size (length initial-list))
  4.            (setq lst initial-list)
  5.            (while (< (* (length lst) 2) size) (setq lst (append lst lst)))
  6.            (append lst (make-list-from (- size (length lst)) initial-list)))
  7.           ((= size (length initial-list)) initial-list)
  8.           (t
  9.            (setq lst (reverse initial-list))
  10.            (reverse (repeat (- (length lst) size) (setq lst (cdr lst))))))))
  11.  
  12. (defun PairLists3  (lst1 lst2 pairs /)
  13.           (make-list-from pairs lst1)
  14.           (make-list-from pairs lst2)))
And it performs better than my original in all cases:
Code: [Select]
_$ (setq l1 '(1 2 3 4 5 6 7) l2 '("a" "b" "c" "d" "e") n 200)
200
_$
; 3 forms loaded from #<editor "J:/Documents/Benchmark.lsp">
_$ (QuickBench (mapcar '(lambda (f) (list f 'l1 'l2 'n)) '(PAIRUP7 PairLists2 PairLists3)))
Benchmarking ... done for 4096 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(PAIRLISTS3 L1 L2 N)                          4096      1560      1560      1.30
(PAIRLISTS2 L1 L2 N)                          4096      1607      1607      1.26
(PAIRUP7 L1 L2 N)                             4096      2027      2027      1.00
--------------------------------------------------------------------------------
Code: [Select]
_$ (setq l1a '(1 2) l2a '("a" "b") n 257)
257
_$ (QuickBench (mapcar '(lambda (f) (list f 'l1a 'l2a 'n)) '(PAIRUP7 PairLists2 PairLists3)))
Benchmarking ... done for 4096 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(PAIRLISTS3 L1A L2A N)                        4096      1701      1701      2.18
(PAIRUP7 L1A L2A N)                           2048      1373      2746      1.35
(PAIRLISTS2 L1A L2A N)                        2048      1855      3710      1.00
--------------------------------------------------------------------------------
Probably since there's no need for the final revers + repeat cdr anymore - that is handled in the make-list-from on much smaller lists.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

Lee Mac

  • Seagull
  • Posts: 12390
  • London, England
Re: Looking for a better way...
« Reply #32 on: June 26, 2012, 02:47:07 PM »
Well done Irne  :-)

Lee Mac

  • Seagull
  • Posts: 12390
  • London, England
Re: Looking for a better way...
« Reply #33 on: June 26, 2012, 02:58:26 PM »
Minor optimisations:

Code - Auto/Visual Lisp: [Select]
  1. (defun make-list-from ( l n / x )
  2.     (cond
  3.         (   (<= n 0)
  4.             nil
  5.         )
  6.         (   (> n (length l))
  7.             (setq x l)
  8.             (while (< (* (length x) 2) n) (setq x (append x x)))
  9.             (append x (make-list-from l (- n (length x))))
  10.         )
  11.         (   (= n (length l))
  12.             l
  13.         )
  14.         (   (setq l (reverse l))
  15.             (reverse (repeat (- (length l) n) (setq l (cdr l))))
  16.         )
  17.     )
  18. )
  19.  
  20. (defun pairup9 ( l1 l2 i )
  21.     (while (< (length l1) i) (setq l1 (append l1 l1)))
  22.     (mapcar 'list l1 (make-list-from l2 i))
  23. )

Code - Auto/Visual Lisp: [Select]
  1. _$ (setq l1 '(1 2 3 4 5 6 7) l2 '("a" "b" "c" "d" "e") n 200)
  2. 200
  3. _$ (benchmark '((pairup7 l1 l2 n) (pairup9 l1 l2 n) (pairlists3 l1 l2 n)))
  4. Benchmarking ................Elapsed milliseconds / relative speed for 8192 iteration(s):
  5.  
  6.     (PAIRUP9 L1 L2 N)........1513 / 1.63 <fastest>
  7.     (PAIRLISTS3 L1 L2 N).....1809 / 1.36
  8.     (PAIRUP7 L1 L2 N)........2465 / 1 <slowest>

Code - Auto/Visual Lisp: [Select]
  1. _$ (setq l1 '(1 2) l2 '("a" "b") n 257)
  2. 257
  3. _$ (benchmark '((pairup7 l1 l2 n) (pairup9 l1 l2 n) (pairlists3 l1 l2 n)))
  4. Benchmarking ................Elapsed milliseconds / relative speed for 8192 iteration(s):
  5.  
  6.     (PAIRLISTS3 L1 L2 N).....1919 / 1.61 <fastest>
  7.     (PAIRUP9 L1 L2 N)........1996 / 1.55
  8.     (PAIRUP7 L1 L2 N)........3089 / 1 <slowest>

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1542
  • Moscow (Russia)
Re: Looking for a better way...
« Reply #34 on: June 26, 2012, 04:06:57 PM »
My first version:

Code - Auto/Visual Lisp: [Select]
  1. (defun eea-pairup (a b n / f)
  2.   (defun f (c d n)
  3.     (cond ((not c) (f a d n))
  4.           ((not d) (f c b n))
  5.           ((> n 0)(cons (list (car c) (car d)) (f (cdr c) (cdr d) (1- n))))
  6.     )
  7.   )
  8.   (f a b n)
  9. )
« Last Edit: June 26, 2012, 04:11:00 PM by ElpanovEvgeniy »
Stay home. Stay safe. Save lives.

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Looking for a better way...
« Reply #35 on: June 27, 2012, 03:36:36 AM »
That's a very novel one EE! It was a bit of a mind-mender for me to figure out what was going on. How you come up with these ideas is beyond me! Thanks for showing though. Unfortunately it's highl;y recursive, so not a good idea for very long lists.

Lee. I hope you don't mind. I had to swap the arguments around on that make-list-from defun ... I prefer sticking with the CL's argument order and not mix it up.


Anyhow, here's the new benchmarking:
Code: [Select]
_$ (setq l1 '(1 2 3 4 5 6 7) l2 '("a" "b" "c" "d" "e") n 200)
200
_$ (QuickBench (mapcar '(lambda (f) (list f 'l1 'l2 'n)) '(PAIRUP7 PairUp9 PairLists2 PairLists3 eea-pairup paircab pairs)))
Benchmarking ....... done for 4096 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(PAIRUP9 L1 L2 N)                             4096      1108      1108      2.68
(PAIRLISTS3 L1 L2 N)                          4096      1278      1278      2.32
(PAIRLISTS2 L1 L2 N)                          4096      1326      1326      2.24
(PAIRUP7 L1 L2 N)                             4096      1793      1793      1.65
(PAIRS L1 L2 N)                               2048      1436      2872      1.03
(PAIRCAB L1 L2 N)                             2048      1467      2934      1.01
(EEA-PAIRUP L1 L2 N)                          2048      1483      2966      1.00
--------------------------------------------------------------------------------
_$ (setq l1 '(1 2) l2 '("a" "b") n 257)
257
_$ (QuickBench (mapcar '(lambda (f) (list f 'l1 'l2 'n)) '(PAIRUP7 PairUp9 PairLists2 PairLists3 eea-pairup paircab pairs)))
Benchmarking ....... done for 4096 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(PAIRLISTS3 L1 L2 N)                          4096      1450      1450      3.10
(PAIRUP9 L1 L2 N)                             4096      1498      1498      3.00
(PAIRUP7 L1 L2 N)                             2048      1123      2246      2.00
(PAIRLISTS2 L1 L2 N)                          2048      1560      3120      1.44
(PAIRS L1 L2 N)                               2048      1810      3620      1.24
(PAIRCAB L1 L2 N)                             2048      1997      3994      1.12
(EEA-PAIRUP L1 L2 N)                          1024      1123      4492      1.00
--------------------------------------------------------------------------------
I think a slight mod on PairUp9 might make it the quickest overall. Something like checking which of l1 & l2 would give the closest match to the specified length by doubling it each time - would have to look at the math on this to not detract on the performance too much. Yet perhaps it might still require an option where both lists are run through the make-list-from function if both produce a list much longer than required.
« Last Edit: June 27, 2012, 03:39:53 AM by irneb »
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

Lee Mac

  • Seagull
  • Posts: 12390
  • London, England
Re: Looking for a better way...
« Reply #36 on: June 27, 2012, 05:27:42 AM »
That's a very novel one EE!

x2 That's an elegant way to 'resupply' the lists when they are exhausted  :-)

Lee. I hope you don't mind. I had to swap the arguments around on that make-list-from defun ... I prefer sticking with the CL's argument order and not mix it up.

No worries  :-)

I think a slight mod on PairUp9 might make it the quickest overall. Something like checking which of l1 & l2 would give the closest match to the specified length by doubling it each time - would have to look at the math on this to not detract on the performance too much.

Implementing this idea (though its not pretty):

Code - Auto/Visual Lisp: [Select]
  1. (defun make-list-from ( n l / x )
  2.     (cond
  3.         (   (<= n 0)
  4.             nil
  5.         )
  6.         (   (> n (length l))
  7.             (setq x l)
  8.             (while (< (* (length x) 2) n) (setq x (append x x)))
  9.             (append x (make-list-from (- n (length x)) l))
  10.         )
  11.         (   (= n (length l))
  12.             l
  13.         )
  14.         (   (setq l (reverse l))
  15.             (reverse (repeat (- (length l) n) (setq l (cdr l))))
  16.         )
  17.     )
  18. )
  19.  
  20. (defun pow2 ( x n )
  21.     (rem (/ (- (log n) (log x)) (log 2.0)) 1)
  22. )
  23.  
  24. (defun pairup10 ( l1 l2 i )
  25.     (if (< (pow2 (length l1) i) (pow2 (length l2) i))
  26.         (progn
  27.             (while (< (length l2) i) (setq l2 (append l2 l2)))
  28.             (mapcar 'list (make-list-from i l1) l2)
  29.         )
  30.         (progn
  31.             (while (< (length l1) i) (setq l1 (append l1 l1)))
  32.             (mapcar 'list l1 (make-list-from i l2))
  33.         )
  34.     )
  35. )

Benchmarking:

Code - Auto/Visual Lisp: [Select]
  1. _$ (setq l1 '(1 2 3 4 5 6 7) l2 '("a" "b" "c" "d" "e") n 200)
  2. 200
  3.  
  4. compound lengths:
  5. ----------------------------
  6. l1 = 7(2^5) = 224
  7. l2 = 5(2^6) = 320
  8. ----------------------------
  9.  
  10. _$ (benchmark '((pairup9 l1 l2 n) (pairup10 l1 l2 n) (pairlists3 l1 l2 n)))
  11. Benchmarking ................Elapsed milliseconds / relative speed for 8192 iteration(s):
  12.  
  13.     (PAIRUP9 L1 L2 N)........1482 / 1.21 <fastest>
  14.     (PAIRUP10 L1 L2 N).......1529 / 1.17
  15.     (PAIRLISTS3 L1 L2 N).....1794 / 1 <slowest>

Code - Auto/Visual Lisp: [Select]
  1. _$ (setq l2 '(1 2 3 4 5 6 7) l1 '("a" "b" "c" "d" "e") n 200)
  2. 200
  3.  
  4. compound lengths:
  5. ----------------------------
  6. l1 = 5(2^6) = 320
  7. l2 = 7(2^5) = 224
  8. ----------------------------
  9.  
  10. _$ (benchmark '((pairup9 l1 l2 n) (pairup10 l1 l2 n) (pairlists3 l1 l2 n)))
  11. Benchmarking ................Elapsed milliseconds / relative speed for 8192 iteration(s):
  12.  
  13.     (PAIRUP10 L1 L2 N).......1529 / 1.18 <fastest>
  14.     (PAIRUP9 L1 L2 N)........1669 / 1.08
  15.     (PAIRLISTS3 L1 L2 N).....1809 / 1 <slowest>

bruno_vdh

  • Guest
Re: Looking for a better way...
« Reply #37 on: June 27, 2012, 09:55:37 AM »
Hello, Thank you for your discussion, I have followed with interest, for functions pow2 and make-list-from, if you want, I offer both small simplifications...

Code: [Select]
(defun pow2 (x n)
    (rem (/ (log (/ n x 1.0)) (log 2)) 1)
)

Code: [Select]
(defun make-list-from  ( n l / x )
    (cond
        (   (<= n 0)
            nil
        )
        (   (>= n (length l))
            (setq x l)
            (while (< (* (length x) 2) n) (setq x (append x x)))
            (append x (make-list-from (- n (length x)) l))
        )
       
        (   (setq l (reverse l))
            (reverse (repeat (- (length l) n) (setq l (cdr l))))
        )
    )
)

Sincerely,
« Last Edit: June 27, 2012, 10:02:43 AM by bruno_vdh »

LibertyOne

  • Guest
Re: Looking for a better way...
« Reply #38 on: June 27, 2012, 12:37:36 PM »
Note that the performance difference between the functions is highly dependent upon the combination of list length and number of pairs; for example, in the test case for all benchmarking performed in this thread we have used:

Code - Auto/Visual Lisp: [Select]
  1.     l1 '(1 2 3 4 5 6 7)
  2.     l2 '("a" "b" "c" "d" "e")
  3.     n 200
  4. )

In Irneb's function, following the exponential doubling operation, the initial lists have lengths 224 and 320 respectively (7x25 | 5x26), meaning that only 24 items need be removed after the mapcar pairing.

Conversely, in my pairup7 code, after the compounding of the restricting list 'l3', 72 items need to be added to obtain the correct length.

If we now skew these parameters, so that the lists both have length 2, and the number of pairs is 257, Irneb's function needs to remove 255 items from the resulting paired list (29 - 257); whereas, my pairup7 function only need add 1 item following the successive doubling.


As far as the pairing is concerned, the first list is a set of integers which could vary in length from 1 to 100. The second list is a point list with exactly 11 lists of 3 reals. This length will never change. The counter will realistically be no less than 200, but more in the range of 750 to 1000. Perhaps these realistic figures will help to give a more accurate benchmark of the functions.

Most of the functions are out of my range of experience with autolisp and I'm struggling a bit to implement them into my code. I've started to rewrite the function getting rid of redundancies so it is more simple to understand and build on. Still, along with the frustration, I have a smirk on my face reading all what I've started with this thread.

Lee Mac

  • Seagull
  • Posts: 12390
  • London, England
Re: Looking for a better way...
« Reply #39 on: June 27, 2012, 02:14:58 PM »
It's certainly been an interesting and enjoyable coding project for us (well, me anyway), even if you perhaps cannot use the final result  :-)

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Looking for a better way...
« Reply #40 on: June 28, 2012, 04:24:39 AM »
Hello, Thank you for your discussion, I have followed with interest, for functions pow2 and make-list-from, if you want, I offer both small simplifications...
For the make-list-from, your optimization seems to give a 2% increase in speed generally, but on the conditions where the length of the sample list has a binary factor congruent to the final size it's actually 6% slower (and the larger the size the smaller the efficiency difference):
Code - Auto/Visual Lisp: [Select]
  1. (defun make-list-from1 (n l / x)
  2.   (cond ((<= n 0) nil)
  3.         ((>= n (length l))
  4.          (setq x l)
  5.          (while (< (* (length x) 2) n) (setq x (append x x)))
  6.          (append x (make-list-from1 (- n (length x)) l)))
  7.         ((setq l (reverse l)) (reverse (repeat (- (length l) n) (setq l (cdr l)))))))
  8.  
  9. ;; Benchmarking
  10. _$ (setq l '(1 2 3 4) n 21)
  11. 21
  12. _$ (Benchmark '((make-list-from1 n l) (make-list-from n l)))
  13. Benchmarking ...................Elapsed milliseconds / relative speed for 65536 iteration(s):
  14.  
  15.     (MAKE-LIST-FROM1 N L).....1794 / 1.02 <fastest>
  16.     (MAKE-LIST-FROM N L)......1825 / 1.00 <slowest>
  17. _$ (setq l '(1 2 3) n 21)
  18. 21
  19. _$ (Benchmark '((make-list-from1 n l) (make-list-from n l)))
  20. Benchmarking ...................Elapsed milliseconds / relative speed for 65536 iteration(s):
  21.  
  22.     (MAKE-LIST-FROM N L)......1638 / 1.06 <fastest>
  23.     (MAKE-LIST-FROM1 N L).....1731 / 1.00 <slowest>
  24. _$ (setq l '(1 2 3 4 5) n 211)
  25. 211
  26. _$ (Benchmark '((make-list-from1 n l) (make-list-from n l)))
  27. Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):
  28.  
  29.     (MAKE-LIST-FROM1 N L).....1918 / 1.00 <fastest>
  30.     (MAKE-LIST-FROM N L)......1919 / 1.00 <slowest>
  31. _$ (setq l '(1 2 3 4 5) n 200)
  32. 200
  33. _$ (Benchmark '((make-list-from1 n l) (make-list-from n l)))
  34. Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):
  35.  
  36.     (MAKE-LIST-FROM N L)......1747 / 1.03 <fastest>
  37.     (MAKE-LIST-FROM1 N L).....1794 / 1.00 <slowest>
It is a slightly smaller defun though, and the efficiency is so similar as to be preferable. So perhaps I'll adopt your take on it.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Looking for a better way...
« Reply #41 on: June 28, 2012, 04:44:19 AM »
As far as the pairing is concerned, the first list is a set of integers which could vary in length from 1 to 100. The second list is a point list with exactly 11 lists of 3 reals. This length will never change. The counter will realistically be no less than 200, but more in the range of 750 to 1000. Perhaps these realistic figures will help to give a more accurate benchmark of the functions.
Well to see the benchmarking on all the functions to those values, use the attached's last function (PairupTest):
Code - Auto/Visual Lisp: [Select]
  1. _$ (PairupTest)
  2.  
  3. Testing with int list of 40 length, and counter of 930
  4. Benchmarking ................ done for 2048 iterations. Sorted from fastest.
  5. Statement                                Increment  Time(ms) Normalize  Relative
  6. --------------------------------------------------------------------------------
  7. (PAIRUP9 L1 L2 N)                             2048      1637      1637     15.72
  8. (PAIRUP10 L1 L2 N)                            2048      1637      1637     15.72
  9. (PAIRLISTS3 L1 L2 N)                          2048      1810      1810     14.21
  10. (PAIRLISTS L1 L2 N)                           1024      1310      2620      9.82
  11. (PAIRLISTS2 L1 L2 N)                          1024      1310      2620      9.82
  12. (PAIRUP8 L1 L2 N)                             1024      1622      3244      7.93
  13. (PAIRUP7 L1 L2 N)                             1024      1669      3338      7.71
  14. (PAIRUP6 L1 L2 N)                              512      1015      4060      6.34
  15. (PAIRUP5 L1 L2 N)                              512      1342      5368      4.79
  16. (PAIRUP2 L1 L2 N)                              512      1359      5436      4.73
  17. (PAIRUP4 L1 L2 N)                              512      1419      5676      4.53
  18. (PAIRCAB L1 L2 N)                              512      1483      5932      4.34
  19. (EEA-PAIRUP L1 L2 N)                           512      1484      5936      4.33
  20. (PAIRS L1 L2 N)                                512      1576      6304      4.08
  21. (PAIRUP3 L1 L2 N)                              128      1341     21456      1.20
  22. (PAIRUP1 L1 L2 N)                              128      1608     25728      1.00
  23. --------------------------------------------------------------------------------
That function might also be helpful in showing how to use these.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

bruno_vdh

  • Guest
Re: Looking for a better way...
« Reply #42 on: July 01, 2012, 06:29:27 PM »
Quote
It is a slightly smaller defun though, and the efficiency is so similar as to be preferable. So perhaps I'll adopt your take on it.

Hello, thank you for testing and personally I would keep this latest version:

Code: [Select]
(defun make-list-from (n l / x)
  (cond
    ((>= n (length l))
     (setq x l)
     (while (< (* (length x) 2) n) (setq x (append x x)))
     (append x (make-list-from (- n (length x)) l))
    )
    ((> n 0)
     (setq l (reverse l))
     (reverse (repeat (- (length l) n) (setq l (cdr l))))
    )
  )
)


For the following lines of code

   
Code: [Select]
(setq l (reverse l))
     (reverse (repeat (- (length l) n) (setq l (cdr l))))


For large lists, there are interesting variations publish on another forum ..
http://cadxp.com/index.php?/topic/19618-challenge-22/page__view__findpost__p__104345
http://cadxp.com/index.php?/topic/19618-challenge-22/page__view__findpost__p__104350

Sincerely,

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Looking for a better way...
« Reply #43 on: July 02, 2012, 02:40:33 AM »
Thanks for the links to Gile's codes ... though I've seen them before. The make-list idea doesn't have such issue though, it does the opposite of what Gile's code is trying. That simplistic butlastN idea I've used since it would hardly ever need to do that on a large list - note it cannot happen with anything larger than the sample list supplied (which would normally not be larger than a few hand-fulls of items).

E.g. my LastN function uses something similar to Gile's. Though I got that idea from Elpanov Evgeniy (as noted on that page).
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Looking for a better way...
« Reply #44 on: July 02, 2012, 04:46:07 AM »
If you want to have the best of both worlds:
Code - Auto/Visual Lisp: [Select]
  1. (defun make-list-from  (n l / x)
  2.   (cond ((>= n (length l))
  3.          (setq x l)
  4.          (while (< (* (length x) 2) n) (setq x (append x x)))
  5.          (append x (make-list-from (- n (length x)) l)))
  6.         ((> n 0)
  7.          (setq l (reverse l))
  8.          (repeat (/ (- (length l) n) 4) (setq l (cddddr l)))
  9.          (repeat (rem (- (length l) n) 4) (setq l (cdr l)))
  10.          (reverse l))))
Though if for one of the permutations n = (length l), then this would do an extra setq, less-than check, multiplication, 2x length, append, subtract and recursive call for no reason. That was the original reason I had the condition for ((= n (length l)) l). True it's only a borderline case, but it does happen since you're effectively working with factors, not just numbers. Though it's a nice idea to get rid of the test for n=zero - again having it as a test at the beginning would speed up borderline cases where the original n = some exponent of 2 times the length of l.

It's one of those situations where you have to decide if efficiency is more important and/or of greater value than elegance. In this case the efficiency gain is very small and only happens in a small subset of scenarios. So your more elegant code does seem preferable.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.