Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.fsmpi.rwth-aachen.de!rt.uk.eu.org!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!usenetcore.com!Xl.tags.giganews.com!border1.nntp.ams.giganews.com!nntp.giganews.com!local2.nntp.ams.giganews.com!nntp.bt.com!news.bt.com.POSTED!not-for-mail NNTP-Posting-Date: Mon, 26 May 2014 06:13:16 -0500 From: "Chris Uppal" Newsgroups: comp.lang.java.programmer References: <375vn9th0bc1faa04eg136be53hbvfjq4v@4ax.com> <3eidnVX27IjQtR_OnZ2dnUVZ8iudnZ2d@giganews.com> Subject: Re: regex tidy Date: Mon, 26 May 2014 12:12:10 +0100 X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2900.5512 X-RFC2646: Format=Flowed; Original X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.5512 Message-ID: Lines: 18 X-Usenet-Provider: http://www.giganews.com X-AuthenticatedUsername: NoAuthUser X-Trace: sv3-wxRJDG2JEwMn1S6mvdWBt38QvlqvhU4gaSMYiy+puV2yQVNWkwnLUBQBnfnzzl7qe/vcnNbLYpnYVQz!r6Pn/SeuUVIBaga4R8jzSMdhIKOfIb9dsSqfN6gQl/AAtzawxMvRF2infJ4fS7m0HdT6L/bu2Co= X-Complaints-To: abuse@btinternet.com X-DMCA-Complaints-To: abuse@btinternet.com X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.3.40 X-Original-Bytes: 1978 Xref: csiph.com comp.lang.java.programmer:28565 Leif Roar Moldskred wrote: > Now, regex engines don't _have_ to use the ordering of the term as a > suggestion for the order of evaluation, but as far as I'm aware, > that's how it's usually done. If the regexp engine is any good at all (some of them -- unforgivably -- are not) then it'll match in O(n) on the length of the input with no dependency at all[*] on the complexity of the pattern. In the process it will convert the regexp into a (possibly lazy, possibly optimal) FSA and the "ordering" of the input patterns will no longer even be meaningful. -- chris [*] to a first approximation, cache effects can presumably be significant sometimes.