* Re: [Caml-list] kth smallest element
2007-01-15 19:56 kth smallest element Jon Harrop
@ 2007-01-16 8:32 ` Bruno De Fraine
2007-01-16 11:25 ` Dário Abdulrehman
0 siblings, 1 reply; 3+ messages in thread
From: Bruno De Fraine @ 2007-01-16 8:32 UTC (permalink / raw)
To: Jon Harrop; +Cc: caml-list
[-- 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
^ permalink raw reply [flat|nested] 3+ messages in thread