Luyện nói tiếng Anh bằng Shadowing qua video: 2. Data Structures and Dynamic Arrays
Chọn chế độ luyện tập
Mỗi chế độ mở một phòng luyện tập toàn màn hình.
666 câu
Nếu các câu quá ngắn hoặc quá dài, hãy bấm Edit để chỉnh sửa.
1
Good morning.
Chào buổi sáng.
2
Welcome to 006
Chào mừng bạn đến với 006
3
Introduction to Algorithms lecture two.
Bài giảng thứ hai môn Giới thiệu về Thuật toán.
4
I am Eric DeMaine and I love algorithms.
Tôi là Eric DeMaine và tôi yêu thích các thuật toán.
5
Are you with me?
Bạn có theo kịp tôi không?
6
Yeah.
Vâng.
7
Today, we're not doing algorithms.
Hôm nay chúng ta không học về thuật toán.
8
No, we're doing data structures.
Không, chúng tôi đang học về cấu trúc dữ liệu.
9
It's OK.
Không sao đâu.
10
There's lots of algorithms in each data structure.
Có rất nhiều thuật toán trong mỗi cấu trúc dữ liệu.
11
It's like multiple algorithms for free.
Giống như có nhiều thuật toán được cung cấp miễn phí vậy.
12
We're going to talk about sequences and sets and linked lists and dynamic arrays.
Chúng ta sẽ nói về dãy, tập hợp, danh sách liên kết và mảng động.
13
Fairly simple data structures today.
Hôm nay chúng ta sẽ tìm hiểu về các cấu trúc dữ liệu khá đơn giản.
14
This is the beginning of several data structures we'll be talking about in the next few lectures.
Đây là phần khởi đầu của một số cấu trúc dữ liệu mà chúng ta sẽ thảo luận trong các bài giảng tiếp theo.
15
But before we actually start with one, let me tell you slash remind you of the idea, the difference between an interface,
Nhưng trước khi chúng ta thực sự bắt đầu với một cái, hãy để tôi nói với bạn hay nhắc lại cho bạn về ý tưởng, sự khác biệt giữa một giao diện,
16
which you might call an API if you're a programmer, or an ADT if you're an ancient algorithms person like me, versus a data structure.
mà nếu bạn là lập trình viên thì có thể gọi đó là API, còn nếu bạn là một người làm thuật toán từ thời cổ đại như tôi thì sẽ gọi là ADT, trái ngược với cấu trúc dữ liệu.
17
These are useful distinctions.
Đây là những sự phân biệt hữu ích.
18
The idea is that an interface says what you want to do.
Ý tưởng là một giao diện sẽ mô tả những gì bạn muốn thực hiện.
19
A data structure says how you do it.
Cấu trúc dữ liệu quy định cách bạn thực hiện việc đó.
20
So you might call this a specification.
Vì vậy, bạn có thể gọi đây là một đặc tả kỹ thuật.
21
And in the context of data structures, we're trying to store some data.
Và trong ngữ cảnh của các cấu trúc dữ liệu, chúng ta đang cố gắng lưu trữ một số dữ liệu.
22
So the interface will specify what data you can store,
Vì vậy, giao diện sẽ quy định rõ loại dữ liệu nào bạn có thể lưu trữ.
23
whereas the data structure will give you an actual representation and tell you how to store it.
trong khi cấu trúc dữ liệu sẽ cung cấp cho bạn một biểu diễn thực tế và cho bạn biết cách lưu trữ nó.
24
This is pretty boring.
Cái này khá nhàm chán.
25
Just storing data is really easy you just throw it in a file or something.
Chỉ lưu trữ dữ liệu thì thực sự rất dễ, bạn chỉ cần bỏ vào một tệp hay thứ gì đó tương tự là được.
26
What makes it interesting is having operations on that data.
Điều khiến nó trở nên thú vị là việc thực hiện các thao tác trên dữ liệu đó.
27
So in the interface, you specify what the operations do,
Vì vậy, trong giao diện, bạn hãy chỉ định chức năng của từng thao tác.
28
what operations are supported, and in some sense, what they mean.
những phép toán nào được hỗ trợ, và theo một nghĩa nào đó, ý nghĩa của chúng là gì.
29
And the data structure actually gives you algorithms.
Và cấu trúc dữ liệu thực chất cung cấp cho bạn các thuật toán.
30
This is where the algorithms come in for how to support those operations.
Đây là lúc các thuật toán phát huy vai trò trong việc xác định cách hỗ trợ những hoạt động đó.
31
All right.
Được rồi.
32
So in this class, we're going to focus on two main interfaces.
Vì vậy, trong buổi học này, chúng ta sẽ tập trung vào hai giao diện chính.
33
and various special cases of them.
và các trường hợp đặc biệt khác nhau của chúng.
34
So the idea is to separate what you want to do versus how to do it, because you can think of this as a problem statement.
Vì vậy, ý tưởng là tách biệt giữa việc bạn muốn làm gì và cách để làm điều đó, bởi vì bạn có thể coi đây là một bản mô tả vấn đề.
35
So last class, Jason talked about problems and defined what a problem was versus algorithmic solutions to the problem.
Vậy là buổi học trước, Jason đã nói về các bài toán và định nghĩa bài toán là gì, phân biệt với các giải thuật giải bài toán đó.
36
And this is the analogous notion for data structures, where we want to maintain some data according to various operations.
Và đây là khái niệm tương tự đối với các cấu trúc dữ liệu, nơi chúng ta muốn duy trì một số dữ liệu nhất định theo các thao tác khác nhau.
37
So the same problem can be solved by many different data structures.
Vì vậy, cùng một bài toán có thể được giải bằng nhiều cấu trúc dữ liệu khác nhau.
38
And we're going to see that.
Và chúng ta sẽ thấy điều đó.
39
And different data structures are going to have different advantages.
Và các cấu trúc dữ liệu khác nhau sẽ có những ưu điểm khác nhau.
40
They might support some operations faster than others.
Chúng có thể hỗ trợ một số hoạt động nhanh hơn các hoạt động khác.
41
And depending on what you actually use those data structures for, you choose the right data structure.
42
But you can maintain the same interface.
43
We're going to think about two data structures.
44
One is called a set and one is called a sequence.
45
These are highly loaded terms.
46
Set means something to a mathematician.
47
It means something else to a Python programmer.
48
Sequence, similarly.
49
I guess there's not a Python sequence data type built in.
50
The idea is we want to store n things.
51
The things will be fairly arbitrary.
52
Think of them as integers or strings.
53
And on the one hand, we care about their values.
54
And maybe we want to maintain them in sorted order and be able to search for a given value, which we'll call a key.
55
And on the other hand, we care about representing a particular sequence that we care about.
56
Maybe we want to represent the numbers 5, 2, 9, 7 in that order and store that in Python.
57
You could store that in a list, for example.
58
And it will keep track of that order.
59
And this is the first item, the second item, the last item.
60
Today we're going to be focusing on this sequence data structure, although at the end I'll I'll mention the interface for sets,
61
but we're going to be actually solving sequences today.
62
And in the next several lectures, we'll be bouncing back and forth between these.
63
They're closely related, pretty abstract at the moment.
64
On the other hand, we're going to have two main
65
Let's call them data structure tools or approaches.
66
One is arrays, and the other is pointers,
67
pointer -based or linked data structures.
68
You may have seen these.
69
They're used a lot in programming, of course.
70
But we're going to see both of these today.
71
I'll come back to this sort of highlight in a moment.
72
Let's jump into the sequence interface, which I conveniently have part of here.
73
There's a few different levels of sequences that we might care about.
74
I'm going to start with the static sequence interface.
75
This is where the number of items doesn't change, though the actual items might.
76
So here we have n items.
77
I'm going to label them x0 to xn minus 1, as in Python.
78
So the number of items is n.
79
And the operations I want to support are build, length, iteration, get, and set.
80
So what do these do?
81
Build is how you get started.
82
To build a data structure in this interface, you call build of x.
83
Exactly how you specify x isn't too important, but the idea is I give you some items in some order.
84
In Python, this would be an iterable.
85
I'm going to want to also know its length.
86
And I want to make a new data structure of size n, a new static sequence of size n that has those items in that order.
87
So that's how you build one of these.
88
Because somehow we have to specify n to this data structure, because n is not going to be allowed to change.
89
I'm going to give you a length method.
90
These methods are the object -oriented way of thinking of operations that your interface supports.
91
So length will just return this fixed value n.
92
Iter sequence, this is the sense in which we want to maintain the order.
93
I want to be able to output x0 through xn minus 1 in the sequence order,
94
in that specified order that they were built in or that it was changed to.
95
So this is going to iterate through all the items.
96
So it's going to take at least linear time to output that.
97
But more interesting is we can dynamically access anywhere in the middle of the sequence.
98
We can get the ith item XI, given the value I, and we can change XI to a given new item.
99
So that's called get at and set at.
100
Pretty straightforward.
101
This should remind you very closely of something, a data structure.
102
So this is an interface.
103
This is something I might want to solve.
104
But what is the obvious data structure that solves this problem?
105
Yeah?
106
A list.
107
In Python, it's called a list.
108
I prefer to call it an array, but to each their own.
109
We're going to use lists.
110
Lists could mean many things.
111
But the solution to this interface problem,
112
the natural solution, is what I'll call a static array.
113
Jason mentioned these in lecture one.
114
It's a little tricky because there are no static arrays in Python.
115
There are only dynamic arrays, which is something we will get to.
116
But I want to talk about what is a static array really.
117
And this relates to our notion of our model of computation, which Jason also talked about, which we call the word RAM.
118
So the idea in word RAM is that your memory is an array of W This is a bit circular.
119
I'm going to define an array in terms of the word ram, which is defined in terms of arrays.
120
But I think you know the idea.
121
So we have a big memory, which goes off to infinity maybe.
122
It's divided into words.
123
Each word here is w bits long.
124
This is word 0, word 1, word 2.
125
And you can access this array randomly, random access memory.
126
So I can give you the number 5 and get 0, 1, 2, 3, 4, 5, the fifth word in this RAM.
127
That's how actual memories work.
128
You can access any of them equally quickly.
129
Okay, so that's memory.
130
And so what we want to do is when we say an array,
131
we want this to be a consecutive chunk of memory.
132
Let me get a color.
133
here.
134
So let's say I have an array of size 4, and it lives here.
135
Jason can't spell, but I can't count, so I think that's 4.
136
So the array starts here, and it ends over here.
137
It's of size 4.
138
And it's consecutive, which means if I want to access the array at index i,
139
then this is the same thing as accessing my memory array at position wherever the array starts,
140
which I'll call the address of the array.
141
In Python, this is ID of array plus i.
142
This is just simple offset arithmetic.
143
If I want to know the zeroth item of the array, it's right here where it starts.
144
The first item is one after that.
145
The second item is one after that.
146
So as long as I store my array consecutively in memory, I can access the array in constant time.
147
I can do get at
148
and set at as quickly as I can randomly access the memory and get a value or set a value, which we're assuming is constant time.
149
So array access is constant time.
150
OK, this is what allows a static array to actually solve this problem in constant time
151
per get at and set at operation.
152
So this may seem simple, but we're really going to need this model
153
and really rely on this model increasingly as we get to more interesting data structures.
154
This is the first time we're actually needing it.
155
Let's see.
156
Length is also constant time.
157
We're just going to store that number n along with its address.
158
And build is going to take linear time.
159
Iteration will take linear time.
160
OK, pretty straightforward.
161
I guess one thing here when defining build, I need to introduce a little bit more of our model of computation,
162
which which is, how do you create an array in the beginning?
163
I claim I could do it in linear time, and that's just part of the model.
164
So this is called the memory allocation model.
165
There are a few possible choices here,
166
but the cleanest one is just to assume that you can allocate an array of size n in theta n time.
167
So it takes linear time to make an array of size n.
168
You could imagine this being constant.
169
It doesn't really matter much, but it does take work.
170
And in particular, if you just allocate some chunk of memory, you have no idea whether it's initialized.
171
So initializing that array to zeros will cost linear time.
172
It won't really matter, constant versus linear, but a nice side effect of this model is that space, if you're just allocating arrays,
173
the amount of space you use is at most the amount of time you use, or I guess big O of that.
174
So that's a nice feature.
175
It's pretty weird if you imagine,
176
it's unrealistic to imagine you can allocate an array that's infinite size and then just use a few items out of it.
177
That won't be, give you a good data structure.
178
So, we'll assume it costs to allocate memory.
179
And okay, great.
180
We solved the static sequence problem.
181
Very simple, kind of boring.
182
These are optimal running times.
183
Now, let's make it interesting.
184
Make sure I didn't miss anything.
185
And talk about, oh, there is one thing I want to talk about in the word RAM.
186
A side effect of this assumption that array access should take constant time
187
and that accessing these positions in my memory should take constant time is that we need to assume
188
w is at least log n. or so.
189
W, remember, is the machine word size.
190
In real computers, this is currently 64 or 256 and some bizarre instructions.
191
But we don't usually think of the machine as getting bigger over time.
192
But you should think of the machine as getting bigger over time.
193
This is a statement that says the word size has to grow with n.
194
It might grow faster than log n, but it has to grow at least as fast as log n.
195
Why do I say that?
196
Because if I have n things that I'm dealing with, n here is the problem size, maybe it's the array I'm trying to store, whatever.
197
If I'm having to deal with n things in my memory, at the very least, I need to be able to address them.
198
I should be able to say, give me the ith one and represent that number i in a word.
199
Otherwise, because the machine is designed to only work with w bit words in constant time,
200
if I want to be able to access the ith word in constant time,
201
I need a word size that's at least log n just to address the n things in my input.
202
So this is a totally reasonable assumption.
203
It may seem weird because you think of a real machine as having constant size, but a real machine has constant size RAM also.
204
My machine has 24 gigs of RAM or whatever.
205
That laptop has eight, but you don't think of that as changing over time.
206
But of course, if you wanted to process a larger input, you would buy more RAM.
207
So eventually, when our Ns get really, really big, we're going to have to increase W just so we can address that RAM.
208
That's the intuition here.
209
But this is a way to bridge reality, which are fixed machines, with theory.
210
In algorithms, we care about scalability for very large n.
211
We want to know what that growth function is and ignore the lead constant factor.
212
That's what asymptotic notation is all about.
213
And for that, we need a notion of word size also changing in this asymptotic way.
214
All right.
215
That will be more important next week when we talk about hashing and why hashing is a reasonable thing to do.
216
But let's move on to dynamic sequences, which is where things get interesting.
217
So I have the update here.
218
So we start with static sequences.
219
So all of these operations are still something we want to support in the dynamic sequence, but we add two dynamic operations,
220
operations, somewhat controversial operations, so exciting.
221
I want to be able to insert in the middle of my sequence,
222
and I want to be able to delete from the middle of my sequence.
223
So here's my sequence, which I'm going to think of in a picture.
224
I'm going to draw it as an array, but it's stored however it's stored, we don't know.
225
This is an interface, not an implementation.
226
So we have x0, x1, x2, x3.
227
And let's say I insert at position 2.
228
So position 2 is here.
229
So I come in with my new x.
230
And I would like x to be the new x2, but I don't want to lose any information.
231
If I did set at 2, then I would erase this and replace it with x.
232
But I wanted to insert at, which means all of these guys conceptually are going to shift over by 1 in terms of their indices.
233
So then I would get this picture that's one bigger.
234
And now I've got the new x.
235
I've got what was the old x2, which I hesitate to call x2 because that's its old name, not its new name.
236
I'm going to draw arrows to say these guys get copied over.
237
These ones are definitely unchanged.
238
Our new x2, which I'll call x2 prime, is x.
239
And this is x3 prime, x4 prime, so on.
240
I want to be careful here.
241
And of course, the new n prime is n plus 1.
242
I want to be careful about the labeling, because the key, what makes insert at interesting is that later when I call get at,
243
it's with the new indexing.
244
So previously, if I did get at at 2, I would get this value.
245
And afterwards, if I did get at at 2, I get the new value.
246
If I did get at it 3 down here, I would get the value that used to be x2.
247
That's maybe hard to track.
248
But this is a conceptually very useful thing to do, especially when you're inserting or deleting at the ends.
249
So we're going to define,
250
in particular, insert and delete first and last.
251
So these are sometimes given.
252
If you have an insert, it has an x.
253
If you do a delete, it has no argument.
254
So this means insert at the beginning of the array, which would be like adding it here.
255
And insert last means adding it on here.
256
So insert last doesn't change the indices of any of the old items.
257
That's a nice feature of insert last.
258
Insert first changes all of them.
259
They all get incremented by one.
260
And we're also interested in the similar things here.
261
We could do get first or last or set first or last,
262
which are the obvious special cases of get at and set at.
263
Now, these special cases are particularly interesting in an algorithms context.
264
If you were a mathematician, you would say, well, why do I even bother this?
265
This is just shorthand for a particular call to get or set.
266
But what makes it interesting from a data structure's perspective is that we care about algorithms for supporting these operations.
267
And maybe the algorithm for supporting get first or set first
268
or in particular insert first
269
or insert last might be more efficient maybe we can solve this problem better than we can solve insert at.
270
So while ideally we could solve the entire dynamic sequence interface constant time per operation, that's not actually possible.
271
You can prove that.
272
But special cases of it where we're just inserting and deleting from the end say, we can do that.
273
So that's why it's interesting to introduce special cases that we care about.
274
Cool.
275
That's the definition of the dynamic sequence interface.
276
Now, we're going to actually solve it.
277
So our first data structure for this is called linked lists.
278
We've taken probably, you've probably seen linked lists before at some point.
279
But the main new part here is we're going to actually analyze them
280
and see how efficiently they to implement all these operations we might care about.
281
So first review, what is a linked list?
282
We store our items in a bunch of nodes.
283
Each node has an item in it and a next field.
284
So you could think of these as class objects with two class variables, the item and the next pointer.
285
And we assemble those into this kind of structure where we store in the item fields,
286
we're going to store the actual values that we want to represent in our sequence, x0 through xn minus 1, in order.
287
And then we're going to use the next pointers to link these all together in that order.
288
So the next pointers are what actually give us the order.
289
And in addition, we're going to keep track of what's called the head of the list.
290
So the data structure is going to be represented by head.
291
If you wanted to, you could also store length.
292
So this could be the data structure itself.
293
And it's pointing to all of these types of data structures.
294
Notice we've just seen an array -based data structure, which is just a static array.
295
And we've seen a pointer -based data structure.
296
And we're relying on the fact that pointers can be stored in a single word,
297
which means we can dereference them and we can see what's on the other side of the pointer
298
in constant time in our word RAM model.
299
In reality, each of these nodes is stored somewhere in the array of the computer.
300
So maybe each one is two words long, so maybe the first node is here, maybe the second node is here, the third node is here.
301
They're in some arbitrary order.
302
We're using this fact that we can allocate an array of size as n in linear time.
303
In this case, we're going to have arrays of size 2.
304
We can just say, oh, please give me a new array of size 2.
305
And that will make us one of these nodes.
306
And then we're storing pointers.
307
Pointers are just indices into the giant memory array.
308
They're just, what is the address of this little array?
309
If you've ever wondered how pointers are implemented,
310
they're just numbers that say where in memory is this thing over here and in memory they're in arbitrary order.
311
This is really nice because it's easy to manipulate the order of a linked list without actually physically moving nodes around,
312
whereas arrays are problematic.
313
Maybe it's worth mentioning.
314
Let's start analyzing things.
315
So we care about these dynamic sequence operations.
316
And we could try to apply it to the static array data a structure,
317
or we could try to implement these operations in a static array.
318
It's possible, just not going to be very good.
319
And we can try to implement it with linked lists.
320
And it's also not going to be that great.
321
Let's go over here.
322
Our goal is the next data structure, which is dynamic arrays.
323
But linked lists and static arrays each have their advantages.
324
So let's first analyze dynamic sequence operations.
325
first on a static array, and then on a linked list.
326
So on a static array, I think you all see, if I try to insert at the beginning of the static array,
327
that's kind of the worst case.
328
If I insert first, then everybody has to shift over.
329
If I'm going to maintain this invariant, that the ith item in the array represents, I guess I didn't write it anywhere here,
330
maybe here, static array, we're going to maintain this invariant that a of i represents xi.
331
If I want to maintain that at all times, when I insert a new thing in the front,
332
because the indices of all the previous items change, I have to spend time to copy those over.
333
You can do it in linear time, but no better.
334
So static array, insert and delete anywhere,
335
cost theta n time.
336
Actually, for two reasons.
337
Reason number one is that if we're near the front, then we have to do shifting.
338
What about insert or delete the last element of an array? Is that any easier?
339
Because then if I insert the very last element, none of the indices change.
340
I'm just adding a new element.
341
So I don't have to do shifting.
342
So can I do insert and delete last in constant time in a static array?
343
Yeah.
344
No, because the size is constant.
345
No, because the size is constant.
346
So our model is that, remember, our allocation model is that we can allocate a static array array of size n,
347
but it's just a size n.
348
I can't just say, please make it bigger by one.
349
I need space to store this extra element.
350
And if you think about where things are in memory, when you call to this memory allocator, which is part of your operating system,
351
you say, please give me some, a chunk of memory, it's going to place them in various places in memory.
352
And some of them might be next to each other.
353
So if I try to grow this array by one, there might already be something there.
354
And that's not possible without first shifting.
355
So even though in the array I don't have to do any shifting, in memory I might have to do shifting.
356
And that's outside the model.
357
So we're going to stick to this model of just you can allocate memory.
358
You can also deallocate memory just to keep space usage small.
359
But the only way to get more space is to ask for a new array.
360
And that new array won't be contiguous to your old one. So question?
361
So how can you do a dynamic array with a static array?
362
What is a dynamic array will be the next topic.
363
So maybe we'll come back to that.
364
Yeah?
365
OK.
366
So in a static array, you're just not allowed to make it bigger.
367
And so you have to allocate a new array, which we say takes linear time.
368
Even if allocating the new array didn't take linear time, you have to copy all the elements over from the old array to the new one
369
then you can throw away the old one.
370
So just the copying from an array of size n to an array of size n plus 1, that will take linear time.
371
So static arrays are really bad for dynamic operations, no surprise.
372
But you could do them.
373
That's static array.
374
Now linked lists are going to be almost the opposite.
375
Well, almost.
376
So if we store the length, we can compute the length through the array very quickly.
377
We can insert and delete at the front really efficiently.
378
If I want to add a new item as a new first item, then what do I do?
379
I allocate a new node, which I'll call x.
380
So this is insert first of x.
381
I'll allocate a new array of size 2.
382
I'm going to change this head pointer.
383
Maybe I should do that later.
384
So I'm going to set the next pointer here to this one.
385
And then I'm going to change this head pointer to point to here.
386
And boom, now I've got a linked list.
387
We don't know anything about the order and memory of these lists.
388
We just care about the order that's represented implicitly by following the next pointers repeatedly.
389
So now I've got a new list that has x in front, and then x0, and then x1, and so on.
390
So insert and delete first, at least, are really efficient.
391
We won't get much more than that.
392
The linked list, insert and delete first are constant time. So that's cool.
393
However, everything else is going to be slow.
394
So if I want to get the 10th item in a linked list, I have to follow these pointers 10 times.
395
I go 0, 1, 2, 3, and so on.
396
Follow 10 next pointers, and I'll get the 10th item.
397
Accessing the ith item is going to take order i time.
398
So get and set at need i time,
399
which in the worst case is theta n.
400
So we have sort of complementary data structures here.
401
On the one hand, a static array can do constant time get at set at.
402
So it's very fast at the random access aspect because it's an array.
403
Linked lists are very bad at random access, but they're better at being dynamic.
404
We can insert and delete at the beginning at least in constant time.
405
Now, if we want to actually insert and delete at a particular position, that's still hard because we have to walk to that position.
406
Even inserting and deleting at the end of the list is hard, although that's fixable.
407
And maybe I'll leave that for problem session or problem set.
408
But an easy, so here's a small puzzle.
409
Suppose you wanted to solve get last efficiently in a linked list.
410
How would you solve that in constant time?
411
Yeah.
412
Doubly linked list is a good idea, but actually not the right answer.
413
That's an answer to the next question I might ask.
414
Yeah.
415
Store a pointer to the last element.
416
Store a pointer to the last element.
417
That's all we need here.
418
And often a doubly linked list has this.
419
They usually call this the tail, head and tail.
420
And if you always just store a pointer to the last list, this is what we call data structure augmentation,
421
where we add some extra information to the data structure.
422
We have to keep it up to date all the time.
423
So if we do an insert last or something,
424
insert last also becomes easy because I can just add a new node here and update the pointer here.
425
Delete last is trickier.
426
That's where you need a doubly linked list.
427
But whenever I add something to the end of this list, I have to update the tail pointer also.
428
As long as I maintain this, now suddenly get last is fast in constant time.
429
So linked lists are great if you're working on the ends, even dynamically.
430
Arrays are great if you're doing random access and nothing dynamic, nothing adding or deleting being at the ends or in the middle.
431
So our final goal for today is to get the best of both worlds with dynamic arrays.
432
We're going to try to get all the good running times of linked lists
433
and all the good running times of static arrays.
434
We won't get quite all of them, but most of them.
435
And in some sense, another way to describe what these introductory lectures are about is telling you about how
436
Python is implemented.
437
So what we're going to talk about next, dynamic arrays, I've alluded to many times,
438
but these These are what
439
Python calls lists.
440
So you don't have to implement a dynamic array by hand
441
because it's already built into many fancy new languages for free because they're so darn useful.
442
This lecture is about how these are actually implemented and why they're efficient.
443
And in recitation notes, you'll see how to actually implement them if all you had were static arrays,
444
but luckily we have dynamic arrays so we don't have to actually implement them.
445
But inside the Python interpreter, this is exactly what's happening.
446
Okay?
447
So the idea is to...
448
relax the constraint or the invariant,
449
whatever, that the size of the array we use equals n,
450
which is the number of items in the sequence.
451
Remember, in the sequence problem, we're supposed to represent n items.
452
With a static array, we allocate an array of size exactly n.
453
So let's relax that.
454
Let's not make it exactly n.
455
Let's make it roughly n.
456
How roughly?
457
You can think about for a while.
458
But from an algorithm's perspective, usually when we say roughly, we mean throw away constant factors.
459
And that turns out to be the right answer here.
460
It's not always the right answer.
461
But we're going to enforce that the size of the array I is theta n,
462
probably also greater than or equal to n.
463
0 .5 n would not be very helpful.
464
So it's going to be at least n.
465
And it's going to be, at most, some constant times n.
466
2n, 10n, 1 .1 times n.
467
Any of these constants will work.
468
I'm going to use 2n here, but there are lots of options.
469
And now, things almost work for free.
470
There's going to be one subtlety here.
471
And I'm going to focus on we're still going to maintain that the ith item of the array represents x i.
472
So this data structure, let me draw a picture.
473
So we've got an array of some size.
474
The first few items are used to store the sequence but then there's going to be some blank ones at the end.
475
Maybe we'll keep track of this.
476
So the data structure itself is going to have an array, and it's going to have a length, something like this.
477
So we're also going to keep track of the length.
478
So we know that the first length items are where their data is, and the remainder are just meaningless.
479
So now, if I want to go and do an insert last, What do I do?
480
I just go to A of length and set it to x.
481
And then I increment length.
482
Boom, easy, constant time.
483
Yeah.
484
How do you know you have enough room?
485
Indeed, I don't.
486
This was an incorrect algorithm.
487
But it's usually correct.
488
As long as I have extra space, this This is all I need to do for insert last.
489
But I'm also going to store the size of the array.
490
This is the actual, this whole thing is size and this part is length.
491
So length is always going to be less than or equal to size.
492
And so there's a problem if length equals size, then I don't have any space.
493
OK.
494
Just add to the end unless n equals size.
495
I'm using n and length for the same thing.
496
So length here is the same as n.
497
That's our actual number of things we're trying to represent. And size.
498
This is great.
499
This is the interface size.
500
This is what we're trying to represent.
501
And this is the representation size.
502
This is the size of my array.
503
These are the number of items I'm trying to store in that array.
504
This is the interface versus data structure.
505
Here's the interface.
506
Here's the data structure.
507
OK, cool.
508
What do I do in the case when n equals size?
509
I'm going to have to make my array bigger.
510
This should sound just like static arrays.
511
With static arrays, we made our array bigger every time we insert it, and that was this linear cost of allocation.
512
We're going to do that sometimes.
513
With static arrays, we had to do it every single time because size equaled n.
514
Now we have some flexibility.
515
We're only going to do it sometimes.
516
It's like cookies are sometimes food, apparently, according to modern cookie monster.
517
I don't understand.
518
But if n equals size,
519
we're going to allocate a new array. of size?
520
Any suggestions?
521
Bigger.
522
Bigger.
523
I like it.
524
Greater than size.
525
How much bigger?
526
Twice.
527
Five things.
528
Five things.
529
Size plus five?
530
Come on, Jason.
531
Trolling me.
532
All right, so there are a couple of natural choices here.
533
One is a constant factor larger.
534
You could use 1 .1 or 1 .01 or 2 or 5 or 10.
535
They'll all work.
536
Or you could use Jason's trolling answer of size plus a constant, like 5.
537
Why is this bad?
538
Yeah.
539
If you like score like six extra three items to that constant, you have to .
540
You'll have to do it again.
541
Again, you'll have to resize frequently. When?
542
Five steps later.
543
So in the original static array, we were reallocating every single time.
544
That's like n plus one.
545
If we do n plus five, that really doesn't change things if we ignore constant factors.
546
Now we'll have to spend linear time every five steps instead of linear time every one step.
547
That's still linear time per operation.
548
It's just we're changing the constant factor.
549
OK, whereas two times size, well, now we have to think a little bit harder here,
550
let's just think about the case where we're inserting at the end of an array.
551
So let's say we do n insert las from an empty array. When do we resize?
552
Well, at the beginning, I guess I didn't say what we do for an empty array.
553
Let's say size equals 1.
554
So we can insert one item for free.
555
As soon as we insert the second item, then we have to resize.
556
That seems bad.
557
Immediately, we have to resize.
558
Then we insert the third item.
559
Now let's draw a picture.
560
So we start with one item.
561
We fill it up.
562
Then we grow to size 2, because that's twice 1.
563
Then we fill it up.
564
Immediately, we have to resize again.
565
But now we start to get some benefit.
566
Now we have size 4.
567
And so we can insert two items before we have to resize.
568
And now we're size eight.
569
And we get to insert four items before we refill.
570
So this is going to resize.
571
And again, resizes are expensive, both because we have to pay to allocate the new array.
572
I drew it as just extending it.
573
But in fact, we're creating a whole new array.
574
And then we have to copy all of the items over.
575
So there's the allocation cost and then the copying cost.
576
So it's linear either way.
577
But we're going to resize at n equals 1, 2, 4, 8, 16.
578
You know this sequence.
579
All the powers of 2 because we're doubling.
580
That is exactly powers of 2.
581
So we pay a linear cost.
582
So this resize cost, the allocation and the copying, is going to be, it's linear each time.
583
So it's 1 plus 2 plus 4 plus 8 plus 16.
584
Really, I should write this as sum from i equals 1 to roughly log n.
585
Log base 2 of n is lg of 2 to the i.
586
If you want a terminus here, it's roughly n.
587
It's actually the previous power of 2 of n or something.
588
OK, but that won't matter.
589
That'll just affect things by a constant factor.
590
What is the sum of 2 to the i?
591
This is a geometric series.
592
Anyone know the answer?
593
Yeah?
594
2 to the top limit plus 1 minus 1.
595
Yeah, so this is the identity.
596
The sum of 2 to the i from i equals 1 to k is 2 to the k plus 1 minus 1.
597
So the plus 1 is upstairs, minus 1 is downstairs.
598
An easy way to remember this is if you think in binary, as we all should.
599
We're computer scientists.
600
2 to the i means you set the ith bit to 1.
601
So here is a bit string.
602
This is the ith bit.
603
This is 2 to the i.
604
The 0 is down here.
605
If I sum them all up, what that means is I'm putting ones here.
606
And if you think about what this means, this is up to k from 0.
607
Sorry, I should do 0 to be proper. If I write.
608
So that's the left -hand side.
609
The right -hand side is 2 to the k plus 1, which is a 1 here, and the rest 0's.
610
So if you know your binary arithmetic, if you add 1 to this, you get this.
611
Or if you subtract 1 from this, you get this.
612
This is why this identity holds.
613
Or the higher level thing is to say, oh, this is a geometric series.
614
So I know you should know this.
615
I'm telling you now.
616
Geometric series are dominated by the last term, the biggest term.
617
If you have any series you can identify as geometric, which means it's growing at least exponentially, then in terms of theta notation,
618
you can just look at the last term and put a theta around it, and you're done.
619
So this is theta of the last term, like 2 to the log n, which is theta n.
620
Cool.
621
Linear time.
622
Linear time for all of my operations.
623
I'm doing n operations here, and I spend linear total time to do all the resizing.
624
That's good.
625
That's like constant each, kind of.
626
The kind of is an important notion which we call amortization.
627
So I want to say an operation takes takes t of n amortized time if,
628
let's say, any k of those operations take,
629
at most, k times t of n time.
630
This is a little bit sloppy, but it would be good enough.
631
So the idea is here, if this works for n or k, to do n operations from an empty array here takes linear time,
632
which means I would call this constant amortized.
633
Amortized means a particular kind of averaging, averaging over the sequence of operations.
634
So while individual operations will be expensive, one near the end, when I have to resize the array,
635
is going to take linear time just for that one operation.
636
But most of the operations are cheap.
637
Most of them are constant.
638
So I can think of charging that high cost to all of the other operations that made it happen.
639
And so this is averaging over the operation sequence.
640
Once every insert last over there only takes constant time on average over the sequence of operations that we do.
641
And so it's almost constant.
642
It's not quite as good as constant worst case,
643
but it's almost as good and it's as good as you could hope to do in this dynamic array allocation model.
644
Let me put this into a table and you'll find these in the lecture notes also.
645
So we have on the top the main operations of sequence interface, which we will revisit in lecture seven.
646
We'll see some other data structures for this.
647
GetAt and SetAt in the first column, insert and delete first, insert and delete last, insert and delete at an arbitrary position.
648
So we've seen three data structures now.
649
Arrays, we're really good at GetAt, SetAt.
650
They took constant time.
651
That's the blue one.
652
We're remitting the thetas here.
653
All the other operations took linear time no matter where they were linked lists were really good at insert and delete first.
654
They took constant time, but everything else took linear time in the worst case.
655
These new dynamic arrays achieve get at and set at in constant time
656
because they maintain this invariant here that a of i equals xi.
657
So we can still do gets and set at quickly.
658
And we also just showed that insert last is is constant amortized.
659
Delete last, you don't have to resize the array.
660
You could just decrease length, and boom, you've deleted the last item.
661
It's not so satisfying, because if you insert n items and then delete n items, you'll still have an array of size theta n,
662
even though your current value of n is 0.
663
You can get around that with a little bit more trickery, which are described in the lecture notes.
664
But it's beyond the we're only going to do very simple amortized analysis in this class
665
To prove that that algorithm is also constant amortized, which it is, you'll see in 046 or you can find it in the CLRS book.
666
That's it for today.
Tải Ứng Dụng
Mọi thứ bạn cần để nói trôi chảy
Chấm điểm AIChấm từng câu nói
Luyện IPAThành thạo mọi âm
Từ vựngMở rộng vốn từ
Game Từ vựngHọc qua chơi
Cùng kênh
C12
11. Introduction to Machine Learning
Daily ConversationUniversity Students
C1Lec 1 | MIT 18.06 Linear Algebra, Spring 2005
TOEFL PrepCambridge Exam PrepUniversity Students
C28
Independence, Basis, and Dimension
University Students
C14
Big Picture: Derivatives
Cambridge Exam PrepUniversity Students
C1Lec 1: Introduction to Principles of Microeconomics and Supply & Demand
TOEFL PrepBusiness EnglishUniversity Students
FOR YOU
Video gợi ý
C11
199 câu
Stack Data Structure In STL | C++ Tutorial
Daily ConversationUniversity Students
C12
279 câu
Microservices with Databases can be challenging...
Daily ConversationUniversity StudentsWorking Adults
C11
398 câu
Sec Growth DataScience staff meeting Sep 14 2022
Daily ConversationUniversity StudentsWorking Adults
C13
68 câu
what is a database index?
Daily ConversationUniversity StudentsWorking Adults
C1287 câu
Differential equations, a tourist's guide | DE1
Daily ConversationUniversity Students
C11
154 câu
Distributed Systems 1.1: Introduction
Daily ConversationUniversity Students
C177 câu
1 7 What is Information
Daily ConversationUniversity Students
C1117 câu
Anatomy & Physiology: The Ultimate Beginner's Guide | Dr. Bee's Tutorials
Daily ConversationUniversity Students
![[TALK 13] Structure Prediction and Design using AlphaFold – Sami Chaaban](https://img.youtube.com/vi/my6uceci0S4/mqdefault.jpg)
C11
606 câu
[TALK 13] Structure Prediction and Design using AlphaFold – Sami Chaaban
Daily ConversationUniversity Students
C11
27 câu
You are wasting memory
Daily ConversationUniversity StudentsWorking Adults
C11
689 câu
Database Sharding! Designing Data-Intensive Applications chapter 6
Daily ConversationUniversity StudentsWorking Adults
Từ vựng và ghi chú luyện nói cho bài học này
Bài luyện nói này dựa trên video “2. Data Structures and Dynamic Arrays”. Những từ được nhắc lại nhiều nhất trong bài: array, size, insert, constant, item. Video này có 666 câu và 6917 từ để luyện shadowing. Phần lời nói dài 49:57. Người nói giữ tốc độ đều, khoảng 138 từ mỗi phút, vừa sức để nói đuổi theo. 82% số từ nằm trong 3.000 từ tiếng Anh thông dụng nhất; phần còn lại nên xem trước khi luyện.
Từ vựng quan trọng trong video
15 từ đáng học trong video, kèm phiên âm và nghĩa:
| Từ | Phiên âm | Nghĩa |
|---|---|---|
| insert động từ | /ɪnˈsɝt/ | chèn, nhét |
| sequence danh từ | /ˈsiː.kwəns/ | dãy |
| delete động từ | /dɪˈliːt/ | xóa, gạch |
| pointer danh từ | /ˈpɔɪn.təɹ/ | que chỉ |
| algorithm danh từ | /ˈælɡəɹɪðm̩/ | thuật toán |
| solve động từ | /sɒlv/ | giải quyết |
| node danh từ | /noʊd/ | gióng |
| implement động từ | /ˈɪmpləmənt/ | thực hiện, chấp hành |
| lecture danh từ | /ˈlɛk.t͡ʃə/ | bài giảng |
| element danh từ | /ˈɛləmənt/ | yếu tố |
| minus | /ˈmaɪ.nəs/ | trừ |
| versus | /ˈvɝsəs/ | đối, đối đầu |
| notion danh từ | /ˈnoʊʃən/ | khái niệm |
| tail danh từ | /ˈteɪ̯l/ | đuôi |
| boom động từ | /bum/ | nổ bùm, nổ đùng |
Cụm động từ bạn sẽ nghe
| Từ | Nghĩa |
|---|---|
| throw away động từ | vất, vứt |
Những câu đáng luyện lại
Các câu ngắn, trọn ý trong video mà bạn có thể dùng lại khi giao tiếp hằng ngày:
- Are you with me?
- Today, we're not doing algorithms.
- Why do I say that?
- How would you solve that in constant time?
- How do you know you have enough room?
Ngữ pháp trong video
Những cấu trúc người nói dùng nhiều nhất, kèm đúng cụm từ trong video:
| Cấu trúc | Trong video |
|---|---|
| Câu điều kiện if + mệnh đề, will/would + động từ — điều kiện và kết quả | If you were a mathematician, you would say |
| Câu bị động be + quá khứ phân từ — nhấn vào việc xảy ra, không phải người làm | are supported · can be solved · is called |
| Mệnh đề quan hệ who / which + mệnh đề — thêm thông tin về người hoặc vật | arrays, which is · ram, which is · consecutive, which means |
| Thì hiện tại hoàn thành have/has + quá khứ phân từ — việc đã xảy ra nhưng còn liên quan đến hiện tại | We've taken · we've just seen · we've seen |
Phát âm cần chú ý
Người nói dùng 165 dạng rút gọn, ví dụ we're, I'm, don't. Hãy nói theo dạng ngắn đúng như bạn nghe.
- Âm “th”: algorithm /ˈælɡəɹɪðm̩/, bother /ˈbɑðɚ/, theta /ˈθiːtə/, arithmetic /æɹɪθˈmɛtɪk/, mathematician /ˌmæθ.(ə.)məˈtɪʃ.ən/
- Âm “sh” và “zh”: allocation /ˌæl.əˈkeɪ.ʃən/, notion /ˈnoʊʃən/, efficient /ɪˈfɪʃənt/, representation /ˌɹɛp.ɹə.zɛnˈteɪ.ʃən/, assumption /əˈsʌm(p).ʃ(ə)n/
- Từ dài — đặt trọng âm cho đúng: allocation /ˌæl.əˈkeɪ.ʃən/, arbitrary /ˈɑː.bɪ.tɹə.ɹi/, geometric /ˌd͡ʒiː.əʊˈmɛt.ɹɪk/, representation /ˌɹɛp.ɹə.zɛnˈteɪ.ʃən/, consecutive /kənˈsɛkjʊtɪv/
Những âm người Việt thường gặp khó:
- Cụm phụ âm cuối — đọc đủ từng âm, đừng nuốt âm cuối: sequence /ˈsiː.kwəns/, solve /sɒlv/, implement /ˈɪmpləmənt/, element /ˈɛləmənt/, efficient /ɪˈfɪʃənt/
- Âm /tʃ/, /dʒ/ và /ʒ/ — tiếng Việt không có, đừng đọc thành “ch” hay “gi”: lecture /ˈlɛk.t͡ʃə/, geometric /ˌd͡ʒiː.əʊˈmɛt.ɹɪk/, chunk /t͡ʃʌŋk/, suggestion /səˈd͡ʒɛst.ʃən/, usage /ˈjuːsɪd͡ʒ/
- Âm /æ/ — mở miệng rộng hơn âm “e”: static /ˈstæt.ɪk/, dynamic /daɪˈnæm.ɪk/, algorithm /ˈælɡəɹɪðm̩/, allocation /ˌæl.əˈkeɪ.ʃən/, whereas /(h)wɛɹˈæz/
Cách luyện với video này
- Nghe hết video một lần, chưa cần nói, và ghi lại những từ bạn chưa biết.
- Nói đuổi từng câu ở tốc độ bình thường, lặp lại mỗi câu đến khi nhịp của bạn khớp với người nói.
- Ghi âm giọng mình rồi so với bản gốc, chú ý các từ như insert, sequence, delete.
Phương Pháp Shadowing Là Gì?
Shadowing là kỹ thuật học ngôn ngữ có cơ sở khoa học, ban đầu được phát triển cho chương trình đào tạo phiên dịch viên chuyên nghiệp và được phổ biến rộng rãi bởi nhà đa ngôn ngữ học Dr. Alexander Arguelles. Nguyên lý cốt lõi đơn giản nhưng cực kỳ hiệu quả: bạn nghe tiếng Anh của người bản xứ và lặp lại to ngay lập tức — như một "cái bóng" (shadow) đuổi theo người nói với độ trễ chỉ 1–2 giây. Khác với luyện ngữ pháp hay học từ vựng bị động, Shadowing buộc não bộ và cơ miệng phải đồng thời xử lý và tái tạo ngôn ngữ thực tế. Các nghiên cứu khoa học xác nhận phương pháp này cải thiện đáng kể phát âm, ngữ điệu, nhịp điệu, nối âm, kỹ năng nghe và độ lưu loát khi nói — đặc biệt hiệu quả cho người luyện IELTS Speaking và muốn giao tiếp tiếng Anh tự nhiên như người bản ngữ.