From: Oleh Krehel <ohwoeowho@gmail.com>
To: Dmitry Gutov <dgutov@yandex.ru>
Cc: 20365@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 [thread overview]
Message-ID: <CAA01p3qiH4SUbOXkAVtYnh7V4q9k7Q9RgOjAbof4dSWg=K1mOg@mail.gmail.com> (raw)
In-Reply-To: <5533DB54.8000000@yandex.ru>
On Sun, Apr 19, 2015 at 6:44 PM, Dmitry Gutov <dgutov@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
next prev parent reply other threads:[~2015-04-19 17:00 UTC|newest]
Thread overview: 18+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-04-18 16:11 bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1 Oleh Krehel
2015-04-18 17:41 ` Stefan Monnier
2015-04-18 17:49 ` Oleh Krehel
2015-04-19 2:04 ` Stefan Monnier
2015-04-19 11:53 ` Oleh Krehel
2015-04-19 14:43 ` Drew Adams
2015-04-19 16:44 ` Dmitry Gutov
2015-04-19 17:00 ` Oleh Krehel [this message]
2015-04-19 17:12 ` Dmitry Gutov
2015-04-20 2:29 ` Stefan Monnier
2015-04-20 8:38 ` Oleh Krehel
2015-04-20 12:30 ` Oleh Krehel
2022-04-17 10:51 ` Lars Ingebrigtsen
2015-04-20 14:38 ` Stefan Monnier
2015-04-20 14:52 ` Oleh Krehel
2015-04-20 19:14 ` Stefan Monnier
2015-04-18 23:40 ` Drew Adams
2015-04-19 1:50 ` Stefan Monnier
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/emacs/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAA01p3qiH4SUbOXkAVtYnh7V4q9k7Q9RgOjAbof4dSWg=K1mOg@mail.gmail.com' \
--to=ohwoeowho@gmail.com \
--cc=20365@debbugs.gnu.org \
--cc=dgutov@yandex.ru \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).