From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id TAA15147 for caml-red; Tue, 19 Sep 2000 19:44:11 +0200 (MET DST) 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 JAA07247 for ; Tue, 19 Sep 2000 09:41:35 +0200 (MET DST) Received: from ext.lri.fr (ext.lri.fr [129.175.15.4]) by nez-perce.inria.fr (8.10.0/8.10.0) with ESMTP id e8J7fZT07610 for ; Tue, 19 Sep 2000 09:41:35 +0200 (MET DST) Received: from pc803.lri.fr (IDENT:root@pc803 [129.175.8.114]) by ext.lri.fr (8.9.3/jtpda-5.3.2) with ESMTP id JAA10514 ; Tue, 19 Sep 2000 09:41:34 +0200 (MET DST) Received: by pc803.lri.fr (8.9.3/feuille) id JAA32041 ; Tue, 19 Sep 2000 09:41:34 +0200 X-Authentication-Warning: localhost.localdomain: filliatr set sender to filliatr@pc803 using -f From: Jean-Christophe Filliatre MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <14791.6318.709323.906054@pc803> Date: Tue, 19 Sep 2000 09:41:34 +0200 (MEST) To: David.Mentre@irisa.fr (David=?iso-8859-1?q?_Mentr=E9?=) Cc: caml-list@inria.fr Subject: Re: Data structure efficiency questions In-Reply-To: References: X-Mailer: VM 6.49 under Emacs 20.4.1 Reply-To: Jean-Christophe.Filliatre@lri.fr (Jean-Christophe Filliatre) Sender: weis@pauillac.inria.fr In his message of September 18, 2000, David=?iso-8859-1?Q?_Mentr=E9?= writes: > > 1. Is the @ operator costly or is it implemented as a simple pointers > manipulation? @ cannot be implemented as a simple pointer manipulation, because lists are persistent data structures. It means that l1 and l2 must remain the same lists after the evaluation of l1 @ l2. If you look at the code of @ (in stdlib/pervasives.ml) you'll see that the cons of l1 are duplicated. You cannot do otherwise to maintain the persistence of lists. So the complexity of @ is linear in time and space in the size of its first argument. But, of course, you may define your own type of mutable lists, and have a faster implementation of append in that case. > 2. Somebody on this list told about a set-like data structure that was > very efficient to give an answer when an element is NOT in the > set. What is the name of this structure? Patricia tree? (I wasn't > able to figure it out looking at the ml archives) I distribute an implementation of sets and maps using Patricia trees (when elements and keys are integers). They are not particularly fast at determining that an element is NOT in the set (resp. the map). But it is true that membership test is roughly twice faster than the corresponding test with the ocaml standard library's AVL. If you are interested, the code is here: http://www.lri.fr/~filliatr/software.en.html Best regards, -- Jean-Christophe FILLIATRE mailto:Jean-Christophe.Filliatre@lri.fr http://www.lri.fr/~filliatr