Re: Newton-Raphson, was Re: Performance issue of 'git branch'

Hi,

On Thu, 23 Jul 2009, Tony Finch wrote:

I think Newton-Raphson is a brilliant but misleading idea. (As Junio 
said, "egg of Columbus" - it certainly blew my mind!) However, Newton's 
method works with smooth curves, but a pack index is a straight line 
plus stochastic deviations. If you try to apply Newton's method then the 
more you zoom in the more the random variations will send you away from 
the place you want to be.

No.

Think about it, absent any further information than "it is a hash, i.e. 
distributed pretty equally in _any_ byte", even subsets of a sorted list 
will me more or less linear.  And assuming that they are linear is _still_ 
your best bet.

Assuming that subsets of said sorted list will _still_ minimize the 
average number of steps to take until you find the correct entry.

Unless you have more information about the nature of the hashes, of 
course.

This should give you O(1) seeks in the index per object lookup.

There is no way to achieve that, best thing you can hope for is _expected_ 
O(1) (e.g. with a hashmap, with exponential worst case).

Ciao,
Dscho