Mailing-List: contact cygwin-help AT sourceware DOT cygnus DOT com; run by ezmlm
List-Subscribe: <mailto:cygwin-subscribe AT sources DOT redhat DOT com>
List-Archive: <http://sources.redhat.com/ml/cygwin/>
List-Post: <mailto:cygwin AT sources DOT redhat DOT com>
List-Help: <mailto:cygwin-help AT sources DOT redhat DOT com>, <http://sources.redhat.com/ml/#faqs>
Sender: cygwin-owner AT sources DOT redhat DOT com
Delivered-To: mailing list cygwin AT sources DOT redhat DOT com
To: Jim Blandy <jimb AT cygnus DOT com>
Cc: Eli Zaretskii <eliz AT is DOT elta DOT co DOT il>, dj AT redhat DOT com, gcc AT gcc DOT gnu DOT org,
        gdb AT sources DOT redhat DOT com, binutils AT sources DOT redhat DOT com,
        cygwin AT sources DOT redhat DOT com
Subject: Re: Another RFC: regex in libiberty
References: <200106080127 DOT VAA01308 AT greed DOT delorie DOT com>
	<9003-Fri08Jun2001100651+0300-eliz AT is DOT elta DOT co DOT il>
	<nplmmyz1qv DOT fsf AT zwingli DOT cygnus DOT com>
From: Jim Blandy <jimb AT zwingli DOT cygnus DOT com>
Date: 12 Jun 2001 08:48:54 -0500
In-Reply-To: Jim Blandy's message of 12 Jun 2001 00:49:28 -0500
Message-ID: <np3d95zu49.fsf@zwingli.cygnus.com>
Lines: 9
X-Mailer: Gnus v5.3/Emacs 19.34


Jim Blandy <jimb AT cygnus DOT com> writes:
> To generate every possible match, you have to choose every possible
> way to divide up those twenty a's amongst six .* patterns.  I think
> this is 20 choose 5, or 1.9 million, matches you have to try.  In
> general, I think the time to match POSIXly can increase exponentially
> in the length of your regexp, given a long enough data string.

20 choose 5 is, of course, only 15504, not 1.9 million.  Oops.

--
Want to unsubscribe from this list?
Check out: http://cygwin.com/ml/#unsubscribe-simple