61–70 of 117 posts
how does it fare on time complexity compared to normal tests like say AKS?
tl;dr if you know a little regex - convert your number to a string of that length (1 = 1, 2 = 11, 3 = 111) - handle 0 / 1 separately - ^(..+?)\1+$ - trick; the WHOLE thing has to match to return (^$) - first \1 match is "11", ergo string must be "11", "1111", "111111" to match - second \1 match "111", ergo string must be "111", "111111", "111111111" to match - and so on. if you find before length of string, it was no…
(I was curious about how it worked but didn't need a long article about the basics of RE's, prime numbers, and other things I understand well enough.)
Earlier quoted context omitted.
"regular language" is a mathematical term. You can add any features you want to your matcher, but some features allow you to match languages that are not "regular". However, most programmers are not mathematicians or computer scientists, and so are effectively using lay terminology which is similar to but not precisely the same as the mathematical terminology. Most programmers only care that their regex library allow…
I don't buy the layman argument. Programmers might not be mathematicians or computer scientists, but they should be professionals and held to the same standards as professionals in other fields. For example, a mechanical engineer doesn't use a "laymen" definition of tensile strength when choosing materials for a design.
Earlier quoted context omitted.
"regular language" is a mathematical term. You can add any features you want to your matcher, but some features allow you to match languages that are not "regular". However, most programmers are not mathematicians or computer scientists, and so are effectively using lay terminology which is similar to but not precisely the same as the mathematical terminology. Most programmers only care that their regex library allow…
I don't buy the layman argument. Programmers might not be mathematicians or computer scientists, but they should be professionals and held to the same standards as professionals in other fields. For example, a mechanical engineer doesn't use a "laymen" definition of tensile strength when choosing materials for a design.
The point here is that users of (colloquial) regular expressions, however professional they are or aren't, are just engaging with the surface of a deeper set of mathematical principles that require greater nuances of meaning to discuss than their applications do.
Earlier quoted context omitted.
One of my pet peeves is how PRCE destroyed the definition of "regular" in regular expressions. It has basically made a huge number of programmers illiterate as to what truly is regular in the formal sense.
That wasn't PCRE. That was Perl. PCRE just copied the features that people liked in Perl, and made them available elsewhere. The same features have also been implemented independently many times. For example Ruby, Java and Python all have independent implementations of regular expressions with a lot of the same features.
Earlier quoted context omitted.
Sure, but on the pragmatic hand, "regular" isn't super useful unless you're designing a language yourself. If you're parsing something, not understanding "regular" is going to hurt a lot less than attempting to use PCRE to do something it can't.
Regular expressions has implications in space time complexity. PCRE tosses that away.
The sad thing is that the libraries use the same algorithms even if the expression doesn't contain backreferences. A while ago, Stack Overflow had a brief outage because of regular expression performance, although the expression that caused it didn't even use backreferences or other non-regular features:
http://stackstatus.net/post/147710624694/outage-postmortem-j...
In contrast, Google Code Search - when it still existed - supported regular expression searches over world's public codebases. One key ingredient making this possible was to only use proper regular expressions:
It should be noted that this is not possible with regular expressions in the traditional sense (i.e. regular expressions only matching regular languages): http://math.stackexchange.com/a/181233/21405 Because of back references PCRE regular expressions can match non-regular languages as well.
For some great exposition on what "regular" actually means, check out http://nikic.github.io/2012/06/15/The-true-power-of-regular-... "Thus the question arises: Can regular expressions match only regular grammars, or can they also match more? The answer to this is both yes and no"...
You can think of this as the languages that can be matched with an algorithm that is bounded (i.e., O(1) ) in memory, no matter what is the string to be matched.
The following pseudocode is not bounded in memory -- can you guess why?
bool is_prime(Number n)
{
for (Number i = 2; i Very interesting. Thanks for writing this up. This is a bit more Perlish (not that I'm an authority): sub is_prime { (1x$_[0]) !~ /^(?:.?|(.{2,}?)\1+)$/; } But perhaps less clear to a novice reader. You can also leave off the semicolon.
perl -wle 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\1+$/' [number] (My first exposure to that was in '97 or so as a .sig from abigail in comp.lang.perl.misc)
Earlier quoted context omitted.
That wasn't PCRE. That was Perl. PCRE just copied the features that people liked in Perl, and made them available elsewhere. The same features have also been implemented independently many times. For example Ruby, Java and Python all have independent implementations of regular expressions with a lot of the same features.
When were back-references introduced in sed?
> Grouping and backreferences: All versions of sed support grouping and backreferences on the LHS and backreferences only on the RHS.
Earlier quoted context omitted.
Presumably, they thought of A as in front of B in the expression "AB" rather than in the expression "BA". (Which is also how I would normally think of "in front", for what it's worth!)
Oh, that was probably it. That would be true if we were talking about FIFO queues :)