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 QAA11675; Thu, 26 Sep 2002 16:57:13 +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 QAA11628 for ; Thu, 26 Sep 2002 16:57:12 +0200 (MET DST) Received: from mlabdial.hit.bme.hu (mlabdial.hit.bme.hu [152.66.248.201]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id g8QEvB523546 for ; Thu, 26 Sep 2002 16:57:11 +0200 (MET DST) Received: from localhost (kgergely@localhost) by mlabdial.hit.bme.hu (8.11.6/8.11.6) with ESMTP id g8QEi1119503; Thu, 26 Sep 2002 16:44:01 +0200 Date: Thu, 26 Sep 2002 16:44:00 +0200 (CEST) From: "Kontra, Gergely" To: Brian Hurt cc: Ocaml Mailing List Subject: Re: [Caml-list] Probably FAQ: Why is list-append (list :: elem) so expensive? In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=iso-8859-2 Content-Transfer-Encoding: 8BIT Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk >I get that the cost of list concatenation is proportional to the length of >the first list. So (elem :: list) is O(1) no matter what the length of >list is. But (list :: elem) is O(n), with n being the length of the list. [...] >An example of where this would come in usefull. Consider the merge >portion of a merge sort (yes, I know I'm duplicating code that is in the >List module- I'm doing it so that I can learn the language. Plus, here we >all understand the problem). The current implementation I have (probably >chock full of inefficiencies) is: If you want to build up a list from the beginning to the tail, just append the new elements before the list, and then reverse the list. (* Sorry, new to ocaml, my syntax may be SML-ish *) (* tail-recursive function to reverse a list *) let reverse List = (* returns a list like: (reverse L2) @ L1 *) let rec revapp L1 L2 = match L2 with | [] -> L1 | hd::tl -> revapp hd::L1 tl in revapp [] List Since reversing is not so slow, this might be, what you want. Gergõ +-[Kontra, Gergely @ Budapest University of Technology and Economics]-+ | Email: kgergely@mcl.hu, kgergely@turul.eet.bme.hu | | URL: turul.eet.bme.hu/~kgergely Mobile: (+36 20) 356 9656 | +-------"Olyan langesz vagyok, hogy poroltoval kellene jarnom!"-------+ . Magyar php mirror es magyar php dokumentacio: http://hu.php.net ------------------- 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