Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2002
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2002

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: complexity of AppendTo

  • To: mathgroup at smc.vnet.net
  • Subject: [mg32965] Re: complexity of AppendTo
  • From: Jens-Peer Kuska <kuska at informatik.uni-leipzig.de>
  • Date: Fri, 22 Feb 2002 01:48:47 -0500 (EST)
  • Organization: Universitaet Leipzig
  • References: <a526b6$20d$1@smc.vnet.net>
  • Reply-to: kuska at informatik.uni-leipzig.de
  • Sender: owner-wri-mathgroup at wolfram.com

Hi,

Mathematica use internal arrays to represent lists.
Thats why a[[i]] is resonable fast and Append[] need
n-Operations. Linked lists would need n operations
for a[[i]] and that is much harder than to avoid Append[]
Prepend[] in loops, because nobody needs explicit loops in a
functional language.

Regard
  Jens

Gerhard Wesp wrote:
> 
> % math
> Mathematica 4.1 for Linux
> Copyright 1988-2000 Wolfram Research, Inc.
>  -- Motif graphics initialized --
> 
> In[1]:= Table[ l = Table[ {} , { n } ] ;
>   Timing[ AppendTo[ l , {} ] ][[1]] , { n , 10^6 , 4*10^6 , 10^6 } ]
> 
> Out[1]= {0.5 Second, 1. Second, 1.49 Second, 2. Second}
> 
> In[2]:= % / %[[1]]
> 
> Out[2]= {1., 2., 2.98, 4.}
> 
> obviously, AppendTo takes O(n) time.  why is this?  if List[] is
> implemented as a linked list, the complexity should be constant.  and
> even for vectors, it is trivial to implement amortized constant time
> append.
> 
> (for c++ programmers: compare this to std::list<> and std::vector<>, or
> std::deque<>)
> 
> regards,
> -gerhard
> --
> | voice: +43 (0)676 6253725  ***  web: http://www.cosy.sbg.ac.at/~gwesp
> |
> | Passts auf, seid's vuasichdig, und lossds eich nix gfoin!
> |  -- Dr. Kurt Ostbahn


  • Prev by Date: Re: Integrating over a Minimum
  • Next by Date: Re: mathgl3d
  • Previous by thread: Re: complexity of AppendTo
  • Next by thread: Getting Coordinates from plot