- Mazes For Programmers part 1, introduction
- Mazes For Programmers part 2, some basics
- Mazes For Programmers part 3, graphical UI
- Mazes For Programmers part 4, implementing the first two algorithms
- Mazes For Programmers part 5, Dijkstra’s algorithm
- Mazes For Programmers part 6, paths through the mazes
- Mazes For Programmers part 7, the Aldous-Broder algorithm, and when random is not very random
- Mazes For Programmers part 8, a random walk with Wilson’s algorithm
- Mazes For Programmers part 9, some statistics, and combining the Aldous-Broder and Wilson’s algorithms
- Mazes For Programmers part 10, improving the Aldous-Broder algorithm to remove short dead-ends
- Mazes For Programmers part 11, Ruby vs C# speed tests
- Source code on GitHub
Following on from my experiments in timing the algorithms in part 9 of this series, I was curious as to why my code for Wilson’s algorithm took so much longer than the code for the Aldous-Broder algorithm.
Jamis Buck (the author of the book this is all based on) was foolish enough to leave his email address on his blog, inviting people like me to ask him questions! I asked if he had seen anything like this difference. Turns out he hadn’t actually tried timing them, so couldn’t comment.
This got me curious, so I pulled up his code, and started searching around to find out how to time code in Ruby. This turned out to be fairly simple (as it should), giving me the following…
require 'benchmark' for i in 1..10 s = Benchmark.realtime { maze = Grid.new(100, 100) AldousBroder.on(maze) } puts(s) end
This gave me 10 numbers, which enabled me to calculate an average, as well as check on the variation (standard deviation for the statistical types). I forgot to mention in the earlier post, but I was intrigued to see that my implementation of Wilson’s algorithm was fairly consistent in its running speed, whereas my conversion of his code into C# led to a much wider variation in running speed…
The orange line is my version, which is fairly steady around the 6-7s mark, whereas his version showed a much bigger variation.
I know a line graph isn’t strictly the right thing here, as the numbers aren’t in any sequence, but forgive me, I’m not a statistician!
Anyway, returning the previous point, I was now in a position to time his two Ruby implementations and compare them to mine…
My C# | His Ruby | |
---|---|---|
Aldous-Broder | 51 | 197 |
Wilson’s | 427 | 6160 |
Be First to Comment