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 HAA30943; Sat, 3 May 2003 07:43:18 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id HAA31199 for ; Sat, 3 May 2003 07:43:16 +0200 (MET DST) X-SPAM-Warning: Sending machine is listed in blackholes.five-ten-sg.com Received: from maild.telia.com (maild.telia.com [194.22.190.101]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h435hFH12996 for ; Sat, 3 May 2003 07:43:15 +0200 (MET DST) Received: from d1o849.telia.com (d1o849.telia.com [213.66.248.241]) by maild.telia.com (8.12.9/8.12.9) with ESMTP id h435h8Oa024587; Sat, 3 May 2003 07:43:08 +0200 (CEST) X-Original-Recipient: caml-list@inria.fr Received: from gateway (h199n1fls34o849.telia.com [213.67.121.199]) by d1o849.telia.com (8.10.2p2/8.10.1) with ESMTP id h435h4D09617; Sat, 3 May 2003 07:43:04 +0200 (CEST) From: "Mattias Waldau" To: , "'Ocaml Mailing List'" Subject: RE: [Caml-list] Efficiency of 'a list Date: Sat, 3 May 2003 07:43:01 +0200 Message-ID: <03b801c31136$e122db50$0200a8c0@gateway> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook, Build 10.0.3416 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1165 Importance: Normal In-Reply-To: <200305022227.20136.exa@kablonet.com.tr> X-Spam: no; 0.00; mattias:01 waldau:01 caml-list:01 appends:01 behave:01 resonable:01 scalable:01 eray:01 ozkural:01 topological:01 incarnations:01 model:01 erayo:01 bilkent:01 ankara:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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) > 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