From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id IAA30195 for caml-redistribution; Wed, 13 Oct 1999 08:59:21 +0200 (MET DST) 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 UAA04521 for ; Tue, 12 Oct 1999 20:58:55 +0200 (MET DST) Received: from ruby (pm1-22.triode.net.au [203.63.235.38]) by nez-perce.inria.fr (8.8.7/8.8.7) with ESMTP id UAA27452; Tue, 12 Oct 1999 20:58:50 +0200 (MET DST) Received: from maxtal.com.au (IDENT:root@localhost [127.0.0.1]) by ruby (8.9.3/8.9.3) with ESMTP id EAA12245; Wed, 13 Oct 1999 04:52:38 +1000 Sender: weis Message-ID: <38038375.4D58AFC3@maxtal.com.au> Date: Wed, 13 Oct 1999 04:52:37 +1000 From: skaller Organization: Maxtal P/L X-Mailer: Mozilla 4.51 [en] (X11; I; Linux 2.2.12 i586) X-Accept-Language: en MIME-Version: 1.0 To: Lyn A Headley CC: Pierre Weis , caml-list@inria.fr Subject: Re: Data structures in ocaml References: <19991011053733.76BC3120@yeenoghu.cs.uchicago.edu> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lyn A Headley wrote: > Python "lists" are based on arrays, so I believe the performance is as > follows (some of these functions don't really exists, but would be > "faked" using slices or somesuch): > append_lists([l1, l2, ... ln]) not sure if this exists. The naive > implementation using "+" would be quadratic. That's an interesting observation: thanks for pointing it out. In fact, expressions like x = a + b + c + d are common manipulating strings in Python. Because I represent this as a list, _not_ recursively, I can get linear performance, if there is a way to preallocate the storage. [I can't remember off hand if the 'Buffer' class allows this]. I can also do it for (python) lists, using Varray. -- John Skaller, mailto:skaller@maxtal.com.au 1/10 Toxteth Rd Glebe NSW 2037 Australia homepage: http://www.maxtal.com.au/~skaller downloads: http://www.triode.net.au/~skaller