Topic: fastest way to get count of an item in a list

[mailmaverick]

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]

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]

Maybe pass the result of (vl-remove-if-not ...) to (length ...)?  Because coordinates are REALs you'll need a specific comparison method.

[irneb]

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.

[Marc'Antonio Alessi]

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]

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]

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]

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]

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]

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]

@ Marc'Antonio Alessi:
Isn't it more logical to use mapcar instead of vl-every?

[Marc'Antonio Alessi]

@ Marc'Antonio Alessi:
Isn't it more logical to use mapcar instead of vl-every?

Yes, but vl-every is surprisingly faster...

[irneb]

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.

[Marc'Antonio Alessi]

@ 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]

...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.