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 JAA30430; Sun, 4 May 2003 09:43:22 +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 JAA30432 for ; Sun, 4 May 2003 09:43:21 +0200 (MET DST) Received: from mail.exomi.com (mail.exomi.com [217.169.64.72]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h447hKT09497 for ; Sun, 4 May 2003 09:43:21 +0200 (MET DST) Received: from exomi.com (unknown [10.0.5.5]) by mail.exomi.com (Postfix) with ESMTP id B47CD5EB6; Sun, 4 May 2003 10:43:18 +0300 (EEST) Date: Sun, 4 May 2003 10:43:17 +0300 Subject: Re: [Caml-list] Two types of efficiency (Was Efficiency of 'a list) Content-Type: text/plain; charset=US-ASCII; format=flowed Mime-Version: 1.0 (Apple Message framework v552) Cc: , "'caml Mailing List''" To: "Mattias Waldau" From: Ville-Pertti Keinonen In-Reply-To: <041d01c31208$f02327e0$0200a8c0@gateway> Message-Id: <11CA0EB8-7E04-11D7-A11A-000393863F70@exomi.com> Content-Transfer-Encoding: 7bit X-Mailer: Apple Mail (2.552) X-Spam: no; 0.00; caml-list:01 mattias:01 waldau:01 scalable:01 beginners:01 hashtbl:01 functors:01 arrays:01 ocaml:01 trading:98 trivial:01 typechecker:02 wrote:03 benchmarks:03 library:03 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Sunday, May 4, 2003, at 09:46 Europe/Helsinki, Mattias Waldau wrote: > We are talking about two kinds of efficiency: > 1. Absolute speed for mostly small benchmarks > 2. Scalable programs, i.e. they work fine for input of length 100, > but goes on forever for input of length 1000. No. What you suggested (replace lists with sets, replace arrays with maps) would in many places be trading O(1) behavior for O(log n) behavior, which certainly doesn't make programs more scalable. > It would be nice if the typechecker could deduce the type of the set > and > add the above declaration automatically to the program. That would make > it easier for beginners to use the advanced datastructures of Ocaml. Implementing 'a set and ('a, 'b) map types in OCaml is trivial; in the OCaml library, for some reason ('a, 'b) Hashtbl.t is available but Set and Map are only provided through functors. ------------------- 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