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