Version française
Home     About     Download     Resources     Contact us    
Browse thread
Re: Data structures in ocaml
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Lyn A Headley <laheadle@c...>
Subject: Re: Data structures in ocaml
>>>>> "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