1

00:00:06,350 --> 00:00:10,305

Welcome come back. I

can hear you saying,

2

00:00:10,305 --> 00:00:12,000

yes, you tried it out on

3

00:00:12,000 --> 00:00:14,760

one example and you

were much better.

4

00:00:14,760 --> 00:00:17,415

But how about on other examples?

5

00:00:17,415 --> 00:00:21,265

Specifically, we had two

evil regular expressions.

6

00:00:21,265 --> 00:00:23,480

How about the other case?

7

00:00:23,480 --> 00:00:27,480

Well, let's have a look at

that other case in this video.

8

00:00:29,140 --> 00:00:32,705

So I'm back here

in this re2.sc file.

9

00:00:32,705 --> 00:00:35,180

And here's this test

case which run quite

10

00:00:35,180 --> 00:00:39,665

nicely for strings between 0 and 1000.

11

00:00:39,665 --> 00:00:42,725

Here is the other test case.

12

00:00:42,725 --> 00:00:44,090

I still run it only

13

00:00:44,090 --> 00:00:48,470

for relatively small

strings between 0 and 20.

14

00:00:48,470 --> 00:00:50,240

And let's see what it says.

15

00:00:50,240 --> 00:00:51,800

So I'm running the test in

16

00:00:51,800 --> 00:00:57,320

the Amoonite REPL and it 

doesn't look too bad.

17

00:00:57,320 --> 00:01:01,160

But this might be because

20 is not generous enough.

18

00:01:01,160 --> 00:01:03,620

So let's try it with 30.

19

00:01:03,620 --> 00:01:06,530

Let's run this test again.

20

00:01:06,530 --> 00:01:11,075

And 20 is quite okay.

21

00:01:11,075 --> 00:01:15,965

22, okay, that's now

almost ten times as much.

22

00:01:15,965 --> 00:01:18,995

And then the next

one would be 24.

23

00:01:18,995 --> 00:01:23,615

And we're waiting and waiting.

24

00:01:23,615 --> 00:01:26,410

And we are waiting.

25

00:01:26,410 --> 00:01:29,300

Actually, it isn't

calculated at all.

26

00:01:29,300 --> 00:01:31,399

It run out of memory.

27

00:01:31,399 --> 00:01:33,905

So here is something going on,

28

00:01:33,905 --> 00:01:37,640

which is definitely bad and we

have to have a look at that.

29

00:01:37,640 --> 00:01:40,640

It's always

instructive with

30

00:01:40,640 --> 00:01:43,460

this algorithm to

look at the sizes of

31

00:01:43,460 --> 00:01:45,695

the regular expressions

we calculate.

32

00:01:45,695 --> 00:01:49,625

The EVIL2 is this

a star, star b.

33

00:01:49,625 --> 00:01:51,800

So there's nothing we

can compress there.

34

00:01:51,800 --> 00:01:55,490

It has just stars and

sequences and nothing else.

35

00:01:55,490 --> 00:01:58,430

And so it's not that we

can play the same trick

36

00:01:58,430 --> 00:02:01,805

of trying to introduce

an explicit constructor.

37

00:02:01,805 --> 00:02:04,190

But now let's have a

look at the derivatives.

38

00:02:04,190 --> 00:02:05,600

As you can see here.

39

00:02:05,600 --> 00:02:08,420

If I take this EVIL2 regular

40

00:02:08,420 --> 00:02:09,935

expression and then build

41

00:02:09,935 --> 00:02:12,470

longer and

longer derivatives,

42

00:02:12,470 --> 00:02:14,090

you can see this grows.

43

00:02:14,090 --> 00:02:16,055

And as you see in this line,

44

00:02:16,055 --> 00:02:17,270

if I'm trying to take

45

00:02:17,270 --> 00:02:20,180

the derivative of a

quite large string,

46

00:02:20,180 --> 00:02:21,680

it is quite quick.

47

00:02:21,680 --> 00:02:26,870

But the size of the

regular expression,

48

00:02:26,870 --> 00:02:28,310

the number of nodes,

49

00:02:28,310 --> 00:02:30,815

is also like nearly

eight millions.

50

00:02:30,815 --> 00:02:33,845

And so even if that calculates

relatively quickly,

51

00:02:33,845 --> 00:02:37,865

that is the reason why at 24,

52

00:02:37,865 --> 00:02:39,560

it just runs out of memory.

53

00:02:39,560 --> 00:02:42,785

This regular expression

just grew too much.

54

00:02:42,785 --> 00:02:46,520

So we somehow need

to still compress

55

00:02:46,520 --> 00:02:49,655

this regular expression

and make it not

56

00:02:49,655 --> 00:02:52,700

grow so much when we

build the derivative.

57

00:02:52,700 --> 00:02:54,020

So we have to look at

58

00:02:54,020 --> 00:02:57,050

where does that grow

actually come from.

59

00:02:57,050 --> 00:03:00,170

Let's look at the

derivative operation

60

00:03:00,170 --> 00:03:01,895

again in more detail.

61

00:03:01,895 --> 00:03:03,740

When we introduced

it, we looked at

62

00:03:03,740 --> 00:03:06,560

this example of a

regulat expression r,

63

00:03:06,560 --> 00:03:11,465

which is a star of some

alternative and some sequence.

64

00:03:11,465 --> 00:03:13,130

And we can build now

65

00:03:13,130 --> 00:03:15,800

the derivative of this

r according to a,

66

00:03:15,800 --> 00:03:18,965

b, and c and see

what it calculates.

67

00:03:18,965 --> 00:03:21,935

And you see in case of a,

68

00:03:21,935 --> 00:03:26,570

it's like one times b plus

0 and then followed by r,

69

00:03:26,570 --> 00:03:29,015

which is this whole

regular expression again.

70

00:03:29,015 --> 00:03:30,935

So you can also see

71

00:03:30,935 --> 00:03:34,745

the derivative operation

introduces a lot of junk.

72

00:03:34,745 --> 00:03:38,165

This plus 0 isn't

really necessary.

73

00:03:38,165 --> 00:03:42,455

And this times 1 could

be also thrown away.

74

00:03:42,455 --> 00:03:43,685

So in the first case,

75

00:03:43,685 --> 00:03:48,110

actually we could just have

one times b is b plus 0,

76

00:03:48,110 --> 00:03:49,580

it still b,

77

00:03:49,580 --> 00:03:54,905

so it would be b followed by

r. And in this second case,

78

00:03:54,905 --> 00:03:57,515

0 times b, that will be just 0.

79

00:03:57,515 --> 00:03:59,270

Then 0 plus one is

80

00:03:59,270 --> 00:04:05,330

1 ... times r would be just

r. And in the last case,

81

00:04:05,330 --> 00:04:12,155

0 times b would be 0. 0 plus

0 is 0. 0 times r would be 0.

82

00:04:12,155 --> 00:04:17,540

Okay? So we could throw out

all these useless zeros and

83

00:04:17,540 --> 00:04:20,960

ones because actually

we have to throw

84

00:04:20,960 --> 00:04:24,845

them out because over time

they just accumulate.

85

00:04:24,845 --> 00:04:27,035

And then we build

the next derivative.

86

00:04:27,035 --> 00:04:31,130

And the 0s wouldn't go away by

building a new derivative.

87

00:04:31,130 --> 00:04:34,310

So we need to somehow

a mechanism to

88

00:04:34,310 --> 00:04:39,120

delete the junk from

these derivatives.

89

00:04:39,280 --> 00:04:41,900

But how to delete junk?

90

00:04:41,900 --> 00:04:43,370

We already know we have

91

00:04:43,370 --> 00:04:47,825

the simplification rules

which say like if r plus 0,

92

00:04:47,825 --> 00:04:53,000

I can just replace by

r and the other ones.

93

00:04:53,000 --> 00:04:55,760

And so what I now

need to do is in

94

00:04:55,760 --> 00:04:58,715

my algorithm when I

built the derivative,

95

00:04:58,715 --> 00:05:01,415

this might have

introduced some junk.

96

00:05:01,415 --> 00:05:02,960

And I now have to have

97

00:05:02,960 --> 00:05:06,590

essentially an additional function

98

00:05:06,590 --> 00:05:08,945

which deletes this junk again.

99

00:05:08,945 --> 00:05:10,490

And in doing so,

100

00:05:10,490 --> 00:05:13,340

keeps the regular expression,

101

00:05:13,340 --> 00:05:16,730

relatively small, because that

102

00:05:16,730 --> 00:05:19,535

is the Achilles' heel

of this algorithm.

103

00:05:19,535 --> 00:05:22,565

If this regular expression

grows too much,

104

00:05:22,565 --> 00:05:25,070

then all these functions

will slow down.

105

00:05:25,070 --> 00:05:26,360

So the purpose of

106

00:05:26,360 --> 00:05:30,455

the simplification function

is to after the derivative,

107

00:05:30,455 --> 00:05:33,080

compress again this

regular expression

108

00:05:33,080 --> 00:05:35,570

and then do the next derivative.

109

00:05:35,570 --> 00:05:39,815

So if we introduce that

additional functions simp,

110

00:05:39,815 --> 00:05:42,440

which essentially

just goes through

111

00:05:42,440 --> 00:05:46,040

this regular expression and

deletes all this junk,

112

00:05:46,040 --> 00:05:50,045

then we should be in a

much better position.

113

00:05:50,045 --> 00:05:52,490

As you can see on this slide,

114