Re: [Caml-list] Efficiency of 'a list

[Eray Ozkural <exa@kablonet.com.tr>]

On Sunday 04 May 2003 00:13, Lauri Alanko wrote:
> It's easy to commit performance genocide with any data structure if you
> use it for things for which it is not efficient. Singly linked immutable
> lists have some nice characteristics: O(1) for cons, head and tail, all
> purely functionally so you can safely share structure between multiple
> lists. For example, lists are perfect for representing several alternate
> paths in a path search.

OK. So as Mattias said it is the same thing as LISP lists.

>
> For the second line I think you mean either
> a.(i) <- x :: a.(i)
> or
> a.(i) <- [x] @ a.(i)
>

*blush* yes I meant the former.

> Both of these are O(1). The first allocates a single cell, the second
> theoretically two (one of which is discarded immediately) unless the
> compiler is smart.
>
> If you really need to add stuff to both ends of a data structure,
> ocaml's primitive lists aren't the thing. You might consider some sort
> of a deque.
>

Hmm. I'm just trying to understand if ocaml lists would be adequate for 
representing adjacency lists. I thought it'd be easier for programmers to 
deal with it than something else that I might write. [And since such a thing 
is likely to pervade my library I should decide early :) ]

I also wanted to learn if the compiler went to any length in optimization when 
it can determine that a mutable field is being overwritten like in a.(i) <- 
a.(i) @ [x]  --- Of course here it is obvious that there is no reference 
count associated with objects, and another structure might be sharing the 
list, etc. so there is probably no room for optimization.

BTW, we don't have imperative lists in the standard library...I wonder if 
something like a really simple doubly linked list or non-shared singly linked 
list would be worthwhile (wasn't that an exercise in ocaml book?)

> However, the copying garbage collector is quite likely to enhance
> locality of lists when it runs. Someone more knowledgeable can probably
> tell more on this.

I understand that garbage collectors are pretty smart nowadays. Maybe it might 
be attempting to compact memory in a way.

Happy hacking,

-- 
Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr>
Comp. Sci. Dept., Bilkent University, Ankara  KDE Project: http://www.kde.org
www: http://www.cs.bilkent.edu.tr/~erayo  Malfunction: http://mp3.com/ariza
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners