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