TheSwamp

Code Red => AutoLISP (Vanilla / Visual) => Topic started by: LibertyOne on June 23, 2012, 04:56:58 PM

Title: Looking for a better way...
Post by: LibertyOne on June 23, 2012, 04:56:58 PM

...to reprogram a bit of code.

I wrote a small program about 11 years ago (for AutoCAD R14), and at that time with my knowledge of AutoLisp that I had. I recently dug this code out, reevaluated it and made it work for AutoCAD 2010. Knowing what I know now, I have a feeling this code is a bit redundant and I'm looking for a way to shorten it or find a different solution.

The function does the following:

Starting with two lists of different length, it cycles through each one simultaneously pairing the atoms of each list. When one list comes to the end, it starts over from the beginning. The same with the other list. For example, the first list could have any number of atoms from 1 to the maximal allowed. The second list is an  list of points which are fixed at 11.

Added to the program is a counter that exits the program once so many paired items have gone through which the user sets at the beginning of the program.

The counter is a WHILE statement counting down the total number of points and the cycling is done with IF statements. At the time I wrote the program I didn't think COND could be an option because it would exit the program during the 11 point cycle. The program needs to continuously step through the 11 point cycle and has to decide if the point is to be carried out or not. If the counter is exhausted, then it stops at this point and exits the program.

I've listed the basic structure of the code to read through, but took out what it does to each point in the PROGN statement because it's not relevant. Trying to run it would fail.

The main question I have is if I could somehow get rid of all the IF statements and substitute them with something else.

If my question is not clear, just ask I'll try to explain it again. I look forward to hearing from you.

Code: [Select]

(setq num_pl 0)
        (setq        num 100)
(while (< num_pl num)
(if (< num_pl num)
(progn
(...pt01)
)
)
(command "_.change" el "" "_p" "_c" col_pl "")
(setq num_pl (1+ num_pl))
(if (< num_pl num)
(progn
(...pt02)
)
)
(setq num_pl (1+ num_pl))
(if (< num_pl num)
(progn
(...pt03)
)
)
(setq num_pl (1+ num_pl))
(if (< num_pl num)
(progn
(...pt04)
)
)
(setq num_pl (1+ num_pl))
(if (< num_pl num)
(progn
(...pt05)
)
)
(setq num_pl (1+ num_pl))
(if (< num_pl num)
(progn
(...pt06)
)
)
(setq num_pl (1+ num_pl))
(if (< num_pl num)
(progn
(...pt07)
)
)
(setq num_pl (1+ num_pl))
(if (< num_pl num)
(progn
(...pt08)
)
)
(setq num_pl (1+ num_pl))
(if (< num_pl num)
(progn
(...pt09)
)
)
(setq num_pl (1+ num_pl))
(if (< num_pl num)
(progn
(...pt10)
)
)
(setq num_pl (1+ num_pl))
(if (< num_pl num)
(progn
(...pt11)
)
)
)



Title: Re: Looking for a better way...
Post by: Lee Mac on June 23, 2012, 05:01:00 PM

What are each of these?

Code: [Select]

(...pt01)

(...pt02)

...

Title: Re: Looking for a better way...
Post by: LibertyOne on June 23, 2012, 05:05:40 PM

those are the points from the second list

Title: Re: Looking for a better way...
Post by: gile on June 23, 2012, 06:11:53 PM

hi,

Code: [Select]

(setq n 0)
(foreach n lst1
  (... (nth (rem n 11) lst2)) ; instead of pt0n
  (setq n (1+ n))
) 

Title: Re: Looking for a better way...
Post by: CAB on June 23, 2012, 08:43:08 PM

It's not clear what you are doing but this is a simple example of looping through two lists with a limit on the first list.

Code: [Select]

(defun c:test(/ idx)
  (defun do_something (x y)
    (print (+ x y))
  )
  (setq listA '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16)
        listB '(1 2 3 4 5 6 7 8 9 10 11)
        )

  (setq MaxListA 10) ; max number to process, why I don't know

 
  (setq idx 0) ; index pointer to listA
  (setq MaxListA (1- MaxListA)) ; make zero based
  (while
    (and
      (< idx MaxListA) ; did not exceed the max allowed
      (setq itm (nth idx ListA)) ; got a valid item
    )
    ;;  OK to process the item - 11 times from ListB
    (foreach B_item listB
      (do_something itm B_item)
    )
    (setq idx (1+ idx))
  ) ; endwhile
  (princ)
)

Title: Re: Looking for a better way...
Post by: LibertyOne on June 24, 2012, 09:29:41 AM

Thanks to everyone for their replies!

@CAB - my explanation may have not been as clear for all. There are basisly three things involved here. One list is a set of X and Y coordinates, the second list is a set of integers and the third thing is a counter, which the user defines in the beginning of the function. The counter corresponds to the amount of pairs which are made. The first list of items is paired with the second list of items.

Look at it like this: let's say the first list has 11 items and the second list has 4 items. The counter is set at 200. Now we want to make 200 pairs or matchups with the two lists. This means the second list is exhausted at 4, but cycles back through from the beginning. That means we have a pairing of the two lists like this:

Code: [Select]

(1 1) (2 2) (3 3) (4 4) (5 1) (6 2) (7 3) (8 4) (9 1) (10 2) (11 3) (1 4) (2 1) (3 2) ...

Notice how each list once it reaches the end it returns back to the beginning and starts over. This is to be done with each list until the counter reaches the end. In this case 200 pairs are made.

Perhaps this explanation is clearer.

Title: Re: Looking for a better way...
Post by: CAB on June 24, 2012, 11:41:02 AM

Try this:

Code: [Select]

(defun c:test(/ idxA idxB)
  (defun do_something (x y)
    (print (list x y))
  )
(setq lista '("a" "b" "c" "d" "e" "f" "g" "h" "i" "j" "k" "l")
      listB '(1 2 3 4 5 6 7 8 9 10 11)
        )

  (setq MaxPairs 20) ; max number to process, why I don't know

 
  (setq cnt 0 ; counter
        idxA 0 ; index pointer
        idxB 0 ; index pointer
        lenA (length ListA) ; length of list
        lenB (length ListB)
        )
  (while (< (setq cnt (1+ cnt)) MaxPairs)
    (do_something (nth idxA ListA) (nth idxB ListB))
    (setq idxB (1+ idxB))
    (if (= idxB lenB)
      (progn
        (setq idxA (1+ idxA)
              idxB 0)
        (if (= idxA lenA)
          (setq inxA 0)
        )
      )
    )
  ) ; endwhile
  (princ)
)

Title: Re: Looking for a better way...
Post by: Stefan on June 24, 2012, 01:37:07 PM

This will return a list of pairs, as you described

Code - Auto/Visual Lisp: [Select]

1. (defun pairs (l1 l2 i / n m j lst)
2.   (setq n (length l1)
3.         m (length l2)
4.         j 0
5.         )
6.   (repeat i
7.     (setq lst (cons (list (nth (rem j n) l1) (nth (rem j m) l2)) lst)
8.           j (1+ j)
9.           )
10.     )
11.   (reverse lst)
12. )
13.  

Code: [Select]

_$ (pairs '(1 2 3 4 5 6 7 8 9 10 11) '(1 2 3 4) 15)
((1 1) (2 2) (3 3) (4 4) (5 1) (6 2) (7 3) (8 4) (9 1) (10 2) (11 3) (1 4) (2 1) (3 2) (4 3))

Title: Re: Looking for a better way...
Post by: LibertyOne on June 24, 2012, 05:30:02 PM

Thanks for both replies. I'll be looking into both possibilities. I like the simplicity of Stefans code, but remember I still have the PROGN part to deal with. This is where CAB's code looks good.

The last two hours I've been sitting on the edge of my seat watching the European Cup and I'm sorry to see England lose to Italy. I think the Germans would have liked to have played them in the semi-final more. Sorry Lee  :-(

Haven't had time to test either but will do this tomorrow. Time to head to bed...

Title: Re: Looking for a better way...
Post by: Lee Mac on June 24, 2012, 06:16:10 PM

Some highly inefficient recursive solutions...

Code - Auto/Visual Lisp: [Select]

1. (defun pairup1 ( l1 l2 i )
2.     (if (< 0 i)
3.         (if (< (length l1) i)
4.             (pairup1 (append l1 l1) l2 i)
5.             (if (< (length l2) i)
6.                 (pairup1 l1 (append l2 l2) i)
7.                 (cons (list (car l1) (car l2))
8.                     (pairup1 (cdr l1) (cdr l2) (1- i))
9.                 )
10.             )
11.         )
12.     )
13. )

Code - Auto/Visual Lisp: [Select]

1. (defun pairup2 ( l1 l2 i )
2.     (if (< 0 i)
3.         (if (< (length l1) i)
4.             (pairup2 (append l1 l1) l2 i)
5.             (if (< (length l2) i)
6.                 (pairup2 l1 (append l2 l2) i)
7.                 (apply 'append
8.                     (mapcar
9.                        '(lambda ( a b ) (if (<= 0 (setq i (1- i))) (list (list a b))))
10.                         l1 l2
11.                     )
12.                 )
13.             )
14.         )
15.     )
16. )

Code - Auto/Visual Lisp: [Select]

1. (defun pairup3 ( l1 l2 i )
2.     (if (< 0 i)
3.         (cons (list (car l1) (car l2))
4.             (pairup3
5.                 (append (cdr l1) (list (car l1)))
6.                 (append (cdr l2) (list (car l2)))
7.                 (1- i)
8.             )
9.         )
10.     )
11. )

...still reeling from England's knock-out

Title: Re: Looking for a better way...
Post by: Lee Mac on June 24, 2012, 06:28:03 PM

One more...

Code - Auto/Visual Lisp: [Select]

1. (defun pairup4 ( l1 l2 n / l3 )
2.     (while (< (length l1) n) (setq l1 (append l1 l1)))
3.     (while (< (length l2) n) (setq l2 (append l2 l2)))
4.     (repeat n
5.         (setq l3 (cons (list (car l1) (car l2)) l3)
6.               l1 (cdr l1)
7.               l2 (cdr l2)
8.         )
9.     )
10.     (reverse l3)
11. )

Title: Re: Looking for a better way...
Post by: Lee Mac on June 24, 2012, 06:42:39 PM

Quick bench...

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 '((pairs l1 l2 n) (pairup1 l1 l2 n) (pairup2 l1 l2 n) (pairup3 l1 l2 n) (pairup4 l1 l2 n)))
4. Benchmarking ...............Elapsed milliseconds / relative speed for 4096 iteration(s):
5.  
6.     (PAIRUP2 L1 L2 N).....1809 / 2.32 <fastest>
7.     (PAIRUP4 L1 L2 N).....1981 / 2.12
8.     (PAIRS L1 L2 N).......2200 / 1.91
9.     (PAIRUP1 L1 L2 N).....4072 / 1.03
10.     (PAIRUP3 L1 L2 N).....4197 / 1 <slowest>

Title: Re: Looking for a better way...
Post by: Lee Mac on June 24, 2012, 06:54:15 PM

Minor optimisation...

Code - Auto/Visual Lisp: [Select]

1. (defun pairup5 ( l1 l2 i )
2.     (while (< (length l1) i) (setq l1 (append l1 l1)))
3.     (while (< (length l2) i) (setq l2 (append l2 l2)))
4.     (apply 'append
5.         (mapcar
6.            '(lambda ( a b ) (if (<= 0 (setq i (1- i))) (list (list a b))))
7.             l1 l2
8.         )
9.     )
10. )

Code - Auto/Visual Lisp: [Select]

1. Benchmarking ...............Elapsed milliseconds / relative speed for 4096 iteration(s):
2.  
3.     (PAIRUP5 L1 L2 N).....1763 / 2.33 <fastest>
4.     (PAIRUP2 L1 L2 N).....1810 / 2.27
5.     (PAIRUP4 L1 L2 N).....1981 / 2.07
6.     (PAIRS L1 L2 N).......2153 / 1.91
7.     (PAIRUP1 L1 L2 N).....4025 / 1.02
8.     (PAIRUP3 L1 L2 N).....4102 / 1 <slowest>

Title: Re: Looking for a better way...
Post by: Lee Mac on June 24, 2012, 07:26:27 PM

Code - Auto/Visual Lisp: [Select]

1. (defun pairup6 ( l1 l2 i / l3 )
2.     (while (< (length l1) i) (setq l1 (append l1 l1)))
3.     (while (< (length l2) i) (setq l2 (append l2 l2)))
4.     (repeat i (setq l3 (cons i l3)))
5.     (mapcar '(lambda ( a b c ) (list a b)) l1 l2 l3)
6. )

Code - Auto/Visual Lisp: [Select]

1. (defun pairup7 ( l1 l2 i / l3 )
2.     (while (< (length l1) i) (setq l1 (append l1 l1)))
3.     (while (< (length l2) i) (setq l2 (append l2 l2)))
4.     (setq l3 (list i))
5.     (repeat (fix (/ (log i) (log 2))) (setq l3 (append l3 l3)))
6.     (repeat (- i (length l3)) (setq l3 (cons i l3)))
7.     (mapcar '(lambda ( a b c ) (list a b)) l1 l2 l3)
8. )

Code - Auto/Visual Lisp: [Select]

1. (defun pairup8 ( l1 l2 i / l3 )
2.     (repeat (1+ (fix (/ (- (log i) (log (length l1))) (log 2)))) (setq l1 (append l1 l1)))
3.     (repeat (1+ (fix (/ (- (log i) (log (length l2))) (log 2)))) (setq l2 (append l2 l2)))
4.     (setq l3 (list i))
5.     (repeat (fix (/ (log i) (log 2))) (setq l3 (append l3 l3)))
6.     (repeat (- i (length l3)) (setq l3 (cons i l3)))
7.     (mapcar '(lambda ( a b c ) (list a b)) l1 l2 l3)
8. )

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 '((pairup5 l1 l2 n) (pairup6 l1 l2 n) (pairup7 l1 l2 n) (pairup8 l1 l2 n)))
4. Benchmarking ...............Elapsed milliseconds / relative speed for 4096 iteration(s):
5.  
6.     (PAIRUP7 L1 L2 N).....1263 / 1.4 <fastest>
7.     (PAIRUP8 L1 L2 N).....1279 / 1.38
8.     (PAIRUP6 L1 L2 N).....1498 / 1.18
9.     (PAIRUP5 L1 L2 N).....1762 / 1 <slowest>

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. (Benchmark
5.    '(
6.         (pairs   l1 l2 n)
7.         (pairup1 l1 l2 n)
8.         (pairup2 l1 l2 n)
9.         (pairup3 l1 l2 n)
10.         (pairup4 l1 l2 n)
11.         (pairup5 l1 l2 n)
12.         (pairup6 l1 l2 n)
13.         (pairup7 l1 l2 n)
14.         (pairup8 l1 l2 n)
15.     )
16. )
17.  
18. Benchmarking ...............Elapsed milliseconds / relative speed for 4096 iteration(s):
19.  
20.     (PAIRUP7 L1 L2 N).....1279 / 3.22 <fastest>
21.     (PAIRUP8 L1 L2 N).....1279 / 3.22
22.     (PAIRUP6 L1 L2 N).....1498 / 2.75
23.     (PAIRUP5 L1 L2 N).....1779 / 2.32
24.     (PAIRUP2 L1 L2 N).....1826 / 2.26
25.     (PAIRUP4 L1 L2 N).....1887 / 2.18
26.     (PAIRS L1 L2 N).......2059 / 2
27.     (PAIRUP1 L1 L2 N).....3900 / 1.06
28.     (PAIRUP3 L1 L2 N).....4119 / 1 <slowest>

Title: Re: Looking for a better way...
Post by: CAB on June 24, 2012, 07:53:21 PM

If you are sill awake over there how does my clunker hold up?

Code: [Select]

(defun paircab (lista listb maxpairs / idxa idxb lena lenb cnt)
  (setq cnt  0 ; counter
        idxa 0 ; index pointer
        idxb 0 ; index pointer
        lena (length lista) ; length of list
        lenb (length listb)
  )
  (while (< (setq cnt (1+ cnt)) maxpairs)
    (setq lst (cons (list (nth idxa lista) (nth idxb listb)) lst))
    (setq idxb (1+ idxb))
    (if (= idxb lenb)
      (progn
        (setq idxa (1+ idxa)  idxb 0)
        (if (= idxa lena)
          (setq inxa 0)
        )
      )
    )
  ) ; endwhile
  (reverse lst)
)

Title: Re: Looking for a better way...
Post by: Lee Mac on June 25, 2012, 05:58:23 AM

Quote from: CAB on June 24, 2012, 07:53:21 PM

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'  :-)

Title: Re: Looking for a better way...
Post by: irneb 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

Title: Re: Looking for a better way...
Post by: Lee Mac 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 :-)

Title: Re: Looking for a better way...
Post by: irneb 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.

Title: Re: Looking for a better way...
Post by: CAB 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>

Title: Re: Looking for a better way...
Post by: LibertyOne on June 26, 2012, 01:37:12 AM

So many options...I'm confused as what to do next... :oops:

Title: Re: Looking for a better way...
Post by: pBe 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
_$

Title: Re: Looking for a better way...
Post by: irneb 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
--------------------------------------------------------------------------------

Title: Re: Looking for a better way...
Post by: irneb 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
--------------------------------------------------------------------------------

Title: Re: Looking for a better way...
Post by: pBe on June 26, 2012, 04:06:14 AM

Quote from: irneb on June 26, 2012, 03:29:23 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   :-)

Title: Re: Looking for a better way...
Post by: irneb on June 26, 2012, 04:40:28 AM

Quote from: pBe on June 26, 2012, 04:06:14 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.

Title: Re: Looking for a better way...
Post by: irneb 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.   (apply (function append)
5.          (mapcar (function (lambda (a b)
6.                              (if (<= 0 (setq i (1- i)))
7.                                (list (list a b)))))
8.                  l1
9.                  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.

Title: Re: Looking for a better way...
Post by: Lee Mac 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. (setq
2.     l1 '(1 2 3 4 5 6 7)
3.     l2 '("a" "b" "c" "d" "e")
4.     n 200
5. )

In Irneb's function, following the exponential doubling operation, the initial lists have lengths 224 and 320 respectively (7x2⁵ | 5x2⁶), 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 (2⁹ - 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>

Title: Re: Looking for a better way...
Post by: irneb 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 (http://www.lispworks.com/documentation/HyperSpec/Body/f_mk_lis.htm#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:

Title: Re: Looking for a better way...
Post by: Lee Mac 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...

Title: Re: Looking for a better way...
Post by: irneb on June 26, 2012, 08:23:56 AM

Exactly! That's the "blank" I was mentioning hitting  ;)

Title: Re: Looking for a better way...
Post by: irneb 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.   (mapcar 'list
14.           (make-list-from pairs lst1)
15.           (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.

Title: Re: Looking for a better way...
Post by: Lee Mac on June 26, 2012, 02:47:07 PM

Well done Irne  :-)

Title: Re: Looking for a better way...
Post by: Lee Mac 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>

Title: Re: Looking for a better way...
Post by: ElpanovEvgeniy 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. )

Title: Re: Looking for a better way...
Post by: irneb 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.

Title: Re: Looking for a better way...
Post by: Lee Mac on June 27, 2012, 05:27:42 AM

Quote from: irneb on June 27, 2012, 03:36:36 AM

That's a very novel one EE!

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

Quote from: irneb on June 27, 2012, 03:36:36 AM

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  :-)

Quote from: irneb on June 27, 2012, 03:36:36 AM

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>

Title: Re: Looking for a better way...
Post by: bruno_vdh 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,

Title: Re: Looking for a better way...
Post by: LibertyOne on June 27, 2012, 12:37:36 PM

Quote from: Lee Mac 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. (setq
2.     l1 '(1 2 3 4 5 6 7)
3.     l2 '("a" "b" "c" "d" "e")
4.     n 200
5. )

In Irneb's function, following the exponential doubling operation, the initial lists have lengths 224 and 320 respectively (7x2⁵ | 5x2⁶), 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 (2⁹ - 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.

Title: Re: Looking for a better way...
Post by: Lee Mac 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  :-)

Title: Re: Looking for a better way...
Post by: irneb on June 28, 2012, 04:24:39 AM

Quote from: bruno_vdh 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...

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.

Title: Re: Looking for a better way...
Post by: irneb on June 28, 2012, 04:44:19 AM

Quote from: LibertyOne on June 27, 2012, 12:37:36 PM

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.

Title: Re: Looking for a better way...
Post by: bruno_vdh 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,

Title: Re: Looking for a better way...
Post by: irneb 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 (http://alisp-ext.wikidot.com/autolisp-firstn) function uses something similar to Gile's. Though I got that idea from Elpanov Evgeniy (as noted on that page).

Title: Re: Looking for a better way...
Post by: irneb 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.

Title: Re: Looking for a better way...
Post by: Stefan on July 02, 2012, 04:53:13 AM

I thought this topic is closed.
But if it was revived, I added another method for make-list.

Code - Auto/Visual Lisp: [Select]

1. (defun ph:make (l n / r)
2.   (setq r (list (mapcar '(lambda (x y) x) l (repeat (rem n (length l)) (setq r (cons 1 r))))))
3.   (apply 'append
4.      (repeat (/ n (length l)) (setq r (cons l r)))
5.     )
6.   )

However, I think the result can be improved if some other method is used instead of (repeat.
Pairs1 and Pairs2 code inside of test lisp.
Here are the results:

Code: [Select]

_$ (PairupTest)

Testing with int list of 95 length, and counter of 991
Benchmarking .................. done for 2048 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(PAIRS1 L1 L2 N)                              2048      1500      1500     26.33
(PAIRS2 L1 L2 N)                              2048      1608      1608     24.56
(PAIRUP10 L1 L2 N)                            2048      1937      1937     20.39
(PAIRLISTS3 L1 L2 N)                          1024      1048      2096     18.84
(PAIRUP9 L1 L2 N)                             1024      1062      2124     18.59
(PAIRLISTS L1 L2 N)                           1024      1686      3372     11.71
(PAIRLISTS2 L1 L2 N)                          1024      1702      3404     11.60
(PAIRUP7 L1 L2 N)                              512      1093      4372      9.03
(PAIRUP8 L1 L2 N)                              512      1109      4436      8.90
(PAIRUP6 L1 L2 N)                              512      1296      5184      7.62
(PAIRUP5 L1 L2 N)                              512      1765      7060      5.59
(PAIRUP2 L1 L2 N)                              512      1861      7444      5.30
(PAIRUP4 L1 L2 N)                              512      1890      7560      5.22
(EEA-PAIRUP L1 L2 N)                           256      1109      8872      4.45
(PAIRCAB L1 L2 N)                              256      1188      9504      4.15
(PAIRS L1 L2 N)                                256      1283     10264      3.85
(PAIRUP3 L1 L2 N)                              128      1937     30992      1.27
(PAIRUP1 L1 L2 N)                               64      1234     39488      1.00
--------------------------------------------------------------------------------

Title: Re: Looking for a better way...
Post by: irneb on July 02, 2012, 05:26:41 AM

Awesome! That one's actually a lot nicer ... and faster!

Although, just be careful of running into the same trap I've run into before:

Code - Auto/Visual Lisp: [Select]

1. _$ (ph:make '(1 2 3 4 5 6 7) 5)
2. nil

Title: Re: Looking for a better way...
Post by: irneb on July 02, 2012, 05:34:11 AM

Hope you don't mind ... I've altered the make-list-from:

Code - Auto/Visual Lisp: [Select]

1. (defun make-list-from  (n l / r)
2.   (if (= n (length l))
3.     l
4.     (progn
5.       (setq r (list (mapcar '(lambda (x y) x) l (repeat (rem n (length l)) (setq r (cons 1 r))))))
6.       (if (< n (length l))
7.         r
8.         (apply 'append (repeat (/ n (length l)) (setq r (cons l r))))))))

Now the benchmarking's a bit different:

Code - Auto/Visual Lisp: [Select]

1. _$ (PairupTest)
2.  
3. Testing with int list of 48 length, and counter of 814
4. --------------------------------------------------------------------------------
5. Testing for correctness in relation to the PAIRS function:
6. PAIRUP1 = T
7. PAIRUP2 = T
8. PAIRUP3 = T
9. PAIRUP4 = T
10. PAIRUP5 = T
11. PAIRCAB = nil
12. PAIRUP6 = T
13. PAIRUP7 = T
14. PAIRUP8 = T
15. PAIRUP9 = T
16. PAIRLISTS = T
17. PAIRLISTS2 = T
18. PAIRLISTS3 = T
19. EEA-PAIRUP = T
20. PAIRUP10 = T
21. PAIRS1 = T
22. PAIRS2 = T
23.  
24. Benchmarking .................. done for 2048 iterations. Sorted from fastest.
25. Statement                                Increment  Time(ms) Normalize  Relative
26. --------------------------------------------------------------------------------
27. (PAIRS1 L1 L2 N)                              2048      1435      1435     21.92
28. (PAIRLISTS3 L1 L2 N)                          2048      1685      1685     18.67
29. (PAIRS2 L1 L2 N)                              2048      1686      1686     18.66
30. (PAIRUP9 L1 L2 N)                             2048      1777      1777     17.70
31. (PAIRUP10 L1 L2 N)                            2048      1841      1841     17.09
32. (PAIRUP8 L1 L2 N)                              512      1076      4304      7.31
33. (PAIRUP7 L1 L2 N)                              512      1077      4308      7.30
34. (PAIRLISTS L1 L2 N)                            512      1092      4368      7.20
35. (PAIRLISTS2 L1 L2 N)                           512      1092      4368      7.20
36. (PAIRUP6 L1 L2 N)                              512      1435      5740      5.48
37. (PAIRUP4 L1 L2 N)                              512      1966      7864      4.00
38. (PAIRUP5 L1 L2 N)                              512      2027      8108      3.88
39. (PAIRS L1 L2 N)                                256      1045      8360      3.76
40. (PAIRCAB L1 L2 N)                              256      1045      8360      3.76
41. (PAIRUP2 L1 L2 N)                              256      1047      8376      3.76
42. (EEA-PAIRUP L1 L2 N)                           256      1139      9112      3.45
43. (PAIRUP3 L1 L2 N)                              128      1451     23216      1.35
44. (PAIRUP1 L1 L2 N)                              128      1966     31456      1.00
45. --------------------------------------------------------------------------------

Title: Re: Looking for a better way...
Post by: Stefan on July 02, 2012, 06:07:51 AM

OMG you're right.
This

Code: [Select]

(if (< n (length l))
       rshould be

Code: [Select]

(if (< n (length l))
       (car r)

Title: Re: Looking for a better way...
Post by: irneb on July 02, 2012, 06:15:56 AM

Thanks yes, I should've noticed  :-[

Title: Re: Looking for a better way...
Post by: chlh_jd on July 09, 2012, 10:19:08 AM

For short list perhaps  :lol:

Code: [Select]

(defun ph:make  (l n / r f1)
  (defun f1(n l) (setq l (reverse l)) (repeat (- (length l) n) (setq l (cdr l)))(reverse l))
  (setq r (list (f1 (rem n (length l)) l)))
  (apply 'append (repeat (/ n (length l)) (setq r (cons l r)))))