Topic: prelst and sufflst - witch code is the best ?

[chlh_jd]

In a hurry to go out, have not had time to join the others function to compare ,
I am very apologize . good nithgt !

[Lee Mac]

Code: [Select]

(defun prelst (x l / n)
  (setq n (length (vl-member-if-not '(lambda (a) (equal a x 1e-8)) l))
l (reverse l))
  (repeat (/ n 4)
    (setq l (cddddr l)))
  (repeat (rem n 4)
    (setq l (cdr l)))
  (reverse l))


This will always return nil if the supplied item is not the first element of the list (since vl-member-if-not will return the whole list if not).

[Lee Mac]

Another:

Code - Auto/Visual Lisp: [Select]

1. (defun prelst ( x l / f )
2.     (defun f ( x l a )
3.         (if l
4.             (if (equal x (car l) 1e-8)
5.                 (reverse a)
6.                 (f x (cdr l) (cons (car l) a))
7.             )
8.             (reverse a)
9.         )
10.     )
11.     (f x l nil)
12. )

[Lee Mac]

Benchmarking all prelst functions:

Test Function:

Code - Auto/Visual Lisp: [Select]

1. ;; Benchmark function by MP
2. ;; http://www.theswamp.org/lilly_pond/mp/lisp/benchmark.txt
3.  
4. (defun c:test ( / f i l n )
5.     (setq i 0)
6.     (repeat 100 (setq l (cons (setq i (1+ i)) l)))
7.     (setq l (reverse l))
8.     (setq f
9.        '(
10.             (mr:prelst1 l n)
11.             (mr:prelst2 l n)
12.             (mr:prelst3 l n)
13.             (cab:prelst l n)
14.             (ch:prelst  n l 1e-8)
15.             (lm:prelst1 n l)
16.             (ph:pref    l n)
17.             (lm:prelst2 n l)
18.             (lm:prelst3 n l)
19.             (lm:prelst4 n l)
20.             (lm:prelst5 n l)
21.         )
22.     )
23.  
24.     (setq n 25)
25.     (benchmark f)
26.     (gc)
27.     (setq n 50)
28.     (benchmark f)
29.     (gc)
30.     (setq n 75)
31.     (benchmark f)
32.     (gc)
33.     (princ)
34. )

List of 100 items, return portion of list up to item n:

n=25

Code - Auto/Visual Lisp: [Select]

1. Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):
2.  
3.     (CAB:PRELST L N).............1014 / 2.28 <fastest>
4.     (LM:PRELST3 N L).............1076 / 2.15
5.     (LM:PRELST5 N L).............1154 / 2.00
6.     (MR:PRELST2 L N).............1217 / 1.90
7.     (CH:PRELST N L 1.0e-008).....1264 / 1.83
8.     (MR:PRELST3 L N).............1295 / 1.78
9.     (LM:PRELST1 N L).............1778 / 1.30
10.     (PH:PREF L N)................1825 / 1.27
11.     (LM:PRELST2 N L).............1825 / 1.27
12.     (LM:PRELST4 N L).............1903 / 1.21
13.     (MR:PRELST1 L N).............2309 / 1.00 <slowest>

n=50

Code - Auto/Visual Lisp: [Select]

1. Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):
2.  
3.     (PH:PREF L N)................1435 / 1.70 <fastest>
4.     (CAB:PRELST L N).............1497 / 1.63
5.     (LM:PRELST3 N L).............1654 / 1.47
6.     (LM:PRELST5 N L).............1748 / 1.39
7.     (LM:PRELST1 N L).............1763 / 1.38
8.     (MR:PRELST2 L N).............1856 / 1.31
9.     (LM:PRELST2 N L).............1919 / 1.27
10.     (CH:PRELST N L 1.0e-008).....1981 / 1.23
11.     (MR:PRELST3 L N).............2184 / 1.11
12.     (LM:PRELST4 N L).............2262 / 1.08
13.     (MR:PRELST1 L N).............2434 / 1.00 <slowest>

n=75

Code - Auto/Visual Lisp: [Select]

1. Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):
2.  
3.     (PH:PREF L N)................1030 / 3.07 <fastest>
4.     (LM:PRELST1 N L).............1528 / 2.07
5.     (LM:PRELST2 N L).............1997 / 1.59
6.     (CAB:PRELST L N).............2028 / 1.56
7.     (LM:PRELST3 N L).............2277 / 1.39
8.     (LM:PRELST5 N L).............2356 / 1.34
9.     (MR:PRELST2 L N).............2496 / 1.27
10.     (MR:PRELST1 L N).............2590 / 1.22
11.     (LM:PRELST4 N L).............2605 / 1.22
12.     (CH:PRELST N L 1.0e-008).....2777 / 1.14
13.     (MR:PRELST3 L N).............3167 / 1.00 <slowest>

Attached are the tested functions.

[CADDOG]

Benchmarking all prelst functions:

The official ruling has been challenged. 
Changing quoted lambda's to optimized (functions) produced a different photo finish.

EDIT:
Lee, I did not raise the ceiling, but did so after you pointed it out.

I removed my results (because of it's innacuracy), and

The top competitors in my own tests were quite supprising.  This is probably due to the lack of overhead that's required for iterative methods.
I was able to get 10,001 length lists to run for all functions..
The tests are fantastic and show me that optimization is important, but also that the least verbose isn't always the bestest under heavy loads of bulk data processing.

Overhead of a function also doesn't mean it's the worst either.  Evidence by the likes of the MergeSort algorithm, which uses three times the memory as, say, a JSort or InsertSort.  At one million entries MergeSort excels while Jsort kills MergeSort below 50,000 (of course this depends further on your implementation methods and even comilers).

The different bench test results vary from the method of testing and the data set as we've seen through the multiple user results.  This thread has shown me that your data set just needs to be considered and the generous contributions tested yourself.

Here's the suprising results I got out of 10,001 length list, contradicts other user's results.  I did not expect function optimized lambda's to perform so poorly.  I remember a post from long ago that explained (in autolisp) why it's one way or the other, but I remember neither the lesson of the author nor where I read it.

Code - Auto/Visual Lisp: [Select]

1. n=10,001
2. Elapsed milliseconds / relative speed for 32768 iteration(s):
3.     (LM:PRELST3 N L)...............1217 / 684.78 <fastest>
4.     (CAB:PRELST L N)...............1232 / 676.44
5.     (CH:PRELST N L 1.0e-008).......1295 / 643.53
6.     (LM:PRELST5 N L)...............1295 / 643.53
7.     (MR:PRELST2 L N)...............1310 / 636.16
8.     (MR:PRELST3 L N)...............1326 / 628.49
9.     (LM:PRELST4 N L)...............1544 / 539.75
10.     (LM:PRELST2 N L).............180992 / 4.60
11.     (LM:PRELST1 N L).............343389 / 2.43
12.     (PH:PREF L N)................825308 / 1.01
13.     (MR:PRELST1 L N).............833373 / 1.00 <slowest>
14.  

Under a presumption that garabage collection could be skewing the results of functions that were later in the test, I switched the order of execution for the test, and the same results were obtained.

As far as I can see ((now)), that there is not just one winner, rather there were 7.  I've enjoyed this thread emensly.  Looking forward to see if there's' any basis of what I noticed with lambda.

They were compiled.

[Lee Mac]

The official ruling has been challenged. 
Changing quoted lambda's to optimized (functions) produced a different photo finish.
LM:PRELST1 is the clear winner for most situations.

Code - Auto/Visual Lisp: [Select]

1. (defun lm:prelst1 ( x l )
2.     (reverse (cdr (vl-member-if (function (lambda ( a ) (equal a x 1e-8))) (reverse l))))
3. )

Good spot CADDOG, thanks

Code - Auto/Visual Lisp: [Select]

1. n=150
2.  
3. < ... >
4.  
5. n=5,000
6.  
7. < ... >
8.  
9. n=10,000

Did you ensure that you altered the length of the list l for these tests involving higher values of the parameter n? Since any value of n over 100 for the curret list size would yield the same result 

[ribarm]

Maybe it's the fastest, but what you haven't checked - it's also wrong one :

Code: [Select]

Command: (setq l '(0 1 2 3 4 5 5 5 6 7 8 9))
(0 1 2 3 4 5 5 5 6 7 8 9)

Command: (lm:prelst1 5 l)
(0 1 2 3 4 5 5)

prelst function should return all first elements from list until first occur of supplied element :

Code: [Select]

Command: (setq l '(0 1 2 3 4 5 5 5 6 7 8 9))
(0 1 2 3 4 5 5 5 6 7 8 9)

Command: (prelst 5 l)
(0 1 2 3 4)

M.R.

[chlh_jd]

Code: [Select]

(defun prelst (x l / n)
  (setq n (length (vl-member-if-not '(lambda (a) (equal a x 1e-8)) l))
l (reverse l))
  (repeat (/ n 4)
    (setq l (cddddr l)))
  (repeat (rem n 4)
    (setq l (cdr l)))
  (reverse l))


This will always return nil if the supplied item is not the first element of the list (since vl-member-if-not will return the whole list if not).

It did return NIL .
That day has no time test .

[chlh_jd]

What about test with Big Pointset ?
More Point can use Qjchen's post . http://www.theswamp.org/index.php?topic=32874.0
Or see I post the attachment

[pBe]

wouldn't it better to use one function for both.

example

Code - Auto/Visual Lisp: [Select]

1. (defun leavem (n l m / x)
2.         (if (setq x (vl-remove-if (function (lambda (j)
3.                         (m n j))) l)) x l))

(setq ls '(0 1 2 3 4 5 5 6 7 8 9 10) )

 (leavem 5 ls >=)
(6 7 8 9 10)

 (leavem 5 ls <=)
(0 1 2 3 4)

(leavem 25 ls <=)
(0 1 2 3 4 5 5 6 7 8 9 10)

[chlh_jd]

 

What about test with Big Pointset ?
More Point can use Qjchen's post . http://www.theswamp.org/index.php?topic=32874.0
Or see I post the attachment

Test in this post dwg , 10000 random points (No same points) .
The benchmark function can't get the test result , error massage :

Code: [Select]

... hard errors ***
Has reached an internal stack limit (analog)
So I change into quickbench .
Quickbench see here http://www.theswamp.org/index.php?action=dlattach;topic=42091.0;attach=22832
Test result with Lee Mac's compare lsp , radom select the search point .
1st (Select center point)

Code: [Select]

Benchmarking ......... done for 256 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(LM:PRELST2 N L)                               256      1576      1576    153.34
(PH:PREF N L)                                  256      1717      1717    140.75
(LM:PRELST4 N L)                               128      1184      2368    102.05
(LM:PRELST3 N L)                               128      1732      3464     69.76
(LM:PRELST5 N L)                               128      1809      3618     66.79
(CH:PRELST N L)                                128      1810      3620     66.76
(MR:PRELST2 N L)                                64      1484      5936     40.71
(MR:PRELST1 N L)                                64      1764      7056     34.25
(MR:PRELST3 N L)                                 2      1888    241664      1.00
--------------------------------------------------------------------------------
2nd (Select rightbottom point)

Code: [Select]

Benchmarking ......... done for 512 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(LM:PRELST4 N L)                               512      1044      1044     13.16
(LM:PRELST3 N L)                               512      1513      1513      9.08
(LM:PRELST5 N L)                               512      1532      1532      8.97
(CH:PRELST N L)                                512      1545      1545      8.89
(LM:PRELST2 N L)                               512      1825      1825      7.53
(MR:PRELST2 N L)                               256      1357      2714      5.06
(PH:PREF N L)                                  128      1591      6364      2.16
(MR:PRELST1 N L)                                64      1419     11352      1.21
(MR:PRELST3 N L)                                64      1717     13736      1.00
--------------------------------------------------------------------------------
3rd (Select LeftTop point)

Code: [Select]

Benchmarking ......... done for 256 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(PH:PREF N L)                                  256      1421      1421    233.30
(LM:PRELST2 N L)                               256      1686      1686    196.63
(LM:PRELST4 N L)                               128      1357      2714    122.15
(LM:PRELST3 N L)                               128      2013      4026     82.34
(LM:PRELST5 N L)                                64      1015      4060     81.66
(CH:PRELST N L)                                 64      1029      4116     80.54
(MR:PRELST1 N L)                                32      1093      8744     37.91
(MR:PRELST2 N L)                                32      1137      9096     36.45
(MR:PRELST3 N L)                                 2      2590    331520      1.00
--------------------------------------------------------------------------------
4th (Select LeftBottom point)

Code: [Select]

Benchmarking ......... done for 128
iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(LM:PRELST2 N L)                               128      1949      1949     32.26
(LM:PRELST4 N L)                               128      2012      2012     31.25
(PH:PREF N L)                                   64      1590      3180     19.77
(LM:PRELST5 N L)                                64      1904      3808     16.51
(LM:PRELST3 N L)                                64      2012      4024     15.63
(MR:PRELST2 N L)                                32      1047      4188     15.01
(CH:PRELST N L)                                 32      1169      4676     13.45
(MR:PRELST1 N L)                                32      1545      6180     10.17
(MR:PRELST3 N L)                                 4      1965     62880      1.00
--------------------------------------------------------------------------------
5th (Select RightTop point)

Code: [Select]

Benchmarking ......... done for 256
iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(PH:PREF N L)                                  256      1092      1092    267.02
(LM:PRELST2 N L)                               256      1856      1856    157.10
(LM:PRELST4 N L)                               128      1514      3028     96.30
(CH:PRELST N L)                                 64      1170      4680     62.30
(LM:PRELST5 N L)                                64      1172      4688     62.20
(LM:PRELST3 N L)                                64      1201      4804     60.70
(MR:PRELST1 N L)                                32      1093      8744     33.35
(MR:PRELST2 N L)                                32      1357     10856     26.86
(MR:PRELST3 N L)                                 1      1139    291584      1.00
--------------------------------------------------------------------------------


[chlh_jd]

Above compares are not compiled , It show the LM:prelst2 win it .

Code: [Select]

;; Lee Mac
;; http://www.theswamp.org/index.php?topic=43004.msg482478#msg482478

(defun lm:prelst2 ( x l / f )
    (vl-remove-if '(lambda ( a ) (or f (setq f (equal a x 1e-8)))) l)
)

Just a little doubt : 'vl-remove-if must traverse the entire List , after find it omitted 'equal .

[chlh_jd]

The above missed Alan function, I so apologize .
Retest after compiled , it get diffrrent result
1st (Center point)

Code: [Select]

Benchmarking .......... done for 256 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(PH:PREF N L)                                  256      1325      1325    153.70
(MR:PRELST1 N L)                               128      1013      2026    100.52
(CAB:PRELST N L)                               128      1014      2028    100.42
(LM:PRELST5 N L)                               128      1232      2464     82.65
(CH:PRELST N L)                                128      1265      2530     80.49
(LM:PRELST3 N L)                               128      1265      2530     80.49
(MR:PRELST2 N L)                               128      1341      2682     75.93
(LM:PRELST2 N L)                               128      1450      2900     70.22
(LM:PRELST4 N L)                               128      1810      3620     56.26
(MR:PRELST3 N L)                                 2      1591    203648      1.00
--------------------------------------------------------------------------------
2nd (RB point)

Code: [Select]

Benchmarking .......... done for 512 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(CAB:PRELST N L)                               512      1966      1966     40.11
(LM:PRELST5 N L)                               256      1217      2434     32.39
(LM:PRELST3 N L)                               256      1218      2436     32.37
(CH:PRELST N L)                                256      1232      2464     32.00
(MR:PRELST2 N L)                               256      1295      2590     30.44
(MR:PRELST1 N L)                               256      1638      3276     24.07
(LM:PRELST4 N L)                               256      1919      3838     20.54
(PH:PREF N L)                                  128      1030      4120     19.14
(LM:PRELST2 N L)                               128      1248      4992     15.79
(MR:PRELST3 N L)                                 8      1232     78848      1.00
--------------------------------------------------------------------------------
3rd (LT point)

Code: [Select]

Benchmarking .......... done for 512 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(PH:PREF N L)                                  512      1637      1637    458.67
(MR:PRELST1 N L)                               128      1173      4692    160.03
(CAB:PRELST N L)                               128      1419      5676    132.28
(LM:PRELST5 N L)                               128      1715      6860    109.45
(CH:PRELST N L)                                128      1732      6928    108.38
(LM:PRELST3 N L)                               128      1746      6984    107.51
(MR:PRELST2 N L)                               128      1903      7612     98.64
(LM:PRELST2 N L)                                64      1015      8120     92.47
(LM:PRELST4 N L)                                64      1482     11856     63.33
(MR:PRELST3 N L)                                 2      2933    750848      1.00
--------------------------------------------------------------------------------
4th (LB point)

Code: [Select]

Benchmarking .......... done for 512 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(PH:PREF N L)                                  512      1436      1436    372.59
(MR:PRELST1 N L)                               128      1216      4864    110.00
(CAB:PRELST N L)                               128      1467      5868     91.18
(CH:PRELST N L)                                128      1826      7304     73.25
(LM:PRELST3 N L)                               128      1857      7428     72.03
(LM:PRELST5 N L)                               128      1857      7428     72.03
(MR:PRELST2 N L)                               128      1996      7984     67.01
(LM:PRELST2 N L)                                64      1140      9120     58.67
(LM:PRELST4 N L)                                64      1637     13096     40.86
(MR:PRELST3 N L)                                 1      1045    535040      1.00
--------------------------------------------------------------------------------
5th (RT pint)

Code: [Select]

Benchmarking .......... done for 256
iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(CAB:PRELST N L)                               256      1562      1562     81.17
(PH:PREF N L)                                  256      1652      1652     76.75
(MR:PRELST1 N L)                               256      1902      1902     66.66
(LM:PRELST5 N L)                               256      1903      1903     66.62
(CH:PRELST N L)                                256      1966      1966     64.49
(LM:PRELST3 N L)                               256      1981      1981     64.00
(MR:PRELST2 N L)                               128      1044      2088     60.72
(LM:PRELST2 N L)                               128      1326      2652     47.81
(LM:PRELST4 N L)                               128      1450      2900     43.72
(MR:PRELST3 N L)                                 4      1981    126784      1.00
--------------------------------------------------------------------------------


[chlh_jd]

It seems PH:PREF is the winner .
But  in the same points case , PH:PREF's result is not M.Ribar wanted ;and in the no element case, it return nil .

It alos show us 'foreach function can be multi-threaded computing  after compiled  ?
(My computer and system : Core i7 920 @ 2.67GHz , 16.0 G Mem , Win7 64 bit , ACAD 2011 .)