From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Lennart Borgman Newsgroups: gmane.emacs.devel Subject: Re: `completion-in-region' Date: Sun, 11 Apr 2010 22:08:11 +0200 Message-ID: References: <493575A8A83B43BCB1AF49E239599A77@us.oracle.com> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Trace: dough.gmane.org 1271016524 21570 80.91.229.12 (11 Apr 2010 20:08:44 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Sun, 11 Apr 2010 20:08:44 +0000 (UTC) Cc: Leo , Drew Adams , emacs-devel@gnu.org To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun Apr 11 22:08:42 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 1O13ST-0003qg-0i for ged-emacs-devel@m.gmane.org; Sun, 11 Apr 2010 22:08:41 +0200 Original-Received: from localhost ([127.0.0.1]:40488 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O13SS-00037u-6Q for ged-emacs-devel@m.gmane.org; Sun, 11 Apr 2010 16:08:40 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1O13SM-00037G-W4 for emacs-devel@gnu.org; Sun, 11 Apr 2010 16:08:35 -0400 Original-Received: from [140.186.70.92] (port=58247 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O13SL-00036r-MV for emacs-devel@gnu.org; Sun, 11 Apr 2010 16:08:34 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1O13SK-0001Vc-B0 for emacs-devel@gnu.org; Sun, 11 Apr 2010 16:08:33 -0400 Original-Received: from mail-bw0-f223.google.com ([209.85.218.223]:42448) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1O13SK-0001VU-33 for emacs-devel@gnu.org; Sun, 11 Apr 2010 16:08:32 -0400 Original-Received: by bwz23 with SMTP id 23so1538332bwz.26 for ; Sun, 11 Apr 2010 13:08:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:in-reply-to:references :from:date:received:message-id:subject:to:cc:content-type :content-transfer-encoding; bh=WhT7ac2Ga7DowsbrWSK7AgkbIxDPpiArH3hq/tLkhGg=; b=MDF1vXU9Z3dO1NKeCraHyKYVo/ZSocegsEDWJnHAtMBi/A0EqT6NpOHmYBIElMik9X XYGq6XOf4jFBDXWTSUWA8F/8flWrGn1JGie4PzDOG8iIv+TySmPZf//frImRwUP+wBlk 3SFXmjEt4swAKW27EdocqSK8p9EQIDLjVM2kM= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type:content-transfer-encoding; b=MyZQC4BFruVbjDKnUyrJaiQuJMqBqr77txKTFEHk/lbxgLJZjU8PF9MR+deqWzVOcE ILHUxZvmR8U8SZB/oQ9RQOzLmPAocc2RhdUjdE913i+uzVQsDaCL2Pg+7mKl2qdLaPsH HXkyMJ4NhJ18v3b70FlsZy3JrQcZWzhhiOPmA= Original-Received: by 10.239.169.18 with HTTP; Sun, 11 Apr 2010 13:08:11 -0700 (PDT) In-Reply-To: Original-Received: by 10.239.158.133 with SMTP id u5mr251363hbc.199.1271016511081; Sun, 11 Apr 2010 13:08:31 -0700 (PDT) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 2) 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:123499 Archived-At: On Sun, Apr 11, 2010 at 9:44 PM, Stefan Monnier wrote: > > I see that ido implements it by turning "abc" into the regexp > ".*a.*b.*c". =C2=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?