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

From: Johannes Schindelin <johannes.schindelin@gmx.de>
Date: Jul 23, 2009, 23:24 UTC
Message-ID: <alpine.DEB.1.00.0907240114410.8306@pacific.mpi-cbg.de>
In-Reply-To: <alpine.LSU.2.00.0907232310220.22113@hermes-2.csi.cam.ac.uk>

Hi,

On Thu, 23 Jul 2009, Tony Finch wrote:

Show 6 quoted lines

> 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