From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id BAA22240; Sun, 4 May 2003 01:18:35 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id BAA22502 for ; Sun, 4 May 2003 01:18:34 +0200 (MET DST) Received: from eposta.kablonet.com.tr ([62.248.102.66]) by nez-perce.inria.fr (8.11.1/8.11.1) with SMTP id h43NIWT27339 for ; Sun, 4 May 2003 01:18:32 +0200 (MET DST) Received: (qmail 12629 invoked by uid 0); 3 May 2003 23:26:01 -0000 Received: from unknown (HELO 195.174.169.185) (exa@kablonet.com.tr@195.174.169.185) by 0 with SMTP; 3 May 2003 23:26:01 -0000 From: Eray Ozkural Reply-To: erayo@cs.bilkent.edu.tr Organization: Bilkent University CS Dept. To: "Mattias Waldau" , "'Vitaly Lugovsky'" Subject: Re: [Caml-list] Efficiency of 'a list Date: Sun, 4 May 2003 02:17:21 +0300 User-Agent: KMail/1.5.9 Cc: "'Ocaml Mailing List'" References: <03ea01c311a3$ee573560$0200a8c0@gateway> In-Reply-To: <03ea01c311a3$ee573560$0200a8c0@gateway> MIME-Version: 1.0 Content-Disposition: inline Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Message-Id: <200305040217.21977.exa@kablonet.com.tr> X-Spam: no; 0.00; eray:01 ozkural:01 caml-list:01 mattias:01 waldau:01 quicksort:01 elt:01 randomized:01 erayo:01 bilkent:01 ankara:01 kde:01 malfunction:01 ariza:01 linked:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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) 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