mAssoc implementations

January 10, 2011

For those who don't know what it is, it performs an assoc on a dotted pair list. But instead of only returning the 1st item found, returns all items matching the code. So as an example a call like: (mAlloc 1 '((1 . 4) (2 . 5) (1 . 3))) should result in: (4 3). It's sometimes used when working with LWPolylines (as they tend to contain numerous code 10's), other entities also sometimes contain multiple codes of the same.

The usual one I find when doing a google is something like this:

(defun mAssoc (Key Alist)
   (cond
       ((null Alist) '())
       (T
        (if (= (caar Alist) Key)
            (cons (cdr (car Alist)) (mAssoc Key (cdr Alist)))
            (mAssoc Key (cdr Alist))
        )
       )
   )
)

However, this uses recursion, which could use up a lot of ram on a very long list. I suppose an iterative approach is possible ... but I wanted something as simple and efficient as possible. So I came up with the following:

(defun mAssoc (key lst /)
 (mapcar 'cdr (vl-remove-if-not (function (lambda (item) (= key (car item)))) lst))
)

Thought I'd share with the community. Any comments / suggestions?

January 10, 2011

So I came up with the following:

(defun mAssoc (key lst /)
 (mapcar 'cdr (vl-remove-if-not (function (lambda (item) (= key (car item)))) lst))
)

That's the construction I would usually implement - or perhaps:

(defun mAssoc ( key lst / result )
 (foreach x lst
   (if (= key (car x))
     (setq result (cons (cdr x) result))
   )
 )
 (reverse result)
)

Lee

January 10, 2011

That's the construction I would usually implement - or perhaps:
(defun mAssoc ( key lst / result )
 (foreach x lst
   (if (= key (car x))
     (setq result (cons (cdr x) result))
   )
 )
 (reverse result)
)
Lee

Or what about this:

(defun mAssocI (key lst / item res n)
 (setq n (length lst))
 (while (>= (setq n (1- n)) 0)
   (setq item (nth n lst))
   (if (= key (car item))
     (setq res (cons (cdr item) res))
   )
 )
)

No need for the reverse. Though I'm not sure if the nth is as efficient as foreach.

January 10, 2011

And then just for fun :wink: I tried doing the recursion a bit more efficiently:

(defun mAssocR1 (key lst / res)
 (if (and lst (setq res (assoc key lst)))
   (cons (cdr res) (mAssocR1 key (cdr (member res lst))))
 )
)

But I think that's going to be less efficient due to the member call.

January 10, 2011

I test using eq in lieu of =. You get more latitude by testing expressions than numeric values. -David

January 10, 2011

?? (Just wanting to play along)

(defun mAssoc (asslist edata)
 (apply (function append)
        (mapcar (function (lambda (x)
                            (if (member (car x) asslist)
                              (list x)
                            )
                          )
                )
                edata
        )
 )
)

January 10, 2011

Just as a test, I used a benchmarking on an association list of 10000 items repeating the function call 1000 times. The list is generated thus:

(defun random (/ modulus multiplier increment random)
 (if (not seed)
   (setq seed (getvar "DATE"))
 )
 (setq modulus    65536
       multiplier 25173
       increment  13849
       seed  (rem (+ (* multiplier seed) increment) modulus)
       random     (/ seed modulus)
 )
)

(defun random1 (maximum / num)
 (setq num (* (random) maximum))
 (if (= (type maximum) 'INT)
   (fix num)
   num
 )
)

Command: (setq lst nil)
Command: (repeat 10000 (setq lst (cons (cons (random1 20) (random1 1000.0))
Command: (length (mAssocI 1 lst))
479

The benchmark code:

(setq BenchStart nil)
(defun BenchTime (start / millisecs)
 (if start
   (setq BenchStart (getvar "Millisecs"))
   (if BenchStart
     (progn
       (princ (strcat "\nElapsed: " (rtos (* 0.001 (- (getvar "Millisecs") BenchStart)))))
       (setq BenchStart nil)
     )
     (princ "\nThere's an error. The bechmark wasn't started yet.")
   )
 )
 t
)

The functions are as follows:

mAssocR - the original recursive
mAssoc - the vl method
mAssocI1 - Lee's iterative method
mAssocI - my iterative method
mAssocR1 - my take on the recursive method

Results:

Command: (progn (BenchTime t) (repeat 1000 (mAssocR 1 lst)) (BenchTime nil))
Elapsed: 44.6560T

Command: (progn (BenchTime t) (repeat 1000 (mAssoc 1 lst)) (BenchTime nil))
Elapsed: 9.9850T

Command: (progn (BenchTime t) (repeat 1000 (mAssocI1 1 lst)) (BenchTime nil))
Elapsed: 19.4690T

Command: (progn (BenchTime t) (repeat 1000 (mAssocI 1 lst)) (BenchTime nil))
Elapsed: 430.8600T

Command: (progn (BenchTime t) (repeat 1000 (mAssocR1 1 lst)) (BenchTime nil))
Elapsed: 3.2190T

As you can see the clear winner is the recursive using the normal assoc & member calls, then the vl. My iterative version is stupidly slow - I think it's due to the nth having to step through the list each time.

As for using eq instead of = ... that's probably a good idea, since the normal assoc also works with strings as key values. The mAssocR1 would not need a change - since it uses assoc directly. But here're the results for the vl, Lee's iterative & the original recursive:

Command: (progn (BenchTime t) (repeat 1000 (mAssoc-e 1 lst)) (BenchTime nil))
Elapsed: 9.2500T

Command: (progn (BenchTime t) (repeat 1000 (mAssocI1-e 1 lst)) (BenchTime nil))
Elapsed: 19.0310T

Command: (progn (BenchTime t) (repeat 1000 (mAssocR-e 1 lst)) (BenchTime nil))
Elapsed: 21.8750T

It's actually faster than using = ... not so much, but ... well ... why not then?

January 10, 2011

Nice idea Alan. Yours can extract more than one key value in one go. However, your time is on par with the original recursive method:

Command: (progn (BenchTime t) (repeat 1000 (mAssocA '(1) lst)) (BenchTime nil))
Elapsed: 21.9370T

January 10, 2011

My test

Benchmark data (random1 function see #7)

(setq lst nil)
(repeat 100 (setq lst (cons (cons (random1 20) (random1 1000.0)) lst)))

Massoc function

(defun mAssocR (Key Alist)
   (cond
       ((null Alist) '())
       (T
        (if (= (caar Alist) Key)
            (cons (cdr (car Alist)) (mAssocR Key (cdr Alist)))
            (mAssocR Key (cdr Alist))
        )
       )
   )
)

(defun mAssocVL (key lst /)
 (mapcar 'cdr (vl-remove-if-not (function (lambda (item) (= key (car item)))) lst))
)

(defun mAssocLee ( key lst / result )
 (foreach x lst
   (if (= key (car x))
     (setq result (cons (cdr x) result))
   )
 )
 (reverse result)
)
(defun mAssocI (key lst / item res n)
 (setq n (length lst))
 (while (>= (setq n (1- n)) 0)
   (setq item (nth n lst))
   (if (= key (car item))
     (setq res (cons (cdr item) res))
   )
 )
)
(defun mAssocR1 (key lst / res)
 (if (and lst (setq res (assoc key lst)))
   (cons (cdr res) (mAssocR1 key (cdr (member res lst))))
 )
)
(defun mAssocAlanjt (asslist edata)
 (apply (function append)
        (mapcar (function (lambda (x)
                            (if (member (car x) asslist)
                              (list x)
                            )
                          )
                )
                edata
        )
 )
)

Benchmark Code

Result

(BenchMark
    '(
                 (mAssocR 1 lst)
                 (mAssocVL 1 lst)
                 (mAssocLee 1 lst)
                 (mAssocI 1 lst)
                 (mAssocR1 1 lst)
                 (mAssocAlanjt (list 1) lst)
             )
        )

_$

Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

(MASSOCR1 1 LST)................1219 / 4.43

(MASSOCVL 1 LST)................2469 / 2.19

(MASSOCLEE 1 LST)...............3203 / 1.69

(MASSOCALANJT (LIST 1) LST).....3281 / 1.65

(MASSOCR 1 LST).................4328 / 1.25

(MASSOCI 1 LST).................5406 / 1.00

_$

January 11, 2011

Thanks for the Benchmark proggy ... that one's a lot nicer! I've modified all the = to eq:

(defun mAssocR (Key Alist)
   (cond
       ((null Alist) '())
       (T
        (if (eq (caar Alist) Key)
            (cons (cdr (car Alist)) (mAssocR Key (cdr Alist)))
            (mAssocR Key (cdr Alist))
        )
       )
   )
)

(defun mAssocVL (key lst /)
 (mapcar 'cdr (vl-remove-if-not (function (lambda (item) (eq key (car item)))) lst))
)

(defun mAssocLee ( key lst / result )
 (foreach x lst
   (if (eq key (car x))
     (setq result (cons (cdr x) result))
   )
 )
 (reverse result)
)
(defun mAssocI (key lst / item res n)
 (setq n (length lst))
 (while (>= (setq n (1- n)) 0)
   (setq item (nth n lst))
   (if (eq key (car item))
     (setq res (cons (cdr item) res))
   )
 )
)
(defun mAssocR1 (key lst / res)
 (if (and lst (setq res (assoc key lst)))
   (cons (cdr res) (mAssocR1 key (cdr (member res lst))))
 )
)
(defun mAssocAlanjt (asslist edata)
 (apply (function append)
        (mapcar (function (lambda (x)
                            (if (member (car x) asslist)
                              (list x)
                            )
                          )
                )
                edata
        )
 )
)

Anyhow, you seem to get the same results (at least the order seems to be the same). I was actually surprised that the R1 method's the fastest. From some other discussions I've noticed that the member function isn't the fastest thing in the world (e.g. rather use vl-position to check if an item is in a list than using member). But this result shows just how optimized lisp's internal functions are for use in lists.

Obviously assoc and member uses something a lot quicker than simply stepping through the list with mapcar / foreach / recursion and cdr. However, I think there would be an optimum ... I assume that when there's relatively few items to pick from the list the mAssocR1 would outperform the others. But if the items to extract gets proportionately more, I think the timings would tend towards those of mAssocR's. Where exactly this optimum lies I don't know.

For example

(progn
 (setq n 0)
 (while (< (setq n (1+ n)) 10)
   (setq lst nil)
   (repeat 100 (setq lst (cons (cons (random1 n) (random1 1000.0)) lst)))
   (princ "\n\nBenchmarking mAssoc @ ")
   (princ (length (mAssocVL 1 lst)))
   (princ "% items in list.\n")
   (BenchMark
     '(
       (mAssocR 1 lst)
       (mAssocVL 1 lst)
       (mAssocLee 1 lst)
       (mAssocI 1 lst)
       (mAssocR1 1 lst)
       (mAssocAlanjt (list 1) lst)
      )
   )
 )
)

Benchmarking mAssoc @ 0% items in list.
Elapsed milliseconds / relative speed for 32768 iteration(s):

(MASSOCR1 1 LST)................1000 / 7.28

(MASSOCVL 1 LST)................2766 / 2.63

(MASSOCLEE 1 LST)...............3656 / 1.99

(MASSOCALANJT (LIST 1) LST).....4406 / 1.65

(MASSOCR 1 LST).................5391 / 1.35

(MASSOCI 1 LST).................7281 / 1

Benchmarking mAssoc @ 56% items in list.

Elapsed milliseconds / relative speed for 16384 iteration(s):

(MASSOCVL 1 LST)................1609 / 2.59

(MASSOCR1 1 LST)................2172 / 1.92

(MASSOCLEE 1 LST)...............2406 / 1.73

(MASSOCALANJT (LIST 1) LST).....2547 / 1.64

(MASSOCR 1 LST).................3250 / 1.28

(MASSOCI 1 LST).................4172 / 1

Benchmarking mAssoc @ 37% items in list.

Elapsed milliseconds / relative speed for 16384 iteration(s):

(MASSOCVL 1 LST)................1562 / 2.56

(MASSOCR1 1 LST)................1687 / 2.37

(MASSOCLEE 1 LST)...............2219 / 1.8

(MASSOCALANJT (LIST 1) LST).....2438 / 1.64

(MASSOCR 1 LST).................3078 / 1.3

(MASSOCI 1 LST).................4000 / 1

Benchmarking mAssoc @ 29% items in list.

Elapsed milliseconds / relative speed for 16384 iteration(s):

(MASSOCR1 1 LST)................1468 / 2.68

(MASSOCVL 1 LST)................1531 / 2.57

(MASSOCLEE 1 LST)...............2141 / 1.84

(MASSOCALANJT (LIST 1) LST).....2391 / 1.65

(MASSOCR 1 LST).................3016 / 1.31

(MASSOCI 1 LST).................3937 / 1

Benchmarking mAssoc @ 17% items in list.

Elapsed milliseconds / relative speed for 16384 iteration(s):

(MASSOCR1 1 LST)................1141 / 3.35

(MASSOCVL 1 LST)................1516 / 2.53

(MASSOCLEE 1 LST)...............2016 / 1.9

(MASSOCALANJT (LIST 1) LST).....2312 / 1.66

(MASSOCR 1 LST).................2875 / 1.33

(MASSOCI 1 LST).................3828 / 1

Benchmarking mAssoc @ 13% items in list.

Elapsed milliseconds / relative speed for 16384 iteration(s):

(MASSOCR1 1 LST)................1031 / 3.68

(MASSOCVL 1 LST)................1500 / 2.53

(MASSOCLEE 1 LST)...............1985 / 1.91

(MASSOCALANJT (LIST 1) LST).....2297 / 1.65

(MASSOCR 1 LST).................2859 / 1.33

(MASSOCI 1 LST).................3796 / 1

Benchmarking mAssoc @ 8% items in list.

Elapsed milliseconds / relative speed for 32768 iteration(s):

(MASSOCR1 1 LST)................1796 / 4.18

(MASSOCVL 1 LST)................2984 / 2.51

(MASSOCLEE 1 LST)...............3860 / 1.94

(MASSOCALANJT (LIST 1) LST).....4579 / 1.64

(MASSOCR 1 LST).................5594 / 1.34

(MASSOCI 1 LST).................7500 / 1

Benchmarking mAssoc @ 14% items in list.

Elapsed milliseconds / relative speed for 16384 iteration(s):

(MASSOCR1 1 LST)................1078 / 3.54

(MASSOCVL 1 LST)................1500 / 2.54

(MASSOCLEE 1 LST)...............2000 / 1.91

(MASSOCALANJT (LIST 1) LST).....2297 / 1.66

(MASSOCR 1 LST).................2859 / 1.33

(MASSOCI 1 LST).................3812 / 1

Benchmarking mAssoc @ 5% items in list.

Elapsed milliseconds / relative speed for 32768 iteration(s):

(MASSOCR1 1 LST)................1531 / 4.84

(MASSOCVL 1 LST)................2969 / 2.49

(MASSOCLEE 1 LST)...............3782 / 1.96

(MASSOCALANJT (LIST 1) LST).....4516 / 1.64

(MASSOCR 1 LST).................5531 / 1.34

(MASSOCI 1 LST).................7406 / 1

Due to the random the 2nd last is a bit out of sync (but the rest do show the trend). From 30% and below (i.e. 1 out of 3 items in the list to be extracted) the mAssocR1 is faster than the rest, from just faster than the VL to about twice as fast at 5%. The others seem to stay pretty much the same order.

January 11, 2011

Irneb,

Where would something like this stand?

(defun LM:MAssoc ( key lst / pair return )
 (while (setq pair (assoc key lst))
   (setq return (cons (cdr pair) return) lst (cdr (member pair lst)))
 )
 (reverse return)
)

Of course, you lose speed in the reverse, but gain perhaps by not using recursion to iterate the list - I figure the list to be reversed is, in most cases, much shorter than the list to be processed so this may not be as detrimental to performance as first thought.

Another for consideration is acet-list-m-assoc, but bear in mind this is likely to be quicker due to optimisation/linking when 'compiled'. Also this function returns the association complete with the key, rather than just the association.

Lee

January 12, 2011

Yep, I think you're correct (on both counts). The following test:

(progn
 (setq n 0)
 (while (< (setq n (1+ n)) 10)
   (setq lst nil)
   (repeat 100 (setq lst (cons (cons (random1 n) (random1 1000.0)) lst)))
   (princ "\n\nBenchmarking mAssoc @ ")
   (princ (length (mAssocVL 1 lst)))
   (princ "% items in list.\n")
   (BenchMark
     '(
       ;; (mAssocR 1 lst)
       (mAssocVL 1 lst)
       ;; (mAssocLee 1 lst)
       ;; (mAssocI 1 lst)
       (mAssocR1 1 lst)
       ;; (mAssocAlanjt (list 1) lst)
       (LM:MAssoc 1 lst)
       (mapcar 'cdr (acet-list-m-assoc 1 lst))
      )
   )
 )
)

Produces these results:

Benchmarking mAssoc @ 0% items in list.
Elapsed milliseconds / relative speed for 32768 iteration(s):
(LM:MASSOC 1 LST)............................1172 / 2.65 <fastest>
(MASSOCR1 1 LST).............................1187 / 2.62
(MAPCAR (QUOTE CDR) (ACET-LIST-M-ASS...).....1375 / 2.26
(MASSOCVL 1 LST).............................3110 / 1.00 <slowest>


Benchmarking mAssoc @ 45% items in list.
Elapsed milliseconds / relative speed for 16384 iteration(s):
(MAPCAR (QUOTE CDR) (ACET-LIST-M-ASS...).....1687 / 1.23 <fastest>
(MASSOCVL 1 LST).............................1781 / 1.17
(LM:MASSOC 1 LST)............................1922 / 1.08
(MASSOCR1 1 LST).............................2078 / 1.00 <slowest>


Benchmarking mAssoc @ 39% items in list.
Elapsed milliseconds / relative speed for 16384 iteration(s):
(MAPCAR (QUOTE CDR) (ACET-LIST-M-ASS...).....1578 / 1.20 <fastest>
(MASSOCVL 1 LST).............................1750 / 1.08
(LM:MASSOC 1 LST)............................1766 / 1.07
(MASSOCR1 1 LST).............................1890 / 1.00 <slowest>


Benchmarking mAssoc @ 23% items in list.
Elapsed milliseconds / relative speed for 8192 iteration(s):
(MAPCAR (QUOTE CDR) (ACET-LIST-M-ASS...).....1110 / 1.66 <fastest>
(LM:MASSOC 1 LST)............................1234 / 1.49
(MASSOCR1 1 LST).............................1328 / 1.39
(MASSOCVL 1 LST).............................1843 / 1.00 <slowest>


Benchmarking mAssoc @ 20% items in list.
Elapsed milliseconds / relative speed for 8192 iteration(s):
(MAPCAR (QUOTE CDR) (ACET-LIST-M-ASS...).....1078 / 1.71 <fastest>
(LM:MASSOC 1 LST)............................1156 / 1.59
(MASSOCR1 1 LST).............................1234 / 1.49
(MASSOCVL 1 LST).............................1843 / 1.00 <slowest>


Benchmarking mAssoc @ 16% items in list.
Elapsed milliseconds / relative speed for 8192 iteration(s):
(LM:MASSOC 1 LST)............................1047 / 1.75 <fastest>
(MAPCAR (QUOTE CDR) (ACET-LIST-M-ASS...).....1047 / 1.75
(MASSOCR1 1 LST).............................1109 / 1.65
(MASSOCVL 1 LST).............................1828 / 1.00 <slowest>


Benchmarking mAssoc @ 21% items in list.
Elapsed milliseconds / relative speed for 8192 iteration(s):
(MAPCAR (QUOTE CDR) (ACET-LIST-M-ASS...).....1078 / 1.71 <fastest>
(LM:MASSOC 1 LST)............................1187 / 1.55
(MASSOCR1 1 LST).............................1266 / 1.46
(MASSOCVL 1 LST).............................1843 / 1.00 <slowest>


Benchmarking mAssoc @ 18% items in list.
Elapsed milliseconds / relative speed for 8192 iteration(s):
(MAPCAR (QUOTE CDR) (ACET-LIST-M-ASS...).....1062 / 1.74 <fastest>
(LM:MASSOC 1 LST)............................1110 / 1.66
(MASSOCR1 1 LST).............................1187 / 1.55
(MASSOCVL 1 LST).............................1844 / 1.00 <slowest>


Benchmarking mAssoc @ 10% items in list.
Elapsed milliseconds / relative speed for 16384 iteration(s):
(LM:MASSOC 1 LST)............................1797 / 2.09 <fastest>
(MASSOCR1 1 LST).............................1875 / 2.00
(MAPCAR (QUOTE CDR) (ACET-LIST-M-ASS...).....2032 / 1.85
(MASSOCVL 1 LST).............................3750 / 1.00 <slowest>

Your 2nd iterative method consistently outperforms my R1 (although ever so slightly). But the acet-list-m-assoc outperforms everything in most cases, except equal to yours at 15% and worse than both at 0%.

Of course one could go and compile the test functions into a FAS file and see if that would speed the others up as well (retesting even those which were slow):

Benchmarking mAssoc @ 0% items in list.
Elapsed milliseconds / relative speed for 32768 iteration(s):
(LM:MASSOC 1 LST)............................1000 / 5.42 <fastest>
(MASSOCR1 1 LST).............................1015 / 5.34
(MAPCAR (QUOTE CDR) (ACET-LIST-M-ASS...).....1219 / 4.45
(MASSOCLEE 1 LST)............................1906 / 2.84
(MASSOCVL 1 LST).............................2625 / 2.07
(MASSOCALANJT (LIST 1) LST)..................3985 / 1.36
(MASSOCR 1 LST)..............................4281 / 1.27
(MASSOCI 1 LST)..............................5422 / 1.00 <slowest>


Benchmarking mAssoc @ 57% items in list.
Elapsed milliseconds / relative speed for 16384 iteration(s):
(MASSOCLEE 1 LST)............................1297 / 2.37 <fastest>
(MASSOCVL 1 LST).............................1516 / 2.03
(LM:MASSOC 1 LST)............................1563 / 1.97
(MAPCAR (QUOTE CDR) (ACET-LIST-M-ASS...).....1750 / 1.76
(MASSOCR1 1 LST).............................1859 / 1.66
(MASSOCALANJT (LIST 1) LST)..................2313 / 1.33
(MASSOCR 1 LST)..............................2562 / 1.20
(MASSOCI 1 LST)..............................3078 / 1.00 <slowest>


Benchmarking mAssoc @ 34% items in list.
Elapsed milliseconds / relative speed for 16384 iteration(s):
(MASSOCLEE 1 LST)............................1156 / 2.54 <fastest>
(LM:MASSOC 1 LST)............................1219 / 2.41
(MASSOCR1 1 LST).............................1391 / 2.11
(MAPCAR (QUOTE CDR) (ACET-LIST-M-ASS...).....1391 / 2.11
(MASSOCVL 1 LST).............................1453 / 2.02
(MASSOCALANJT (LIST 1) LST)..................2172 / 1.35
(MASSOCR 1 LST)..............................2422 / 1.21
(MASSOCI 1 LST)..............................2938 / 1.00 <slowest>


Benchmarking mAssoc @ 21% items in list.
Elapsed milliseconds / relative speed for 16384 iteration(s):
(LM:MASSOC 1 LST)............................1015 / 2.80 <fastest>
(MASSOCLEE 1 LST)............................1079 / 2.64
(MASSOCR1 1 LST).............................1125 / 2.53
(MAPCAR (QUOTE CDR) (ACET-LIST-M-ASS...).....1188 / 2.39
(MASSOCVL 1 LST).............................1421 / 2.00
(MASSOCALANJT (LIST 1) LST)..................2110 / 1.35
(MASSOCR 1 LST)..............................2313 / 1.23
(MASSOCI 1 LST)..............................2844 / 1.00 <slowest>


Benchmarking mAssoc @ 23% items in list.
Elapsed milliseconds / relative speed for 16384 iteration(s):
(LM:MASSOC 1 LST)............................1562 / 2.24 <fastest>
(MASSOCLEE 1 LST)............................1594 / 2.20
(MASSOCR1 1 LST).............................1703 / 2.06
(MAPCAR (QUOTE CDR) (ACET-LIST-M-ASS...).....2141 / 1.63
(MASSOCVL 1 LST).............................2641 / 1.33
(MASSOCR 1 LST)..............................2906 / 1.20
(MASSOCI 1 LST)..............................3437 / 1.02
(MASSOCALANJT (LIST 1) LST)..................3500 / 1.00 <slowest>


Benchmarking mAssoc @ 16% items in list.
Elapsed milliseconds / relative speed for 16384 iteration(s):
(LM:MASSOC 1 LST)............................1453 / 2.40 <fastest>
(MASSOCR1 1 LST).............................1546 / 2.25
(MASSOCLEE 1 LST)............................1547 / 2.25
(MAPCAR (QUOTE CDR) (ACET-LIST-M-ASS...).....2031 / 1.72
(MASSOCVL 1 LST).............................2641 / 1.32
(MASSOCR 1 LST)..............................2844 / 1.23
(MASSOCI 1 LST)..............................3375 / 1.03
(MASSOCALANJT (LIST 1) LST)..................3485 / 1.00 <slowest>


Benchmarking mAssoc @ 18% items in list.
Elapsed milliseconds / relative speed for 16384 iteration(s):
(LM:MASSOC 1 LST)............................1469 / 2.38 <fastest>
(MASSOCLEE 1 LST)............................1562 / 2.24
(MASSOCR1 1 LST).............................1594 / 2.20
(MAPCAR (QUOTE CDR) (ACET-LIST-M-ASS...).....2344 / 1.49
(MASSOCVL 1 LST).............................2656 / 1.32
(MASSOCR 1 LST)..............................2860 / 1.22
(MASSOCI 1 LST)..............................3391 / 1.03
(MASSOCALANJT (LIST 1) LST)..................3500 / 1.00 <slowest>


Benchmarking mAssoc @ 10% items in list.
Elapsed milliseconds / relative speed for 16384 iteration(s):
(LM:MASSOC 1 LST)............................1844 / 2.66 <fastest>
(MASSOCR1 1 LST).............................1922 / 2.55
(MASSOCLEE 1 LST)............................2015 / 2.43
(MAPCAR (QUOTE CDR) (ACET-LIST-M-ASS...).....2828 / 1.73
(MASSOCR 1 LST)..............................3359 / 1.46
(MASSOCVL 1 LST).............................3875 / 1.27
(MASSOCI 1 LST)..............................3906 / 1.26
(MASSOCALANJT (LIST 1) LST)..................4906 / 1.00 <slowest>


Benchmarking mAssoc @ 12% items in list.
Elapsed milliseconds / relative speed for 16384 iteration(s):
(LM:MASSOC 1 LST)............................1859 / 2.64 <fastest>
(MASSOCR1 1 LST).............................1969 / 2.49
(MASSOCLEE 1 LST)............................2031 / 2.42
(MAPCAR (QUOTE CDR) (ACET-LIST-M-ASS...).....2844 / 1.73
(MASSOCR 1 LST)..............................3375 / 1.45
(MASSOCVL 1 LST).............................3891 / 1.26
(MASSOCI 1 LST)..............................3922 / 1.25
(MASSOCALANJT (LIST 1) LST)..................4906 / 1.00 <slowest>

So giving them all an equal chance shows that the acet method's not that fast at all. Strangely the FAS optimization seems to do more for that extremely slow iterative method of mine than for Alan's multiple key method.

Not to mention ... your 1st iterative seems to benefit greatly from FAS optimization, while the vl method doesn't get any better at all.

January 12, 2011

Interesting results Irneb!

I'm surprised by how much the order changes through FAS optimisation...

January 12, 2011

I'm not too surprised :wink: ... compilation optimization is quite a dark-magic ... performing better optimizations in some instances, while it could even make for slower as well (hopefully not ). Maybe the optimization of foreach is extremely good, but with while and recursive it's not as good, while mapcar doesn't seem to have much at all. And the VL code would not have a lot of optimization available to it - it's probably already using some internal ARX code, so the FAS is still just calling that.

January 12, 2011

I'm not too surprised :wink: ... compilation optimization is quite a dark-magic ... performing better optimizations in some instances, while it could even make for slower as well (hopefully not ). Maybe the optimization of foreach is extremely good, but with while and recursive it's not as good, while mapcar doesn't seem to have much at all. And the VL code would not have a lot of optimization available to it - it's probably already using some internal ARX code, so the FAS is still just calling that.

True, some good points - perhaps I'm too easily surprised

Sign In

mAssoc implementations

Recommended Posts

irneb

Lee Mac

irneb

irneb

David Bethel

alanjt

irneb

irneb

VVA

irneb

Lee Mac

irneb

Lee Mac

irneb

Lee Mac

Join the conversation

Tutorials

Forums

Activity