Re: git-rev-list: "--bisect" flag

[Jon Seymour <jon.seymour@gmail.com>]

> I am exploring another variation of the idea which is even simpler.
> Experimentally it seems quite similar to your average case
> performance, but doesn't yet approach your low std deviations.
> However, I think I know why that is, so I will, after a few games of
> pool and a similar number of beers, have another crack at it.
> 

Ok, just for information, I have a linear bisection algorithm which
results in a bug-blatt algorithm with the following characteristics on
the Linux 2.6 kernel:

AVERAGE	13.64589235
MEDIAN	13
MAX	28
MIN	9
STDEV	2.171923221

These results were derived by running the algorithm over the full 2118
commits of the
current Linux 2.6 source.

I'll document what this algorithm is and what its flaws are.

The algorithm is as follows:

Consider the graph as a closed network of pipes with N reservoirs of 1
unit of volume. Rotate this graph so the head is at the top. Now, pour
N units of liquid into the top of the network of pipes. The liquid
percolates through the network of pipes and ends up in the reservoirs.
The selected bisection point is the node that saw as close to N/2
units of liquid as any other node.

Now, why isn't this as good (in terms of average and stdev) as Linus'
algorithm? The flaw with this algorithm is that some liquid from peer
nodes reaches the lower half of the network before the liquid that
went through the selected node. As a result, the selected node is
elevated "above" the ideal bisection point, by a factor that I believe
would be sufficient to explain the higher average and also the greater
standard deviation.

Still, my algorithm is very simple and very linear, so it's very good a start.

As it happens, I believe I have (re-?)discovered a precise way to
discover the bisection points in O(n). I am in the midst of
implementing that now.

jon.