MathGroup Archive 2005

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

Search the Archive

Re: Re: aggregation of related elements in a list

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

On Sun, 30 Oct 2005 10:50:19 +0000 (UTC), Maxim <ab_def at>  

> 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

Here's a simple test:

In[1]:= $Version

Out[1]= "5.2 for Microsoft Windows (June 20, 2005)"

f = Module[{L = Array[True&, #]},
   Do[L[[i + 1]] = !L[[i]], {i, # - 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:

f = Compile[{{n, _Integer}},
   Module[{L = Array[0&, 2*n]},
     Do[L[[{2*i - 1, 2*i}]] = i, {i, n}]]];

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 ). A  
simple fix is to rewrite the assignment as L[[{2*i - 1, 2*i}]] = {i, i}.

Maxim Rytin
m.r at

  • Prev by Date: Re: FixedPoint
  • Next by Date: Anyone familiar with Clearspeed?
  • Previous by thread: Re: Re: aggregation of related elements in a list
  • Next by thread: help on kind of 'inverse exponential' function ?