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

0 Members and 1 Guest are viewing this topic.

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: Looking for a better way...
« Reply #15 on: June 25, 2012, 05:58:23 AM »
If you are sill awake over there how does my clunker hold up?

Not quite CAB  :wink:

Code: [Select]
_$ (paircab '(1 2 3) '("a" "b") 8)
((1 "a") (1 "b") (2 "a") (2 "b") (3 "a") (3 "b") (nil "a"))

Code: [Select]
_$ (pairup7 '(1 2 3) '("a" "b") 8)
((1 "a") (2 "b") (3 "a") (1 "b") (2 "a") (3 "b") (1 "a") (2 "b"))

Also, be sure to localise 'lst'  :-)

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Looking for a better way...
« Reply #16 on: June 25, 2012, 06:27:23 AM »
My version:
Code - Auto/Visual Lisp: [Select]
  1. (defun PairLists (lst1 lst2 pairs / )
  2.   (while (< (length lst1) pairs) (setq lst1 (append lst1 lst1)))
  3.   (while (< (length lst2) pairs) (setq lst2 (append lst2 lst2)))
  4.   (setq lst1 (reverse (mapcar 'list lst1 lst2)))
  5.   (reverse (repeat (- (length lst1) pairs) (setq lst1 (cdr lst1)))))
And it seems to be faster:
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)) '(PAIRUP5 PAIRUP6 PAIRUP7 PAIRUP8 PAIRLISTS paircab)))
Benchmarking ...... done for 8192 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(PAIRLISTS L1 L2 N)                           8192      1701      1701     27.30
(PAIRUP7 L1 L2 N)                             4096      1387      2774     16.74
(PAIRUP8 L1 L2 N)                             4096      1388      2776     16.73
(PAIRUP6 L1 L2 N)                             4096      1763      3526     13.17
(PAIRUP5 L1 L2 N)                             4096      1980      3960     11.73
(PAIRCAB L1 L2 N)                              256      1451     46432      1.00
--------------------------------------------------------------------------------
And it gives the same result:
Code: [Select]
_$ (equal (PairLists l1 l2 n) (pairup5 l1 l2 n))
T
« Last Edit: June 25, 2012, 06:32:04 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: 12906
  • London, England
Re: Looking for a better way...
« Reply #17 on: June 25, 2012, 06:45:23 AM »
I would've thought the reverse calls would have slowed the processing, but apparently not!

Code - Auto/Visual Lisp: [Select]
  1. _$ (benchmark '((pairup7 l1 l2 n) (pairup6 l1 l2 n) (pairup5 l1 l2 n) (pairlists l1 l2 n)))
  2. Benchmarking ................Elapsed milliseconds / relative speed for 8192 iteration(s):
  3.  
  4.     (PAIRLISTS L1 L2 N).....1794 / 1.94 <fastest>
  5.     (PAIRUP7 L1 L2 N).......2481 / 1.4
  6.     (PAIRUP6 L1 L2 N).......2949 / 1.18
  7.     (PAIRUP5 L1 L2 N).......3478 / 1 <slowest>

Nice one Irne :-)

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Looking for a better way...
« Reply #18 on: June 25, 2012, 07:02:24 AM »
Yep, I also thought so until a few days ago when I found something like this and actually did the test. Another thing which is quite strange is the slight difference between your pairup7 and -8. It seems that a call to length is actually extremely efficient. If it was only moderately efficient 8 should have been a bit quicker since the calculation is only done once, while in 7 the call to length is done at least 5 times.

It must be something to do with the implementation of lists in AutoLisp. Perhaps it's implemented as a doubly-linked-list with a count property. Thus length is simply a variable, and reverse is a setting to use the prior pointer instead of the next pointer and visa-versa. Well that's AFAICT what's going on. I know it "has" to be a linked list and not a dynamic array, since nth isn't all that fast compared to car - otherwise there would have been no difference in speed between the 2.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

CAB

  • Global Moderator
  • Seagull
  • Posts: 10401
Re: Looking for a better way...
« Reply #19 on: June 25, 2012, 11:43:35 PM »
Finally had time to get mine debugged.  :oops:
Code: [Select]
(defun paircab (lista listb maxpairs / idxa idxb lena lenb cnt lst)
  (setq cnt  0
        idxa 0
        idxb 0
        lena (length lista)
        lenb (length listb)
  )
  (while (<= (setq cnt (1+ cnt)) maxpairs)
    (setq lst (cons (list (nth idxa lista) (nth idxb listb)) lst))
    (if (= (setq idxb (1+ idxb)) lenb)
      (progn
        (setq idxa (1+ idxa)  idxb 0)
        (if (= idxa lena)  (setq idxa 0))))
  ) ; endwhile
  (reverse lst)
)

Code: [Select]
Benchmarking [M.P. 2005] ...............Elapsed milliseconds for 4096 iteration(s)/ relative Timing :

    (PAIRUP1 L1 L2 N).....3401 / 4.0344 <slowest>
    (PAIRUP3 L1 L2 N).....2886 / 3.4235
    (PAIRS L1 L2 N).......1544 / 1.8316
    (PAIRCAB L1 L2 N).....1497 / 1.7758
    (PAIRUP4 L1 L2 N).....1357 / 1.6097
    (PAIRUP2 L1 L2 N).....1248 / 1.4804
    (PAIRUP5 L1 L2 N).....1186 / 1.4069
    (PAIRUP6 L1 L2 N).....1014 / 1.2028
    (PAIRUP7 L1 L2 N)......858 / 1.0178
    (PAIRUP8 L1 L2 N)......843 / 1.0000 <fastest>
I've reached the age where the happy hour is a nap. (°¿°)
Windows 10 core i7 4790k 4Ghz 32GB GTX 970
Please support this web site.

LibertyOne

  • Guest
Re: Looking for a better way...
« Reply #20 on: June 26, 2012, 01:37:12 AM »
So many options...I'm confused as what to do next... :oops:


pBe

  • Bull Frog
  • Posts: 402
Re: Looking for a better way...
« Reply #21 on: June 26, 2012, 02:57:59 AM »
Code - Auto/Visual Lisp: [Select]
  1. (defun _iterNilAt  (func l1 l2 n / i non)
  2.       (setq i 0)
  3.       (while (< i n)
  4.             (if (not (setq x (apply 'func (list l1 l2 (setq i (1+ i))))))
  5.                         (setq non (cons i non)))
  6.             )
  7.       (reverse non)
  8.       )

Watch out....

(_iterNilAt PairLists l1 l2 200)
(5 7 10 14 20 28 40 56 80 112 160) ; <--- nil value at  n

(_iterNilAt Paircab l1 l2 200)
nil

(_iterNilAt pairup6 l1 l2 200)
nil

Code - Auto/Visual Lisp: [Select]
  1. (defun _iterEnd (func l1 l2 n / i r)
  2. (setq i 0)      
  3. (while (< i n)
  4.        (if (setq x  (apply 'func (list l1 l2 (setq  i (1+ i) r i))))
  5.                       (print x)(setq r (1- i) i n))
  6.       )
  7. (princ (strcat "\nEnd at "  (itoa r)))(princ)
  8.       )
Code: [Select]
_$ (_iterEnd pairup6 l1 l2 8)

((1 "a"))
((1 "a") (2 "b"))
((1 "a") (2 "b") (3 "c"))
((1 "a") (2 "b") (3 "c") (4 "d"))
((1 "a") (2 "b") (3 "c") (4 "d") (5 "e"))
((1 "a") (2 "b") (3 "c") (4 "d") (5 "e") (6 "a"))
((1 "a") (2 "b") (3 "c") (4 "d") (5 "e") (6 "a") (7 "b"))
((1 "a") (2 "b") (3 "c") (4 "d") (5 "e") (6 "a") (7 "b") (1 "c"))
End at 8
_$ (_iterEnd paircab l1 l2 8)

((1 "a"))
((1 "a") (1 "b"))
((1 "a") (1 "b") (1 "c"))
((1 "a") (1 "b") (1 "c") (1 "d"))
((1 "a") (1 "b") (1 "c") (1 "d") (1 "e"))
((1 "a") (1 "b") (1 "c") (1 "d") (1 "e") (2 "a"))
((1 "a") (1 "b") (1 "c") (1 "d") (1 "e") (2 "a") (2 "b"))
((1 "a") (1 "b") (1 "c") (1 "d") (1 "e") (2 "a") (2 "b") (2 "c"))
End at 8
_$ (_iterEnd PairLists l1 l2 8)

((1 "a"))
((1 "a") (2 "b"))
((1 "a") (2 "b") (3 "c"))
((1 "a") (2 "b") (3 "c") (4 "d"))
End at 4
_$


irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Looking for a better way...
« Reply #22 on: June 26, 2012, 03:29:23 AM »
Sorry, yes I should've thought of that!  :-[

Here's the fix:
Code - Auto/Visual Lisp: [Select]
  1. (defun PairLists2  (lst1 lst2 pairs /)
  2.   (while (< (length lst1) pairs) (setq lst1 (append lst1 lst1)))
  3.   (while (< (length lst2) pairs) (setq lst2 (append lst2 lst2)))
  4.   (setq lst1 (reverse (mapcar 'list lst1 lst2)))
  5.   (repeat (- (length lst1) pairs) (setq lst1 (cdr lst1)))
  6.   (reverse lst1))
No real difference from the original's speed
Code: [Select]
Benchmarking ............ done for 4096 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(PAIRLISTS2 L1 L2 N)                          4096      1030      1030      4.97
(PAIRLISTS L1 L2 N)                           4096      1060      1060      4.83
(PAIRUP8 L1 L2 N)                             4096      1485      1485      3.45
(PAIRUP7 L1 L2 N)                             4096      1575      1575      3.25
(PAIRUP6 L1 L2 N)                             4096      1842      1842      2.78
(PAIRUP5 L1 L2 N)                             2048      1030      2060      2.49
(PAIRUP2 L1 L2 N)                             2048      1139      2278      2.25
(PAIRUP4 L1 L2 N)                             2048      1184      2368      2.16
(PAIRS L1 L2 N)                               2048      1325      2650      1.93
(PAIRCAB L1 L2 N)                             2048      1325      2650      1.93
(PAIRUP3 L1 L2 N)                             1024      1200      4800      1.07
(PAIRUP1 L1 L2 N)                             1024      1280      5120      1.00
--------------------------------------------------------------------------------
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 #23 on: June 26, 2012, 04:00:04 AM »
And of course the recursive methods don't gain much from compiling:
Code: [Select]
Benchmarking ............ done for 8192 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(PAIRLISTS L1 L2 N)                           8192      1872      1872      4.37
(PAIRLISTS2 L1 L2 N)                          8192      1888      1888      4.33
(PAIRUP8 L1 L2 N)                             4096      1389      2778      2.94
(PAIRUP7 L1 L2 N)                             4096      1405      2810      2.91
(PAIRUP4 L1 L2 N)                             4096      1420      2840      2.88
(PAIRUP6 L1 L2 N)                             4096      1435      2870      2.85
(PAIRS L1 L2 N)                               4096      1622      3244      2.52
(PAIRCAB L1 L2 N)                             4096      1809      3618      2.26
(PAIRUP2 L1 L2 N)                             2048      1046      4184      1.95
(PAIRUP5 L1 L2 N)                             2048      1062      4248      1.92
(PAIRUP3 L1 L2 N)                             2048      1997      7988      1.02
(PAIRUP1 L1 L2 N)                             2048      2043      8172      1.00
--------------------------------------------------------------------------------
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

pBe

  • Bull Frog
  • Posts: 402
Re: Looking for a better way...
« Reply #24 on: June 26, 2012, 04:06:14 AM »

Here's the fix:
Code - Auto/Visual Lisp: [Select]
  1. (defun PairLists2  (lst1 lst2 pairs /)
  2.   (while (< (length lst1) pairs) (setq lst1 (append lst1 lst1)))
  3.   (while (< (length lst2) pairs) (setq lst2 (append lst2 lst2)))
  4.   (setq lst1 (reverse (mapcar 'list lst1 lst2)))
  5.   (repeat (- (length lst1) pairs) (setq lst1 (cdr lst1)))
  6.   (reverse lst1))


Nice recover   :-)

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Looking for a better way...
« Reply #25 on: June 26, 2012, 04:40:28 AM »
Nice recover   :)
A situation of trying to make it too elegant and forgetting borderline situations like binary-exponent factor lengths  :pissed:   - making for repeat 0 times --> nil.
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 #26 on: June 26, 2012, 04:59:22 AM »
BTW, notice Lee's pairup5 loosing ground on all the others when compiling? Here's why:
Code - Auto/Visual Lisp: [Select]
  1. (defun pairup5a (l1 l2 i)
  2.   (while (< (length l1) i) (setq l1 (append l1 l1)))
  3.   (while (< (length l2) i) (setq l2 (append l2 l2)))
  4.          (mapcar (function (lambda (a b)
  5.                              (if (<= 0 (setq i (1- i)))
  6.                                (list (list a b)))))
  7.                  l1
  8.                  l2)))
And the test before compiling:
Code: [Select]
Benchmarking .. done for 2048 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(PAIRUP5 L1 L2 N)                             2048      1108      1108      1.10
(PAIRUP5A L1 L2 N)                            2048      1216      1216      1.00
--------------------------------------------------------------------------------
Actually looks like it less efficient doesn't it ... but wait:
Code: [Select]
Benchmarking .. done for 4096 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(PAIRUP5A L1 L2 N)                            4096      1981      1981      1.17
(PAIRUP5 L1 L2 N)                             2048      1156      2312      1.00
--------------------------------------------------------------------------------
Although it still doesn't gain enough to move it up in the list.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: Looking for a better way...
« Reply #27 on: June 26, 2012, 07:24:25 AM »
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 expected, here are the results:

Code - Auto/Visual Lisp: [Select]
  1. _$ (benchmark '((pairup7 '(1 2) '("a" "b") 257) (pairlists2 '(1 2) '("a" "b") 257)))
  2. Benchmarking ...............Elapsed milliseconds / relative speed for 4096 iteration(s):
  3.  
  4.     (PAIRUP7 (QUOTE (1 2)) (QUOTE ("a" ....).....1560 / 1.39 <fastest>
  5.     (PAIRLISTS2 (QUOTE (1 2)) (QUOTE ("a"..).....2168 / 1 <slowest>

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Looking for a better way...
« Reply #28 on: June 26, 2012, 07:54:51 AM »
Very good point Lee! I was thinking of doing it the same manner as I used to implement my version of the CL function make-list:
Code - Auto/Visual Lisp: [Select]
  1. (defun make-list (size initial-element / lst)
  2.   (if (> size 0)
  3.     (progn (setq lst (list initial-element))
  4.       (while (< (* (length lst) 2) size) (setq lst (append lst lst)))
  5.       (append lst (make-list (- size (length lst)) initial-element)))))
But I hit a blank ... probably just a blank in my head  :lmao:
« Last Edit: June 26, 2012, 07:59:11 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: 12906
  • London, England
Re: Looking for a better way...
« Reply #29 on: June 26, 2012, 08:11:16 AM »
Nice idea Irne, using the binary representation of the resultant list length; however, that method could be difficult for this task as the corresponding 'initial-element' parameter will vary for each list, depending on the number of items already appended...