Re: Data structures in ocaml

[Lyn A Headley <laheadle@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