kth smallest element

kth smallest element

[Jon Harrop]

Anyone got code for the kth smallest element in a list that I can borrow?

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] kth smallest element

[Bruno De Fraine]

[-- Attachment #1: Type: text/plain, Size: 469 bytes --]

On 15 Jan 2007, at 20:56, Jon Harrop wrote:
> Anyone got code for the kth smallest element in a list that I can  
> borrow?

I have code for a set that can be limited to a certain size. While  
you add a potentially very large number of elements, the set will  
retain the 30 largest elements it has seen up to that point (given  
that the set was initialized with bound 30). You could modify the  
code to keep track of the smallest elements instead.

Regards,
Bruno


[-- Attachment #2: extSet.ml --]
[-- Type: application/octet-stream, Size: 1157 bytes --]

module type KeyedType =
sig
	type t
	type key
	val get_key : t -> key
end ;;

module type S =
sig
	type elt
	type t
	val empty : int option -> t
	val add : elt -> t -> t
	val cardinal : t -> int
	val iter : (elt -> unit) -> t -> unit
	val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
end ;;

let at_bound b c = match b with
	| Some m -> c >= m
	| None -> false
;;

module Make(Kyd: KeyedType) =
struct
	type elt = Kyd.t ;;
	
	module Ord =
	struct
		type t = Kyd.t ;;
		let compare a b =
			let k1 = Kyd.get_key a and k2 = Kyd.get_key b in
			let res = Pervasives.compare k1 k2 in
			if res <> 0 then res
			else Pervasives.compare a b
		;;
	end ;;
	
	module OrdSet = Set.Make(Ord) ;;
	
	(* implementation through bound, count and set *)
	type t = (int option * int * OrdSet.t) ;;
	
	let empty b = (b,0,OrdSet.empty) ;;

	let add x (b,c,s) =
		if c <> 0 && at_bound b c then
			let cand = OrdSet.min_elt s in
			if (Ord.compare x cand) < 0 then (b,c,s)
			else (b,c,OrdSet.add x (OrdSet.remove cand s))
		else (b,c+1,OrdSet.add x s)
	;;
	
	let cardinal (_,c,_) = c ;;
	
	let iter f (_,_,s) = OrdSet.iter f s ;;
	
	let fold f (_,_,s) a = OrdSet.fold f s a ;;
end

[-- Attachment #3: extSet.mli --]
[-- Type: application/octet-stream, Size: 422 bytes --]

(* A set, ordered according to some key, and optionally bounded to a certain size *)

module type KeyedType =
sig
	type t
	type key
	val get_key : t -> key
end

module type S =
sig
	type elt
	type t
	val empty : int option -> t
	val add : elt -> t -> t
	val cardinal : t -> int
	val iter : (elt -> unit) -> t -> unit
	val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
end

module Make(Kyd: KeyedType): S with type elt = Kyd.t

[-- Attachment #4: Type: text/plain, Size: 215 bytes --]



-- 
Bruno De Fraine
Vrije Universiteit Brussel
Faculty of Applied Sciences, INFO - SSEL
Room 4K208, Pleinlaan 2, B-1050 Brussels
tel: +32 (0)2 629 29 75
fax: +32 (0)2 629 28 70
e-mail: Bruno.De.Fraine@vub.ac.be

Re: [Caml-list] kth smallest element

[Dário Abdulrehman]

[-- Attachment #1: Type: text/plain, Size: 1363 bytes --]

This is not a trivial problem as can be seen here:

http://en.wikipedia.org/wiki/Selection_algorithm
http://www.derekroconnor.net/home/MMS406/Sorting.pdf

Bruno, I think the modified quicksort explained in the PDF is more efficient
than using a min-heap.



On 1/16/07, Bruno De Fraine <Bruno.De.Fraine@vub.ac.be> wrote:
>
> On 15 Jan 2007, at 20:56, Jon Harrop wrote:
> > Anyone got code for the kth smallest element in a list that I can
> > borrow?
>
> I have code for a set that can be limited to a certain size. While
> you add a potentially very large number of elements, the set will
> retain the 30 largest elements it has seen up to that point (given
> that the set was initialized with bound 30). You could modify the
> code to keep track of the smallest elements instead.
>
> Regards,
> Bruno
>
>
>
>
>
> --
> Bruno De Fraine
> Vrije Universiteit Brussel
> Faculty of Applied Sciences, INFO - SSEL
> Room 4K208, Pleinlaan 2, B-1050 Brussels
> tel: +32 (0)2 629 29 75
> fax: +32 (0)2 629 28 70
> e-mail: Bruno.De.Fraine@vub.ac.be
>
>
>
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
>
>
>

[-- Attachment #2: Type: text/html, Size: 2127 bytes --]