Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #14173

Re: Timing puzzle

From Daniel Lichtblau <danl@wolfram.com>
Newsgroups comp.soft-sys.math.mathematica
Subject Re: Timing puzzle
Date 2013-04-13 06:02 +0000
Message-ID <kkasdn$rj9$1@smc.vnet.net> (permalink)
References <kk2qvl$bip$1@smc.vnet.net> <kk88rk$c1g$1@smc.vnet.net>
Organization Time-Warner Telecom

Show all headers | View raw


On Apr 12, 1:16 am, carlos%colorado....@gtempaccount.com wrote:
> Clarification: n was 1000 in the posted test; for some reason the top line was mangled in copy/paste.
> For n=5000 the results are
>
> 5.37185 Second
> 5.27741 Second
> 5.41862 Second
> 3.18303 Second
> 0.024265 Second
>
> Conclusion: time for the top 4 goes up ~linearly, which suggests that the list is being modified by just appending one item, instead of placing a pointer to it.  For the last one it goes up sublinearly.
>
> Reason for worry: in the actual plot package n is not known until the plot is finished. My  plotter actually builds dynamically three Graphics3D sublists: faces, edges, points and labels. Optional commands such as changing point size, thickness, colors and font styles, may be inserted at any point in those sublists.  So the faster method (preallocating addresses with Table) is ruled out.

Method 4 in any recent version (8 or 9 or even 7 with a nondefault
system option setting) should be fine for this. Use of Sow and Reap,
likewise, and with every version since I gorget which, but probably 4.

As others have noted, a Mathematica list is akin to what is often
called an array in computer science. It is not a linked list under the
hood, and will not behave like one in terms of computational
complexity. Actually this forum has seen related discussion going well
back into the last millenium.

If you desperately want to emulate a linked list, one way to do so is
described at

http://stackoverflow.com/questions/6691491/implementing-a-quadtree-in-mathematica/6795762#6795762

Title notwithstanding, there is a bit about linked lists near the end.

Daniel Lichtblau
Wolfram Research

Back to comp.soft-sys.math.mathematica | Previous | Next — Previous in thread | Find similar | Unroll thread


Thread

Timing puzzle carlos%colorado.edu@gtempaccount.com - 2013-04-10 04:48 +0000
  Re: Timing puzzle awnl <awnl@gmx-topmail.de> - 2013-04-11 08:10 +0000
  Re: Timing puzzle carlos%colorado.edu@gtempaccount.com - 2013-04-12 06:16 +0000
    Re: Timing puzzle Daniel Lichtblau <danl@wolfram.com> - 2013-04-13 06:02 +0000

csiph-web