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

["Mattias Waldau" <mattias.waldau@abc.se>]

Ocaml lists are as efficient or inefficient as Lisp lists.

Lists are only good for prototyping. 

If you need to use repeated appends (or @), then lists are inefficient
and there are better solutions.

If you do stuff like List.mem, your program will behave very badly if
the lists get longer than 100 elements.

The only legitimate use of lists is for collecting data using a simple
cons and then looping over it. (If you want efficiency.)

Normally, my new programs starts out with lists, however after a while
they are all replaced by more efficient data structures like arrays or
sets.

Many modern programming languages (JavaScript, Perl, PHP) have arrays
that can take arbitrary keys as an index. This makes many people use
them all the time, and it makes the programs resonable efficient, since
people do not loop all the time.

I think more conventional languages like Java and Ocaml could learn from
this and introduce more advanced data structures as primitives, for
example replace lists by sets, and let arrays take arbitrary data types
as index. This would automatically improve the O-behavior of the
programs, ie. make them more scalable.

/mattias



> -----Original Message-----
> From: owner-caml-list@pauillac.inria.fr 
> [mailto:owner-caml-list@pauillac.inria.fr] On Behalf Of Eray Ozkural
> Sent: den 2 maj 2003 21:27
> To: Ocaml Mailing List
> 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.
> 
> Could somebody please point to an explanation of ocaml linked list 
> 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

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