Topic: =={challenge}==Find k th smallest element

[irneb]

We're discussing something which is not really of any consequence in this thread. It was me who started it, so I should apologise and start a new thread for that.

[Lee Mac]

My revision of Highflyingbird's method:

Code - Auto/Visual Lisp: [Select]

1. (defun LM:kth2 ( l k / a b x )
2.     (if (cdr l)
3.         (progn
4.             (setq x (car l))
5.             (foreach y (cdr l)
6.                 (if (< x y)
7.                     (setq a (cons y a))
8.                     (setq b (cons y b))
9.                 )
10.             )
11.             (cond
12.                 (   (= k (setq l (length b))) x)
13.                 (   (< k l) (LM:kth2 b k))
14.                 (   (LM:kth2 a (- k l 1)))
15.             )
16.         )
17.         (car l)
18.     )
19. )

Bench:

Code - Auto/Visual Lisp: [Select]

1. _$ (length (repeat 10000 (setq lst (cons (LM:randomrange 0 200) lst))))
2. 10000
3. _$ (setq low 0 high (length lst) k (/ (length lst) 2))
4. 5000
5. _$ (benchmark
6.       '(
7.            (H:kth lst low high k)
8.            (LM:Kth lst k)
9.            (LM:Kth2 lst k)
10.            (IB:kth-smallest-r lst k)
11.            (IB:kth-smallest-i lst k)
12.        )
13.    )
14. Benchmarking .........Elapsed milliseconds / relative speed for 64 iteration(s):
15.  
16.     (LM:KTH2 LST K)................1482 / 29.21 <fastest>
17.     (H:KTH LST LOW HIGH K).........1622 / 26.69
18.     (LM:KTH LST K).................3370 / 12.85
19.     (IB:KTH-SMALLEST-I LST K).....27566 / 1.57
20.     (IB:KTH-SMALLEST-R LST K).....43290 / 1.00 <slowest>