Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2012

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

Search the Archive

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



  • Prev by Date: Re: Mantaining the same form
  • Next by Date: Re: How to plot divergence of gradient as contour plot
  • Previous by thread: Re: Memory usage of a Sierpinski triangle algorithm
  • Next by thread: Re: Memory usage of a Sierpinski triangle algorithm