Re: Large LS_COLORS makes auto_cd very slow

[Philippe Troin <phil@fifi.org>]

On Thu, 2012-04-05 at 09:33 -0700, Bart Schaefer wrote:
> On Apr 5,  8:51am, Bart Schaefer wrote:
> }
> } Or perhaps someone else has an even more clever idea.  Anything better
> } than O(N^2) would help.
> 
> Incidentally the requirement that the output remain in the same order as
> the input puts a dent in many of the algorithms you'll find with google
> on this question.

The patch in
<CAKw7uVh4X_VoJxqtjjC9Cvv2ZS2-xfr29kHyAqyG3V1=DyPQTg@mail.gmail.com>
uses a hash table.
The array uniquification while preserving order with hash is only O(n^2)
in the worst case.  If hsearch's hash implementation is reasonably good,
this algorithm should give you O(kn) where k is a small constant between
1 and 2.

Or so it seems to me. ;-)

Phil.