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

0 Members and 1 Guest are viewing this topic.

#### highflyingbird

• Bull Frog
• Posts: 415
• Later equals never.
##### =={challenge}==Find k th smallest element
« on: June 28, 2012, 01:00:46 AM »
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.

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.       (setq First (car lst))                                    ;The first one as pivot.
17.       (setq Copy lst)                                           ;Copy the list
18.       (while (setq Copy (cdr Copy))                             ;CDR the copy list
19.         (if (> First (car Copy))                                ;Get the first one in copy list and Compare to the pivot
20.           (setq Less (cons (car Copy) Less))                    ;If less,add it into the less part
21.           (setq Greater (cons (car Copy) Greater))              ;If greater, add it into the greater part
22.         )
23.       )
24.       (setq Index (+ (length Less) low))                        ;The position of the first element
25.       (cond
26.         ( (= Index n) First)                                    ;End the recursion.
27.         ( (< Index n) (H:kth Greater (1+ Index) high n))        ;Recurse the greater part
28.         (t (H:kth Less low (1- Index) n))                       ;Recurse the Less part
29.       )
30.     )
31.     (car lst)                                                   ;Just one element or nil
32.   )
33. )
34.
test ,find  6 th element.
Code: [Select]
(H:kth '(2 1 3 2 7 12 5 3 9) 0 8 6)
==> 7
« Last Edit: June 28, 2012, 01:15:33 PM by HighflyingBird »
I am a bilingualist,Chinese and Chinglish.

#### Kerry

• Mesozoic relic
• Seagull
• Posts: 11654
• class keyThumper<T>:ILazy<T>
##### Re: =={challenge}==Find k th smallest element
« Reply #1 on: June 28, 2012, 03:24:52 AM »
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

and naming the method MeanCalculator or MedianCalculator may help too
« Last Edit: June 28, 2012, 03:28:38 AM by Kerry »
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

#### highflyingbird

• Bull Frog
• Posts: 415
• Later equals never.
##### Re: =={challenge}==Find k th smallest element
« Reply #2 on: June 28, 2012, 03:50:05 AM »
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

and naming the method MeanCalculator or MedianCalculator may help too
Thank you very much. Very good advice.

Regards
highflyingbird
I am a bilingualist,Chinese and Chinglish.

#### Lee Mac

• Seagull
• Posts: 12892
• London, England
##### Re: =={challenge}==Find k th smallest element
« Reply #3 on: June 28, 2012, 07:21:56 AM »
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

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

#### ribarm

• Gator
• Posts: 3180
• Marko Ribar, architect
##### Re: =={challenge}==Find k th smallest element
« Reply #5 on: July 09, 2012, 01:01:46 PM »
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.
Marko Ribar, d.i.a. (graduated engineer of architecture)

#### irneb

• Water Moccasin
• Posts: 1794
• ACad R9-2016, Revit Arch 6-2016
##### Re: =={challenge}==Find k th smallest element
« Reply #6 on: July 09, 2012, 04:12:41 PM »
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)
T
Thus 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.
« Last Edit: July 09, 2012, 04:35:49 PM by irneb »
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

#### irneb

• Water Moccasin
• Posts: 1794
• ACad R9-2016, Revit Arch 6-2016
##### Re: =={challenge}==Find k th smallest element
« Reply #7 on: July 09, 2012, 04:24:04 PM »
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  :-[
« Last Edit: July 09, 2012, 04:38:23 PM by irneb »
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

#### highflyingbird

• Bull Frog
• Posts: 415
• Later equals never.
##### Re: =={challenge}==Find k th smallest element
« Reply #8 on: July 09, 2012, 06:58:51 PM »
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
« Last Edit: July 09, 2012, 07:05:30 PM by HighflyingBird »
I am a bilingualist,Chinese and Chinglish.

#### ribarm

• Gator
• Posts: 3180
• Marko Ribar, architect
##### Re: =={challenge}==Find k th smallest element
« Reply #9 on: July 10, 2012, 02:21:46 AM »
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.
Marko Ribar, d.i.a. (graduated engineer of architecture)

#### irneb

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

#### irneb

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

#### irneb

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

#### ribarm

• Gator
• Posts: 3180
• Marko Ribar, architect
##### Re: =={challenge}==Find k th smallest element
« Reply #13 on: July 10, 2012, 03:58:58 AM »
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.
Marko Ribar, d.i.a. (graduated engineer of architecture)

#### ribarm

• Gator
• Posts: 3180
• Marko Ribar, architect
##### Re: =={challenge}==Find k th smallest element
« Reply #14 on: July 10, 2012, 04:45:20 AM »
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.
Marko Ribar, d.i.a. (graduated engineer of architecture)