From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id TAA27807 for caml-redistribution; Mon, 11 Oct 1999 19:31:02 +0200 (MET DST) Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id HAA16631 for ; Mon, 11 Oct 1999 07:37:41 +0200 (MET DST) Received: from alexandria.cs.uchicago.edu (alexandria.cs.uchicago.edu [128.135.11.87]) by nez-perce.inria.fr (8.8.7/8.8.7) with ESMTP id HAA07269; Mon, 11 Oct 1999 07:37:39 +0200 (MET DST) Received: from yeenoghu.cs.uchicago.edu (yeenoghu.cs.uchicago.edu [128.135.11.46]) by alexandria.cs.uchicago.edu (8.9.1/8.9.3) with ESMTP id AAA28440; Mon, 11 Oct 1999 00:37:34 -0500 (CDT) Received: from yeenoghu.cs.uchicago.edu (localhost [127.0.0.1]) by yeenoghu.cs.uchicago.edu (Postfix) with ESMTP id 76BC3120; Mon, 11 Oct 1999 00:37:33 -0500 (CDT) To: Pierre Weis Cc: caml-list@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 Message-Id: <19991011053733.76BC3120@yeenoghu.cs.uchicago.edu> Sender: weis >>>>> "Pierre" == Pierre Weis 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