Re: Data structures in ocaml

From: skaller (skaller@maxtal.com.au)
Date: Tue Oct 12 1999 - 20:52:37 MET DST


Date: Wed, 13 Oct 1999 04:52:37 +1000
From: skaller <skaller@maxtal.com.au>
To: Lyn A Headley <laheadle@cs.uchicago.edu>
Subject: Re: Data structures in ocaml

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



This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:27 MET