Following One Path to the End
Last timeSpreading Out One Ring at a Time
Going as deep as possible before backtracking uses almost no memory, gives up the shortest path guarantee, and answers two questions the ring walk cannot.
One change to the previous walk
Take the ring walk from the last lesson and change exactly one thing: serve
the waiting line from the end that was most recently joined, rather than the
end that joined first. Nothing else about the method changes.
The behaviour changes completely. Instead of spreading out evenly, the walk
takes a neighbour, then a neighbour of that, then a neighbour of that, driving
as far from the start as the links allow, and only when it runs out of new
ground does it back up to the most recent place that still has an unexplored
neighbour. It is how a person explores a building with no map, and it is how
anybody walks a maze.
| step | step | taken from the back | its neighbours | newly added | the pile now |
|---|---|---|---|---|---|
| 1 | 1 | a | b, c | b, c | b, c |
| 2 | 2 | c | a, d | d | b, d |
| 3 | 3 | d | b, c, e | e | b, e |
| 4 | 4 | e | d, f | f | b, f |
| 5 | 5 | f | e | nothing | b |
| 6 | 6 | b | a, d | nothing | empty, done |
What was given up
The ring walk could say that f is four links from a. This walk cannot say
anything of the kind. It reached f after four steps because it happened to go
that way, and on a graph with a few more links it might have reached f by a
route of twenty steps and recorded that instead. There is no sense in which
the deep walk finds a short route, and treating a route it produces as a
shortest route is simply an error.
That is a real loss, and it is paid for with memory. The ring walk holds a
whole ring; this one holds one path from the start to wherever it currently
is, plus the unexplored neighbours alongside it.
| widest ring | longest path | ring walk holds | deep walk holds | |
|---|---|---|---|---|
| road network | 3000 | 2000 | 3000 | 2000 |
| social graph | 400000 | 40 | 400000 | 40 |
| long chain | 2 | 1000000 | 2 | 1000000 |
This is also why the deep walk is usually written with an explicit pile rather
than by letting the language call itself. A recursive version is shorter and
reads better, and it fails on the third row of that table, because a path of a
million points is a million nested calls and every language gives up long
before that. Writing the pile out by hand costs four lines and removes the
failure.
The lesson stops here
3 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents