English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
AW: [Caml-list] generic Hashtbl.to_array
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2006-07-25 (10:46)
From: skaller <skaller@u...>
Subject: Re: AW: [Caml-list] generic Hashtbl.to_array
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 

	let get1 h = 
		Hashtbl.iter (fun k v -> raise XSome (k,v)) h;
		raise XNone

(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? *)

(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 <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net