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

[David Kastrup <dak@gnu.org>]

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

> 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