find_difference shortcut failure without walking out
Aaron Bentley
aaron.bentley at utoronto.ca
Thu Dec 13 12:31:05 GMT 2007
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Aaron Bentley wrote:
> John Arbash Meinel wrote:
>> The only algorithm I can think of off-hand, is the Greatest Distance From
>> Origin that Aaron and Robert talked about in London. Basically, every node is:
>> max(parent_distances) + 1.
>
> It seems to me that the problem here is finding the right stop
> condition; stop too early and you incorrectly determine nodes to be
> "uncommon", stop too late and you waste resources.
>
> So when can we stop? When it's impossible that we can determine any
> more nodes to be common. Since ancestry is a DAG, we know that no
> descendant of a node can also be its ancestor. In order for a searcher
> to find that a previously-uncommon node is common, it must search from
> an ancestor of that node.
Okay, I think I swapped some terms here. Let's try again.
So when can we stop? When it's impossible that we can determine any
more nodes to be common. Since ancestry is a DAG, we know that no
descendant of a node can also be its ancestor. In order for a searcher
to find that an apparently-uncommon node is actually common, it must
search from an descendant of that node.
Therefore, when all search nodes are ancestors of all
apparently-uncommon nodes, more searching will not find any
apparently-uncommon nodes to be common. Therefore, we can stop.
Aaron
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFHYSYJ0F+nu1YWqI0RAtrIAJ4hb7HA6hxVoDj5LuuWGEctkUAiYgCgghqo
xsxwTsg1gpB+GUyoGdxT5Po=
=zGue
-----END PGP SIGNATURE-----
More information about the bazaar
mailing list