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