Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2005
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2005

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

Search the Archive

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


  • 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 ?