I don't care about the link to the slides - this presentation was created in 2011, by one of the most powerful companies on this planet. So I need to watch the video in one window, have the slides in another and then switch the slides? Sure, I could do that ...
The slides are available at goo[dot]gl[slash]FzEjQ Sorry for the weird URL formatting: that's the only way that TH-cam will let us post the comment. Josh and Jeremy
Does Pattern.compile() automatically add anchors? In most other languages, the regexp as presented in the video will run (rather quickly in fact) and print 99. To demonstrate the catastrophic backtracking the canonical regexp would have to be ^(aa|aab?)+$
Generally they film with two different cameras, or they overlay the slides in post production. Obviously that didn't happen in this case, but if you could read better, you would see that the top comment is a link directly to the slides. Please don't try so hard to be angry!
At 25:05 "it effects any regular expression library that does backtracking, that is the default library in Perl..." No it is not. Perl compiles the regular expressions to a deterministic finit automaton. $count = 0; for( $s = '' ; length($s) < 200 ; $s = $s . 'a' ){ $count ++ if $s =~ /^(aa|aab?)+$/ ; } print $count; This code just prints 99.
Just one thing guys. In the catastrophic backtracking example there shouldnt be backtracking if a DFA was created right. Didnt the tree show an NFA? Is the regex parser not generating a DFA?
You're right, and you're right. Modern regex essentially has extra features and allows somewhat 'invalid' syntax (like this) which result in NFA algorithms, where in CS regex you wouldn't normally be able to. Keep in mind, all NFAs can be converted into an equivalent DFA. The problem is the complexity - converting to a DFA doesn't fix the O(2^n) complexity you get in this case. The key is the "aab?" - the "?" is just convent shorthand. Expanded out, it means (aa|aab). When you sub that into the original, you get (aa|aa|aab)+. This is an NFA because there are multiple paths you can take when you get 'aa'. Obviously they are just duplicates of the same path, but the regex compiler doesn't recognize this. As they pointed out, the equivalent regex is (aa|aab) which doesn't need backtracking because each state has a unique new state for each input.
The problem is in backtracking, which is how Java's regex is implemented. Non-backtracking regex has guaranteed O(n) time complexity (n-num of chars in string). Checkout this article: swtch.com/~rsc/regexp/regexp1.html
31:30 I am surprised that the Java language and compiler allow you to pretend to override a method when in fact you are not overriding anything. I.e. it lets you think that you can override foo(Object[] array) with foo(String[] array), but you can't as those are not compatible signatures. The bridge method thing seems dangerous... I wonder where else similar things happen.
As usual it is necessary for the viewer to remind the incompetent hacks who filmed and edited the talk that the viewer needs to see the slides from time to time. I don't understand why Google, of all companies, would spend time and money to record these events and put them on TH-cam, but then, consistently, over a period of years, make most of them just impossible to enjoy.
I don't care about the link to the slides - this presentation was created in 2011, by one of the most powerful companies on this planet. So I need to watch the video in one window, have the slides in another and then switch the slides?
Sure, I could do that ...
Michael Riess I don't see what the problem is. They do show the slides throughout this video.
I have seen that guy live! He's awesome!
Where have you been?
The slides are available at goo[dot]gl[slash]FzEjQ
Sorry for the weird URL formatting: that's the only way that TH-cam will let us post the comment.
Josh and Jeremy
Does Pattern.compile() automatically add anchors? In most other languages, the regexp as presented in the video will run (rather quickly in fact) and print 99. To demonstrate the catastrophic backtracking the canonical regexp would have to be ^(aa|aab?)+$
Generally they film with two different cameras, or they overlay the slides in post production. Obviously that didn't happen in this case, but if you could read better, you would see that the top comment is a link directly to the slides. Please don't try so hard to be angry!
fashnek I don't see what the problem is. They do show the slides throughout this video.
i am waiting javapuzzle website to list all the session related to JavaPuzzle.
25:05 one thing about regexp puzzle php preg_match doesn`t have this problem or am i missing something?
You can't see it in the video, but at 9:30 Josh was making the L above his own head.
Nice! Regarding the EnumMap puzzler, the bug seems to have been fixed on Java 7 (bugs.java.com/view_bug.do?bug_id=6312706).
Any links to slides?
Couldn't get the catastrophic backtracking to work with PHP's regex engine...
@sdfdsv Edited? This was recorded live.
At 25:05 "it effects any regular expression library that does backtracking, that is the default library in Perl..."
No it is not. Perl compiles the regular expressions to a deterministic finit automaton.
$count = 0;
for( $s = '' ; length($s) < 200 ; $s = $s . 'a' ){
$count ++ if $s =~ /^(aa|aab?)+$/ ;
}
print $count;
This code just prints 99.
The "full-screen" slides make this video almost impossible to watch. Great content though...
Just one thing guys. In the catastrophic backtracking example there shouldnt be backtracking if a DFA was created right. Didnt the tree show an NFA? Is the regex parser not generating a DFA?
You're right, and you're right. Modern regex essentially has extra features and allows somewhat 'invalid' syntax (like this) which result in NFA algorithms, where in CS regex you wouldn't normally be able to. Keep in mind, all NFAs can be converted into an equivalent DFA. The problem is the complexity - converting to a DFA doesn't fix the O(2^n) complexity you get in this case.
The key is the "aab?" - the "?" is just convent shorthand. Expanded out, it means (aa|aab). When you sub that into the original, you get (aa|aa|aab)+. This is an NFA because there are multiple paths you can take when you get 'aa'. Obviously they are just duplicates of the same path, but the regex compiler doesn't recognize this. As they pointed out, the equivalent regex is (aa|aab) which doesn't need backtracking because each state has a unique new state for each input.
Ah totally. I forgot that the conversion from the NFA to DFA just moves the complexity around instead of eliminating it. Cheers
The problem is in backtracking, which is how Java's regex is implemented. Non-backtracking regex has guaranteed O(n) time complexity (n-num of chars in string). Checkout this article: swtch.com/~rsc/regexp/regexp1.html
SHOOOOOW THE SLIDES LOOOOOOOOOOOOOOOONGER!
Awesome!!
Mmmm. Just on full screen. Weird.
31:30 I am surprised that the Java language and compiler allow you to pretend to override a method when in fact you are not overriding anything. I.e. it lets you think that you can override foo(Object[] array) with foo(String[] array), but you can't as those are not compatible signatures. The bridge method thing seems dangerous... I wonder where else similar things happen.
@sdfdsv they all are, unfortunately. kinda annoying, but the talk content is still great...
So bad that java doesnt treat generics like C# and also the varargs make it much more confusing, half of the problems in this talk wouldnt occur..
Out of sync audio! Argh!
The last puzzler is a proof that Courier New is an awful font for programming.
Or you could be an insufferable complainer on an online video website.
Oyó fuste
Glommer of System lmfao.....
As usual it is necessary for the viewer to remind the incompetent hacks who filmed and edited the talk that the viewer needs to see the slides from time to time.
I don't understand why Google, of all companies, would spend time and money to record these events and put them on TH-cam, but then, consistently, over a period of years, make most of them just impossible to enjoy.
test
I simply hate Autoboxing/unboxing. Thanks for the convenience, but not thanks.
private enum IsMale {TRUE, FALSE, PHAL_NOT_FOUND}; >:D
awfully edited
OK, 5 minutes in and I'm done - this is unwatchable. A pity, given that I'm a huge fan of Joshua Bloch and Effective Java.