### Author Topic: =={challenge}==Find k th smallest element  (Read 5835 times)

0 Members and 1 Guest are viewing this topic.

#### irneb

• Water Moccasin
• Posts: 1794
• ACad R9-2016, Revit Arch 6-2016
##### Re: =={challenge}==Find k th smallest element
« Reply #15 on: July 10, 2012, 05:10:08 AM »
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.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

#### Lee Mac

• Seagull
• Posts: 12892
• London, England
##### Re: =={challenge}==Find k th smallest element
« Reply #16 on: July 10, 2012, 12:14:31 PM »
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.             (setq x (car l))
4.             (foreach y (cdr l)
5.                 (if (< x y)
6.                     (setq a (cons y a))
7.                     (setq b (cons y b))
8.                 )
9.             )
10.             (cond
11.                 (   (= k (setq l (length b))) x)
12.                 (   (< k l) (LM:kth2 b k))
13.                 (   (LM:kth2 a (- k l 1)))
14.             )
15.         )
16.         (car l)
17.     )
18. )

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>
« Last Edit: July 10, 2012, 12:24:04 PM by Lee Mac »