[r-t] Big searches
mark at snowtiger.net
Sun Jan 6 11:09:33 UTC 2008
Mike Ovenden writes,
> So I suppose your node count is pretty much my branch count, but I'm
> wondering how come we're 1% apart.
I don't think this is very surprising - there are several ways to write an
inner loop of a search engine, and various places to put the counter
increment, depending on whether it is before or after various tests for
inclusion of the current node. My code appears to do the following:
1. Use current call to load pointer to next node.
2. Is next node null? (Implies this call not allowed from current node)
Yes -> jump out to try next call.
3. Next node is valid, increment node pointer.
4. Check to see if node has been visited before. Yes -> jump out to try
5. Check to see if composition too long with new node. Yes -> jump out.
6. Check to see if node is false against anything visited before. Yes ->
7. Node OK, mark it as visited.
8. Prepare for next iteration, jump to Loop top.
This is a very simplistic version of the loop, with no pruning, however it
shows that I count all nodes considered for inclusion, even if they may be
false or already included in the comp.
More information about the ringing-theory