Re: What's cooking in git.git (topics)

On Tue, Oct 02, 2007 at 01:08:20AM -0400, Jeff King wrote:

One approach which I haven't tried but might be promising is to actually
keep each list sorted, and then do a "merge" of the two lists, comparing
as you go. We don't really need to do arbitrary lookups in the hash; we
just need to compare two hash tables at a time. My approach was to be
simple, but have O(HASH_SIZE) comparisons (where HASH_SIZE is on the
order of 2^17), and that's clearly just too big. But with a list merge,
it should be O(n), where n is the actual number of lines in the files
(or binary chunks for the binary case).

BTW, I don't want to steal credit for this idea...it comes from thinking
about what David Kastrup said earlier in the thread, though I think he
was proposing sorting just inside buckets.

-Peff