From: Jeff King <peff@peff.net>
Date: Tue, 02 Oct 2007 05:13:32 GMT
Subject: Re: What's cooking in git.git (topics)
Message-ID: <20071002051332.GA4462@coredump.intra.peff.net>
In-Reply-To: <20071002050820.GA4261@coredump.intra.peff.net>

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