From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 28618 invoked by alias); 5 Apr 2012 17:09:22 -0000 Mailing-List: contact zsh-users-help@zsh.org; run by ezmlm Precedence: bulk X-No-Archive: yes List-Id: Zsh Users List List-Post: List-Help: X-Seq: 16990 Received: (qmail 7367 invoked from network); 5 Apr 2012 17:09:21 -0000 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on f.primenet.com.au X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,SPF_HELO_PASS autolearn=ham version=3.3.2 Received-SPF: pass (ns1.primenet.com.au: SPF record at fifi.org designates 173.255.216.206 as permitted sender) Subject: Re: Large LS_COLORS makes auto_cd very slow From: Philippe Troin To: Bart Schaefer Cc: zsh-users@zsh.org In-Reply-To: <120405093309.ZM13749@torch.brasslantern.com> References: <120404005237.ZM10249@torch.brasslantern.com> <120405085125.ZM13673@torch.brasslantern.com> <120405093309.ZM13749@torch.brasslantern.com> Content-Type: text/plain; charset="UTF-8" Date: Thu, 05 Apr 2012 10:00:06 -0700 Message-ID: <1333645206.4223.42.camel@air.home.fifi.org> Mime-Version: 1.0 X-Mailer: Evolution 2.30.3 (2.30.3-1.fc13) Content-Transfer-Encoding: 7bit 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 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.