From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: * X-Spam-Status: No, score=1.4 required=5.0 tests=AWL,HTML_MESSAGE,SPF_NEUTRAL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id A3A81BC0B for ; Tue, 16 Jan 2007 12:26:01 +0100 (CET) Received: from py-out-1112.google.com (py-out-1112.google.com [64.233.166.181]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l0GBQ04j003390 for ; Tue, 16 Jan 2007 12:26:01 +0100 Received: by py-out-1112.google.com with SMTP id b50so1075895pyh for ; Tue, 16 Jan 2007 03:26:00 -0800 (PST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:references; b=ABpeYfkVHGD+uVMCchlXATHlPNX79qyyY/VQH2VTR6JoHeOqHnl9FilYfMUNkolElVCgKX262PRj5kLMQb/+TzCvTE6J2pzozFmHpxok0Wl0G62DRhY71GPm8/pXcDNqbIO7Ci2w0Dzr0zeIzkXpk3OgT4jTc82jA/KOhD10zKM= Received: by 10.35.128.17 with SMTP id f17mr66808pyn.1168946759754; Tue, 16 Jan 2007 03:25:59 -0800 (PST) Received: by 10.35.111.7 with HTTP; Tue, 16 Jan 2007 03:25:59 -0800 (PST) Message-ID: <6aeedf580701160325tdcf56cbvb2b1cef00998148c@mail.gmail.com> Date: Tue, 16 Jan 2007 11:25:59 +0000 From: "=?ISO-8859-1?Q?D=E1rio_Abdulrehman?=" To: "Bruno De Fraine" Subject: Re: [Caml-list] kth smallest element Cc: "Jon Harrop" , caml-list@inria.fr In-Reply-To: <64962DD2-F738-4812-B6BA-29ED5CF1AD75@vub.ac.be> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_102694_21866380.1168946759695" References: <200701151956.02144.jon@ffconsultancy.com> <64962DD2-F738-4812-B6BA-29ED5CF1AD75@vub.ac.be> X-j-chkmail-Score: MSGID : 45ACB648.000 on discorde : j-chkmail score : XX : 0/20 2 0.000 -> 2 X-Miltered: at discorde with ID 45ACB648.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; trivial:01 wikipedia:01 wiki:01 initialized:01 universiteit:01 beginner's:01 ocaml:01 bug:01 trivial:01 wikipedia:01 wiki:01 initialized:01 universiteit:01 beginner's:01 ocaml:01 ------=_Part_102694_21866380.1168946759695 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline 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 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 > > > > ------=_Part_102694_21866380.1168946759695 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline
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




------=_Part_102694_21866380.1168946759695--