Re: Data structure efficiency questions

[Jean-Christophe Filliatre <Jean-Christophe.Filliatre@lri.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