Author Topic: Assoc List - Group By Keys  (Read 8070 times)

0 Members and 1 Guest are viewing this topic.

Grrr1337

  • Swamp Rat
  • Posts: 812
Assoc List - Group By Keys
« on: October 06, 2017, 05:01:30 PM »
Hi guys,
Just sharing this one (and hoping I won't loose it again) :

Code - Auto/Visual Lisp: [Select]
  1. (defun GroupByKeys ( aL / nL )
  2.   (mapcar
  3.     (function
  4.       (lambda (x / k ov nv sL)
  5.         (if (listp x)
  6.           (cond
  7.             ( (setq sL (assoc (setq k (car x)) nL)) (setq ov (cdr sL)) (setq nv (cdr x))
  8.               (setq nL (subst (cons k (append (if (atom ov) (list ov) ov) (if (atom nv) (list nv) nv))) sL nL)) ; (subst newitem olditem lst) - I have bad memory
  9.             )
  10.             ( (setq nL (cons x nL)) )
  11.           ); cond
  12.         )
  13.       ); lambda
  14.     ); function
  15.     aL
  16.   ); mapcar
  17.   (reverse nL)
  18. ); defun GroupByKeys

Here are the results/what it does :

Code - Auto/Visual Lisp: [Select]
  1. _$ (GroupByKeys nil)
  2. nil
  3.  
  4. _$ (GroupByKeys '("A" "B" "C"))
  5. nil
  6.  
  7. _$ (GroupByKeys
  8.   '(("KeyA" . "Info1")("KeyB" . "Info1")("KeyC" . "Info1")
  9.     ("KeyA" . "Info2")("KeyB" . "Info2")("KeyC" . "Info2")
  10.     ("KeyA" . "Info3")("KeyB" . "Info3")("KeyC" . "Info3")
  11.     ("KeyA" . "Info4")("KeyB" . "Info4")("KeyC" . "Info4")
  12.   )
  13. )
  14. (("KeyA" "Info1" "Info2" "Info3" "Info4") ("KeyB" "Info1" "Info2" "Info3" "Info4") ("KeyC" "Info1" "Info2" "Info3" "Info4"))
  15.  
  16. _$ (GroupByKeys
  17.   '(("KeyA" "Info1Aa" "Info1Ba" "Info1Ca")("KeyB" "Info1Ab" "Info1Bb" "Info1Cb")("KeyC" "Info1")
  18.     ("KeyA" "Info2Aa" "Info2Ba" "Info2Ca")("KeyB" "Info2Ab" "Info2Bb" "Info2Cb")("KeyC" "Info2")
  19.   )
  20. )
  21. (("KeyA" "Info1Aa" "Info1Ba" "Info1Ca" "Info2Aa" "Info2Ba" "Info2Ca") ("KeyB" "Info1Ab" "Info1Bb" "Info1Cb" "Info2Ab" "Info2Bb" "Info2Cb") ("KeyC" "Info1" "Info2"))
  22.  
  23. _$ (GroupByKeys (entget (car (entsel "\nPick Polyline: "))))
  24. ((-1 . <Entity name: 1ce8146d10>)
  25.   (0 . "LWPOLYLINE")
  26.   (330 . <Entity name: 1ce81419f0>)
  27.   (5 . "269")
  28.   (100 "AcDbEntity" "AcDbPolyline")
  29.   (67 . 0)
  30.   (410 . "Model")
  31.   (8 . "0")
  32.   (90 . 4)
  33.   (70 . 1)
  34.   (43 . 0.0)
  35.   (38 . 0.0)
  36.   (39 . 0.0)
  37.   (10 0.0 0.0 0.0 95.0 95.0 95.0 95.0 0.0)
  38.   (40 0.0 0.0 0.0 0.0)
  39.   (41 0.0 0.0 0.0 0.0)
  40.   (42 0.0 0.0 0.0 0.0)
  41.   (91 0 0 0 0)
  42.   (210 0.0 0.0 1.0)
  43. )

Now, I remembered having routine like this - but got it lost in my lisp archives, so I wrote it from scratch again.
...And after another search... TA-DA! found the old one:

Code - Auto/Visual Lisp: [Select]
  1. ; Groups the second elements for every duplicate key
  2. ; _$ (assoc 10 (NestAssoc (entget (car (entsel "\nSelect a LWpolyline: "))))) --> (10 (-15516.0 17644.3) (-15772.5 17644.3) (-15772.5 17423.9) (-15516.0 17423.9))
  3. ; _$ (NestAssoc '(("A" . 1)("B" . 1)("A" . 1)("C" . 1)("A" . 1)("B" . 1)("D" . 1)("D" . 1)("C" . 1)("B" . 1)))
  4. ; (("A" 1 1 1) ("B" 1 1 1) ("C" 1 1) ("D" 1 1))
  5. ; _$
  6. (defun NestAssoc ( enx / UQkeys )
  7.   (if (and (vl-consp enx) (vl-every 'vl-consp enx))
  8.     (progn
  9.       (mapcar (function (lambda (x) (if (not (member x UQkeys)) (setq UQkeys (cons x UQkeys))))) (mapcar 'car enx))
  10.       (reverse
  11.         (mapcar ; iterate thru the keys
  12.           (function
  13.             (lambda (key)
  14.               (append (list key)
  15.                 (mapcar 'cdr (vl-remove-if-not (function (lambda (x) (= key (car x)))) enx)); iterate thru the assoc list
  16.               ); append
  17.             ); lambda
  18.           ); function
  19.           UQkeys
  20.         ); mapcar
  21.       ); reverse
  22.     ); progn
  23.   ); if
  24. ); defun NestAssoc

And yeah, it has a bit different returns - so I guess to use what suits the case.

Now you might ask me where I'm using this:
By prompting for a selection of attributed blocks(filtering by certain blockname) I'm constructing an assoc list of items like: (<Tag String> <Text String Values>)
Then generating and populating some ACAD_TABLE.

Cheers!
(apply ''((a b c)(a b c))
  '(
    (( f L ) (apply 'strcat (f L)))
    (( L ) (if L (cons (chr (car L)) (f (cdr L)))))
    (72 101 108 108 111 32 87 111 114 108 100)
  )
)
vevo.bg

Lee Mac

  • Seagull
  • Posts: 12904
  • London, England
Re: Assoc List - Group By Keys
« Reply #1 on: October 07, 2017, 05:42:45 AM »
Thank you for sharing Grr1337.

In my experience, you wouldn't typically construct a function which includes conditionals to test for variations in the data type of the supplied argument: since you are developing the program, you know ahead of time the data that will eventually be supplied to the function, and can therefore construct the function accordingly.

For example, I think it would be very rare to develop a program in which a function would process a data set in the form of an association list of dotted pairs, and subsequently process a list of lists in the same manner. The developer would likely decide ahead of time which data type is better suited to storing the required data and would develop the appropriate function accordingly.

As such, for dotted pairs, I would use this:
Code - Auto/Visual Lisp: [Select]
  1. (defun groupbykey ( lst / rtn tmp )
  2.     (foreach itm (reverse lst)
  3.         (if (setq tmp (assoc (car itm) rtn))
  4.             (setq rtn (subst (vl-list* (car itm) (cdr itm) (cdr tmp)) tmp rtn))
  5.             (setq rtn (cons  (list (car itm) (cdr itm)) rtn))
  6.         )
  7.     )
  8. )

And for nested lists, I would use:
Code - Auto/Visual Lisp: [Select]
  1. (defun groupbykey ( lst / rtn tmp )
  2.     (foreach itm (reverse lst)
  3.         (if (setq tmp (assoc (car itm) rtn))
  4.             (setq rtn (subst (append itm (cdr tmp)) tmp rtn))
  5.             (setq rtn (cons itm rtn))
  6.         )
  7.     )
  8. )

fools

  • Newt
  • Posts: 72
  • China
Re: Assoc List - Group By Keys
« Reply #2 on: October 07, 2017, 09:18:59 AM »
Sort list before grouping them is recommended. No sort, the time's complexity is O(n2/2), sort and group is O(nLOGn).

Code - Auto/Visual Lisp: [Select]
  1. ;;Sort and Group (dotted pairs) by Fools, 2017.10.7
  2. ;;A non-nested list must do (mapcar 'list lst) before sort. Because duplicate elements may be eliminated from the list.
  3. (defun groupbykey-Fools (lst / tmp out)
  4.   (setq lst (vl-sort lst (function (lambda (x1 x2) (> (car x1) (car x2)))))) ;_sort
  5.   (setq tmp (list (cdar lst) (caar lst))) ;_first
  6.   (foreach item (cdr lst)
  7.     (if (= (car item) (last tmp))
  8.       (setq tmp (cons (cdr item) tmp))
  9.       (setq out (cons (reverse tmp) out)
  10.             tmp (list (cdr item) (car item))
  11.       )
  12.     )
  13.   )
  14.   (cons (reverse tmp) out) ;_last
  15. )

Test four function:
LM:randrange see http://www.lee-mac.com/random.html
Code - Auto/Visual Lisp: [Select]
  1. ;; Random list
  2. (defun F-RanLst (n / lst) (repeat n (setq lst (cons (cons (chr (LM:randrange 65 90)) 1) lst))))
  3.  
  4. ;;test1 only contain 70 elements
  5. (setq test1 (F-RanLst 70))  


_$ (benchmark '((groupbykey-Fools test1) (groupbykey-LeeMac test1) (GroupByKeys-Grrr1337 test1) (NestAssoc-Grrr1337 test1)))

Benchmarking ...............Elapsed milliseconds / relative speed for 4096 iteration(s):
    (GROUPBYKEY-FOOLS TEST1).........1701 / 3.55 <fastest>
    (GROUPBYKEY-LEEMAC TEST1)........1810 / 3.34
    (GROUPBYKEYS-GRRR1337 TEST1).....2168 / 2.79
    (NESTASSOC-GRRR1337 TEST1).......6038 / 1 <slowest>
Good good study , day day up . Sorry about my Chinglish .

fools

  • Newt
  • Posts: 72
  • China
Re: Assoc List - Group By Keys
« Reply #3 on: October 07, 2017, 09:25:55 AM »
_$ (groupbykey-Fools test1)
(("A" 1 1 1 1) ("B" 1 1) ("C" 1 1 1 1 1) ("D" 1 1 1) ("E" 1 1) ("F" 1 1 1 1) ("G" 1 1) ("H" 1 1 1) ("I" 1) ("J" 1) ("K" 1 1 1) ("L" 1 1) ("M" 1) ("N" 1 1 1) ("O" 1 1 1) ("P" 1 1 1 1 1 1) ("Q" 1 1) ("R" 1 1 1) ("S" 1) ("T" 1) ("V" 1 1 1 1 1) ("W" 1) ("X" 1 1 1 1) ("Y" 1 1 1 1 1) ("Z" 1 1 1))
Good good study , day day up . Sorry about my Chinglish .

Lee Mac

  • Seagull
  • Posts: 12904
  • London, England
Re: Assoc List - Group By Keys
« Reply #4 on: October 07, 2017, 10:02:00 AM »
Good optimisation Fools  :-)

Here's another method, but not likely to be quick:
Code - Auto/Visual Lisp: [Select]
  1. (defun groupbykey ( lst / key tmp )
  2.     (if (setq key (caar lst))
  3.         (setq lst (vl-remove-if '(lambda ( x ) (if (= key (car x)) (setq tmp (cons (cdr x) tmp)))) lst)
  4.               lst (cons (cons key (reverse tmp)) (groupbykey lst))
  5.         )
  6.     )
  7. )

fools

  • Newt
  • Posts: 72
  • China
Re: Assoc List - Group By Keys
« Reply #5 on: October 07, 2017, 10:22:30 AM »
Thanks for your encouragement, Lee. :-D
Good good study , day day up . Sorry about my Chinglish .

Lee Mac

  • Seagull
  • Posts: 12904
  • London, England
Re: Assoc List - Group By Keys
« Reply #6 on: October 07, 2017, 11:13:53 AM »
Another variation:
Code - Auto/Visual Lisp: [Select]
  1. (defun groupbykey ( lst / key rtn )
  2.     (foreach itm lst
  3.         (or (assoc (setq key (car itm)) rtn)
  4.             (setq rtn (cons (cons key (massoc key lst)) rtn))
  5.         )
  6.     )
  7.     (reverse rtn)
  8. )
  9. (defun massoc ( key lst / ass )
  10.     (if (setq ass (assoc key lst))
  11.         (cons (cdr ass) (massoc key (cdr (member ass lst))))
  12.     )
  13. )

Grrr1337

  • Swamp Rat
  • Posts: 812
Re: Assoc List - Group By Keys
« Reply #7 on: October 07, 2017, 12:37:05 PM »

Thank you for sharing Grr1337.

Hi Lee! :)

In my experience, you wouldn't typically construct a function which includes conditionals to test for variations in the data type of the supplied argument: since you are developing the program, you know ahead of time the data that will eventually be supplied to the function, and can therefore construct the function accordingly.
For example, I think it would be very rare to develop a program in which a function would process a data set in the form of an association list of dotted pairs, and subsequently process a list of lists in the same manner. The developer would likely decide ahead of time which data type is better suited to storing the required data and would develop the appropriate function accordingly.

I agree that this is an "uneffective" approach:
Quote
"Simplier" list construction, and then reconstruct that list, using a subfunction.
but I've tried constructing before a list like the expected (in the main program), without any need of such subfunction.
The problem was maintaining the code: writing new versions or similar codes(that use the same approach) - required a reminder-investigations of what I did back then (keeping off my concentration on the significant part).
So IMO the "KISS" principle for the main code is worthy for the cost of unnoticeable function slow-down.



I've forgot that this type of iteration is not effective - by mapping a function to the list I'm about to operate, when my intention is to construct a new list from scratch.
Hence should used foreach instead (like I see in your example codes).
Also yeah, I could used the if function instead of cond (I've just built myself a habit to avoid if and use and / or / cond conditionals).

Your first suggested function processes exactly like I'd wanted (construct a sublists in the cdr - for each instance with the same key) :

Code - Auto/Visual Lisp: [Select]
  1. (defun groupbykey ( lst / rtn tmp )
  2.   (foreach itm (reverse lst)
  3.     (if (setq tmp (assoc (car itm) rtn))
  4.       (setq rtn (subst (vl-list* (car itm) (cdr itm) (cdr tmp)) tmp rtn))
  5.       (setq rtn (cons  (list (car itm) (cdr itm)) rtn))
  6.     )
  7.   )
  8. )

Code - Auto/Visual Lisp: [Select]
  1. _$ (GroupByKey
  2.   '(("KeyA" "Info1Aa" "Info1Ba" "Info1Ca")("KeyB" "Info1Ab" "Info1Bb" "Info1Cb")("KeyC" "Info1")
  3.     ("KeyA" "Info2Aa" "Info2Ba" "Info2Ca")("KeyB" "Info2Ab" "Info2Bb" "Info2Cb")("KeyC" "Info2")
  4.   )
  5. )
  6. (("KeyA" ("Info1Aa" "Info1Ba" "Info1Ca") ("Info2Aa" "Info2Ba" "Info2Ca")) ("KeyB" ("Info1Ab" "Info1Bb" "Info1Cb") ("Info2Ab" "Info2Bb" "Info2Cb")) ("KeyC" ("Info1") ("Info2")))

My result is not that clean:
Code - Auto/Visual Lisp: [Select]
  1. (GroupByKeys
  2.   '(("KeyA" "Info1Aa" "Info1Ba" "Info1Ca")("KeyB" "Info1Ab" "Info1Bb" "Info1Cb")("KeyC" "Info1")
  3.     ("KeyA" "Info2Aa" "Info2Ba" "Info2Ca")("KeyB" "Info2Ab" "Info2Bb" "Info2Cb")("KeyC" "Info2")
  4.   )
  5. )
  6. (("KeyA" "Info1Aa" "Info1Ba" "Info1Ca" "Info2Aa" "Info2Ba" "Info2Ca") ("KeyB" "Info1Ab" "Info1Bb" "Info1Cb" "Info2Ab" "Info2Bb" "Info2Cb") ("KeyC" "Info1" "Info2"))


Sort list before grouping them is recommended. No sort, the time's complexity is O(n2/2), sort and group is O(nLOGn).

I always thought that sorting is redundant and slows down the function, when its used for tasks other than.. sorting.
But with this benchmark you proved me wrong!

(apply ''((a b c)(a b c))
  '(
    (( f L ) (apply 'strcat (f L)))
    (( L ) (if L (cons (chr (car L)) (f (cdr L)))))
    (72 101 108 108 111 32 87 111 114 108 100)
  )
)
vevo.bg

VovKa

  • Water Moccasin
  • Posts: 1621
  • Ukraine
Re: Assoc List - Group By Keys
« Reply #8 on: October 07, 2017, 04:19:04 PM »
But with this benchmark you proved me wrong!
compile all functions and run the benchmark again, i guess results will be different

i'd stick to the simple solution assoc->subst just like in Lee's code

fools

  • Newt
  • Posts: 72
  • China
Re: Assoc List - Group By Keys
« Reply #9 on: October 07, 2017, 09:35:30 PM »
Test lsp :
Please enter the length for the test list : 50
Elapsed milliseconds / relative speed for 4096 iteration(s):
    (GROUPBYKEY-LEEMAC TEST1)........1061 / 3.84 <fastest>
    (GROUPBYKEY-FOOLS TEST1).........1076 / 3.78
    (GROUPBYKEY-MEMBER TEST1)........1107 / 3.68
    (GROUPBYKEYS-GRRR1337 TEST1).....1248 / 3.26
    (NESTASSOC-GRRR1337 TEST1).......3853 / 1.06
    (GROUPBYKEY-VLREMOVE TEST1)......4072 / 1 <slowest>

Please enter the length for the test list : 100
Elapsed milliseconds / relative speed for 2048 iteration(s):
    (GROUPBYKEY-FOOLS TEST1).........1155 / 3.88 <fastest>
    (GROUPBYKEY-MEMBER TEST1)........1248 / 3.59
    (GROUPBYKEY-LEEMAC TEST1)........1341 / 3.34
    (GROUPBYKEYS-GRRR1337 TEST1).....1622 / 2.76
    (GROUPBYKEY-VLREMOVE TEST1)......4056 / 1.1
    (NESTASSOC-GRRR1337 TEST1).......4478 / 1 <slowest>

*********************************************************************

Test fas:
Please enter the length for the test list : 50
Elapsed milliseconds / relative speed for 8192 iteration(s):
    (GROUPBYKEY-FOOLS TEST1).........1123 / 7.36 <fastest>
    (GROUPBYKEY-LEEMAC TEST1)........1856 / 4.45
    (GROUPBYKEY-MEMBER TEST1)........1904 / 4.34
    (GROUPBYKEYS-GRRR1337 TEST1).....1981 / 4.17
    (NESTASSOC-GRRR1337 TEST1).......5101 / 1.62
    (GROUPBYKEY-VLREMOVE TEST1)......8268 / 1 <slowest>

Please enter the length for the test list : 100
Elapsed milliseconds / relative speed for 4096 iteration(s):
    (GROUPBYKEY-FOOLS TEST1).........1201 / 5.09 <fastest>
    (GROUPBYKEY-MEMBER TEST1)........2059 / 2.97
    (GROUPBYKEY-LEEMAC TEST1)........2434 / 2.51
    (GROUPBYKEYS-GRRR1337 TEST1).....2902 / 2.11
    (NESTASSOC-GRRR1337 TEST1).......5007 / 1.22
    (GROUPBYKEY-VLREMOVE TEST1)......6115 / 1 <slowest>

*********************************************************************

Test vlx:
Please enter the length for the test list : 50
Elapsed milliseconds / relative speed for 8192 iteration(s):
    (GROUPBYKEY-FOOLS TEST1).........1108 / 7.35 <fastest>
    (GROUPBYKEY-LEEMAC TEST1)........1685 / 4.83
    (GROUPBYKEY-MEMBER TEST1)........1872 / 4.35
    (GROUPBYKEYS-GRRR1337 TEST1).....2028 / 4.02
    (NESTASSOC-GRRR1337 TEST1).......5101 / 1.6
    (GROUPBYKEY-VLREMOVE TEST1)......8143 / 1 <slowest>

Please enter the length for the test list : 100
Elapsed milliseconds / relative speed for 4096 iteration(s):
    (GROUPBYKEY-FOOLS TEST1).........1186 / 4.87 <fastest>
    (GROUPBYKEY-MEMBER TEST1)........1996 / 2.89
    (GROUPBYKEY-LEEMAC TEST1)........2340 / 2.47
    (GROUPBYKEYS-GRRR1337 TEST1).....2902 / 1.99
    (NESTASSOC-GRRR1337 TEST1).......4758 / 1.21
    (GROUPBYKEY-VLREMOVE TEST1)......5773 / 1 <slowest>
Good good study , day day up . Sorry about my Chinglish .

fools

  • Newt
  • Posts: 72
  • China
Re: Assoc List - Group By Keys
« Reply #10 on: October 07, 2017, 09:43:05 PM »
Test vlx :
Please enter the length for the test list : 1000
Elapsed milliseconds / relative speed for 512 iteration(s):
    (GROUPBYKEY-FOOLS TEST1).........1965 / 2.82 <fastest>
    (GROUPBYKEY-MEMBER TEST1)........2996 / 1.85
    (GROUPBYKEY-VLREMOVE TEST1)......3838 / 1.44
    (GROUPBYKEY-LEEMAC TEST1)........4259 / 1.3
    (GROUPBYKEYS-GRRR1337 TEST1).....5039 / 1.1
    (NESTASSOC-GRRR1337 TEST1).......5538 / 1 <slowest>

Please enter the length for the test list : 10000
Elapsed milliseconds / relative speed for 32 iteration(s):
    (GROUPBYKEY-FOOLS TEST1).........1794 / 2.8 <fastest>
    (GROUPBYKEY-MEMBER TEST1)........1903 / 2.64
    (GROUPBYKEY-VLREMOVE TEST1)......2168 / 2.32
    (NESTASSOC-GRRR1337 TEST1).......3354 / 1.5
    (GROUPBYKEY-LEEMAC TEST1)........3572 / 1.41
    (GROUPBYKEYS-GRRR1337 TEST1).....5023 / 1 <slowest>

Please enter the length for the test list : 20000
Elapsed milliseconds / relative speed for 16 iteration(s):
    (GROUPBYKEY-MEMBER TEST1)........1903 / 3.87 <fastest>
    (GROUPBYKEY-VLREMOVE TEST1)......2199 / 3.35
    (GROUPBYKEY-FOOLS TEST1).........2262 / 3.26
    (NESTASSOC-GRRR1337 TEST1).......3401 / 2.16
    (GROUPBYKEY-LEEMAC TEST1)........4680 / 1.57
    (GROUPBYKEYS-GRRR1337 TEST1).....7363 / 1 <slowest>

Please enter the length for the test list : 30000
Elapsed milliseconds / relative speed for 8 iteration(s):
    (GROUPBYKEY-MEMBER TEST1).........1435 / 12.87 <fastest>
    (GROUPBYKEY-VLREMOVE TEST1).......1654 / 11.17
    (GROUPBYKEY-FOOLS TEST1)..........1950 / 9.47
    (NESTASSOC-GRRR1337 TEST1)........2559 / 7.22
    (GROUPBYKEY-LEEMAC TEST1).........4321 / 4.27
    (GROUPBYKEYS-GRRR1337 TEST1).....18470 / 1 <slowest>


Since the test sample has only 26 groups (A-Z), the MEMBER function might be a little faster.
When data is more cluttered, it is better to use sorting algorithm first.
« Last Edit: October 07, 2017, 10:25:49 PM by fools »
Good good study , day day up . Sorry about my Chinglish .

fools

  • Newt
  • Posts: 72
  • China
Re: Assoc List - Group By Keys
« Reply #11 on: October 07, 2017, 10:49:25 PM »
Rewrite this function to get 676 combinations.

Code - Auto/Visual Lisp: [Select]
  1. ;; Random list
  2. (defun F-RanLst (n / lst)
  3.   (repeat n
  4.     (setq lst (cons (cons (strcat (chr (LM:randrange 65 90)) (chr (LM:randrange 65 90))) 1) lst))
  5.   )
  6. )

Test lsp : The speed difference is obvious.
Please enter the length for the test list : 30000
Elapsed milliseconds / relative speed for 2 iteration(s):
    (GROUPBYKEY-FOOLS TEST1)..........1279 / 33.82 <fastest>
    (GROUPBYKEY-MEMBER TEST1).........9423 / 4.59
    (GROUPBYKEY-LEEMAC TEST1)........13697 / 3.16
    (GROUPBYKEY-VLREMOVE TEST1)......19906 / 2.17
    (GROUPBYKEYS-GRRR1337 TEST1).....21419 / 2.02
    (NESTASSOC-GRRR1337 TEST1).......43259 / 1 <slowest>
Good good study , day day up . Sorry about my Chinglish .

VovKa

  • Water Moccasin
  • Posts: 1621
  • Ukraine
Re: Assoc List - Group By Keys
« Reply #12 on: October 08, 2017, 08:16:51 AM »
Since the test sample has only 26 groups (A-Z), the MEMBER function might be a little faster.
When data is more cluttered, it is better to use sorting algorithm first.
i agree
but just to show the influence of compilation i ran the test on entities lists (300 entities)
Code: [Select]
(vlisp-compile 'lsa "C:\\Temp\\tmp1.lsp")
(setq test1 (apply 'append (mapcar 'entget (SS2EntList (ssget)))))
(load "C:\\Temp\\tmp1.lsp")
(benchmark '((groupbykey-Fools test1) (NestAssoc-Grrr1337_1 test1)))
(load "C:\\Temp\\tmp1.fas")
(benchmark '((groupbykey-Fools test1) (NestAssoc-Grrr1337_1 test1)))

Quote
; 1 form loaded from #<file "C:/Temp/tmp1.lsp">

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

    (GROUPBYKEY-FOOLS TEST1).........1092 / 1.16 <fastest>
    (NESTASSOC-GRRR1337_1 TEST1).....1263 / 1.00 <slowest>

 
 
; 1 form loaded from #<file "C:/Temp/tmp1.fas">

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

    (NESTASSOC-GRRR1337_1 TEST1).....1107 / 1.13 <fastest>
    (GROUPBYKEY-FOOLS TEST1).........1248 / 1.00 <slowest>
Lee's MEMBER is faster than both but i didn't include it in the benchmark because it is recursive and won't work on much longer lists

JohnK

  • Administrator
  • Seagull
  • Posts: 10595
Re: Assoc List - Group By Keys
« Reply #13 on: October 09, 2017, 09:48:39 AM »
Interesting aside:
I was reading an article on sorting a while back and the whole premise of sorting was called into question and studied; the author stated that sorting a list was wasted time more often then not because (this is the good part) the most requested information was the last to be added. They made the analogy of a stack of papers where the next document gets added to the top of the stack -i.e. the stack is basically in no particular order- and statistically speaking the next document needed, in the case of retrieval, would be on or near the top (a simple LIST-POP will suffice most often).
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: Assoc List - Group By Keys
« Reply #14 on: October 09, 2017, 02:34:37 PM »
My demential version (only for "string Keys"):
Code: [Select]
(defun ALE_GroupByKey (lst / TKey OKey keys tmpL OutLst)
  (foreach itm lst
    (setq OKey (car itm)   tmpL (cdr itm))
    (if (vl-position (setq TKey (strcat "###" OKey)) keys)
      (set (read TKey) (vl-list* OKey tmpL (cdr (eval (read TKey)))))
      (progn
        (set (read TKey) (list OKey tmpL))
        (setq keys (cons TKey keys))
      )
    )
  )
  (foreach itm keys
    (setq OutLst (cons (eval (read itm)) OutLst))
    (set (read itm) nil)
  )
  OutLst
)
Code: [Select]
(setq test1 (F-RanLst 300000)) 
Benchmark.lsp | © 2005 Michael Puckett | All Rights Reserved
Elapsed milliseconds / relative speed for 1 iteration(s):
    (GROUPBYKEY-FOOLS TEST1).....2828 / 1.25 <fastest>
    (ALE_GROUPBYKEY TEST1).......3546 / 1 <slowest>

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: Assoc List - Group By Keys
« Reply #15 on: October 09, 2017, 03:38:51 PM »
Just a little faster
Code: [Select]
(defun ALE_GroupByKey2 (lst / TKey OKey RKey keys tmpL OutLst)
  (setq TKey (strcat "#" (caar lst))  keys (list TKey))
  (set (read TKey) (list (caar lst) (cdar lst)))
  (foreach itm (cdr lst)
    (setq OKey (car itm)   tmpL (cdr itm) TKey (strcat "#" OKey)  RKey (read TKey))
    (if (vl-position TKey keys)
      (set RKey (vl-list* OKey tmpL (cdr (eval RKey))))
      (progn
        (set RKey (list OKey tmpL))
        (setq keys (cons TKey keys))
      )
    )
  )
  (foreach itm keys
    (setq RKey (read itm)  OutLst (cons (eval RKey) OutLst))
    (set RKey nil)
  )
  OutLst
)
Code: [Select]
Benchmark.lsp | © 2005 Michael Puckett | All Rights Reserved
Elapsed milliseconds / relative speed for 1 iteration(s):
    (ALE_GROUPBYKEY2 TEST1)......2547 / 1.05 <fastest>
    (GROUPBYKEY-FOOLS TEST1).....2672 / 1 <slowest>

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: Assoc List - Group By Keys
« Reply #16 on: October 10, 2017, 08:46:18 AM »
Other 2 versions slower on big lists:
Code: [Select]
(defun ALE_GroupByKey3 (l / k s r p)
  (foreach i l
    (if (vl-position (setq k (car i)) s)
      (setq p (assoc k r)  r (subst (vl-list* (car i) (cdr i) (cdr p)) p r))
      (setq s (cons k s)   r (cons (list k (cdr i)) r))
    )
  )
)
(defun ALE_GroupByKey4 (l / k s r p x)
  (foreach i l
    (if (setq x (vl-position (setq k (car i)) s))
      (setq p (nth x r)    r (subst (vl-list* (car i) (cdr i) (cdr p)) p r))
      (setq s (cons k s)   r (cons (list k (cdr i)) r))
    )
  )
)

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: Assoc List - Group By Keys
« Reply #17 on: October 10, 2017, 10:10:59 AM »
; UltraDemential > ALE_List_Nth see: https://www.theswamp.org/index.php?topic=46419.msg514475#msg514475
Code: [Select]
(defun ALE_GroupByKeyUD (l / k s r p x)
  (foreach i l
    (if (setq x (vl-position (setq k (car i)) s))
      (setq p (ALE_List_Nth x r)   r (subst (vl-list* (car i) (cdr i) (cdr p)) p r))
      (setq s (cons k s)           r (cons (list k (cdr i)) r))
    )
  )
)