Re: Data structures in ocaml

From: Lyn A Headley (laheadle@cs.uchicago.edu)
Date: Mon Oct 11 1999 - 07:37:32 MET DST


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