Data structure efficiency questions

Data structure efficiency questions

[David Mentré]

Hello all camlists,

1. Is the @ operator costly or is it implemented as a simple pointers
   manipulation? 

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)


Thanks a lot,
d.
-- 
 David.Mentre@irisa.fr -- http://www.irisa.fr/prive/dmentre/
 Opinions expressed here are only mine.

Re: Data structure efficiency questions

[Jean-Christophe Filliatre]

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

Re: Data structure efficiency questions

[Stefan Monnier]

>>>>> "Jean-Christophe" == Jean-Christophe Filliatre <Jean-Christophe.Filliatre@lri.fr> writes:
> 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?

I'm not sure what you mean by "not costly" since the "pointer manipulation"
still requires to go down one of the lists.

> @  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.

You could of course have a list datatype as (pardon the SML syntax):

    datatype 'a list = Nil | Cons of 'a * 'a list | @ of 'a list * 'a list

Although this probably wouldn't be described as "pointer manipulation".


        Stefan