Re: Re: aggregation of related elements in a list

*To*: mathgroup at smc.vnet.net*Subject*: [mg62231] Re: Re: aggregation of related elements in a list*From*: Maxim <m.r at inbox.ru>*Date*: Wed, 16 Nov 2005 04:21:53 -0500 (EST)*References*: <djcgcs$6du$1@smc.vnet.net> <djfnjr$b1i$1@smc.vnet.net> <200510270902.FAA19490@smc.vnet.net> <djsl5n$8qd$1@smc.vnet.net> <dk28hb$e4v$1@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

On Sun, 30 Oct 2005 10:50:19 +0000 (UTC), Maxim <ab_def at prontomail.com> wrote: > > A surprising discovery is that if we take agg3 and modify LvisitF to be a > vector of False/True instead of 0/1, agg3 won't be linear time anymore. A > list of booleans cannot be a packed array, but it is still an ordinary > Mathematica list, which is basically a fixed size array of pointers, so > theoretically it ought to have constant access time. The problem is that > list elements may have upvalues associated with them, and in principle > after an element of the list has changed the whole structure must be > reevaluated, in case an upvalue associated with another element takes > effect now. Mathematica uses various optimizations to avoid the > reevaluation whenever possible, but it seems that for lists of symbols > (including True/False) there's still some overhead. > > Maxim Rytin > m.r at inbox.ru > Here's a simple test: In[1]:= $Version Out[1]= "5.2 for Microsoft Windows (June 20, 2005)" In[2]:= f = Module[{L = Array[True&, #]}, Do[L[[i + 1]] = !L[[i]], {i, # - 1}]]&; Timing[f[10^4];] Timing[f[2*10^4];] %[[1]]/%%[[1]] Out[3]= {1.828*Second, Null} Out[4]= {7.282*Second, Null} Out[5]= 3.9835886 Clearly the time grows quadratically. If each of the n steps takes O(n) time, a plausible explanation is that it is related to the reevaluation of the whole list on each step. Another similar problem appears only in compiled code: In[6]:= f = Compile[{{n, _Integer}}, Module[{L = Array[0&, 2*n]}, Do[L[[{2*i - 1, 2*i}]] = i, {i, n}]]]; Timing[f[5*10^4];] Timing[f[10^5];] %[[1]]/%%[[1]] Out[7]= {22.093*Second, Null} Out[8]= {86.891*Second, Null} Out[9]= 3.9329652 It is not clear what could be the reason for this (except that assigning values to parts of expressions in combination with Compile is just extremely shoddy, that is; see for example http://forums.wolfram.com/mathgroup/archive/2005/Apr/msg00799.html ). A simple fix is to rewrite the assignment as L[[{2*i - 1, 2*i}]] = {i, i}. Maxim Rytin m.r at inbox.ru