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

0 Members and 1 Guest are viewing this topic.

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