Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Memory usage of a Sierpinski triangle algorithm

• To: mathgroup at smc.vnet.net
• Subject: [mg124144] Re: Memory usage of a Sierpinski triangle algorithm
• From: Heike Gramberg <heike.gramberg at gmail.com>
• Date: Wed, 11 Jan 2012 04:19:47 -0500 (EST)
• Delivered-to: l-mathgroup@mail-archive0.wolfram.com
• References: <201201101058.FAA27787@smc.vnet.net>

Every time you set Subscript[P, n] = ..  you're not assigning a value 
to P, but you're actually adding an element to the list of down values 
of Subscript. Try for example

Clear[Subscript];
DownValues[Subscript]
Sierp[10];
DownValues[Subscript]

Since the new value of P only depends on the current value, you can do 
something like
Sierp1[N_, x0_: 0.5, y0_: 0.5] :=
 Module[{nmax = N, n, P, list},
  P = {x0, y0}; n = 1;
  list = startlist;
  Do[Evaluate[P = 1/2 (startlist[[RandomInteger[1,3]]] + P)];
   list = Append[list, P], {n, nmax}];
  ListPlot[list, PlotStyle -> PointSize[0.0001]]]

This performs a bit better than the original one. To do the same thing 
in a functional way, you could do something like

Sierp2[N_, x0_: 0.5, y0_: 0.5] := Module[{list},
  list = Join[startlist,
    NestList[1/2 (RandomChoice[startlist] + #) &, {x0, y0}, N]];
  ListPlot[list, PlotStyle -> PointSize[0.0001]]]

The timings I get for these two versions are

Sierp1[10000]; // Timing
Sierp2[10000]; // Timing

out:

{2.5849, Null}
{0.199617, Null}

so the second version is about a factor 13 faster for 20000 iterations.

Heike.


> Cheers!
>
> I began some Mathematica programming exercises recently and I wrote 
some simple algorithm to create a list of points that resembles a 
Sierpinski triangle when plotted with ListPlot. Basically you choose on 
of the three edges by random, create a point in the middle between 
{0.5,0.5} and the chosen edge and continue to create new points in the 
middle between a randomly chosen edge and the last created point:
>
> ########################### CODE ###########################
> throwd3[] := Module[{}, x = Random[];
>  If[x < 1/3, y = 1, If[1/3 < x < 2/3, y = 2, y = 3]]; y]
>
>
> startlist = {{0, 0}, {1, 0}, {0.5, 1}};
>
>
> Sierp[N_, x0_: 0.5, y0_: 0.5] :=
> Module[{nmax = N, n, P, list}, Subscript[P, 0] = {x0, y0}; n = 
1;
>   Subscript[list, 0] = startlist;
>   Do[Evaluate [
>      Subscript[P, n] =
>     1/2 (startlist[[throwd3[]]] + Subscript[P, n - 1])];
>     Subscript[list, n] =
>     Append[Subscript[list, (n - 1)], Subscript[P, n]], {n, nmax}];
>  ListPlot[Subscript[list, nmax], PlotStyle -> PointSize[0.0001]]]
> ########################### END CODE ########################
>
> The thing is that this code uses huge amounts of memory since it 
stores all the lists and points needed during the calculations, although 
these shouldn't be stored because I'm using a Module, right?
> Obviously, I'm missing something here...
>
> Thanks for any advice in advance!
>
> -W.
>

• References:
  • Memory usage of a Sierpinski triangle algorithm
    • From: Wojciech Morawiec <wmorawie@students.uni-mainz.de>