From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: `completion-in-region' Date: Sun, 11 Apr 2010 16:51:19 -0400 Message-ID: References: <493575A8A83B43BCB1AF49E239599A77@us.oracle.com> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable X-Trace: dough.gmane.org 1271019095 29279 80.91.229.12 (11 Apr 2010 20:51:35 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Sun, 11 Apr 2010 20:51:35 +0000 (UTC) Cc: Leo , Drew Adams , emacs-devel@gnu.org To: Lennart Borgman Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun Apr 11 22:51:32 2010 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1O147v-0000fc-QY for ged-emacs-devel@m.gmane.org; Sun, 11 Apr 2010 22:51:32 +0200 Original-Received: from localhost ([127.0.0.1]:37453 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O147v-0006ho-9H for ged-emacs-devel@m.gmane.org; Sun, 11 Apr 2010 16:51:31 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1O147p-0006gY-Cy for emacs-devel@gnu.org; Sun, 11 Apr 2010 16:51:25 -0400 Original-Received: from [140.186.70.92] (port=36571 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O147m-0006eb-A0 for emacs-devel@gnu.org; Sun, 11 Apr 2010 16:51:24 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1O147l-0005ad-4Y for emacs-devel@gnu.org; Sun, 11 Apr 2010 16:51:22 -0400 Original-Received: from ironport2-out.teksavvy.com ([206.248.154.181]:58825 helo=ironport2-out.pppoe.ca) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1O147k-0005aX-Mk for emacs-devel@gnu.org; Sun, 11 Apr 2010 16:51:21 -0400 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AvsEAE7TwUtMCqWu/2dsb2JhbACbRXK1YIUMBItG X-IronPort-AV: E=Sophos;i="4.52,185,1270440000"; d="scan'208";a="60633651" Original-Received: from 76-10-165-174.dsl.teksavvy.com (HELO ceviche.home) ([76.10.165.174]) by ironport2-out.pppoe.ca with ESMTP; 11 Apr 2010 16:51:19 -0400 Original-Received: by ceviche.home (Postfix, from userid 20848) id 9027A660BF; Sun, 11 Apr 2010 16:51:19 -0400 (EDT) In-Reply-To: (Lennart Borgman's message of "Sun, 11 Apr 2010 22:08:11 +0200") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.0.50 (gnu/linux) X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:123503 Archived-At: >> I see that ido implements it by turning "abc" into the regexp >> ".*a.*b.*c". =A0But matching this regexp against a string like >> "abababababab" takes time O(N^3) where N is the length of the completion >> candidate, which makes me a bit uneasy > Does not "^a.*?b.*?c" give the same matches? No because of the ^. If you use ".*?a.*?b.*?c", then yes it gives the same matches but it also has the same O(N^3) worst case. Stefan