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=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id 99EF9BC6B for ; Thu, 29 Nov 2007 09:48:24 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAMoLTkeBrw8Edmdsb2JhbACPRQEK X-IronPort-AV: E=Sophos;i="4.23,228,1194217200"; d="scan'208";a="6299973" Received: from ext.lri.fr ([129.175.15.4]) by mail3-smtp-sop.national.inria.fr with ESMTP; 29 Nov 2007 09:48:24 +0100 Received: from localhost (localhost [127.0.0.1]) by ext.lri.fr (Postfix) with ESMTP id 36B73A489E; Thu, 29 Nov 2007 09:48:24 +0100 (CET) X-Virus-Scanned: Debian amavisd-new at lri.fr Received: from ext.lri.fr ([127.0.0.1]) by localhost (ext.lri.fr [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id y+zrNM5K1w6r; Thu, 29 Nov 2007 09:48:24 +0100 (CET) Received: from [129.175.4.117] (lri4-117 [129.175.4.117]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ext.lri.fr (Postfix) with ESMTP id 1B5C8A4634; Thu, 29 Nov 2007 09:48:24 +0100 (CET) Message-ID: <474E7F2B.6090007@lri.fr> Date: Thu, 29 Nov 2007 09:58:19 +0100 From: =?ISO-8859-1?Q?Jean-Christophe_Filli=E2tre?= User-Agent: Thunderbird 1.5.0.14pre (X11/20071023) MIME-Version: 1.0 To: Jon Harrop Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Help with simple ocaml memoization problem References: <005301c83260$15d1a850$017ca8c0@countertenor> <200711290811.29007.jon@ffconsultancy.com> In-Reply-To: <200711290811.29007.jon@ffconsultancy.com> X-Enigmail-Version: 0.94.2.0 OpenPGP: url=http://www.lri.fr/~filliatr/mykey.asc Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Spam: no; 0.00; filliatre:01 filliatre:01 lri:01 ocaml:01 memoization:01 ocaml:01 stdlib:01 hash:01 hash:01 red-black:01 stdlib:01 integers:01 lri:01 filliatr:01 sml:01 Jon Harrop wrote: > The Map implementation in the OCaml stdlib is also quite inefficient. I did a > little benchmark once and discovered that Maps actually waste more space than > Hashtbls. I find it unfair to compare an imperative and a persistence data structure for performances. Of course you are going to use some extra space if you need to keep old versions of the data stuctures valid. But you are sharing *a lot* among the various versions. So if you are manipulating several sets/maps with common ancestors at the same time, you are saving memory w.r.t. other data structures such as hash tables. Of course, if you are using a single data structure, in a linear way, then yes a hash table is probably more efficient (provided you have a good hash function, which is not always easy to achieve). Regarding implementation of ocaml maps, I wouldn't say that it is inefficient: I did my own benchmarls (on sets, but this is the same code) and found that ocaml AVLs are really efficient, on the contrary. It usually beats other implementations (e.g. red-black trees from the SML stdlib), or even specialized structures such as Patricia trees (when keys are integers) on some operations. -- Jean-Christophe Filliātre http://www.lri.fr/~filliatr/