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

[highflyingbird]

Given a set of "n" unordered numbers we want to find the "k th" smallest number. (k is an integer between 0 and n-1). Especially,find the median.
Notice: becareful when you use "vl-sort",because it will remove the duplicate elements.
about median ,see here .


here is my code:

Code - Auto/Visual Lisp: [Select]

1. ;;;============================================================
2. ;;;Highflybird                     2012.06.28.in Shenzhen,China
3. ;;;------------------------------------------------------------
4. ;;;Function: find the "k th" smallest number in a set of "n"  
5. ;;;          unordered numbers or other elements              
6. ;;;Arguments:lst  -- an unordered list                        
7. ;;;          low  -- the low position                          
8. ;;;          high -- the high position                        
9. ;;;          n    -- Index of elements will be found(0 to n-1)
10. ;;;Return:The element will be found                            
11. ;;;------------------------------------------------------------
12. ;;;Example: (H:kth '(2 1 3 2 7 12 5 3 9) 0 8 6)  ==> 7        
13. ;;;============================================================
14. (defun H:kth (lst low high n / Greater Less Index Copy First)
15.   (if (cdr lst)
16.     (progn
17.       (setq First (car lst))                                    ;The first one as pivot.
18.       (setq Copy lst)                                           ;Copy the list
19.       (while (setq Copy (cdr Copy))                             ;CDR the copy list
20.         (if (> First (car Copy))                                ;Get the first one in copy list and Compare to the pivot
21.           (setq Less (cons (car Copy) Less))                    ;If less,add it into the less part
22.           (setq Greater (cons (car Copy) Greater))              ;If greater, add it into the greater part
23.         )
24.       )
25.       (setq Index (+ (length Less) low))                        ;The position of the first element
26.       (cond
27.         ( (= Index n) First)                                    ;End the recursion.
28.         ( (< Index n) (H:kth Greater (1+ Index) high n))        ;Recurse the greater part
29.         (t (H:kth Less low (1- Index) n))                       ;Recurse the Less part
30.       )
31.     )
32.     (car lst)                                                   ;Just one element or nil
33.   )
34. )
35.  

test ,find  6 th element.

Code: [Select]

(H:kth '(2 1 3 2 7 12 5 3 9) 0 8 6) 
==> 7


[Kerry]

Just for fun, rewrite that using variable names that represent the value they hold and see how much easier it is to read
... for us now and for you next week

Regards
kdub

added:
and naming the method MeanCalculator or MedianCalculator may help too

[highflyingbird]

Just for fun, rewrite that using variable names that represent the value they hold and see how much easier it is to read
... for us now and for you next week

Regards
kdub

added:
and naming the method MeanCalculator or MedianCalculator may help too

Thank you very much. Very good advice.

Regards
highflyingbird

[Lee Mac]

Code - Auto/Visual Lisp: [Select]

1. (defun f ( l n ) (nth (nth n (vl-sort-i l '<)) l))

Code: [Select]

_$ (f '(2 1 3 2 7 12 5 3 9) 6)
7

[irneb]

I think Lee's is going to be the most efficient, but just for fun:

Code - Auto/Visual Lisp: [Select]

1. (defun kth-smallest  (lst k / m slst)
2.   (if lst
3.     (progn (setq m    (apply 'min lst)
4.                  slst (vl-remove-if-not '(lambda (a) (= a m)) lst))
5.            (cond ((<= k 0) (car slst))
6.                  ((< k (length slst)) (nth k slst))
7.                  (t (kth-smallest (vl-remove-if '(lambda (a) (= a m)) lst)
8.                                   (- k (length slst))))))))

Though it's obviously extremely inefficient  :ugly: , in comparison! Not to mention if k is too large (20000+) the recursion might error out on stack space.

Though it does allow for order of duplicates, whereas the sorting does not. Consider this:

Code: [Select]

_$ (f '(2 1 3 7. 2 7 12 5 3 9) 6)
7
_$ (f '(2 1 3 7. 2 7 12 5 3 9) 7)
7.0
_$ (kth-smallest '(2 1 3 7. 2 7 12 5 3 9) 6)
7.0
_$ (kth-smallest '(2 1 3 7. 2 7 12 5 3 9) 7)
7

[ribarm]

My opinion is that vl-sort-i function is correct - integer is smaller than real, (7<7.0) so Lee's code wins...

M.R.

[irneb]

My opinion is that vl-sort-i function is correct - integer is smaller than real, (7<7.0) so Lee's code wins...

M.R.

Not too sure I follow. AFAICT:

Code: [Select]

Command: (< 7.0 7)
nil
Command: (< 7 7.0)
nil
Command: (= 7 7.0)
TThus to me it seems that the order of equal items is the defining factor.

All I can think of to support your claim is that an integer uses less bits in RAM to store the same number.

Anyhow, the vl-sort doesn't actually do what you think. The quick-sort algorithm doesn't order equal items in any particular order. It's one of it's drawbacks. Thus if the list order was slightly different, the vl-sort idea could give a different result.

Edit: Obviously that's splitting hairs though. In this case the OP does state that the list contains only integers, so this idea is moot anyway.

[irneb]

Anyhow, here's my iterative version:

Code - Auto/Visual Lisp: [Select]

1. (defun kth-smallest-i  (lst k / n m)
2.   (while (and (not n) lst)
3.     (setq m (apply 'min lst)
4.           lst (vl-remove-if '(lambda (a) (if (= a m) (progn (if (= (setq k (1- k)) -1) (setq n a)) t))) lst)))
5.   n)

Still not in the same speed league as Lee's though.

Edit: Stupid mistake  :-[

[highflyingbird]

My opinion is that vl-sort-i function is correct - integer is smaller than real, (7<7.0) so Lee's code wins...

M.R.

Actually, Although Lee's code is very short, but my code is faster.
Especially for a large number list. because  "nth" will take some time ,it's very different from  C++ or VB.

Code: [Select]

_$ (h:kth '(7 7.0 7 7 7.0) 0 4 3)
7

Lee's
_$ (f '(7 7.0 7 7 7.0) 3)
7.0


[ribarm]

All I can think of to support your claim is that an integer uses less bits in RAM to store the same number.

Anyhow, the vl-sort doesn't actually do what you think. The quick-sort algorithm doesn't order equal items in any particular order. It's one of it's drawbacks. Thus if the list order was slightly different, the vl-sort idea could give a different result.

Irne, I think you're wrong, vl-sort-i does really sort numbers by its exact order - here is example with negative numbers (now real is smaller than integer)

Code: [Select]

(setq lst '(1 -1.0 2 3))
(f lst 0) => -1.0
(f lst 1) => 1

And I think that this more RAM for storing real number is exactly the difference between real and integer, so (-1.0<1) just like it should be (order of numbers inside list is totally irrelevant for determination of smallest number)...

M.R.

[irneb]

All I can think of to support your claim is that an integer uses less bits in RAM to store the same number.

Anyhow, the vl-sort doesn't actually do what you think. The quick-sort algorithm doesn't order equal items in any particular order. It's one of it's drawbacks. Thus if the list order was slightly different, the vl-sort idea could give a different result.

Irne, I think you're wrong, vl-sort-i does really sort numbers by its exact order - here is example with negative numbers (now real is smaller than integer)

Code: [Select]

(setq lst '(1 -1.0 2 3))
(f lst 0) => -1.0
(f lst 1) => 1

And I think that this more RAM for storing real number is exactly the difference between real and integer, so (-1.0<1) just like it should be (order of numbers inside list is totally irrelevant for determination of smallest number)...

M.R.

Of course -1.0 is smaller than +1 ... the real is negative white the integer is positive! ... that's not what I'm saying (see your own previous post - you mentioned 7 and 7.0 ... both positive!). What I was referring to is when both are the SAME sign: +1.0 is EQUAL to +1

The vl-sort-i does not order EQUAL items in any order, see here

Code: [Select]

_$ (f '(1 1.0 2) 0)
1.0
_$ (f '(1.0 1 2) 0)
1
_$ (f '(1.0 1 2 1) 0)
1
_$ (f '(1 1.0 2 1) 0)
1While usually this doesn't matter, it's when your comparison only takes note of a portion of the data items - then you get a sort-of random ordering of "equal" items among each other.

[irneb]

As for speed:

Code: [Select]

_$ (setq lst '(2 1 3 2 7 12 5 3 9) low (apply 'min lst) high (apply 'max lst) k (/ (length lst) 2))
4
_$ (QuickBench '((H:kth lst low high k) (LM:Kth lst k) (IB:kth-smallest-r lst k) (IB:kth-smallest-i lst k)))
Benchmarking .... done for 32768 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(LM:KTH LST K)                               32768      1544      1544      6.79
(H:KTH LST LOW HIGH K)                       16384      1107      2214      4.74
(IB:KTH-SMALLEST-I LST K)                     4096      1154      9232      1.14
(IB:KTH-SMALLEST-R LST K)                     4096      1311     10488      1.00
--------------------------------------------------------------------------------


Code: [Select]

_$ (setq lst '(2 1 3 2 7 12 5 3 9 4 6 2 8 10 1 7 4 8 3 6 3 4 6 3 6 87 34 3 7 4 32 2 2 6 7 8 4 3 6 7 4 348 3 24 32) low (apply 'min lst) high (apply 'max lst) k (/ (length lst) 2))
22
_$ (QuickBench '((H:kth lst low high k) (LM:Kth lst k) (IB:kth-smallest-r lst k) (IB:kth-smallest-i lst k)))
Benchmarking .... done for 8192 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(LM:KTH LST K)                                8192      1154      1154      5.67
(H:KTH LST LOW HIGH K)                        4096      1529      3058      2.14
(IB:KTH-SMALLEST-I LST K)                     2048      1327      5308      1.23
(IB:KTH-SMALLEST-R LST K)                     2048      1637      6548      1.00
--------------------------------------------------------------------------------


Code: [Select]

_$ (setq lst nil)
nil
_$ (length (repeat (RandomMinMax 0 10000 nil) (setq lst (cons (RandomMinMax 0 200 nil) lst)))))
6731
_$ (setq low (apply 'min lst) high (apply 'max lst) k (/ (length lst) 2))
3365
_$ (QuickBench '((H:kth lst low high k) (LM:Kth lst k) (IB:kth-smallest-r lst k) (IB:kth-smallest-i lst k)))
Benchmarking .... done for 64 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(H:KTH LST LOW HIGH K)                          64      1031      1031     26.61
(LM:KTH LST K)                                  32      1187      2374     11.56
(IB:KTH-SMALLEST-I LST K)                        8      2013     16104      1.70
(IB:KTH-SMALLEST-R LST K)                        4      1715     27440      1.00
--------------------------------------------------------------------------------Yes, yours' does go faster on long lists.

[irneb]

Sorry ... no I misunderstood what your low and high arguments were about! Though it's still faster:

Code: [Select]

_$ (setq lst nil)
nil
_$ (length (repeat 10000 (setq lst (cons (RandomMinMax 0 200 nil) lst))))
10000
_$ (setq low 0 high (length lst) k (/ (length lst) 2))
5000
_$ (QuickBench '((H:kth lst low high k) (LM:Kth lst k) (IB:kth-smallest-r lst k) (IB:kth-smallest-i lst k)))
Benchmarking .... done for 32 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(H:KTH LST LOW HIGH K)                          32      1296      1296     13.31
(LM:KTH LST K)                                  32      1824      1824      9.46
(IB:KTH-SMALLEST-I LST K)                        4      1404     11232      1.54
(IB:KTH-SMALLEST-R LST K)                        2      1078     17248      1.00
--------------------------------------------------------------------------------

[ribarm]

Irne, what I ment to say (my "typo" mistake) :

Code: [Select]

(setq lst '(-1 -1.0 2 3))
(f lst 0) => -1.0
(f lst 1) => -1

So -1.0<-1...
check it on your own... I thaught you'll correct me...
M.R.

[ribarm]

Yes, I see it now :

Code: [Select]

(f '(1 1.0 2) 0) => 1.0

But now I've changed Lee's code :

Code - Auto/Visual Lisp: [Select]

1. (defun f ( lst n )
2.   (nth (nth n (vl-sort-i lst '<=)) lst)
3. )
4.  

And now order of equal elements is preserved from original list - correct me if I'm wrong...

Code: [Select]

(f '(1 1.0 2) 0) => 1
(f '(1.0 1 2) 0) => 1.0
(f '(-1 -1.0 2 3) 0) => -1
(f '(-1.0 -1 2 3) 0) => -1.0

M.R.