A few years ago I was very proud of myself for managing to translate the original Pascal of the Reingold-Tilford algorithm into C/C++ and every since then I have had a fascination for drawing binary trees.
The one drawn here was actually done “by hand” in Metapost – I realised only as I finished it that I could have or maybe should used an algorithmic approach and not a heuristic (“does it look ok?”), though Metapost is a pretty inflexible programming tool (though as this book shows can produce some beautiful results) and I reckon a decent tree drawing algorithm in that ought to be worth at least an MSc.
Of course, real world fractals do exist, but it is interesting to appear to have “discovered” one, or at least a pattern which certainly shows many fractal-like properties.
I am plotting the relative efficiency of different page replacement algorithms – and here I am looking at Belady’s OPT (or MIN), or as it is sometimes called, the clairvoyant page replacement algorithm.
Here I am measuring the proportion of time a page stands idle (including its loading time). So a page with a ratio of 1.0 is loaded but never used, a page with a ratio of 0.999 is used one-thousandth of the time it is in the system and a page with a ratio of 0.99 is used one-hundredth of the time it’s in the system and so on.
So, here’s the “full” plot for my data:
Not much to see – except most pages are idle most of the time: so we go closer:
That’s about the limit of the precision of the data, but it looks pretty fractal like to me…
(Should add, other page replacement policies studied don’t appear to show this fractal-like pattern, exhibiting only one peak/modal frequency.)