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: Oleh Krehel <ohwoeowho <at> gmail.com>
To: Dmitry Gutov <dgutov <at> yandex.ru>
Cc: Stefan Monnier <monnier <at> iro.umontreal.ca>, 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:00:48 +0200

On Sun, Apr 19, 2015 at 6:44 PM, Dmitry Gutov <dgutov <at> yandex.ru> wrote:

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

No problem: no completion package will complain if you don't pass it duplicates.
Then it's just a matter of fixing the offening callers of completion one by 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.

Actually, 0.08 is a lot when you consider that I would call this after
each key press (in case when the collection is a function, not for the
static list).  The sluggishness would be perceptible even for a
relatively slow typist. And this is only the overhead, there's also
actual computing to be done. There's no reason not to avoid this
overhead cost.

Oleh

Previous Next

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