Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: List concatenation - two more methods, one truly fast

• To: mathgroup at smc.vnet.net
• Subject: [mg87827] Re: List concatenation - two more methods, one truly fast
• From: carlos at Colorado.EDU
• Date: Fri, 18 Apr 2008 02:39:18 -0400 (EDT)
• References: <ftv8ro$7o1$1@smc.vnet.net> <fu7akb$f0t$1@smc.vnet.net>

>
> This result is fascinating - it is reasonable that all the solutions
> based on appending lists work O(n^2), but the nested list approach
> should not behave this way. If you repeat the timing, but without
> defining p:
>
> n = 5000; poly = Table[0, {n}];
> Print[Timing[Do[poly = {poly, p[i]}, {i, 1, n}];
>      poly = Flatten[poly]][[1]]];
>
> I get 0.02 seconds rather than 11 seconds (I obviously have a slightly
> slower machine. This means that the time depends crucially on what you
> are accumulating.
>
> Consider the semantics of the operation:
>
> poly = {poly, p[i]}
>
> This will only be efficient if Mathematica 'knows' that the old value of
> poly is already fully evaluated. As I understand it, Mathematica does
> this using a hashing method, and my guess is that in this case the hash
> table overflows and the ever growing expression gets repeatedly
> evaluated - hence O(n^2).
>
> It would be nice if someone from Wolfram could comment on these timing
> results.
>
> Incidentally, the following method works efficiently without requiring
> the array size to be known in advance:
>
> n = 5000; poly = Table[0, {n}];
> Print[Timing[poly = Reap[Do[Sow[p[i]], {i, 1, n}]][[2, 1]]][[1]]];
>
> David Baileyhttp://www.dbaileyconsultancy.co.uk

Note that  O(n^2) dependence  is a killer for building long object lists.
For example suppose I increase n to 200000 polygons.  In FEM work that is a
medium size plot. Building the Show[] list by one of the O(n^2)
methods extrapolates
to about 50000 seconds (14 hours) on my desktop G5. And I know that on that
machine elapsed time is about 3 times that reported by Timing[].  Waiting 40+
hours for one plot is not  exactly interactive speed.

On the other hand a O(n) scheme would build it in less than a second.

• Follow-Ups:
  • Re: Re: List concatenation - two more methods, one truly
    • From: Daniel Lichtblau <danl@wolfram.com>