From: Dmitry Gutov <dgutov@yandex.ru>
To: Oleh Krehel <ohwoeowho@gmail.com>,
Stefan Monnier <monnier@iro.umontreal.ca>
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:44:04 +0300 [thread overview]
Message-ID: <5533DB54.8000000@yandex.ru> (raw)
In-Reply-To: <CAA01p3ozqEygTNsmWMDwvcYSnJKCQSqJ8dKnSTZJuvmierPUTA@mail.gmail.com>
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.
next prev parent reply other threads:[~2015-04-19 16:44 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 [this message]
2015-04-19 17:00 ` Oleh Krehel
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=5533DB54.8000000@yandex.ru \
--to=dgutov@yandex.ru \
--cc=20365@debbugs.gnu.org \
--cc=monnier@iro.umontreal.ca \
--cc=ohwoeowho@gmail.com \
/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).