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: Mon, 12 Apr 2010 11:46:33 +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 1271065649 16367 80.91.229.12 (12 Apr 2010 09:47:29 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Mon, 12 Apr 2010 09:47:29 +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 Mon Apr 12 11:47:28 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 1O1GEp-0001as-HW for ged-emacs-devel@m.gmane.org; Mon, 12 Apr 2010 11:47:27 +0200 Original-Received: from localhost ([127.0.0.1]:44637 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O1GEo-0003kO-P5 for ged-emacs-devel@m.gmane.org; Mon, 12 Apr 2010 05:47:26 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1O1GEd-0003kG-Qh for emacs-devel@gnu.org; Mon, 12 Apr 2010 05:47:15 -0400 Original-Received: from [140.186.70.92] (port=47657 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O1GEb-0003jw-Gg for emacs-devel@gnu.org; Mon, 12 Apr 2010 05:47:14 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1O1GEI-0002F3-Gr for emacs-devel@gnu.org; Mon, 12 Apr 2010 05:46:55 -0400 Original-Received: from mail-bw0-f223.google.com ([209.85.218.223]:35084) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1O1GEI-0002Ev-AU for emacs-devel@gnu.org; Mon, 12 Apr 2010 05:46:54 -0400 Original-Received: by bwz23 with SMTP id 23so2082978bwz.26 for ; Mon, 12 Apr 2010 02:46:53 -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=uC72jEM0i1G22JFT15KpEu4dN46r8PLz79/nz1+kTlE=; b=IEol04vNFVUydro8k41p8blQ//tw9iOvBcMU5PaqQ7FiI2HgLmDIo8S1Zisyqg+76D fIe9LR3nq7ZkMxvWxVFYhpMWPAsNcPgFnhvjPYtM3m6meXLBk+686ZYGbZ85Vw3HpWyy HuHYhM+8YCc52RYiF2qzuA0uTazhRYAp6wCMM= 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=EPrvm+eLxCcryJSZOIl475dJUJ0PbWwmfRhB4/hvoeXmRwhCiPgC1gV5rmWJfT9dSs gz+PvweWhfa831hwNPYLgxC2b3sgphS39t5wphMAkmeNe38RdhwlOGoL2F2yfEfrj+vg v1hMOiDhGz1TIdKKr4RI14wRZCq4kCYoD9PPs= Original-Received: by 10.239.169.18 with HTTP; Mon, 12 Apr 2010 02:46:33 -0700 (PDT) In-Reply-To: Original-Received: by 10.239.193.80 with SMTP id h16mr341576hbi.151.1271065613165; Mon, 12 Apr 2010 02:46:53 -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:123515 Archived-At: On Mon, Apr 12, 2010 at 4:10 AM, Stefan Monnier wrote: >>> 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)? > > When matched against "ababab", it will do the following: > - search for a in the string. > - for each match of a, search for b in the remaining string. I do not understand the "for each" here. I thought that since ".*?" is greedy that means that only the first "a" could match. But maybe I am missing that the first ".*?" is not anchored. Would "^.*?a.*?b.*?c" behave differently? > - for each match of b, search for c in the remaining string. > > These are 3 nested loops, each of them doing a number of iterations > proportional to N, so you get O(N^3) complexity. > > > =C2=A0 =C2=A0 =C2=A0 =C2=A0Stefan >