GNU bug report logs - #20365
24.5; all-completions returns duplicates for Info-read-node-name-1

Previous Next

Full log

View this message in rfc822 format

From: Dmitry Gutov <dgutov <at> yandex.ru>
To: Oleh Krehel <ohwoeowho <at> gmail.com>, Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 20365 <at> debbugs.gnu.org
Subject: bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1
Date: Sun, 19 Apr 2015 19:44:04 +0300

On 04/19/2015 02:53 PM, Oleh Krehel wrote:

> About the duplicate entries, I think it should be the responsibility
> of the caller to remove the duplicates.

That could have been a decent argument if we're discussing a new API, 
and not an already widely-used one.

> Here's my line of thought: a
> completion function is expected to have an O(N) complexity, where N is
> the amount of candidates. Removing duplicates is O(N^2) at worst, and
> O(NlogN) at best.

O(NlogN) is closer to the truth:

First, you copy - O(N), then sort - O(NlogN), then call 
`delete-consecutive-dups' (linear time).

> So the completion function should not attempt to
> remove the duplicates. It's doesn't affect the performance when I do
> it for 1000 candidates, but when it's 20k (`describe-function') it can
> have an impact.

Even on a decently-sized collection (38K), this takes only 80ms:

(delete-consecutive-dups (sort (all-completions "" obarray) #'string<))

That's not terrible.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.