[r-t] Big searches

Mark Davies 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 
next call.
  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 -> 
jump out.
  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 mailing list