From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 580FDBC88 for ; Sat, 29 Jan 2005 20:34:30 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j0TJYT2O000867 for ; Sat, 29 Jan 2005 20:34:29 +0100 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 UAA22168 for ; Sat, 29 Jan 2005 20:34:29 +0100 (MET) Received: from rproxy.gmail.com (rproxy.gmail.com [64.233.170.207]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j0TJYSqP000862 for ; Sat, 29 Jan 2005 20:34:29 +0100 Received: by rproxy.gmail.com with SMTP id i8so86640rne for ; Sat, 29 Jan 2005 11:34:28 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:reply-to:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:references; b=mcBn9h4oWH49TsafA4spBzw96OGxc966kRKTZ3m6C+cnpcpI0P8SUJGoT2aMGlkzWkF/bcYbPT4Fdxpc1uog3XHwwTtXNV+4bGS3jWoK3kL+4XS5WgL9Ai25Dzqw4KO9K5t2jzl+kIZolD+VTlpHrTlvhGPwUzCxMypkd4sfB3o= Received: by 10.38.11.55 with SMTP id 55mr17376rnk; Sat, 29 Jan 2005 11:34:28 -0800 (PST) Received: by 10.38.65.58 with HTTP; Sat, 29 Jan 2005 11:34:28 -0800 (PST) Message-ID: <7f8e92aa05012911345344cbc6@mail.gmail.com> Date: Sat, 29 Jan 2005 21:34:28 +0200 From: Radu Grigore Reply-To: Radu Grigore To: =?ISO-8859-1?Q?Fr=E9d=E9ric_Gava?= Subject: Re: [Caml-list] Missing a function Cc: sejourne_kevin , caml-list@inria.fr In-Reply-To: <003601c4da0b$774ac220$0100a8c0@mshome.net> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable References: <9E571848-430E-11D9-AF66-000A95CDFBE4@cs.unc.edu> <281F644B-43EF-11D9-BA22-000D9345235C@inria.fr> <6FBBD2B0-44FC-11D9-AF66-000A95CDFBE4@cs.unc.edu> <1102062166.666.25.camel@localhost> <001501c4d9f1$1b1c4600$0100a8c0@mshome.net> <41B1BAD4.2000004@yahoo.fr> <003601c4da0b$774ac220$0100a8c0@mshome.net> X-Miltered: at nez-perce with ID 41FBE545.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 41FBE544.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 gava:01 gava:01 wrote:01 ocaml:01 pointers:01 pointer:01 pointer:01 ...:98 ...:98 slower:01 functions:01 data:02 tree:02 guess:02 X-Spam-Checker-Version: SpamAssassin 3.0.0 (2004-09-13) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=RCVD_BY_IP autolearn=disabled version=3.0.0 X-Spam-Level: On Sat, 4 Dec 2004 15:13:44 +0100, Fr=E9d=E9ric Gava wrote: > > let cardinal e =3D fold (fun _ _ x -> succ x) e 0;; > [...] Map are also implemented as balanced > tree (like sets) and therefore, it is easy to add a function of "cardinal= ". I agree it's strange not to have "cardinal" in Map.Make. The implementations of Set and Map are likely to be very similar anyway. I do not have the ocaml sources handy right now but... Set and Map are probably RB-trees. In this case there are at least 2 pointers for links (left and right children), one pointer for key and, for maps, one pointer for data. So a set of N elements occupies at least 12xN bytes, while a map occupies at least 16xN bytes. If an element counter is added then the sizes would increase to 16xN and 20xN. That doesn't seem too bad. The advantages would be: a. O(1) cardinal function. Right now for Map the user can implement a O(n) one and for Set the complexity isn't specified. It is probably O(lg n). b. O(lg n) indexed access. Such a change implies minimal modification of existing functions: Set.cardinal becomes faster (if my guess -- lg n -- was correct) and add/remove will be _slightly_ slower. The advantage would be Map.cardinal and indexed access. --=20 regards, radu http://rgrig.idilis.ro/