Re: Re: List concatenation - two more methods, one truly
- To: mathgroup at smc.vnet.net
- Subject: [mg87870] Re: [mg87827] Re: List concatenation - two more methods, one truly
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Sat, 19 Apr 2008 03:33:02 -0400 (EDT)
- References: <ftv8ro$7o1$1@smc.vnet.net> <fu7akb$f0t$1@smc.vnet.net> <200804180639.CAA12541@smc.vnet.net>
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
>>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.
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:
http://forums.wolfram.com/mathgroup/archive/2008/Apr/msg00555.html
I will also add that Sow/Reap does not suffer from this potential speed
liability.
Daniel Lichtblau
Wolfram Research
- References:
- Re: List concatenation - two more methods, one truly fast
- From: carlos@Colorado.EDU
- Re: List concatenation - two more methods, one truly fast