Hi Mattias,

On Saturday 03 May 2003 21:43, Mattias Waldau wrote:
> I have been doing pure programming since MACLISP on the TOPS-20, and the
> a large percentage of performance problems can be traced back to
> IMAPPROPRIATE USE OF LISTS. Therefor my previous post where I
> essentially say:
>
> *** Do not use lists, there is always a better datastructure ***

I fully understand your concern. If you recall I said a similar thing:

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

That I had understood when we had been given an assignment to implement 
quicksort in our LISP course some years ago :) I had a quick look at how the 
other people did it, and realized that almost all of them had achieved this 
inappropriate complexity by using elt function.. However, you can of course 
implement quick sort (or some other comparison sorting like merge sort) using 
a linked list, the only problem would be that you can't do it in place (you 
can even implement randomized quicksort but you'd need two scans of the list 
instead of a single scan)

That's why the programmer must understand how "integral" data structures 
interact in a PL, especially in one that encompasses both imperative and 
functional semantics. Of course he must in addition to that have a good 
understanding of architectural/implementation issues, otherwise he can never 
predict the performance of his program.

Cheers,

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