Re: Efficiency of repeatedly appending to a List
- To: mathgroup at smc.vnet.net
- Subject: [mg71235] Re: Efficiency of repeatedly appending to a List
- From: Jon Harrop <jon at ffconsultancy.com>
- Date: Sat, 11 Nov 2006 03:38:37 -0500 (EST)
- References: <eisg8h$n5a$1@smc.vnet.net> <eius22$gkv$1@smc.vnet.net>
Jon Harrop wrote:
> Andrew Moylan wrote:
>> This caused me to wonder about the efficiency of appending items to
>> Lists in Mathematica in general. Is it an O(N) operation (i.e.,
>> something akin to a realloc in C)? Or does Mathematica employ some sort
>> of anticipatory memory allocation scheme to make adding new elements to
>> lists usually faster than O(N)?
>
> I think I tested this a while ago and found it to be amortised
> constant-time complexity.
I just tested it again:
l = {};
ListPlot[Table[
First@Timing[Do[AppendTo[l, Random[]], {i, 100}]], {j, 100}] /.
Second -> 1]
and I was most certainly wrong, Append is O(n) as Daniel said.
--
Dr Jon D Harrop, Flying Frog Consultancy
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists