Author Topic: fastest way to get count of an item in a list  (Read 10783 times)

0 Members and 1 Guest are viewing this topic.

mailmaverick

  • Bull Frog
  • Posts: 494
fastest way to get count of an item in a list
« on: May 29, 2014, 08:43:47 AM »
I have a list containing coordinates in form of ( (x1 y1 z1) (x2 y2 z2) (x3 y3 z3) (x4 y4 z4) ......).

I want to count occurence of a particular coordinate in the list.

What is the fastest way of doing so ?

Note that I want the number of times the particular coordinate occurs in the list, not the position(s) of occurences.

reltro

  • Guest
Re: fastest way to get count of an item in a list
« Reply #1 on: May 29, 2014, 08:50:25 AM »
Hey...
Maybe something like this?
Code: [Select]
(defun foo (lst c / ) (apply '+ (mapcar '(lambda (a / ) (if (equal a c) 1 0)) lst)))
Code: [Select]
(foo '((1 2.0 3) (2 3 4) (1 2 3) (1 2 3.0)) '(1 2 3))-> 3

May not the fastest way...

reltro

dgorsman

  • Water Moccasin
  • Posts: 2437
Re: fastest way to get count of an item in a list
« Reply #2 on: May 29, 2014, 10:13:26 AM »
Maybe pass the result of (vl-remove-if-not ...) to (length ...)?  Because coordinates are REALs you'll need a specific comparison method.
If you are going to fly by the seat of your pants, expect friction burns.

try {GreatPower;}
   catch (notResponsible)
      {NextTime(PlanAhead);}
   finally
      {MasterBasics;}

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: fastest way to get count of an item in a list
« Reply #3 on: May 29, 2014, 11:30:17 AM »
Maybe pass the result of (vl-remove-if-not ...) to (length ...)?  Because coordinates are REALs you'll need a specific comparison method.
Seems to be correct.
Code - Auto/Visual Lisp: [Select]
  1. (defun reltro:count-found  (lst c /)
  2.   (apply '+
  3.          (mapcar '(lambda (a /)
  4.                     (if (equal a c)
  5.                       1
  6.                       0))
  7.                  lst)))
  8.  
  9. (defun reltro:count-found1  (lst c /)
  10.   (apply '+
  11.          (mapcar (function (lambda (a /)
  12.                              (if (equal a c)
  13.                                1
  14.                                0)))
  15.                  lst)))
  16.  
  17. (defun dg:count-found  (lst item)
  18.   (length (vl-remove-if-not (function (lambda (node) (equal node item))) lst)))
Note I've tried optimizing reltro's to use as a compiled function instead of a quoted lambda.

Test
Code: [Select]
_$ (setq lst nil)
nil
_$ (length (repeat 1000 (setq lst (cons (list (random nil) (random nil) (random nil)) lst))))
1000
_$ (length (repeat 6 (setq lst (append lst lst))))
64000
_$ (setq search (nth 12345 lst))
(0.750793 0.933797 0.674399)
_$ (quickbench '((reltro:count-found lst search) (reltro:count-found1 lst search) (reltro:count-found lst search)))
Benchmarking ... done for 32 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(RELTRO:COUNT-FOUND LST SEARCH)                 32      2106      2106      1.13
(RELTRO:COUNT-FOUND1 LST SEARCH)                16      1168      2336      1.02
(RELTRO:COUNT-FOUND LST SEARCH)                 16      1186      2372      1.00
--------------------------------------------------------------------------------
Not a hell of a lot though.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: fastest way to get count of an item in a list
« Reply #4 on: May 29, 2014, 11:35:07 AM »
Code: [Select]
(defun ALE_ListCountItem (TstItm In_Lst)
  (-
    (length In_Lst)
    (length (vl-remove TstItm In_Lst))
  )
)
(ALE_ListCountItem '(3 4 5) '((1 2 3)(3 4 5)(5 6 7)(3 4 5)(8 9 10)(3 4 5)(3 4 5)) )
=> 4

(defun ALE_ListCountItem2 (n l / c)
  (setq c 0)
  (vl-every
    (function
      (lambda (x)
        (if (equal x n)
          (setq c (1+ c))
          T
        )
      )
    )
    l
  )
  c
)
(ALE_ListCountItem2 '(3 4 5) '((1 2 3)(3 4 5)(5 6 7)(3 4 5)(8 9 10)(3 4 5)(3 4 5)) )
=> 4

reltro

  • Guest
Re: fastest way to get count of an item in a list
« Reply #5 on: May 29, 2014, 12:24:18 PM »
Code: [Select]
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(RELTRO:COUNT-FOUND LST SEARCH)                 32      2106      2106      1.13
(RELTRO:COUNT-FOUND1 LST SEARCH)                16      1168      2336      1.02
(RELTRO:COUNT-FOUND LST SEARCH)                 16      1186      2372      1.00
--------------------------------------------------------------------------------
Not a hell of a lot though.

Hey...
You tested two times the same function with different results?  :?

whats about dg:count-found ?

reltro

Lee Mac

  • Seagull
  • Posts: 12905
  • London, England
Re: fastest way to get count of an item in a list
« Reply #6 on: May 29, 2014, 05:53:51 PM »
Another simple one:

Code: [Select]
(defun countitemfuzz ( itm lst fuz / cnt )
    (setq cnt 0)
    (foreach x lst (if (equal itm x fuz) (setq cnt (1+ cnt))))
    cnt
)

Code: [Select]
_$ (countitemfuzz '(1 2 3) '((1 2.0 3) (2 3 4) (1 2 3) (1 2 3.0)) 1e-8)
3

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: fastest way to get count of an item in a list
« Reply #7 on: May 30, 2014, 03:20:58 AM »
Hey...
You tested two times the same function with different results?  :?
whats about dg:count-found ?
reltro
The result of the tests often also changes very:
Code: [Select]
(progn
(setq aList nil)
(length (repeat 1000 (setq aList (cons (list (random nil) (random nil) (random nil)) aList))))
(length (repeat 6 (setq aList (append aList aList))))
(setq search (nth 12345 aList))
(princ "\nLength   : ") (princ (length aList)) (princ "\n")
)
Code: [Select]
Benchmark.lsp | © 2005 Michael Puckett | All Rights Reserved
Length   : 64000
Elapsed milliseconds / relative speed for 128 iteration(s):

    (ALE_LISTCOUNTITEM SEARCH ALIST)..........1341 / 3.83 <fastest>
    (ALE_LISTCOUNTITEM SEARCH ALIST)..........1497 / 3.43
    (ALE_LISTCOUNTITEM2 SEARCH ALIST).........2605 / 1.97
    (ALE_LISTCOUNTITEM2 SEARCH ALIST).........2605 / 1.97
    (DG:COUNT-FOUND ALIST SEARCH).............2621 / 1.96
    (DG:COUNT-FOUND ALIST SEARCH).............2792 / 1.84
    (RELTRO:COUNT-FOUND1 ALIST SEARCH)........3776 / 1.36
    (RELTRO:COUNT-FOUND1 ALIST SEARCH)........3869 / 1.33
    (RELTRO:COUNT-FOUND ALIST SEARCH).........3900 / 1.32
    (RELTRO:COUNT-FOUND ALIST SEARCH).........4509 / 1.14
    (COUNTITEMFUZZ SEARCH ALIST 1.0e-008).....5101 / 1.01
    (COUNTITEMFUZZ SEARCH ALIST 1.0e-008).....5132 / 1 <slowest>
Code: [Select]
Others:
    (ALE_LISTCOUNTITEM SEARCH ALIST).......1139 / 3.9 <fastest>
    (ALE_LISTCOUNTITEM SEARCH ALIST).......1294 / 3.44
    (ALE_LISTCOUNTITEM2 SEARCH ALIST)......1513 / 2.94
    (RELTRO:COUNT-FOUND ALIST SEARCH)......3073 / 1.45
    (RELTRO:COUNT-FOUND1 ALIST SEARCH).....3120 / 1.43
    (DG:COUNT-FOUND ALIST SEARCH)..........3152 / 1.41
    (ALE_LISTCOUNTITEM2 SEARCH ALIST)......3354 / 1.33
    (DG:COUNT-FOUND ALIST SEARCH)..........3494 / 1.27
    (RELTRO:COUNT-FOUND1 ALIST SEARCH).....3775 / 1.18
    (RELTRO:COUNT-FOUND ALIST SEARCH)......4446 / 1 <slowest>
Code: [Select]
    (ALE_LISTCOUNTITEM SEARCH ALIST).......1731 / 3.13 <fastest>
    (ALE_LISTCOUNTITEM SEARCH ALIST).......1809 / 2.99
    (DG:COUNT-FOUND ALIST SEARCH)..........2605 / 2.08
    (ALE_LISTCOUNTITEM2 SEARCH ALIST)......2621 / 2.07
    (DG:COUNT-FOUND ALIST SEARCH)..........2621 / 2.07
    (ALE_LISTCOUNTITEM2 SEARCH ALIST)......3650 / 1.48
    (RELTRO:COUNT-FOUND ALIST SEARCH)......4102 / 1.32
    (RELTRO:COUNT-FOUND ALIST SEARCH)......4368 / 1.24
    (RELTRO:COUNT-FOUND1 ALIST SEARCH).....4914 / 1.1
    (RELTRO:COUNT-FOUND1 ALIST SEARCH).....5413 / 1 <slowest>

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: fastest way to get count of an item in a list
« Reply #8 on: May 30, 2014, 03:36:14 AM »
With fuzz is slover:
Code: [Select]
; 2014/06/30
(defun ALE_ListCountItemFuzz (i l f)
  (-
    (length l)
    (length (vl-remove-if (function (lambda (x) (equal x i f))) l))
  )
)
Code: [Select]
Length   : 64000
Elapsed milliseconds / relative speed for 32 iteration(s):

    (ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...).....1342 / 1.96 <fastest>
    (COUNTITEMFUZZ SEARCH ALIST 1.0e-008)........1357 / 1.94
    (ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...).....1498 / 1.76
    (COUNTITEMFUZZ SEARCH ALIST 1.0e-008)........2636 / 1 <slowest>

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: fastest way to get count of an item in a list
« Reply #9 on: May 30, 2014, 03:51:03 AM »
With fuzz is better this:
Code: [Select]
; 2014/06/30
(defun ALE_ListCountItemFuzz2 (i l f / c)
  (setq c 0)
  (vl-every
    (function (lambda (x) (if (equal x i f) (setq c (1+ c)) T)))
    l
  )
  c
)
Code: [Select]
Length   : 64000
Elapsed milliseconds / relative speed for 64 iteration(s):

    (ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...).....2137 / 1.8 <fastest>
    (ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...).....2184 / 1.76
    (ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...).....2402 / 1.6
    (COUNTITEMFUZZ SEARCH ALIST 1.0e-008)........3229 / 1.19
    (ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...).....3604 / 1.07
    (COUNTITEMFUZZ SEARCH ALIST 1.0e-008)........3854 / 1 <slowest>

roy_043

  • Water Moccasin
  • Posts: 1895
  • BricsCAD 18
Re: fastest way to get count of an item in a list
« Reply #10 on: May 30, 2014, 04:49:05 AM »
@ Marc'Antonio Alessi:
Isn't it more logical to use mapcar instead of vl-every?

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: fastest way to get count of an item in a list
« Reply #11 on: May 30, 2014, 05:03:46 AM »
@ Marc'Antonio Alessi:
Isn't it more logical to use mapcar instead of vl-every?
Yes, but vl-every is surprisingly faster...

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: fastest way to get count of an item in a list
« Reply #12 on: May 30, 2014, 05:16:46 AM »
Hey...
You tested two times the same function with different results?  :?

whats about dg:count-found ?

reltro
Oops, yes ... was silly of me. But the variance in the same function isn't that strange at all - any number of things may affect performance (especially if there's other programs running in the background as is ALWAYS the case in Windows). The only way to get past such inconsistencies is to rerun the benchmark a few times and then only take the figures which seem to be the "norm". Notice how the values differ between 3 consecutive tests:
Code: [Select]
_$ (QuickBench '((reltro:count-found aList search) (reltro:count-found1 aList search) (dg:count-found aList search) (ALE_ListCountItemFuzz2 search aList 1e-8) (ALE_ListCountItemFuzz search aList 1e-8) (LM:countitemfuzz search aList 1e-8) (ALE_ListCountItem search aList) (ALE_ListCountItem2 search aList)))
Benchmarking ........ done for 128 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(ALE_LISTCOUNTITEM SEARCH ALIST)               128      1030      1030      1.00
(DG:COUNT-FOUND ALIST SEARCH)                   32      1156      4624      4.49
(ALE_LISTCOUNTITEM2 SEARCH ALIST)               32      1310      5240      5.09
(ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...)        32      1344      5376      5.22
(ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...)        32      1390      5560      5.40
(RELTRO:COUNT-FOUND ALIST SEARCH)               32      1434      5736      5.57
(RELTRO:COUNT-FOUND1 ALIST SEARCH)              32      1467      5868      5.70
(LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-008)        16      1153      9224      8.96
--------------------------------------------------------------------------------
_$ (QuickBench '((reltro:count-found aList search) (reltro:count-found1 aList search) (dg:count-found aList search) (ALE_ListCountItemFuzz2 search aList 1e-8) (ALE_ListCountItemFuzz search aList 1e-8) (LM:countitemfuzz search aList 1e-8) (ALE_ListCountItem search aList) (ALE_ListCountItem2 search aList)))
Benchmarking ........ done for 128 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(ALE_LISTCOUNTITEM SEARCH ALIST)               128      1062      1062      1.00
(DG:COUNT-FOUND ALIST SEARCH)                   32      1185      4740      4.46
(ALE_LISTCOUNTITEM2 SEARCH ALIST)               32      1294      5176      4.87
(ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...)        32      1356      5424      5.11
(ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...)        32      1404      5616      5.29
(RELTRO:COUNT-FOUND ALIST SEARCH)               32      1435      5740      5.40
(RELTRO:COUNT-FOUND1 ALIST SEARCH)              32      1450      5800      5.46
(LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-008)        16      1156      9248      8.71
--------------------------------------------------------------------------------
_$ (QuickBench '((reltro:count-found aList search) (reltro:count-found1 aList search) (dg:count-found aList search) (ALE_ListCountItemFuzz2 search aList 1e-8) (ALE_ListCountItemFuzz search aList 1e-8) (LM:countitemfuzz search aList 1e-8) (ALE_ListCountItem search aList) (ALE_ListCountItem2 search aList)))
Benchmarking ........ done for 128 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(ALE_LISTCOUNTITEM SEARCH ALIST)               128      1091      1091      1.00
(DG:COUNT-FOUND ALIST SEARCH)                   32      1186      4744      4.35
(ALE_LISTCOUNTITEM2 SEARCH ALIST)               32      1373      5492      5.03
(ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...)        32      1406      5624      5.15
(ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...)        32      1419      5676      5.20
(RELTRO:COUNT-FOUND ALIST SEARCH)               32      1434      5736      5.26
(RELTRO:COUNT-FOUND1 ALIST SEARCH)              32      1465      5860      5.37
(LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-008)        16      1216      9728      8.92
--------------------------------------------------------------------------------

But the others have done similar already, though they're using another benchmarking function than I did. I'm just using another routine (attached) because it doesn't hang when the test takes a huge long time (if there's a badly performing test case) - won't test for longer than 1 second on any test expression.

BTW, I've been asked on numerous occasions why that QuickBench of mine is showing the relative speed for faster functions as a higher figure than the slowest. It was due to the benchmarking routine the others are using (notice it also gives 1.0 to the slowest and then higher numbers relative to each faster test, so if you see 2.0 it means it's 2 times faster): http://autolisp.ru/wp-content/uploads/2009/09/benchmark.lsp

But I've changed it due to some comments - now the fastest is shown as 1.0 and the slower as how much longer they take - 3 times would be 3.0. Obviously now I'm waiting for those comments asking why mine's relative differs from the one by Michael Puckett.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: fastest way to get count of an item in a list
« Reply #13 on: May 30, 2014, 05:21:40 AM »
@ Marc'Antonio Alessi:
Isn't it more logical to use mapcar instead of vl-every?
This is much, much less logic, but...
Code: [Select]
; 2014/06/30
(defun ALE_ListCountItem3 (i l / p c)
  (setq c 0)
  (while (setq p (vl-position i l))
    (setq l (cdr (ALE_List_NthCdr p l)) c (1+ c))
  )
  c
)
Code: [Select]
Length   : 64000
Elapsed milliseconds / relative speed for 256 iteration(s):

    (ALE_LISTCOUNTITEM3 SEARCH ALIST).....1373 / 6.11 <fastest>
    (ALE_LISTCOUNTITEM3 SEARCH ALIST).....2231 / 3.76
    (ALE_LISTCOUNTITEM SEARCH ALIST)......4461 / 1.88
    (ALE_LISTCOUNTITEM SEARCH ALIST)......4976 / 1.69
    (ALE_LISTCOUNTITEM2 SEARCH ALIST).....6880 / 1.22
    (ALE_LISTCOUNTITEM2 SEARCH ALIST).....8393 / 1 <slowest>
Code: [Select]
; 2014/02/19 - n (Position) Nth like
(defun ALE_List_NthCdr (n l)   
  (repeat (/       n              1000) (setq l (Cd1000r l)))   
  (repeat (/ (setq n (rem n 1000)) 100) (setq l (Cd100r  l)))   
  (repeat (/ (setq n (rem n  100))  10) (setq l (Cd10r   l)))   
  (repeat (/ (setq n (rem n   10))   4) (setq l (cddddr  l)))   
  (repeat (rem n 4)                     (setq l (cdr     l)))   
  l   
)
>>> for Cdxxxxr functions see my previous post:
http://www.theswamp.org/index.php?topic=46419.msg514475#msg514475
http://www.theswamp.org/index.php?topic=46657.msg516785#msg516785

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: fastest way to get count of an item in a list
« Reply #14 on: May 30, 2014, 05:32:11 AM »
...Obviously now I'm waiting for those comments asking why mine's relative differs from the one by Michael Puckett.
I do not have an answer, what I can say is that I find more stable test results testing the same function multiple times in the same test.
Ciao.

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: fastest way to get count of an item in a list
« Reply #15 on: May 30, 2014, 06:43:40 AM »
I do not have an answer, what I can say is that I find more stable test results testing the same function multiple times in the same test.
Ciao.
Mine is using the same method as Micheal's is. His ensures that the fastest one runs at least for a second by repeating the runs until more than 1sec elapsed. Then it repeats the rest for the same number of times (so if the 2nd takes twice as long it will be slightly more than 2sec).

Mine simply performs the same as Micheal's does for the fastest - i.e. run each until 1 sec elapsed. Then uses math to compare the various values. The Increment is the number of times each item was run, then the normalized column adjusts the time by multiplying it with the factor to match the fastest.

What I was actually referring to - is the value under the Relative column as compared to Michael’s relative speed value. If I take my old version it takes around 10 seconds to do this:
Code: [Select]
Benchmarking ........ done for 128 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Rating
--------------------------------------------------------------------------------
(ALE_LISTCOUNTITEM SEARCH ALIST)               128      1075      1075      8.59
(DG:COUNT-FOUND ALIST SEARCH)                   32      1169      4676      1.97
(ALE_LISTCOUNTITEM2 SEARCH ALIST)               32      1294      5176      1.78
(ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...)        32      1388      5552      1.66
(ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...)        32      1388      5552      1.66
(RELTRO:COUNT-FOUND1 ALIST SEARCH)              32      1452      5808      1.59
(RELTRO:COUNT-FOUND ALIST SEARCH)               32      1466      5864      1.57
(LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-008)        16      1154      9232      1.00
--------------------------------------------------------------------------------
Then running the same with Micheal's it takes about 1 minute to complete
Code: [Select]
Benchmarking ...........Elapsed milliseconds / relative speed for 256 iteration(s):

    (ALE_LISTCOUNTITEM SEARCH ALIST).............1108 / 8.71 <fastest>
    (DG:COUNT-FOUND ALIST SEARCH)................4758 / 2.03
    (ALE_LISTCOUNTITEM2 SEARCH ALIST)............5538 / 1.74
    (ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...).....5600 / 1.72
    (ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...).....5709 / 1.69
    (RELTRO:COUNT-FOUND1 ALIST SEARCH)...........5991 / 1.61
    (RELTRO:COUNT-FOUND ALIST SEARCH)............6021 / 1.6
    (LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-...).....9656 / 1 <slowest>

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

    (ALE_LISTCOUNTITEM SEARCH ALIST).............1092 / 8.83 <fastest>
    (DG:COUNT-FOUND ALIST SEARCH)................4758 / 2.03
    (ALE_LISTCOUNTITEM2 SEARCH ALIST)............5413 / 1.78
    (ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...).....5601 / 1.72
    (ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...).....5725 / 1.68
    (RELTRO:COUNT-FOUND1 ALIST SEARCH)...........5990 / 1.61
    (RELTRO:COUNT-FOUND ALIST SEARCH)............6006 / 1.61
    (LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-...).....9641 / 1 <slowest>
Not too different in the values.

But now with the new one those relative figures are reversed:
Code: [Select]
Benchmarking ........ done for 128 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(ALE_LISTCOUNTITEM SEARCH ALIST)               128      1061      1061      1.00
(DG:COUNT-FOUND ALIST SEARCH)                   32      1170      4680      4.41
(ALE_LISTCOUNTITEM2 SEARCH ALIST)               32      1295      5180      4.88
(ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...)        32      1373      5492      5.18
(ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...)        32      1389      5556      5.24
(RELTRO:COUNT-FOUND ALIST SEARCH)               32      1437      5748      5.42
(RELTRO:COUNT-FOUND1 ALIST SEARCH)              32      1467      5868      5.53
(LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-008)        16      1155      9240      8.71
--------------------------------------------------------------------------------
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: fastest way to get count of an item in a list
« Reply #16 on: May 30, 2014, 08:49:14 AM »
My results:
Code: [Select]
Length   : 64000
Benchmarking .................. done for 128 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(ALE_LISTCOUNTITEM3 SEARCH ALIST)              128      1263      1263      1.00
(ALE_LISTCOUNTITEM3 SEARCH ALIST)              128      1358      1358      1.08
(ALE_LISTCOUNTITEM SEARCH ALIST)                64      1467      2934      2.32
(ALE_LISTCOUNTITEM SEARCH ALIST)                64      1949      3898      3.09
(ALE_LISTCOUNTITEM2 SEARCH ALIST)               32      1296      5184      4.10
(ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...)        32      1436      5744      4.55
(DG:COUNT-FOUND ALIST SEARCH)                   32      1450      5800      4.59
(ALE_LISTCOUNTITEM2 SEARCH ALIST)               32      1451      5804      4.60
(RELTRO:COUNT-FOUND1 ALIST SEARCH)              32      1840      7360      5.83
(RELTRO:COUNT-FOUND ALIST SEARCH)               32      1872      7488      5.93
(RELTRO:COUNT-FOUND ALIST SEARCH)               16      1013      8104      6.42
(RELTRO:COUNT-FOUND1 ALIST SEARCH)              16      1029      8232      6.52
(ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...)        16      1061      8488      6.72
(LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-008)        16      1217      9736      7.71
(ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...)        16      1231      9848      7.80
(LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-008)        16      1233      9864      7.81
(ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...)        32      2590     10360      8.20
(DG:COUNT-FOUND ALIST SEARCH)                   16      1450     11600      9.18
Code: [Select]
Elapsed milliseconds / relative speed for 256 iteration(s):

    (ALE_LISTCOUNTITEM3 SEARCH ALIST).............1388 / 10.68 <fastest>
    (ALE_LISTCOUNTITEM3 SEARCH ALIST).............1654 / 8.96
    (ALE_LISTCOUNTITEM SEARCH ALIST)..............2933 / 5.05
    (ALE_LISTCOUNTITEM SEARCH ALIST)..............4337 / 3.42
    (DG:COUNT-FOUND ALIST SEARCH).................6755 / 2.19
    (ALE_LISTCOUNTITEM2 SEARCH ALIST).............7098 / 2.09
    (ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...)......7207 / 2.06
    (DG:COUNT-FOUND ALIST SEARCH).................7910 / 1.87
    (ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...)......8798 / 1.68
    (ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...)......8861 / 1.67
    (ALE_LISTCOUNTITEM2 SEARCH ALIST).............9141 / 1.62
    (RELTRO:COUNT-FOUND1 ALIST SEARCH)...........10015 / 1.48
    (RELTRO:COUNT-FOUND ALIST SEARCH)............10233 / 1.45
    (ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...).....10639 / 1.39
    (RELTRO:COUNT-FOUND ALIST SEARCH)............11419 / 1.3
    (RELTRO:COUNT-FOUND1 ALIST SEARCH)...........11731 / 1.26
    (LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-...).....14789 / 1
    (LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-...).....14820 / 1 <slowest>

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: fastest way to get count of an item in a list
« Reply #17 on: May 30, 2014, 09:20:31 AM »

Quote

But now with the new one those relative figures are reversed:

I believe this is the better way to report benchmarks.

The fastest is always 1
The remainder get assigned values relative to that, with the rating growing in the same direction as the time.
So if we see a relative value of 15.5 we know it take 15.5 times as long to run.

kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

MP

  • Seagull
  • Posts: 17750
  • Have thousands of dwgs to process? Contact me.
Re: fastest way to get count of an item in a list
« Reply #18 on: May 30, 2014, 10:03:37 AM »
I believe this is the better way to report benchmarks.

The fastest is always 1

The remainder get assigned values relative to that, with the rating growing in the same direction as the time.

So if we see a relative value of 15.5 we know it take 15.5 times as long to run.

I guess it depends on your focus.

"Hey, I wrote a new version of my program."

"Cool, how fast is it?"

"15-1/2 times faster than the previous version."

"Awesome".
Engineering Technologist • CAD Automation Practitioner
Automation ▸ Design ▸ Drafting ▸ Document Control ▸ Client
cadanalyst@gmail.comhttp://cadanalyst.slack.comhttp://linkedin.com/in/cadanalyst

Stefan

  • Bull Frog
  • Posts: 319
  • The most I miss IRL is the Undo button
Re: fastest way to get count of an item in a list
« Reply #19 on: May 30, 2014, 11:00:43 AM »
ALE_ListCountItem seems to be one of the fastest, but:
Code: [Select]
_$ (ALE_ListCountItem '(1 2 3) '((1 2.0 3) (2 3 4) (1 2 3) (1 2 3.0)))
1

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: fastest way to get count of an item in a list
« Reply #20 on: May 30, 2014, 11:55:55 AM »
ALE_ListCountItem seems to be one of the fastest, but:
Code: [Select]
_$ (ALE_ListCountItem '(1 2 3) '((1 2.0 3) (2 3 4) (1 2 3) (1 2 3.0)))
1
Yes, use this:
(ALE_ListCountItemFuzz2 '(1 2 3) '((1 2.0 3) (2 3 4) (1 2 3) (1 2 3.0)) 1e-8)
=> 3

Only Lee has a fuzz to compare:
Code: [Select]
Length   : 64000
Benchmark.lsp | © 2005 Michael Puckett | All Rights Reserved
Elapsed milliseconds / relative speed for 32 iteration(s):
    (ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...).....1154 / 2.14 <fastest>
    (ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...).....1560 / 1.58
    (LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-...).....2433 / 1.01
    (LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-...).....2465 / 1 <slowest>


Benchmarking .... done for 32 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...)        32      1559      1559      1.00
(ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...)        32      2434      2434      1.56
(LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-008)        16      1263      2526      1.62
(LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-008)        16      2091      4182      2.68


ymg

  • Guest
Re: fastest way to get count of an item in a list
« Reply #21 on: May 30, 2014, 12:17:52 PM »
Quote
I guess it depends on your focus.

Is my glass half-empty or half-full?   :-)

MP

  • Seagull
  • Posts: 17750
  • Have thousands of dwgs to process? Contact me.
Re: fastest way to get count of an item in a list
« Reply #22 on: May 30, 2014, 12:24:07 PM »
Engineering Technologist • CAD Automation Practitioner
Automation ▸ Design ▸ Drafting ▸ Document Control ▸ Client
cadanalyst@gmail.comhttp://cadanalyst.slack.comhttp://linkedin.com/in/cadanalyst

David Bethel

  • Swamp Rat
  • Posts: 656
Re: fastest way to get count of an item in a list
« Reply #23 on: May 30, 2014, 12:33:58 PM »
Probably not the most efficient, but you should be able to use a (member) call in a simple snippet.  -David
R12 Dos - A2K

reltro

  • Guest
Re: fastest way to get count of an item in a list
« Reply #24 on: May 30, 2014, 12:39:53 PM »
Probably not the most efficient, but you should be able to use a (member) call in a simple snippet.  -David

You mean something like this? ;)
Code: [Select]
(defun reltro:countMember (item lst / i)
    (setq i 0)
    (while (setq lst (member item lst))
        (setq lst (cdr lst))
        (setq i (1+ i))
    )
)

reltro

David Bethel

  • Swamp Rat
  • Posts: 656
Re: fastest way to get count of an item in a list
« Reply #25 on: May 30, 2014, 12:41:13 PM »
yep
R12 Dos - A2K

MP

  • Seagull
  • Posts: 17750
  • Have thousands of dwgs to process? Contact me.
Re: fastest way to get count of an item in a list
« Reply #26 on: May 30, 2014, 01:23:51 PM »
Member can be a good route when item candidacy is absolute but not so much when candidacy depends upon fuzzy hits.
Engineering Technologist • CAD Automation Practitioner
Automation ▸ Design ▸ Drafting ▸ Document Control ▸ Client
cadanalyst@gmail.comhttp://cadanalyst.slack.comhttp://linkedin.com/in/cadanalyst

David Bethel

  • Swamp Rat
  • Posts: 656
Re: fastest way to get count of an item in a list
« Reply #27 on: May 30, 2014, 01:31:24 PM »
Member can be a good route when item candidacy is absolute but not so much when candidacy depends upon fuzzy hits.

I agree.  The OP did use a variable as the value of each axis, which should negate the fuzz.  But as a generic test, a fuzzy call would be warmer.  -David
R12 Dos - A2K

Lee Mac

  • Seagull
  • Posts: 12905
  • London, England
Re: fastest way to get count of an item in a list
« Reply #28 on: May 30, 2014, 02:45:13 PM »
I'm not sure if any of the benchmarking tests so far have been compiled (i.e. to optimised vlx/fas), but I would have thought that compiling would optimise the foreach loop over other iterators such as mapcar/while.... - maybe I can claw back some places :D

mailmaverick

  • Bull Frog
  • Posts: 494
Re: fastest way to get count of an item in a list
« Reply #29 on: May 30, 2014, 02:50:29 PM »
I'm not sure if any of the benchmarking tests so far have been compiled (i.e. to optimised vlx/fas), but I would have thought that compiling would optimise the foreach loop over other iterators such as mapcar/while.... - maybe I can claw back some places :D

Dear Lee

What is optimized VLX file? How is it different from normal VLX file?


Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: fastest way to get count of an item in a list
« Reply #30 on: May 30, 2014, 03:33:59 PM »
< .. >

So if we see a relative value of 15.5 we know it take 15.5 times as long to run.

I guess it depends on your focus.


Yes it does. Everything I say is based on personal opinion, even the absolutes.
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

Lee Mac

  • Seagull
  • Posts: 12905
  • London, England
Re: fastest way to get count of an item in a list
« Reply #31 on: May 30, 2014, 05:32:37 PM »
I'm not sure if any of the benchmarking tests so far have been compiled (i.e. to optimised vlx/fas), but I would have thought that compiling would optimise the foreach loop over other iterators such as mapcar/while.... - maybe I can claw back some places :D

What is optimized VLX file? How is it different from normal VLX file?


mailmaverick

  • Bull Frog
  • Posts: 494
Re: fastest way to get count of an item in a list
« Reply #32 on: June 02, 2014, 05:57:25 AM »
I'm not sure if any of the benchmarking tests so far have been compiled (i.e. to optimised vlx/fas), but I would have thought that compiling would optimise the foreach loop over other iterators such as mapcar/while.... - maybe I can claw back some places :D

What is optimized VLX file? How is it different from normal VLX file?



Does that mean we must select 'Optimize and Link' option every time we compile files ?
Is there any drawback of doing this ?


irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: fastest way to get count of an item in a list
« Reply #33 on: June 02, 2014, 07:35:43 AM »
Does that mean we must select 'Optimize and Link' option every time we compile files ?
Is there any drawback of doing this ?
It helps usually. The most basic portion of that means it in-lines the function - this means it's as if wherever you call it you rather duplicated the code. It tends to make it run faster as there's no new scope created for a new defun and the arguments aren’t passed as new copies to the duplicated code. It's not the only optimization happening, but does show one benefit which could make for much faster running code.

Note however that this can adversely affect your program. E.g. normal lambda's generate some errors when optimized in this way - you should surround lambda's with function to avoid most of these.

Also (I'm not sure about this though) it might be a bit dangerous with the in-lining optimizer, what happens if you re-use one of the parameters inside the defun as if it's a local variable? With the normal defun's scope it won't affect the value outside that defun, but it's unclear what happens due to in-lining (does the scope merge with the calling scope?). I tend to "try" avoid such situations for this reason, perhaps it's not needed - but I'd rather be safe.

Therefore you could say, normal compiling makes code run faster. Optimized + Linked makes it run even faster, but with some possible problems.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

chlh_jd

  • Guest
Re: fastest way to get count of an item in a list
« Reply #34 on: June 04, 2014, 12:24:28 AM »
I'm not sure if any of the benchmarking tests so far have been compiled (i.e. to optimised vlx/fas), but I would have thought that compiling would optimise the foreach loop over other iterators such as mapcar/while.... - maybe I can claw back some places :D
1+
foreach is faster than other when need to through each element after compiled .

If no need the allowance . may be
Code - Auto/Visual Lisp: [Select]
  1. (defun count  (a l)  (if (setq l (member a l))  (1+ (count a (cdr l))) 0))
  2.  

 

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: fastest way to get count of an item in a list
« Reply #35 on: June 04, 2014, 02:04:56 AM »
All these function return bad result, eg check on nullable:
That's because of the equality comparing functions they use:
Code: [Select]
Command: (= '(nil) '(nil))
nil
Command: (eq '(nil) '(nil))
nil
Command: (equal '(nil) '(nil))
T
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

fixo

  • Guest
Re: fastest way to get count of an item in a list
« Reply #36 on: June 04, 2014, 02:24:45 AM »
Thanks Irne,
post removed by my mistake  :ugly:
Oleg

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: fastest way to get count of an item in a list
« Reply #37 on: June 04, 2014, 03:26:01 AM »
Thanks Irne,
post removed by my mistake  :ugly:
Oleg
Nope! You didn't need to remove the post. It actually shows something quite useful to know!
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: fastest way to get count of an item in a list
« Reply #38 on: June 04, 2014, 05:31:12 AM »
My test:
NOT compiled:
Code: [Select]
Elapsed milliseconds / relative speed for 512 iteration(s):
    (ALE_LISTCOUNTITEM3 SEARCH ALIST).............1326 / 9.45 <fastest>
    (ALE_LISTCOUNTITEM3 SEARCH ALIST).............1341 / 9.34
    (ALE_LISTCOUNTITEM SEARCH ALIST)..............2855 / 4.39
    (ALE_LISTCOUNTITEM SEARCH ALIST)..............2980 / 4.2
    (CHLH_JD:COUNT SEARCH ALIST)..................3400 / 3.68
    (CHLH_JD:COUNT SEARCH ALIST)..................4680 / 2.68
    (ALE_LISTCOUNTITEM2 SEARCH ALIST).............5507 / 2.27
    (ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...)......5882 / 2.13
    (ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...)......5991 / 2.09
    (ALE_LISTCOUNTITEM2 SEARCH ALIST).............6380 / 1.96
    (DG:COUNT-FOUND ALIST SEARCH).................7301 / 1.72
    (RELTRO:COUNT-FOUND ALIST SEARCH).............7706 / 1.63
    (ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...)......7738 / 1.62
    (RELTRO:COUNT-FOUND1 ALIST SEARCH)............8003 / 1.57
    (RELTRO:COUNT-FOUND ALIST SEARCH).............8003 / 1.57
    (ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...)......8456 / 1.48
    (RELTRO:COUNT-FOUND1 ALIST SEARCH)............8518 / 1.47
    (LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-...).....11263 / 1.11 <<<<<<<<
    (DG:COUNT-FOUND ALIST SEARCH)................11466 / 1.09
    (LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-...).....12527 / 1 <slowest>  <<<<<<<<<<

Benchmarking .................... done for 128 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(ALE_LISTCOUNTITEM3 SEARCH ALIST)              128      1935      1935      1.00
(CHLH_JD:COUNT SEARCH ALIST)                    64      1686      3372      1.74
(ALE_LISTCOUNTITEM3 SEARCH ALIST)               64      1699      3398      1.76
(CHLH_JD:COUNT SEARCH ALIST)                    32      1233      4932      2.55
(ALE_LISTCOUNTITEM SEARCH ALIST)                32      1311      5244      2.71
(ALE_LISTCOUNTITEM SEARCH ALIST)                32      1357      5428      2.81
(ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...)        32      1559      6236      3.22
(ALE_LISTCOUNTITEM2 SEARCH ALIST)               32      1608      6432      3.32
(RELTRO:COUNT-FOUND1 ALIST SEARCH)              32      1778      7112      3.68
(RELTRO:COUNT-FOUND ALIST SEARCH)               32      1905      7620      3.94
(DG:COUNT-FOUND ALIST SEARCH)                   32      2105      8420      4.35
(ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...)        16      1157      9256      4.78
(ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...)        32      2325      9300      4.81
(DG:COUNT-FOUND ALIST SEARCH)                   32      2339      9356      4.84
(LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-008)        16      1185      9480      4.90 <<<<<<<
(ALE_LISTCOUNTITEM2 SEARCH ALIST)               16      1263     10104      5.22
(RELTRO:COUNT-FOUND1 ALIST SEARCH)              16      1341     10728      5.54
(ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...)        16      1434     11472      5.93
(LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-008)        16      1560     12480      6.45 <<<<<<
(RELTRO:COUNT-FOUND ALIST SEARCH)               16      1734     13872      7.17
Compiled:
Code: [Select]
Elapsed milliseconds / relative speed for 512 iteration(s):
    (ALE_LISTCOUNTITEM3 SEARCH ALIST).............2605 / 8.03 <fastest>
    (ALE_LISTCOUNTITEM3 SEARCH ALIST).............3011 / 6.95
    (ALE_LISTCOUNTITEM SEARCH ALIST)..............6209 / 3.37
    (ALE_LISTCOUNTITEM SEARCH ALIST)..............6739 / 3.1
    (CHLH_JD:COUNT SEARCH ALIST)..................7036 / 2.97
    (CHLH_JD:COUNT SEARCH ALIST)..................9656 / 2.17
    (LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-...).....10312 / 2.03 <<<<<<<<
    (ALE_LISTCOUNTITEM2 SEARCH ALIST)............11185 / 1.87
    (ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...).....11888 / 1.76
    (LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-...).....12948 / 1.62
    (ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...).....13619 / 1.54
    (DG:COUNT-FOUND ALIST SEARCH)................14383 / 1.45
    (ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...).....15694 / 1.33
    (DG:COUNT-FOUND ALIST SEARCH)................17238 / 1.21
    (RELTRO:COUNT-FOUND ALIST SEARCH)............17831 / 1.17
    (ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...).....18330 / 1.14
    (RELTRO:COUNT-FOUND1 ALIST SEARCH)...........18345 / 1.14
    (ALE_LISTCOUNTITEM2 SEARCH ALIST)............18673 / 1.12
    (RELTRO:COUNT-FOUND1 ALIST SEARCH)...........19001 / 1.1
    (RELTRO:COUNT-FOUND ALIST SEARCH)............20919 / 1 <slowest>

 Benchmarking .................... done for 128 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(ALE_LISTCOUNTITEM3 SEARCH ALIST)              128      1110      1110      1.00
(ALE_LISTCOUNTITEM3 SEARCH ALIST)              128      1576      1576      1.42
(ALE_LISTCOUNTITEM SEARCH ALIST)                64      1673      3346      3.01
(LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-008)        64      1840      3680      3.32  <<<<<<<
(CHLH_JD:COUNT SEARCH ALIST)                    32      1029      4116      3.71
(LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-008)        32      1060      4240      3.82
(ALE_LISTCOUNTITEM SEARCH ALIST)                32      1248      4992      4.50
(DG:COUNT-FOUND ALIST SEARCH)                   32      1295      5180      4.67
(ALE_LISTCOUNTITEM2 SEARCH ALIST)               32      1309      5236      4.72
(DG:COUNT-FOUND ALIST SEARCH)                   32      1310      5240      4.72
(ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...)        32      1481      5924      5.34
(CHLH_JD:COUNT SEARCH ALIST)                    32      1593      6372      5.74
(RELTRO:COUNT-FOUND ALIST SEARCH)               32      1902      7608      6.85
(ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...)        32      1903      7612      6.86
(RELTRO:COUNT-FOUND1 ALIST SEARCH)              32      1919      7676      6.92
(RELTRO:COUNT-FOUND ALIST SEARCH)               16      1592     12736     11.47
(ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...)        16      1623     12984     11.70
(ALE_LISTCOUNTITEM2 SEARCH ALIST)               16      1684     13472     12.14
(ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...)        16      1715     13720     12.36
(RELTRO:COUNT-FOUND1 ALIST SEARCH)               8      1013     16208     14.60
--------------------------------------------------------------------------------

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: fastest way to get count of an item in a list
« Reply #39 on: June 04, 2014, 07:03:17 AM »
My test:
Seems something strange happened with the full benchmark during the compiled test, e.g: 512 iterations on RELTRO:COUNT-FOUND took 20s for compiled, but only 8s for not compiled.

At first I thought it's due to the others benefiting more from optimization. But that would mean more iterations (i.e. 1024), but both tests show 512.

Not to mention, the duplicate tests seem all over the place. Did you perhaps have something else running while the tests were done? This is the main reason I didn't like the long benchmark - more tendency to get interference because you need to leave the PC alone during the test.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: fastest way to get count of an item in a list
« Reply #40 on: June 04, 2014, 08:45:23 AM »
Did you perhaps have something else running while the tests were done?
I have only AutoCAD 2013 running:
Code: [Select]
Compiled (only fuzz versions)
Length   : 64000
Elapsed milliseconds / relative speed for 128 iteration(s):
    (LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-...).....1529 / 5.02 <fastest>
    (LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-...).....1669 / 4.6
    (ALE_LISTCOUNTITEMFUZZ4 SEARCH ALIST...).....3729 / 2.06
    (ALE_LISTCOUNTITEMFUZZ4 SEARCH ALIST...).....4524 / 1.7
    (ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...).....6037 / 1.27
    (ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...).....7020 / 1.09
    (ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...).....7160 / 1.07
    (ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...).....7675 / 1 <slowest>

 Benchmarking ........ done for 32 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(ALE_LISTCOUNTITEMFUZZ4 SEARCH ALIST...)        32      1110      1110      1.00
(ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...)        32      1326      1326      1.19
(ALE_LISTCOUNTITEMFUZZ4 SEARCH ALIST...)        32      1546      1546      1.39
(LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-008)        32      1575      1575      1.42
(LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-008)        32      2059      2059      1.85
(ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...)        32      2666      2666      2.40
(ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...)        16      1716      3432      3.09
(ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...)        16      1858      3716      3.35
--------------------------------------------------------------------------------

Second run:
Length   : 64000
Elapsed milliseconds / relative speed for 128 iteration(s):
    (LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-...).....1700 / 2.46 <fastest>
    (ALE_LISTCOUNTITEMFUZZ4 SEARCH ALIST...).....1919 / 2.18
    (ALE_LISTCOUNTITEMFUZZ4 SEARCH ALIST...).....1997 / 2.09
    (LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-...).....2231 / 1.87
    (ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...).....3479 / 1.2
    (ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...).....3869 / 1.08
    (ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...).....4165 / 1
    (ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...).....4181 / 1 <slowest>

 Benchmarking ........ done for 64 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-008)        64      1637      1637      1.00
(LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-008)        32      1325      2650      1.62
(ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...)        32      1732      3464      2.12
(ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...)        32      1918      3836      2.34
(ALE_LISTCOUNTITEMFUZZ4 SEARCH ALIST...)        16      1014      4056      2.48
(ALE_LISTCOUNTITEMFUZZ4 SEARCH ALIST...)        16      1030      4120      2.52
(ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...)        16      1122      4488      2.74
(ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...)        32      2479      4958      3.03
--------------------------------------------------------------------------------
Code: [Select]
; not "logic" version
(defun ALE_ListCountItemFuzz4 (i l f / c)
  (setq c 0)
  (apply
    (function
      (lambda (li ll lf)
        (foreach x ll (if (equal li x lf) (setq c (1+ c))))
      )
    )
    (list i l f)
  )
  c
)
Code: [Select]
COMPILED
Length   : 64000
Elapsed milliseconds / relative speed for 512 iteration(s):
    (ALE_LISTCOUNTITEM3 SEARCH ALIST).......1779 / 10.83 <fastest>
    (ALE_LISTCOUNTITEM3 SEARCH ALIST).......1935 / 9.96
    (CHLH_JD:COUNT SEARCH ALIST)............5475 / 3.52
    (ALE_LISTCOUNTITEM SEARCH ALIST)........5709 / 3.37
    (CHLH_JD:COUNT SEARCH ALIST)............6131 / 3.14
    (ALE_LISTCOUNTITEM SEARCH ALIST)........7925 / 2.43
    (DG:COUNT-FOUND ALIST SEARCH)...........9687 / 1.99
    (ALE_LISTCOUNTITEM2 SEARCH ALIST)......10062 / 1.91
    (DG:COUNT-FOUND ALIST SEARCH)..........10265 / 1.88
    (ALE_LISTCOUNTITEM2 SEARCH ALIST)......14274 / 1.35
    (RELTRO:COUNT-FOUND1 ALIST SEARCH).....14696 / 1.31
    (RELTRO:COUNT-FOUND1 ALIST SEARCH).....14804 / 1.3
    (RELTRO:COUNT-FOUND ALIST SEARCH)......16552 / 1.16
    (RELTRO:COUNT-FOUND ALIST SEARCH)......19266 / 1 <slowest>

 Benchmarking .............. done for 256 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(ALE_LISTCOUNTITEM3 SEARCH ALIST)              256      1746      1746      1.00
(ALE_LISTCOUNTITEM3 SEARCH ALIST)              256      1747      1747      1.00
(ALE_LISTCOUNTITEM SEARCH ALIST)                64      1326      5304      3.04
(ALE_LISTCOUNTITEM SEARCH ALIST)                64      1341      5364      3.07
(CHLH_JD:COUNT SEARCH ALIST)                    64      1342      5368      3.07
(CHLH_JD:COUNT SEARCH ALIST)                    64      1391      5564      3.19
(DG:COUNT-FOUND ALIST SEARCH)                   32      1186      9488      5.43
(ALE_LISTCOUNTITEM2 SEARCH ALIST)               32      1217      9736      5.58
(ALE_LISTCOUNTITEM2 SEARCH ALIST)               32      1232      9856      5.64
(RELTRO:COUNT-FOUND1 ALIST SEARCH)              32      1734     13872      7.95
(RELTRO:COUNT-FOUND1 ALIST SEARCH)              32      1750     14000      8.02
(RELTRO:COUNT-FOUND ALIST SEARCH)               32      1842     14736      8.44
(RELTRO:COUNT-FOUND ALIST SEARCH)               32      1903     15224      8.72
(DG:COUNT-FOUND ALIST SEARCH)                   16      1123     17968     10.29
--------------------------------------------------------------------------------
Code: [Select]
NOT COMPILED
Length   : 64000

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

    (ALE_LISTCOUNTITEM3 SEARCH ALIST).......1357 / 7.41 <fastest>
    (ALE_LISTCOUNTITEM3 SEARCH ALIST).......2309 / 4.36
    (CHLH_JD:COUNT SEARCH ALIST)............3526 / 2.85
    (ALE_LISTCOUNTITEM SEARCH ALIST)........3604 / 2.79
    (CHLH_JD:COUNT SEARCH ALIST)............4555 / 2.21
    (DG:COUNT-FOUND ALIST SEARCH)...........5460 / 1.84
    (ALE_LISTCOUNTITEM SEARCH ALIST)........5741 / 1.75
    (DG:COUNT-FOUND ALIST SEARCH)...........6567 / 1.53
    (ALE_LISTCOUNTITEM2 SEARCH ALIST).......6973 / 1.44
    (ALE_LISTCOUNTITEM2 SEARCH ALIST).......7722 / 1.3
    (RELTRO:COUNT-FOUND1 ALIST SEARCH)......8408 / 1.2
    (RELTRO:COUNT-FOUND ALIST SEARCH).......9173 / 1.1
    (RELTRO:COUNT-FOUND ALIST SEARCH).......9173 / 1.1
    (RELTRO:COUNT-FOUND1 ALIST SEARCH).....10062 / 1 <slowest>

 Benchmarking .............. done for 128 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(ALE_LISTCOUNTITEM3 SEARCH ALIST)              128      1388      1388      1.00
(ALE_LISTCOUNTITEM3 SEARCH ALIST)               64      1544      3088      2.22
(ALE_LISTCOUNTITEM SEARCH ALIST)                64      1558      3116      2.24
(ALE_LISTCOUNTITEM SEARCH ALIST)                32      1012      4048      2.92
(CHLH_JD:COUNT SEARCH ALIST)                    32      1139      4556      3.28
(DG:COUNT-FOUND ALIST SEARCH)                   32      1310      5240      3.78
(ALE_LISTCOUNTITEM2 SEARCH ALIST)               32      1358      5432      3.91
(DG:COUNT-FOUND ALIST SEARCH)                   32      1465      5860      4.22
(CHLH_JD:COUNT SEARCH ALIST)                    32      1577      6308      4.54
(RELTRO:COUNT-FOUND ALIST SEARCH)               16      1045      8360      6.02
(RELTRO:COUNT-FOUND1 ALIST SEARCH)              16      1061      8488      6.12
(RELTRO:COUNT-FOUND ALIST SEARCH)               32      2247      8988      6.48
(ALE_LISTCOUNTITEM2 SEARCH ALIST)               16      1185      9480      6.83
(RELTRO:COUNT-FOUND1 ALIST SEARCH)              32      2386      9544      6.88
--------------------------------------------------------------------------------

chlh_jd

  • Guest
Re: fastest way to get count of an item in a list
« Reply #41 on: June 04, 2014, 09:44:37 PM »
My test:
...
Compiled:
Code: [Select]
Elapsed milliseconds / relative speed for 512 iteration(s):
    (ALE_LISTCOUNTITEM3 SEARCH ALIST).............2605 / 8.03 <fastest>
    (ALE_LISTCOUNTITEM3 SEARCH ALIST).............3011 / 6.95
    (ALE_LISTCOUNTITEM SEARCH ALIST)..............6209 / 3.37
    (ALE_LISTCOUNTITEM SEARCH ALIST)..............6739 / 3.1
    (CHLH_JD:COUNT SEARCH ALIST)..................7036 / 2.97
    (CHLH_JD:COUNT SEARCH ALIST)..................9656 / 2.17
    (LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-...).....10312 / 2.03 <<<<<<<<
    (ALE_LISTCOUNTITEM2 SEARCH ALIST)............11185 / 1.87
    (ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...).....11888 / 1.76
    (LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-...).....12948 / 1.62
    (ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...).....13619 / 1.54
    (DG:COUNT-FOUND ALIST SEARCH)................14383 / 1.45
    (ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...).....15694 / 1.33
    (DG:COUNT-FOUND ALIST SEARCH)................17238 / 1.21
    (RELTRO:COUNT-FOUND ALIST SEARCH)............17831 / 1.17
    (ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...).....18330 / 1.14
    (RELTRO:COUNT-FOUND1 ALIST SEARCH)...........18345 / 1.14
    (ALE_LISTCOUNTITEM2 SEARCH ALIST)............18673 / 1.12
    (RELTRO:COUNT-FOUND1 ALIST SEARCH)...........19001 / 1.1
    (RELTRO:COUNT-FOUND ALIST SEARCH)............20919 / 1 <slowest>

 Benchmarking .................... done for 128 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(ALE_LISTCOUNTITEM3 SEARCH ALIST)              128      1110      1110      1.00
(ALE_LISTCOUNTITEM3 SEARCH ALIST)              128      1576      1576      1.42
(ALE_LISTCOUNTITEM SEARCH ALIST)                64      1673      3346      3.01
(LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-008)        64      1840      3680      3.32  <<<<<<<
(CHLH_JD:COUNT SEARCH ALIST)                    32      1029      4116      3.71
(LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-008)        32      1060      4240      3.82
(ALE_LISTCOUNTITEM SEARCH ALIST)                32      1248      4992      4.50
(DG:COUNT-FOUND ALIST SEARCH)                   32      1295      5180      4.67
(ALE_LISTCOUNTITEM2 SEARCH ALIST)               32      1309      5236      4.72
(DG:COUNT-FOUND ALIST SEARCH)                   32      1310      5240      4.72
(ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...)        32      1481      5924      5.34
(CHLH_JD:COUNT SEARCH ALIST)                    32      1593      6372      5.74
(RELTRO:COUNT-FOUND ALIST SEARCH)               32      1902      7608      6.85
(ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...)        32      1903      7612      6.86
(RELTRO:COUNT-FOUND1 ALIST SEARCH)              32      1919      7676      6.92
(RELTRO:COUNT-FOUND ALIST SEARCH)               16      1592     12736     11.47
(ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...)        16      1623     12984     11.70
(ALE_LISTCOUNTITEM2 SEARCH ALIST)               16      1684     13472     12.14
(ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...)        16      1715     13720     12.36
(RELTRO:COUNT-FOUND1 ALIST SEARCH)               8      1013     16208     14.60
--------------------------------------------------------------------------------
Thanks Alessi for test .
This result seems correct ,  please post your args.lsp , thanks .

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: fastest way to get count of an item in a list
« Reply #42 on: June 05, 2014, 02:29:58 AM »
Thanks Alessi for test .
This result seems correct ,  please post your args.lsp , thanks .
You're welcome, my args are the same of Irne:
Code: [Select]
(defun Random  (seed /)
     (if (not seed)
       (setq seed (if *random:seed*
                    *random:seed*
                    (setq *random:seed* (getvar "DATE"))))
       (setq *random:seed* seed))
     (setq seed          (rem (+ (* 25173 seed) 13849) 65536)
           *random:seed* seed)
     (/ seed 65536)
)
(progn
(setq aList nil)
(length (repeat 1000 (setq aList (cons (list (random nil) (random nil) (random nil)) aList))))
(length (repeat 6 (setq aList (append aList aList))))
(setq search (nth 12345 aList))
(princ "\nLength   : ") (princ (length aList)) (princ "\n")
)

Ex.: (ALE_ListCountItemFuzz5 SEARCH ALIST  1.0e-008)

chlh_jd

  • Guest
Re: fastest way to get count of an item in a list
« Reply #43 on: June 06, 2014, 07:24:06 AM »
Thanks Alessi offer the test list construct function .

In my computer , test result (a position is '(1001 10001 59428 )) :

Michael's Benchmark test result .
Code: [Select]
Benchmarking .............Elapsed milliseconds / relative speed for 1024 iteration(s):

    (ALE_LISTCOUNTITEM3 A L).......1482 / 8.17 <fastest>
    (ALE_LISTCOUNTITEM3 A L).......1482 / 8.17
    (ALE_LISTCOUNTITEM A L)........4883 / 2.48
    (CHLH_JD:COUNT A L)............5195 / 2.33
    (DG:COUNT-FOUND L A)...........8003 / 1.51
    (ALE_LISTCOUNTITEM2 A L).......8174 / 1.48
    (RELTRO:COUNT-FOUND1 L A).....12106 / 1.00 <slowest>
Benchmarking .............Elapsed milliseconds / relative speed for 1024 iteration(s):

    (ALE_LISTCOUNTITEM3 A L).......1482 / 8.18 <fastest>
    (ALE_LISTCOUNTITEM3 A L).......1482 / 8.18
    (ALE_LISTCOUNTITEM A L)........4899 / 2.47
    (CHLH_JD:COUNT A L)............5195 / 2.33
    (DG:COUNT-FOUND L A)...........7987 / 1.52
    (ALE_LISTCOUNTITEM2 A L).......8190 / 1.48
    (RELTRO:COUNT-FOUND1 L A).....12122 / 1.00 <slowest>
Benchmarking .............Elapsed milliseconds / relative speed for 1024 iteration(s):

    (ALE_LISTCOUNTITEM3 A L).......1482 / 8.16 <fastest>
    (ALE_LISTCOUNTITEM3 A L).......1482 / 8.16
    (ALE_LISTCOUNTITEM A L)........4899 / 2.47
    (CHLH_JD:COUNT A L)............5179 / 2.33
    (DG:COUNT-FOUND L A)...........7987 / 1.51
    (ALE_LISTCOUNTITEM2 A L).......8159 / 1.48
    (RELTRO:COUNT-FOUND1 L A).....12090 / 1.00 <slowest>

quickbench function see here  http://www.theswamp.org/index.php?action=dlattach;topic=42091.0;attach=22832
Code: [Select]
Benchmarking ..... done for 256 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(#<USUBR @000000002c51cc50 ALE_LISTC...)       256      1577      1577      4.63
(#<USUBR @000000002c51cc50 ALE_LISTC...)       256      1653      1653      4.41
(#<USUBR @000000002c51c188 ALE_LISTC...)       128      1152      2304      3.17
(#<USUBR @0000000037505c50 CHLH_JD:C...)       128      1325      2650      2.75
(#<USUBR @000000003764d368 ALE_LISTC...)        64      1824      7296      1.00
--------------------------------------------------------------------------------

Benchmarking ..... done for 256 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(#<USUBR @000000002c51cc50 ALE_LISTC...)       256      1590      1590      4.56
(#<USUBR @000000002c51cc50 ALE_LISTC...)       256      1608      1608      4.50
(#<USUBR @000000002c51c188 ALE_LISTC...)       128      1169      2338      3.10
(#<USUBR @0000000037505c50 CHLH_JD:C...)       128      1326      2652      2.73
(#<USUBR @000000003764d368 ALE_LISTC...)        64      1811      7244      1.00
--------------------------------------------------------------------------------

Benchmarking ..... done for 256 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(#<USUBR @000000002c51cc50 ALE_LISTC...)       256      1621      1621      4.58
(#<USUBR @000000002c51cc50 ALE_LISTC...)       256      1622      1622      4.58
(#<USUBR @000000002c51c188 ALE_LISTC...)       128      1200      2400      3.09
(#<USUBR @0000000037505c50 CHLH_JD:C...)       128      1248      2496      2.97
(#<USUBR @000000003764d368 ALE_LISTC...)        64      1856      7424      1.00
--------------------------------------------------------------------------------

I guess : member function's scan method must be one by one , just like only use car & cdr , but vl-position is quickly scan (not car every item or faster alloc the member ) ,and then used cddddr is faster than use 4 times cdr .

If so , suggest VLIDE improve member function  :-)
« Last Edit: June 06, 2014, 07:34:16 AM by chlh_jd »

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: fastest way to get count of an item in a list
« Reply #44 on: June 06, 2014, 08:55:01 AM »
...
If so , suggest VLIDE improve member function  :)
Yes, this is faster of member on long lists or even short lists (1000 elements) if Item is near final position:
(defun ALE_List_Member (i l)
  (ALE_List_NthCdr (vl-position i l) l)
)
%%
One other interesting thing to note is, as Lee said, that the version with "foreach" is much faster if compiled:
Code: [Select]
NOT compiled
Elapsed milliseconds / relative speed for 512 iteration(s):
    (ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...)......5882 / 2.13
    (ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...)......5991 / 2.09
    (ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...)......7738 / 1.62
    (ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...)......8456 / 1.48
    (LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-...).....11263 / 1.11 <<<<<<<<
    (LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-...).....12527 / 1 <slowest>  <<<<<<<<<<

Compiled
Elapsed milliseconds / relative speed for 512 iteration(s):
    (LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-...).....10312 / 2.03 <<<<<<<<
    (ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...).....11888 / 1.76
    (LM:COUNTITEMFUZZ SEARCH ALIST 1.0e-...).....12948 / 1.62
    (ALE_LISTCOUNTITEMFUZZ2 SEARCH ALIST...).....13619 / 1.54
    (ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...).....15694 / 1.33
    (ALE_LISTCOUNTITEMFUZZ SEARCH ALIST ...).....18330 / 1.14