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