From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id PAA06545; Fri, 23 Apr 2004 15:04:23 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id PAA06532 for ; Fri, 23 Apr 2004 15:04:22 +0200 (MET DST) Received: from oceanite.ens-lyon.fr (oceanite.ens-lyon.fr [140.77.1.22]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i3ND4Ljq004048 for ; Fri, 23 Apr 2004 15:04:21 +0200 Received: from localhost (oceanite.ens-lyon.fr [127.0.0.1]) by oceanite.ens-lyon.fr (Postfix) with ESMTP id A8102320356 for ; Fri, 23 Apr 2004 15:04:07 +0200 (CEST) Received: from oceanite.ens-lyon.fr ([127.0.0.1]) by localhost (oceanite [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 00388-10 for ; Fri, 23 Apr 2004 15:04:07 +0200 (CEST) Received: from ens-lyon.org (unknown [140.77.128.163]) by oceanite.ens-lyon.fr (Postfix) with ESMTP id 7A694320352 for ; Fri, 23 Apr 2004 15:04:07 +0200 (CEST) Message-ID: <40891494.5030508@ens-lyon.org> Date: Fri, 23 Apr 2004 15:05:24 +0200 From: Jean-Baptiste Rouquier Reply-To: jrouquie@ens-lyon.fr User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.5) Gecko/20031107 Debian/1.5-3 X-Accept-Language: en MIME-Version: 1.0 Cc: caml-list@inria.fr Subject: Re: [Caml-list] Should be INSIDE STANDARD-LIB: Hashtbl.keys References: <20040421011904.GA1411@first.in-berlin.de> <20040423145141.B3686@pauillac.inria.fr> In-Reply-To: <20040423145141.B3686@pauillac.inria.fr> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Scanned: by amavisd-new-20030616-p7 (Debian) at ens-lyon.fr X-Miltered: at nez-perce by Joe's j-chkmail ("http://j-chkmail.ensmp.fr")! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; ens-lyon:01 caml-list:01 hashtbl:01 quadratic:01 i'm:07 keys:08 function:09 perhaps:09 inside:10 remove:89 sort:11 U6:88 wrong:12 run:12 but:16 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk >With your specification (no repetitions in the list), that function >would run in quadratic time, > Perhaps I'm all wrong, but when I have to get rid of repetitions in a list, I first sort it in O(n log n), then remove the repetitions in O(n). Jean-Baptiste. ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners