MathGroup Archive 2008

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

Search the Archive

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

carlos at Colorado.EDU wrote:
>>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
>>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 Bailey
> 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.

The point, I guess, being that one should use an O(n) method in 
preference to an O(n^2) method. That, or learn relaxation techniques 
(and I don't mean for solving systems of equations).

As for poly = {poly, p[i]} iteration being O(n^2) instead of the 
expected O(n), some explanation is here:

I will also add that Sow/Reap does not suffer from this potential speed 

Daniel Lichtblau
Wolfram Research

  • Prev by Date: Re: SparseArray memory usage
  • Next by Date: problem accessing notebooks
  • Previous by thread: Re: List concatenation - two more methods, one truly fast
  • Next by thread: Parallel Computing Toolkit with ssh tunnels