Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #28560

Re: regex tidy

Show all headers | View raw

On 25.05.2014 19:28, Leif Roar Moldskred wrote:
> Robert Klemme <shortcutter@googlemail.com> 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

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

regex tidy Roedy Green <see_website@mindprod.com.invalid> - 2014-05-23 11:39 -0700
  Re: regex tidy leif.roar@invalid.com (Leif Roar Moldskred) - 2014-05-23 14:33 -0500
    Re: regex tidy Joshua Cranmer 🐧 <Pidgeot18@verizon.invalid> - 2014-05-23 15:05 -0500
  Re: regex tidy Robert Klemme <shortcutter@googlemail.com> - 2014-05-24 14:55 +0200
    Re: regex tidy Roedy Green <see_website@mindprod.com.invalid> - 2014-05-25 09:09 -0700
      Re: regex tidy Robert Klemme <shortcutter@googlemail.com> - 2014-05-25 18:49 +0200
        Re: regex tidy leif.roar@invalid.com (Leif Roar Moldskred) - 2014-05-25 12:28 -0500
          Re: regex tidy Robert Klemme <shortcutter@googlemail.com> - 2014-05-25 19:55 +0200
          Re: regex tidy "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2014-05-26 12:12 +0100
    Re: regex tidy Roedy Green <see_website@mindprod.com.invalid> - 2014-05-25 09:10 -0700
    Re: regex tidy Roedy Green <see_website@mindprod.com.invalid> - 2014-05-25 09:13 -0700
    Re: regex tidy Roedy Green <see_website@mindprod.com.invalid> - 2014-05-25 09:21 -0700
      Re: regex tidy Joshua Cranmer 🐧 <Pidgeot18@verizon.invalid> - 2014-05-25 13:31 -0500
        Re: regex tidy "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2014-05-26 12:31 +0100

csiph-web