[r-t] Exhausted search spaces
richard at ex-parrot.com
Thu Feb 4 21:56:43 UTC 2010
Simon Humphrey wrote:
> Out of idle curiosity I just ran SMC on the sample search provided by
> MBD for extents of PB6, and stoppped it after 6 minutes.
> In that time it had produced 5.5 million compositions, occupying 344
> megabytes of disk space, and (it claimed) was 0.52% through the search.
I find this rate of progress astonishing. I've coded up
what I reckon is a pretty smart search algorithm, while not
being too specific to PB6. But my code only found 602,675
methods in 6 minutes. I can't believe hand coded assembler
is a whole order of magnitude faster, so this suggests that
I'm missing some tricks. So, Mark, Graham, spill the beans.
How do you do it?
I'm also curious as to how you estimate the proportion of
the way through. I'm guessing that you are pruning
rotations as you do the search, as I've found this makes a
big speed improvement. But, in the obvious way of doing
this, the part of the search tree is far deeper around the
earlier branches. For example, if you order the calls p, b,
s, then the part of the search tree beginning pp includes
all extents that have two consecutive plain leads in them
(which must be the vast majority), while the pb and ps
branches contain those extents that have no consecutive
plains, and the b and s branches contain no extents as all
extents include plain leads. In other words, the last 67%
of the search space can be pruned down so heavily that it
can be searched in microseconds.
More information about the ringing-theory