To: Pierre Weis <Pierre.Weis@inria.fr>
Subject: Re: Data structures in ocaml
In-Reply-To: Your message of "Sun, 10 Oct 1999 23:16:02 +0200."
<199910102116.XAA13841@pauillac.inria.fr>
Date: Mon, 11 Oct 1999 00:37:32 -0500
From: Lyn A Headley <laheadle@cs.uchicago.edu>
Message-Id: <19991011053733.76BC3120@yeenoghu.cs.uchicago.edu>
>>>>> "Pierre" == Pierre Weis <Pierre.Weis@inria.fr> writes:
Pierre> For O'Caml we have: hd : O(1), tl : O(1), cons : O(1), nth
Pierre> l n : O(n) append l1 l2 : O(len (l1)) append_lists [l1;
Pierre> l2; ... ln] : O(len (l1) + len (l2) + ... + len (ln-1))
Pierre> What are the figures for Python lists ? Are there other
Pierre> significant function for the list package ?
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):
hd: O(1)
tl: O(n - 1)
cons(a, b): O(len(b) + 1)
nth(l, n): O(1)
append(l1 l2): O(len(l1) + len(l2))
append_lists([l1, l2, ... ln]) not sure if this exists. The naive
implementation using "+" would be quadratic.
-Lyn
This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:26 MET