Re: [PATCH] Remove duplicate pathspecs from ls-files command line

From: David Kastrup <dak@gnu.org>
Date: Aug 30, 2007, 05:52 UTC
Message-ID: <85myw9d0x6.fsf@lola.goethe.zz>
In-Reply-To: <7vr6llak4h.fsf@gitster.siamese.dyndns.org>

Junio C Hamano <gitster@pobox.com> writes:

Show 9 quoted lines

> David Kastrup <dak@gnu.org> writes:
>
>> Does anything speak against sorting the pathspecs?  That is an O(n log
>> n) operation,
>
> Not sorting is O(0) operation without losing cycles for the
> normal case.  I think you can sort first in that error handling
> path to avoid O(n^2) but sorting upfront to remove duplicates
> for every case is unnecessary bloat that penalizes sane callers.

Not if you need to sort the file list anyway in order to merge it with the index. Of course, sorting patterns will not in all cases establish the order of their expansions.

In any case, uniqueness should be establishable when matching to the index, regardless of whether this matching is done by sort&merge (probably the most efficient variant) or by binary search as it is done now if I understand correctly. I am just not happy with the ensuing binary _insertion_ as this is an O(nm) operation when inserting n elements into an m element data structure. A list merge is O(n+m), in contrast, and we can access the index sequentially.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum