1

00:00:06,020 --> 00:00:09,945

They come back after

this disappointment

2

00:00:09,945 --> 00:00:14,115

and case of over promising

and under achieving.

3

00:00:14,115 --> 00:00:17,295

Let's have a look whether

we can recover from that.

4

00:00:17,295 --> 00:00:20,535

So here's one problem.

5

00:00:20,535 --> 00:00:23,790

Then we looked at this end

times vk expression and

6

00:00:23,790 --> 00:00:27,330

be able to represent

that directly.

7

00:00:27,330 --> 00:00:31,275

We had two represented as a

sequence record expression.

8

00:00:31,275 --> 00:00:32,850

So we expanded it.

9

00:00:32,850 --> 00:00:36,510

So times one would be just a,

10

00:00:36,510 --> 00:00:40,595

t, times two would

be a, and so on.

11

00:00:40,595 --> 00:00:43,535

And so you can see if

you go already to 13,

12

00:00:43,535 --> 00:00:47,960

N equals 13, the record

expression becomes quite large.

13

00:00:47,960 --> 00:00:52,865

And now the functions

nullable and also derivative.

14

00:00:52,865 --> 00:00:56,360

They need to traverse

this reg expression.

15

00:00:56,360 --> 00:00:59,060

Remember this tree in sometimes

16

00:00:59,060 --> 00:01:01,820

they have to traverse

that even several times.

17

00:01:01,820 --> 00:01:04,535

So that will slow

down the algorithm.

18

00:01:04,535 --> 00:01:08,150

And in particular, because

our first reg expression was

19

00:01:08,150 --> 00:01:11,840

actually not just a bot

a plus one. So b hat.

20

00:01:11,840 --> 00:01:14,330

In the case of 13,

we had a plus one,

21

00:01:14,330 --> 00:01:17,330

a plus one a plus born 13 times.

22

00:01:17,330 --> 00:01:20,150

And this reg

expression just grows,

23

00:01:20,150 --> 00:01:25,475

stay in number n. Just to

show you this also encode,

24

00:01:25,475 --> 00:01:28,115

I'm Stern, This File rewarm

25

00:01:28,115 --> 00:01:30,920

and D and I have a size function.

26

00:01:30,920 --> 00:01:33,140

The size function takes

a regular expression as

27

00:01:33,140 --> 00:01:36,215

argument and produces in teacher.

28

00:01:36,215 --> 00:01:39,980

And essentially it takes

this rec expression scene as

29

00:01:39,980 --> 00:01:44,045

a tree and count how many

nodes are in this tree.

30

00:01:44,045 --> 00:01:49,490

And so if I take this even

one reg expression, this one,

31

00:01:49,490 --> 00:01:52,160

and increase now this n. So you

32

00:01:52,160 --> 00:01:54,680

can already see

for any cross one,

33

00:01:54,680 --> 00:01:56,540

the size of this

record expression is

34

00:01:56,540 --> 00:01:59,615

five and you see it

slowly increases.

35

00:01:59,615 --> 00:02:02,150

And this 20 n equals 20.

36

00:02:02,150 --> 00:02:07,100

The size of this record

expression is SMOW already a 119.

37

00:02:07,100 --> 00:02:10,145

So now the interesting

line as this one.

38

00:02:10,145 --> 00:02:13,295

Remember it when we

built the derivative,

39

00:02:13,295 --> 00:02:17,150

very often parts of a reg

expression gets copied.

40

00:02:17,150 --> 00:02:19,280

So if you have like EVA,

41

00:02:19,280 --> 00:02:22,325

one of 2019 nodes,

42

00:02:22,325 --> 00:02:25,475

now this will be often copied.

43

00:02:25,475 --> 00:02:31,475

And we want to see what's the

resulting tree look like,

44

00:02:31,475 --> 00:02:32,780

how many nodes it has.

45

00:02:32,780 --> 00:02:34,985

So I take here either one of 20

46

00:02:34,985 --> 00:02:38,405

and the derivative

according to 20 a's.

47

00:02:38,405 --> 00:02:41,820

And just have a look

what the size is.

48

00:02:43,210 --> 00:02:45,680

Okay, that takes away.

49

00:02:45,680 --> 00:02:48,410

You see now this rec expression,

50

00:02:48,410 --> 00:02:52,280

the derivative has already

8 million plus nodes.

51

00:02:52,280 --> 00:02:55,400

And now nullable and

derivative have to

52

00:02:55,400 --> 00:02:58,430

traverse these trees with

a million plus nodes.

53

00:02:58,430 --> 00:03:01,400

So it's no wonder

that this is slow.

54

00:03:01,400 --> 00:03:03,860

The first thing we

can try to mitigate

55

00:03:03,860 --> 00:03:06,350

this explosion problem is to

56

00:03:06,350 --> 00:03:09,050

have an explicit and

times reg expression.

57

00:03:09,050 --> 00:03:11,600

So instead of expanding

58

00:03:11,600 --> 00:03:13,415

it to the sequence

reg expression,

59

00:03:13,415 --> 00:03:17,510

let's just have a single

wreck expression and times,

60

00:03:17,510 --> 00:03:20,540

which takes an expression and

61

00:03:20,540 --> 00:03:24,470

a number and keeps that

regular expression Small.

62

00:03:24,470 --> 00:03:27,095

I'm here in the fire V2,

63

00:03:27,095 --> 00:03:29,090

which is also on Keats.

64

00:03:29,090 --> 00:03:32,570

And the only change I made

is I added explicitly

65

00:03:32,570 --> 00:03:33,860

a wrecker expression for

66

00:03:33,860 --> 00:03:36,770

N times the optional

reg expression.

67

00:03:36,770 --> 00:03:39,920

Very leaf out at the

moment because this a

68

00:03:39,920 --> 00:03:41,975

optional is represented as

69

00:03:41,975 --> 00:03:44,645

a plus one and doesn't

explain too much.

70

00:03:44,645 --> 00:03:47,375

The really the culprit

is this n times.

71

00:03:47,375 --> 00:03:51,095

And instead of expanding

it n times, which has,

72

00:03:51,095 --> 00:03:54,275

take here a wreck expression

and a natural number,

73

00:03:54,275 --> 00:03:56,960

which says how many times

it should be repeated.

74

00:03:56,960 --> 00:03:59,165

And in this week we

can keep it small.

75

00:03:59,165 --> 00:04:01,370

But by adding that

reg expression,

76

00:04:01,370 --> 00:04:05,150

we now have to think about

cases for nullable and

77

00:04:05,150 --> 00:04:07,340

derivative so that we have

78

00:04:07,340 --> 00:04:10,205

to now calculate next

what they look like.

79

00:04:10,205 --> 00:04:14,060

We can actually

calculate what the rule

80

00:04:14,060 --> 00:04:17,525

for nullable should be from

how we defined it earlier.

81

00:04:17,525 --> 00:04:19,580

Remember, if you have

a regular expression,

82

00:04:19,580 --> 00:04:21,980

R and B take in

times of this are,

83

00:04:21,980 --> 00:04:25,220

then indicates if n equals 0,

84

00:04:25,220 --> 00:04:28,130

we find that as the

one reg expression.

85

00:04:28,130 --> 00:04:30,380

If n equals one,

86

00:04:30,380 --> 00:04:32,495

it will be just a

single copy of on.

87

00:04:32,495 --> 00:04:33,725

If n equals two,

88

00:04:33,725 --> 00:04:35,270

it will be two copies.

89

00:04:35,270 --> 00:04:39,260

Sequence if three, we have

three copies and so on.

90

00:04:39,260 --> 00:04:41,390

Now we have to

somehow characterize

91

00:04:41,390 --> 00:04:44,285

when these cases all nullable.

92

00:04:44,285 --> 00:04:47,810

Well, if n equals 0,

93

00:04:47,810 --> 00:04:49,850

then this will be defined as one,

94

00:04:49,850 --> 00:04:52,100

so one can match

the empty string.

95

00:04:52,100 --> 00:04:54,785

So that should be

definitely true.

96

00:04:54,785 --> 00:04:57,725

Okay, if any cross one,

97

00:04:57,725 --> 00:05:00,470

when can this reg expression

match the empty string?

98

00:05:00,470 --> 00:05:02,000

So vent should be nullable.

99

00:05:02,000 --> 00:05:07,535

Well, if nullable of our holes,

100

00:05:07,535 --> 00:05:09,860

okay, so if I can match

the empty string,

101

00:05:09,860 --> 00:05:12,110

then we can match

the empty string.

102

00:05:12,110 --> 00:05:14,870

When can this regular expression

match the empty string?

103

00:05:14,870 --> 00:05:16,265

So these are now two copies of

104

00:05:16,265 --> 00:05:20,690

our well-posed copies need

to match the empty string.

105

00:05:20,690 --> 00:05:22,820

So again, we have to ask

106

00:05:22,820 --> 00:05:25,774

both of them need to be nullable.

107

00:05:25,774 --> 00:05:28,520

Ok? Similarly, in the third case,

108

00:05:28,520 --> 00:05:30,710

all three copies need to be

109

00:05:30,710 --> 00:05:33,230

able to match the empty

string. Men, is that the case?

110

00:05:33,230 --> 00:05:38,360

Well, if nullable of

our holes and so on.

111

00:05:38,360 --> 00:05:48,754

So we can actually define that

if n equals 0, then true.

112

00:05:48,754 --> 00:05:56,045

Else we have to ask with

nullable of our holes.

113

00:05:56,045 --> 00:05:58,550

So that will be the clause we

114

00:05:58,550 --> 00:06:01,625

have to implement for

n times and nullable.