From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Dmitry Gutov 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:44:04 +0300 Message-ID: <5533DB54.8000000@yandex.ru> References: <87egnhfmcd.fsf@gmail.com> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Trace: ger.gmane.org 1429461926 14139 80.91.229.3 (19 Apr 2015 16:45:26 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 19 Apr 2015 16:45:26 +0000 (UTC) Cc: 20365@debbugs.gnu.org To: Oleh Krehel , Stefan Monnier Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Sun Apr 19 18:45:14 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 1YjsLI-0000rT-8U for geb-bug-gnu-emacs@m.gmane.org; Sun, 19 Apr 2015 18:45:12 +0200 Original-Received: from localhost ([::1]:49119 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YjsLH-00069R-Lx for geb-bug-gnu-emacs@m.gmane.org; Sun, 19 Apr 2015 12:45:11 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:33208) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YjsLE-00067w-B5 for bug-gnu-emacs@gnu.org; Sun, 19 Apr 2015 12:45:09 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1YjsL9-0005tZ-3C for bug-gnu-emacs@gnu.org; Sun, 19 Apr 2015 12:45:08 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:42826) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YjsL8-0005tB-Vr for bug-gnu-emacs@gnu.org; Sun, 19 Apr 2015 12:45:03 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1YjsL8-000122-2y for bug-gnu-emacs@gnu.org; Sun, 19 Apr 2015 12:45:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Dmitry Gutov Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 19 Apr 2015 16:45:01 +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.14294618543891 (code B ref 20365); Sun, 19 Apr 2015 16:45:01 +0000 Original-Received: (at 20365) by debbugs.gnu.org; 19 Apr 2015 16:44:14 +0000 Original-Received: from localhost ([127.0.0.1]:60835 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1YjsKL-00010h-Vg for submit@debbugs.gnu.org; Sun, 19 Apr 2015 12:44:14 -0400 Original-Received: from mail-wi0-f179.google.com ([209.85.212.179]:33406) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1YjsKK-00010U-M5 for 20365@debbugs.gnu.org; Sun, 19 Apr 2015 12:44:13 -0400 Original-Received: by wiax7 with SMTP id x7so66664481wia.0 for <20365@debbugs.gnu.org>; Sun, 19 Apr 2015 09:44:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=sender:message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:content-type:content-transfer-encoding; bh=G/8LSwS/GtaYUiG8RXG0RjJPAk24tWXLRXmeibl/qbw=; b=Od9K7DUd4TJX8Di5cZMRWDW5/0gacjg3BOhGHcCxDVMKxe/PAq5iAf730vToMktIJV EXhjNAJgj5hhG07/CbEqIWtfsoT6qtAj5jkTyxeUe4Ra+r0pqRyjy6LG0qVsrWRK+iuB pUk9uVH1RL9oD1S7Zzb/pdCXpXXmHlUZmZJdETAK90L+SII44Jj7SwCahSjOlrb6/k5P Sum0vkoWrOAwXycRinNc62Y8E7hO22PrQgrJNyGW654Bpf3/IBWyWWI7qMqODGgV7EjA zGlLFXkhma4GaEckUp9wJzKaxJJLISwjIIKYVHFuJYVzEAFGhXPf1GAofnIfiJc4SWqI Ai+w== X-Received: by 10.194.61.133 with SMTP id p5mr24140355wjr.132.1429461846945; Sun, 19 Apr 2015 09:44:06 -0700 (PDT) Original-Received: from [192.168.1.2] ([82.102.93.54]) by mx.google.com with ESMTPSA id ub1sm23635497wjc.43.2015.04.19.09.44.05 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 19 Apr 2015 09:44:06 -0700 (PDT) User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:36.0) Gecko/20100101 Thunderbird/36.0 In-Reply-To: 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:101724 Archived-At: 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.