From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Oleh Krehel Newsgroups: gmane.emacs.bugs Subject: bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1 Date: Sun, 19 Apr 2015 19:00:48 +0200 Message-ID: References: <87egnhfmcd.fsf@gmail.com> <5533DB54.8000000@yandex.ru> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 X-Trace: ger.gmane.org 1429462877 28625 80.91.229.3 (19 Apr 2015 17:01:17 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 19 Apr 2015 17:01:17 +0000 (UTC) Cc: 20365@debbugs.gnu.org To: Dmitry Gutov Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Sun Apr 19 19:01:11 2015 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1Yjsak-0001i3-F9 for geb-bug-gnu-emacs@m.gmane.org; Sun, 19 Apr 2015 19:01:10 +0200 Original-Received: from localhost ([::1]:49136 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Yjsaj-0000XA-Oj for geb-bug-gnu-emacs@m.gmane.org; Sun, 19 Apr 2015 13:01:09 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:34982) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Yjsah-0000Wt-5e for bug-gnu-emacs@gnu.org; Sun, 19 Apr 2015 13:01:08 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Yjsac-0001pu-VX for bug-gnu-emacs@gnu.org; Sun, 19 Apr 2015 13:01:07 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:42835) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Yjsac-0001pq-Rv for bug-gnu-emacs@gnu.org; Sun, 19 Apr 2015 13:01:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1Yjsac-0001QD-CF for bug-gnu-emacs@gnu.org; Sun, 19 Apr 2015 13:01:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Oleh Krehel Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 19 Apr 2015 17:01:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 20365 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: Original-Received: via spool by 20365-submit@debbugs.gnu.org id=B20365.14294628575446 (code B ref 20365); Sun, 19 Apr 2015 17:01:02 +0000 Original-Received: (at 20365) by debbugs.gnu.org; 19 Apr 2015 17:00:57 +0000 Original-Received: from localhost ([127.0.0.1]:60844 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1YjsaW-0001Pk-DO for submit@debbugs.gnu.org; Sun, 19 Apr 2015 13:00:56 -0400 Original-Received: from mail-wi0-f180.google.com ([209.85.212.180]:38529) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1YjsaT-0001PX-W1 for 20365@debbugs.gnu.org; Sun, 19 Apr 2015 13:00:54 -0400 Original-Received: by wiun10 with SMTP id n10so67560686wiu.1 for <20365@debbugs.gnu.org>; Sun, 19 Apr 2015 10:00:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=TlgfO+vGBT5bIb1LadftsD4Dcm/POmnXB1hyLzbh7iM=; b=jCE8iVaJ4F1zo32+XCr/snmgX9fNIevv+lihTsmel9/DgGIDB8SPUdeJUOaSwd0N0o mK448mXi9qs0bZANWMwiMM7sQ7L5lyDiU2bwCbay/uBl8Rc/vocuZiL2F9+CCp+h/9ql xX4OV4s1ZSoH3VF8L/aqX+4eVPlnVkME3AsEhzec0mMr2QEDcemxG9hfPXESSdSvHyq7 b5sOM0mgnN6MYKtNaNEcnwqsvt+d/LIhgHFdvKb3iZAzSBfeDAbyAvUVP/8OxixM3lg9 gVUpY56hwIO5oZ4uoSBaYZIofZ2QnopfxUiMENOS7DcPhnBHj+PgST+ITsNx69sDrcHM BSWQ== X-Received: by 10.194.143.20 with SMTP id sa20mr22803429wjb.16.1429462848194; Sun, 19 Apr 2015 10:00:48 -0700 (PDT) Original-Received: by 10.27.215.21 with HTTP; Sun, 19 Apr 2015 10:00:48 -0700 (PDT) In-Reply-To: <5533DB54.8000000@yandex.ru> X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 140.186.70.43 X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.bugs:101726 Archived-At: On Sun, Apr 19, 2015 at 6:44 PM, Dmitry Gutov 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