Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!news.swapon.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: Robert Klemme Newsgroups: comp.lang.java.programmer Subject: Re: regex tidy Date: Sun, 25 May 2014 19:55:40 +0200 Lines: 54 Message-ID: References: <375vn9th0bc1faa04eg136be53hbvfjq4v@4ax.com> <3eidnVX27IjQtR_OnZ2dnUVZ8iudnZ2d@giganews.com> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Trace: individual.net Plb8LGBUNv7/VgplmyWYIwQZ0EeB9BRay/OLOI5bR4eMUEiUA= Cancel-Lock: sha1:vVBDLcs1OgYM/7dqfvgBmZtcIvE= User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.5.0 In-Reply-To: <3eidnVX27IjQtR_OnZ2dnUVZ8iudnZ2d@giganews.com> Xref: csiph.com comp.lang.java.programmer:28560 On 25.05.2014 19:28, Leif Roar Moldskred wrote: > Robert Klemme wrote: >> >> The engine does not need the reordering to do this optimization. If you >> want to help lesser engines which do not optimize here you would have to >> transform it into >> >> (c(?:at|ow)|dog|rabbit) >> >> to get more efficient matching. > > Besides, when we're talking about performance on this scale, the order > in which the terms are evaluated by the regex engine might matter: > we'd want it to check against the more common case first to minimize > the time spent backtracking. Only problem is that this cannot be done by looking at the expression - the optimizer would need additional data about inputs. That would make the reordering more complicated and the result would probably be no longer "tidy". I came to think that Roedy's main concern was human readability and not performance of the expression. However, changing a human crafted expression is probably not wise - for performance reasons (see below) but also for readability: it may actually be crucial for readability that the expression stays as written. > 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. That does make sense: since NFSs are known to execute in order (as opposed to DFAs) it is wise to use the human given order because then we have a chance to do that optimization. > So if "rabbit" is much more prevalent in your expected input than either > "cat", "cow" or "dog", alphabetizing the terms would yield suboptimal > performance. Right, but see above. > (That said, if you find that such low-level details about the regex' > efficency is important enough that it is significant for your program, > you should probably rethink your whole approach.) Yes, for word search there are probably better approaches. I personally haven't come across a case where this order would have mattered. In many cases cost of IO will be dominant anyway. Cheers robert