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 23:06:44 +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 1271020037 32108 80.91.229.12 (11 Apr 2010 21:07:17 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Sun, 11 Apr 2010 21:07:17 +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 23:07:15 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 1O14N8-0005hR-FX for ged-emacs-devel@m.gmane.org; Sun, 11 Apr 2010 23:07:14 +0200 Original-Received: from localhost ([127.0.0.1]:50486 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O14N8-0004SA-1N for ged-emacs-devel@m.gmane.org; Sun, 11 Apr 2010 17:07:14 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1O14N3-0004RW-1X for emacs-devel@gnu.org; Sun, 11 Apr 2010 17:07:09 -0400 Original-Received: from [140.186.70.92] (port=60479 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O14N1-0004Qi-SW for emacs-devel@gnu.org; Sun, 11 Apr 2010 17:07:08 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1O14N0-000712-Bj for emacs-devel@gnu.org; Sun, 11 Apr 2010 17:07:07 -0400 Original-Received: from fg-out-1718.google.com ([72.14.220.158]:58313) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1O14N0-00070q-6A for emacs-devel@gnu.org; Sun, 11 Apr 2010 17:07:06 -0400 Original-Received: by fg-out-1718.google.com with SMTP id d23so906994fga.12 for ; Sun, 11 Apr 2010 14:07:04 -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=mr92j/j79ZHO1yMHr3kIXMmG8wybEvsSM50+K6gsFfo=; b=x1NgrFHjij8yJJYLoy47j/h6FV8IGQQeQBHANdz7YdutiHA7p24UrFtnz7FsmNfHvb UtyDNtoYxVMrWokrHTffC8NF8iZ75m+9yrHj9fZ+Ct+gqh8YMspd5NJwSbA/dXHXzwW8 MgHxevnfe0ERcCNua0HfdFOFvlI00PIs5PPKs= 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=ehy/A612tnTlnlVNcF3L47LrXJYXZIUtqHtbOWf/pDlkmsJ+qWmpTS+KKk9KZTu+uy UuLLu/ucauUfc6n7U1JLZKXltWKgFw8eMSgYWBjaGTj8bGUPWkkngaAJWB6tBeb4rZYK uSAGYo5By2wROkp3ES8a1kEOwVMajWUmTmFcg= Original-Received: by 10.239.169.18 with HTTP; Sun, 11 Apr 2010 14:06:44 -0700 (PDT) In-Reply-To: Original-Received: by 10.239.193.80 with SMTP id h16mr279028hbi.151.1271020024173; Sun, 11 Apr 2010 14:07:04 -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:123504 Archived-At: On Sun, Apr 11, 2010 at 10:51 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 completio= n >>> candidate, which makes me a bit uneasy >> Does not "^a.*?b.*?c" give the same matches? > > No because of the ^. Eh, sorry. > If you use ".*?a.*?b.*?c", then yes it gives the > same matches but it also has the same O(N^3) worst case. This is not the right place perhaps to educate me on this, but to me it looks like just three linear searches with the summed length for the searches equal to that of the candidate strings. Is not that O(N)?