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>
• 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