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.

[Caml-list] Efficiency of 'a list
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2003-05-02 (19:27) From: Eray Ozkural Subject: [Caml-list] Efficiency of 'a list
```Hi there,

In my maniacal pursuit of efficiency I figured that I don't truly understand
the performance of ocaml lists.

implementation or summarize its performance characteristics? This might seem
like a trivial question but having used many functional languages I know that
it's easy to commit performance genocide using linked lists.

For instance, a naive implementation of an optimal comparison sorting
algorithm in LISP almost invariably results in an O(n^2logn) routine :)

Therefore, it would be a good start to explain whether ocaml lists are in fact
LISP lists and if not in what aspects they differ.

The motivation for this question comes from trying to understand the use of
linked lists in an efficient algorithm, such as graph algorithms (say we are
implementing topological sort)

Assume I'm using the following structure that is far from handsome:
type x = (int list) array

Let a's type be x. Consider codes as the following
a.(i) <- a.(i) @ [x;y;z]
a.(i) <- [x] :: a.(i)

What travesty results in execution of such codes with i coming from an
arbitrary sequence? Do using such constructs result in unholy incarnations of
space leaks or gross inefficiencies?

Another question, does ocaml make any effort to place members of a list close
to each other? Or, more naturally, the list element is allocated using a
global model and then simply linked inside the structure?

These questions may sound weird but I'm hoping it will make sense to somebody!

Regards,

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

```