afl-material: comparison videos/02-algo2.srt

equal deleted inserted replaced

-:3bf3f5bb067e
+:260e330f7466
 What would be the
 derivative of one?
 126
 00:06:32,030 --> 00:06:36,140
-So the derivative of c of one.
+So the derivative of c of 1
 127
 00:06:36,140 --> 00:06:38,990
-Peaches defined as 0.
+would be defined as 0.
 128
 00:06:38,990 --> 00:06:41,465
 Okay, fair enough.
 129
 00:06:41,465 --> 00:06:44,960
-If he have any cross one,
+If he have n = 1,
 130
 00:06:44,960 --> 00:06:48,125
 then we just have one copy
 of this regular expression.
 131
 00:06:48,125 --> 00:06:50,120
-So there's not much as we can do.
+So there's not much else we can do.
 132
 00:06:50,120 --> 00:06:53,735
 We would have to calculate
-the derivative of air are.
+the derivative of r.
 133
 00:06:53,735 --> 00:06:57,395
-Now in the n equals two case.
+Now in the n = 2 case,
 134
 00:06:57,395 --> 00:07:00,245
-That would mean we
+that would mean we
-have two copies of
+have two copies of r.
 135
 00:07:00,245 --> 00:07:03,425
-R. And they would be a sequence.
+And they would be a sequence.
 136
 00:07:03,425 --> 00:07:07,775
-How would be the derivative C of
+How would be the derivative c of
 137
 00:07:07,775 --> 00:07:10,340
-R four by R be
+r followed by r be
 138
 00:07:10,340 --> 00:07:13,265
-defined where we would
+defined? Well we would
 look up the definition.
 139
 00:07:13,265 --> 00:07:15,470
 And it would say that's
-the complicated case
+the complicated case,
 140
 00:07:15,470 --> 00:07:16,760
-d sequence or
+the sequence.
 141
 00:07:16,760 --> 00:07:21,875
-if null a bowl of R,
+If nullable of r,
 142
 00:07:21,875 --> 00:07:25,250
-Then the most complicated case.
+then the more complicated case,
 143
 00:07:25,250 --> 00:07:28,225
-Else, That's the easy
+else, that's the easy
-case that would be
+case, that would be
 144
 00:07:28,225 --> 00:07:32,660
-derivative of c of R four
+derivative of c of r, followed
 145
 00:07:32,660 --> 00:07:35,540
-by R. And then I
+by r. And then I just have to copy
-just have to copy
 146
 00:07:35,540 --> 00:07:40,775
-that derivative of C
+that derivative of c
-of four by r here.
+of r followed by r here.
 147
 00:07:40,775 --> 00:07:43,130
 But in this case I have also
 the alternative derivative
 of c of r. And from that,
 149
 00:07:51,145 --> 00:07:55,030
-it looks like we can
+it looks like we can't
 do much better than
 150
 00:07:55,030 --> 00:07:58,390
-that unless we do
+that, unless we do
 151
 00:07:58,390 --> 00:08:02,560
 a little bit of magic and the
-magic to do with this case.
+magic has to do with this case.
 152
 00:08:02,560 --> 00:08:07,420
 So let me look at this
 case a bit more closely.
 00:08:16,945 --> 00:08:18,550
 And this was defined as
 157
 00:08:18,550 --> 00:08:20,680
-this sequence work
+this sequence regular
-expression R followed
+expression r followed by r.
 158
 00:08:20,680 --> 00:08:23,080
-by r. And the question was,
+And the question was,
 159
 00:08:23,080 --> 00:08:26,365
 can we somehow make sense
 out of this derivative
 where we have to build the
 derivative of a sequence.
 161
 00:08:30,370 --> 00:08:33,020
-So features the definition.
+So if we just unfold the definition,
 162
 00:08:33,020 --> 00:08:36,050
-We would ask if
+we would ask if
 the r is nullable,
 163
 00:08:36,050 --> 00:08:39,095
 In this case, we return
 00:08:39,095 --> 00:08:40,640
 And if it's not nullable,
 165
 00:08:40,640 --> 00:08:44,135
-It is just this
+it is just this
-record expression.
+regular expression.
 166
 00:08:44,135 --> 00:08:49,550
 Now my claim is that
 this whole if condition
 decide in which branch we are.
 173
 00:09:08,330 --> 00:09:10,580
 We don't have to
-calculate your now,
+calculate nullable,
 174
 00:09:10,580 --> 00:09:13,880
-but we can just replace
+we can just replace
 it by this expression.
 175
 00:09:13,880 --> 00:09:16,670
 So if we can
 substantiate that claim,
 176
 00:09:16,670 --> 00:09:19,860
 that will be definitely
-good file algorithm.
+good our algorithm.
 177
 00:09:20,140 --> 00:09:22,775
 And to substantiate that,
 record expression here.
 179
 00:09:26,795 --> 00:09:31,100
 And notice that this record
-expression the only be
+expression will only be
 180
 00:09:31,100 --> 00:09:35,780
 called or only be generated
 if r is nullable.
 00:09:35,780 --> 00:09:38,075
 So in any other case,
 182
 00:09:38,075 --> 00:09:40,060
-I will actually not go into it
+I will actually not go into
 183
 00:09:40,060 --> 00:09:43,850
 that if branch and would
 be in the other one.
 So if we are in this if branch,
 185
 00:09:45,260 --> 00:09:47,705
 we definitely know
-that R is nullable.
+that r is nullable.
 186
 00:09:47,705 --> 00:09:52,955
-Okay? Okay, so here's
+Okay, so here's
 our regular expression.
 187
 00:09:52,955 --> 00:09:55,940
 And we know it's nullable.
 Let's see what we can do.
 192
 00:10:05,945 --> 00:10:10,160
 So the first thing
-actually is we multiplying
+actually is we're multiplying
 193
 00:10:10,160 --> 00:10:16,595
 this right hand side of the
-alternative is times one.
+alternative with times 1.
 194
 00:10:16,595 --> 00:10:19,700
 We can do that
 because this does not
 195
 00:10:19,700 --> 00:10:23,090
 change which strings this
-work expression can match.
+regular expression can match.
 196
 00:10:23,090 --> 00:10:25,685
 Remember we even had it
-as a simplification row,
+as a simplification rule,
 197
 00:10:25,685 --> 00:10:27,425
-just in this case B,
+just in this case we
 198
 00:10:27,425 --> 00:10:29,705
 don't apply it as a
-simplification will
+simplification rule,
 199
 00:10:29,705 --> 00:10:31,310
 actually make this
-work expression
+regular expression
 200
 00:10:31,310 --> 00:10:32,720
 a bit more complicated.
 201
 00:10:32,720 --> 00:10:34,910
-But times one doesn't make
+But times 1 doesn't make
 202
 00:10:34,910 --> 00:10:37,820
 a difference because it
-means the end of the string,
+means at the end of a string,
 203
 00:10:37,820 --> 00:10:40,070
 we still want to match
 the empty string.
 you will notice that this
 factor derivative of
 207
 00:10:48,410 --> 00:10:51,860
-stuff are exactly the
+r are exactly the
 same as that one.
 208
 00:10:51,860 --> 00:10:54,650
 And in between is a plus.
 And I'm inside the parentheses
 is left with that.
 213
 00:11:06,320 --> 00:11:09,245
-So now I have r plus one.
+So now I have r + 1.
 214
 00:11:09,245 --> 00:11:13,055
 Usually we cannot
-simplify r plus one.
+simplify r + 1.
 215
 00:11:13,055 --> 00:11:15,530
-If it had been R
+If it had been r + 0, then yes,
-plus 0, then yes,
 216
 00:11:15,530 --> 00:11:18,665
-we could have got rid of the CRO.
+we could have got rid of the 0.
 217
 00:11:18,665 --> 00:11:21,590
-Plus one often
+But this + 1 often
 makes a difference,
 218
 00:11:21,590 --> 00:11:22,970
 but not in our case.
 219
 00:11:22,970 --> 00:11:25,940
 Remember, we know that
-this R is nullable,
+this r is nullable,
 220
 00:11:25,940 --> 00:11:29,840
 so on its own can already
 match the empty string.
 00:11:35,300 --> 00:11:37,070
 Okay, and so now we have
 224
 00:11:37,070 --> 00:11:40,535
-a much simpler wound
+a much simpler equivalent
-reg expression.
+regular expression.
 225
 00:11:40,535 --> 00:11:44,285
 And this actually helps a
-lot for our if condition.
+lot for our if-condition.
 226
 00:11:44,285 --> 00:11:46,925
 Look, this was the
-original if condition
+original if-condition
 227
 00:11:46,925 --> 00:11:50,270
-and this is direct expression
+and this is the regular expression
-h. We just simplified.
+we just simplified.
 228
 00:11:50,270 --> 00:11:53,105
 If we replace it with this one,
 the if condition is actually
 231
 00:11:59,510 --> 00:12:02,750
 pointless because you
-check if it's null above,
+check if it's nullable,
 232
 00:12:02,750 --> 00:12:05,060
-we return this reg
+we return this regular
 expression or it's
 233
 00:12:05,060 --> 00:12:08,210
 not nullable and we
 So let's take stock
 what we have so far.
 240
 00:12:24,170 --> 00:12:26,915
-So we know India CEO case,
+So we know in the 0-case,
 241
 00:12:26,915 --> 00:12:30,920
 the derivative needs
 to be defined as 0.
 242
 00:12:30,920 --> 00:12:33,095
-So because we define this
+Because we define this
 243
 00:12:33,095 --> 00:12:36,785
-and times as one,
+n-times as one,
 the derivative is 0.
 244
 00:12:36,785 --> 00:12:39,889
-For chest r, this will
+For just r, this will
 be the derivative.
 245
 00:12:39,889 --> 00:12:42,170
 And we can't do any
-better than that
+better than that.
 246
 00:12:42,170 --> 00:12:45,620
-for our followed by
+For r followed by r, as we
-RB just found out.
+just found out
 247
 00:12:45,620 --> 00:12:47,270
-Actually it is quite simple.
+actually it is quite simple
 248
 00:12:47,270 --> 00:12:51,410
-Reg expression is equivalent
+regular expression is equivalent
 to the derivative.
 249
 00:12:51,410 --> 00:12:53,870
 Now, we have to continue with
 00:12:56,090 --> 00:12:58,099
 now have three copies
 252
 00:12:58,099 --> 00:13:02,390
-of this or what should
+of this r. What should
 be the derivative?
 253
 00:13:02,390 --> 00:13:05,330
 Well, if you look very carefully
 00:13:16,400 --> 00:13:18,275
 we end up with this.
 258
 00:13:18,275 --> 00:13:21,290
-Because then what we have is.
+Because then what we have is this.
 259
 00:13:21,290 --> 00:13:25,370
 We can define our
-nullable for n times
+nullable for n-times
 260
 00:13:25,370 --> 00:13:31,025
-s. If any cross 0 then
+as if n = 0 then
-true as nullable.
+true, else nullable r.
 261
 00:13:31,025 --> 00:13:33,875
 And for the derivative,
 we can save if n is equal to 0,
 263
 00:13:37,190 --> 00:13:40,235
 then we return the
-Sierra reg expression.
+0 regular expression.
 264
 00:13:40,235 --> 00:13:43,295
 Otherwise, as you can see
 from this pattern here,
 265
 00:13:43,295 --> 00:13:50,735
 it would be derivative of
-c r four by r n minus one.
+c r followed by r{n-1}.
 266
 00:13:50,735 --> 00:13:54,770
 Okay? And the only
 267
 00:13:54,770 --> 00:13:56,330
-thing we have to make choice that
+thing we have to make csure is that
 268
 00:13:56,330 --> 00:13:58,175
 this pattern actually holds.
 00:14:00,470 --> 00:14:03,735
 the case for n equals three.
 271
 00:14:03,735 --> 00:14:07,810
-If we have a wreck expression R
+If we have a regular expression r
 272
 00:14:07,810 --> 00:14:09,820
 and it's followed
 by r and another r,
 We can just unfold
 again the definition.
 275
 00:14:14,245 --> 00:14:16,930
-So we would ask if I is nullable,
+So we would ask if r is nullable,
 276
 00:14:16,930 --> 00:14:19,765
 then we have this if branch.
 277
 00:14:19,765 --> 00:14:23,905
-And if i is not nullable
+And if r is not nullable,
-or we have this as branch.
+we have this else branch.
 278
 00:14:23,905 --> 00:14:27,010
 Okay? What can we do here?
 this one is just now
 280
 00:14:30,310 --> 00:14:34,510
 the derivative of two
-Rs, one after another.
+r's, one after another.
 281
 00:14:34,510 --> 00:14:37,330
 But this we just
 calculated a moment ago,
 So I can pull that
 out to be like that.
 287
 00:14:52,700 --> 00:14:57,380
-And I have now followed
+And I have now r followed
-by R plus R. Oh,
+by r plus r.
 288
 00:14:57,380 --> 00:14:59,030
-hey, man, now you probably
+But now you probably
 289
 00:14:59,030 --> 00:15:00,680
 remember how we did it earlier.
 in this reasoning.
 296
 00:15:18,995 --> 00:15:22,700
 We go in this if branch
-only if r is nullable,
+only if r is nullable.
 297
 00:15:22,700 --> 00:15:26,150
-so on its own can already
+So r on its own can already
 match the empty string.
 298
 00:15:26,150 --> 00:15:28,895
 So I don't need
 I can just get rid of it.
 300
 00:15:30,695 --> 00:15:33,140
 And so I now just have
-to rearrange the parent,
+to rearrange the parentheses
 301
 00:15:33,140 --> 00:15:35,450
-the thesis which we
+which we said we can also do.
-said we can also do.
 302
 00:15:35,450 --> 00:15:37,595
 So we have something like that.
 And here again, the
 same reasoning,
 304
 00:15:39,740 --> 00:15:41,975
-we have a if condition
+we have an if condition
 305
 00:15:41,975 --> 00:15:43,310
 where it doesn't
 really matter what
 And yes, now we can be
 pretty sure they'll
 310
 00:15:51,920 --> 00:15:55,310
-work for all the n times
+work for all the n-times
 regular expressions.
 311
 00:15:55,310 --> 00:15:57,860
-And leave that to
+And I leave
 the calculation for
 312
 00:15:57,860 --> 00:16:02,570
-maybe R to the four to you.
+maybe r to the four to you.
 313
 00:16:02,570 --> 00:16:04,490
 And the reason why I do it
 I'm now back in our
 implementation.
 318
 00:16:16,250 --> 00:16:20,660
-In this Reto, said We have
+In this re2.sc, we said we have
-this explicit constructor now
+this explicit constructor
 319
 00:16:20,660 --> 00:16:25,535
-for n times b can now fill
+for n-times. We can now fill
 in the cases for nullable.
 320
 00:16:25,535 --> 00:16:27,635
-So if we have R in times,
+So if we have r n-times,
 321
 00:16:27,635 --> 00:16:30,995
 if this n is equal to
 0, we return true.
 322
 00:16:30,995 --> 00:16:34,190
 Otherwise we have to test
-whether eyes nullable.
+whether r is nullable.
 323
 00:16:34,190 --> 00:16:37,565
-And in the derivative case, oi,
+And in the derivative case,
 324
 00:16:37,565 --> 00:16:40,339
 if this n is equal to 0,
 325
 00:16:40,339 --> 00:16:43,564
 the return this 0
-wreck expression.
+regular expression.
 326
 00:16:43,564 --> 00:16:46,700
 Otherwise we return the
 sequence of the derivative
 327
 00:16:46,700 --> 00:16:50,270
-of psi of r four by n times of r,
+of c of r followed by n times of r,
 328
 00:16:50,270 --> 00:16:54,545
-but n minus one times and
+but n minus one times, and
 everything else stays the same.
 329
 00:16:54,545 --> 00:16:56,510
 Here's the function for strings,
 00:16:56,510 --> 00:16:58,430
 derivative function for strings.
 331
 00:16:58,430 --> 00:17:01,595
-In the main mantra
+In the main matcher
-function as all the same.
+function is all the same.
 332
 00:17:01,595 --> 00:17:04,820
 We still require this
 definition because
 00:17:04,820 --> 00:17:06,050
 we haven't done anything about
 334
 00:17:06,050 --> 00:17:08,090
-the optional record
+the optional regular
 expression yet.
 335
 00:17:08,090 --> 00:17:10,670
-And we have now at this
+And we have now this
 336
 00:17:10,670 --> 00:17:13,250
-either warm and evil
+EVIL1 and EVIL2
-2-break expression.
+regular expression.
 337
 00:17:13,250 --> 00:17:15,290
 And let's test it. And let's be
 338
 00:17:15,290 --> 00:17:17,000
 a bit more ambitious.
-Be testing it.
+We're testing it with
 339
 00:17:17,000 --> 00:17:20,315
-The strings between 01000
+strings between 0 and 1000
 340
 00:17:20,315 --> 00:17:22,580
 and let's see what the time say.
 341
 00:17:22,580 --> 00:17:26,210
 I'm testing this again
-inside the ammonite rebel.
+inside the Ammonite REPL.
 342
 00:17:26,210 --> 00:17:30,180
 And you'll see it should
 be now much quicker.
 down also around 600.
 344
 00:17:34,640 --> 00:17:40,490
 700 needs two seconds,
-three seconds, 4800.
+three seconds for 800.
 345
 00:17:40,490 --> 00:17:43,940
-Let's see about it
+Let's see what it
-needs 4 thousand.
+needs for one thousand?
 346
 00:17:43,940 --> 00:17:47,435
 But you have to remember
-Ruby and Python.
+Ruby and Python
 347
 00:17:47,435 --> 00:17:51,530
-They needed half a
+needed half a
-minute to just 43 TAs.
+minute for just 30 a's.
 348
 00:17:51,530 --> 00:17:54,485
 We need a little bit
 more than six seconds,
 00:17:54,485 --> 00:17:57,110
 but we are processing a string of
 350
 00:17:57,110 --> 00:18:00,575
-1000 days so that success.
+1000 a's. So that success.
 351
 00:18:00,575 --> 00:18:04,775
-So this speed is also explained
+This speed is also explained
 if you look at the sizes.
 352
 00:18:04,775 --> 00:18:08,975
 Since we now have this explicit
-and times constructor,
+n-times constructor,
 353
 00:18:08,975 --> 00:18:11,930
 it doesn't really matter
 how big this n is.
 354
 00:18:11,930 --> 00:18:14,540
-This evil one reg
+This EVIL1 regular
 expression will always be
 355
 00:18:14,540 --> 00:18:17,195
-of this size seven,
+of this size seven, at
 the beginning.
 356
 00:18:17,195 --> 00:18:20,315
 And you can also see if you
 but much more moderately.
 359
 00:18:24,740 --> 00:18:28,100
 And let's try out this
-example, this 20 a.
+example with 20 a's.
 360
 00:18:28,100 --> 00:18:31,685
 So we build the derivative
-according to 20 character A's.
+according to 20 character a's.
 361
 00:18:31,685 --> 00:18:33,890
 In the earlier example,
 362
 00:18:33,890 --> 00:18:35,780
-we ended up this a
+we ended up with a
-wreck expression which
+regular expression that
 363
 00:18:35,780 --> 00:18:37,895
 had like 8 million plus nodes.
 00:18:37,895 --> 00:18:39,830
 And if we do this now,
 365
 00:18:39,830 --> 00:18:43,205
-then we just have a wreck
+then we just have a regular
 expression with 211 nodes.
 366
 00:18:43,205 --> 00:18:44,750
 And that is much smaller and
 all the calculations
 would be much quicker.
 368
 00:18:47,165 --> 00:18:49,550
-So yeah, there's
+So yeah, the Brzozowski
 369
 00:18:49,550 --> 00:18:52,205
-this push off CKY algorithm
+algorithm
-and this improvement.
+and with this improvement,
 370
 00:18:52,205 --> 00:18:54,890
-We're now running
+we're now running
 circles around Ruby and
 371
 00:18:54,890 --> 00:18:58,445
 Python because they're just
 for just 30 a's.
 374
 00:19:02,975 --> 00:19:05,930
 We now can do something
-like thousand a's.
+like thousand a's
 375
 00:19:05,930 --> 00:19:07,580
-And in reasonable time.
+in a reasonable time.
 376
 00:19:07,580 --> 00:19:09,740
 I think this must be
 timing I obtained with
 Because remember we
 had something like
 379
 00:19:14,210 --> 00:19:16,670
-six seconds here, it says 15.
+six seconds. Here it says 15.
 380
 00:19:16,670 --> 00:19:18,080
-So you always have to take
+You always have to take
 381
 00:19:18,080 --> 00:19:20,885
 these times with
 the pinch of salt.
 but it's clear we are
 much, much better.
 384
 00:19:25,100 --> 00:19:27,065
-So we have worked a lot,
+We have worked a lot,
 385
 00:19:27,065 --> 00:19:30,720
 but we also got something
 for it in return.

changeset 773	260e330f7466
parent 772	3bf3f5bb067e