From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id AC943D185 for ; Tue, 26 Jul 2005 03:20:10 +0200 (CEST) Received: from cenn.mc.mpls.visi.com (cenn.mc.mpls.visi.com [208.42.156.9]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j6Q1KAnY007258 for ; Tue, 26 Jul 2005 03:20:10 +0200 Received: from [192.168.42.2] (bhurt.dsl.visi.com [208.42.141.66]) by cenn.mc.mpls.visi.com (Postfix) with ESMTP id 988CC8107; Mon, 25 Jul 2005 20:20:09 -0500 (CDT) Date: Mon, 25 Jul 2005 20:20:40 -0500 (CDT) From: Brian Hurt X-X-Sender: bhurt@localhost.localdomain To: Jon Harrop Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] How to do this properly with OCaml? In-Reply-To: <200507260205.45941.jon@ffconsultancy.com> Message-ID: References: <200507241623.13705.Stephane.Glondu@crans.org> <1122251570.9027.362.camel@localhost.localdomain> <200507260205.45941.jon@ffconsultancy.com> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-Miltered: at concorde with ID 42E58FCA.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 ocaml:01 stl:01 arrays:01 tweaking:01 ocaml:01 run-time:01 arrays:01 hashtbl:01 hashtbl:01 resizing:01 hash:01 stack:01 2005,:98 wrote:01 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 On Tue, 26 Jul 2005, Jon Harrop wrote: > I came from a C++/STL background and was accustomed to using extensible > arrays. Having tweaking my perception of suitable data structures to be more > appropriate when coding in OCaml, I now prefer the idea of a faster run-time > and no extensible arrays. I've never actually needed them (except inside > Hashtbl). Actually, they aren't needed in hashtbl either. If you're resizing the array, you need to go through and rehash all the elements anyways, as many will need to be moved. So you might as well copy them into a new array while you're at it. And since you need to deal with hash collisions anyways, the easiest way is to make the underlying type really a 'a list array, which gives you an obvious empty element- the empty list. No- variable length arrays are needed when you're implementing other data structures on top of arrays, like stacks or queues. At which point I start asking which data structure you really need- a variable length array, or a stack or queue? Brian