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

0 Members and 1 Guest are viewing this topic.

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.com • http://cadanalyst.slack.com • http://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.com • http://cadanalyst.slack.com • http://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.com • http://cadanalyst.slack.com • http://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?