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: [mg124143] Re: Memory usage of a Sierpinski triangle algorithm
• From: DrMajorBob <btreat1 at austin.rr.com>
• Date: Wed, 11 Jan 2012 04:19:26 -0500 (EST)
• Delivered-to: l-mathgroup@mail-archive0.wolfram.com
• References: <201201101058.FAA27787@smc.vnet.net>
• Reply-to: drmajorbob at yahoo.com

a) That code uses almost zero memory and doesn't even create a plot. Did  
you leave out a CALL, perhaps? (I had to guess what size N would be  
useful.)

b) It turns out that N needs to be HUGE... because PointSize is too small.  
I suggest a larger one.

c) Do NOT use N as a variable. It's a built-in function. It's generally  
best to never start your own variables with capitals, to eliminate  
conflicts like that. You don't need to display N or P as symbols, so  
change them to n and p.

d) The plot includes the data, so using Module may do very little to  
minimize memory.

e) Evaluate isn't doing anything where you've put it, since its argument  
isn't held, anyway.

f) The first Module has no module variables, which makes Module useless  
and makes x a global variable.

You could write it

throwd3[] := Module[{x = Random[]},
   If[x < 1/3, y = 1, If[1/3 < x < 2/3, y = 2, y = 3]]; y]

or

throwd3[] =
  Module[{x = Random[]},
   Piecewise[{{1, x < 1/3}, {2, 1/3 <= x <= 2/3}}, 3]]

Either of those would make sense.

g) Do you intend to get 3 when x is 1/3 or 2/3 to machine precision? If  
not, change < to <= accordingly.

(It doesn't really matter, since 1/3 and 2/3 occur with 0 probability.)

h) startlist[[throwd3[[]]] can be replaced with RandomChoice@startlist,  
eliminating throwd3 entirely.

i) list never changes, but you subscript it with an integer, and store  
another list in the result??? The result is N different lists, from small  
to large, giving N (N + 1)/2 total stored pairs, with only N of them  
distinct... and you plot only the last subscripted list, so the others are  
useless. I assume this is why memory usage grows so much.

j) p also need a subscript either, for similar reasons.

k) Here's a working code, including a call:

Clear[sierpinski]
startlist = {{0, 0}, {1, 0}, {0.5, 1}};
sierpinski[nmax_, x0_: 0.5, y0_: 0.5] :=
  Module[{n = 1, p, list = startlist},
   p = {x0, y0};
   Do[p = 1/2 (RandomChoice@startlist + p);
    AppendTo[list, p], {n, nmax}];
   ListPlot[list, PlotStyle -> PointSize[0.005], PlotRange -> All]]
sierpinski[10000]//Timing

(0.603191 seconds)

Table instead of Do, eliminating AppendTo, is five times faster:

Clear[sierpinski]
startlist = {{0, 0}, {1, 0}, {0.5, 1}};
sierpinski[nmax_, x0_: 0.5, y0_: 0.5] := Module[{n = 1, p, list},
   list = Join[Append[startlist, p = {x0, y0}],
     Table[p = 1/2 (RandomChoice@startlist + p), {n, nmax}]];
   ListPlot[list, PlotStyle -> PointSize[0.005], PlotRange -> All]]
sierpinski[10000] // Timing

(0.1222112 seconds)

NestList is still faster:

Clear[sierpinski]
startlist = {{0, 0}, {1, 0}, {0.5, 1}};
sierpinski[nmax_, x0_: 0.5, y0_: 0.5] := Module[{n = 1, p, list},
   list = Join[startlist,
     NestList[(# + RandomChoice@startlist)/2 &, {x0, y0}, nmax]];
   ListPlot[list, PlotStyle -> PointSize[0.005], PlotRange -> All]]
sierpinski[10000] // Timing

(0.079853 seconds)

All three codes give pretty much the same plot.

Bobby

On Tue, 10 Jan 2012 04:58:57 -0600, Wojciech Morawiec  
<wmorawie at students.uni-mainz.de> wrote:

> 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.
>


-- 
DrMajorBob at yahoo.com

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