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 -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html