flat assembler
Message board for the users of flat assembler.

Index > Heap > Some interesting regular expressions article

Author
Thread Post new topic Reply to topic
typedef



Joined: 25 Jul 2010
Posts: 2913
Location: 0x77760000
typedef
I was looking into data structures and algorithms and I acme across this interesting article.

http://swtch.com/~rsc/regexp/regexp1.html

Thought I might share
Post 25 Nov 2011, 10:22
View user's profile Send private message Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4237
Location: 2018
edfed
i'd like to win the one million prize, but i don't understand what means:

find an efficient way to MATCH a NP problem using BACKTRACKING.

if only i know what means UPCASE words....
Post 25 Nov 2011, 18:25
View user's profile Send private message Visit poster's website Reply with quote
emc



Joined: 20 Aug 2011
Posts: 90
Location: France
emc
I've read only the first part, but it's interesting. Thanks for sharing Wink
Post 25 Nov 2011, 19:44
View user's profile Send private message Reply with quote
f0dder



Joined: 19 Feb 2004
Posts: 3170
Location: Denmark
f0dder
The Article wrote:
Some might argue that this test is unfair to the backtracking implementations, since it focuses on an uncommon corner case. This argument misses the point: given a choice between an implementation with a predictable, consistent, fast running time on all inputs or one that usually runs quickly but can take years of CPU time (or more) on some inputs, the decision should be easy.
I don't really agree with this argument, as long as pathological behaviour is triggered solely by the regular expression, and not the input to the RegEx.

If the, say, PCRE algorithm outperforms the Thompson approach by large enough margins on real-world style RegExes, it would be stupid not to use it for a lot of scenarios.

Just keep in mind to never construct RegExes from user input in situations where you don't want to be DOS'ed Smile
Post 26 Nov 2011, 16:22
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You can attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.