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 7FF2FBBB7 for ; Tue, 25 Jul 2006 12:46:04 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id k6PAk3Ca008457 for ; Tue, 25 Jul 2006 12:46:03 +0200 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 MAA13256 for ; Tue, 25 Jul 2006 12:46:03 +0200 (MET DST) Received: from smtp3.adl2.internode.on.net (smtp3.adl2.internode.on.net [203.16.214.203]) by nez-perce.inria.fr (8.13.6/8.13.6) with ESMTP id k6PAk0Yv022918 for ; Tue, 25 Jul 2006 12:46:02 +0200 Received: from rosella (ppp232-211.lns3.syd7.internode.on.net [59.167.232.211]) by smtp3.adl2.internode.on.net (8.13.6/8.13.5) with ESMTP id k6PAjjrf030008; Tue, 25 Jul 2006 20:15:49 +0930 (CST) (envelope-from skaller@users.sourceforge.net) Subject: Re: AW: [Caml-list] generic Hashtbl.to_array From: skaller To: Christoph Bauer Cc: Erick Tryzelaar , caml-list In-Reply-To: <26EB47FDD566A7469FC862DAF373792F0171128D@kaiserslautern1.lmsintl.com> References: <26EB47FDD566A7469FC862DAF373792F0171128D@kaiserslautern1.lmsintl.com> Content-Type: text/plain Date: Tue, 25 Jul 2006 20:45:44 +1000 Message-Id: <1153824344.1389.45.camel@rosella.wigram> Mime-Version: 1.0 X-Mailer: Evolution 2.6.1 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 44C5F66B.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 44C5F668.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; hashtbl:01 inverting:01 hashtbl:01 iterator:01 iter:01 iter:01 initialise:01 initialise:01 2006:98 wrote:01 sourceforge:01 caml-list:01 closure:01 closure:01 data:02 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, 2006-07-25 at 12:19 +0200, Christoph Bauer wrote: > Hi, > > > > > You could also try inverting the Hashtbl fold into an > > iterator+closure and pass the closure into the Array.init > > function, but I'm not sure how complicated/efficient that would be. > > Something like: > > let to_array_2 t = > let init _ = fun () -> raise Not_found in > let a = Array.init (Hashtbl.length t) init in > ignore > (Hashtbl.fold (fun k v i -> a.(i) <- (fun () -> (k, v)); i+1) t 0); > Array.map (fun f -> f ()) a ugg .. really need a variable length array here. However the most efficient solution is: (1) Use Hashtbl.iter to capture just one value out of the Hashtble: let get1 h = Hashtbl.iter (fun k v -> raise XSome (k,v)) h; raise XNone in (2) Initialise the array with it: let a = try get1 h with | XSome x -> Array.init (Hashtbl.length h) x | XNone -> raise Not_found (* zero length array? *) in (3) Now use Hashtbl.fold or iter to initialise the array. This 'costs' a write barrier but there is no additional data structure required, and the whole thing is quite safe. This leaves open the problem of making a zero length array of the correct type.. not a problem if you're writing the code inside the Hashtbl module, but trickier if you're doing it outside. -- John Skaller Felix, successor to C++: http://felix.sf.net