Практика Shadowing: 2. Data Structures and Dynamic Arrays - Изучайте разговорный английский по видео

Выберите режим практики

Каждый режим открывает полноэкранную комнату практики.

666 предложений

Если предложения слишком короткие или длинные, нажмите Edit, чтобы их изменить.

Good morning.

Welcome to 006

Introduction to Algorithms lecture two.

I am Eric DeMaine and I love algorithms.

Are you with me?

Yeah.

Today, we're not doing algorithms.

No, we're doing data structures.

It's OK.

There's lots of algorithms in each data structure.

It's like multiple algorithms for free.

We're going to talk about sequences and sets and linked lists and dynamic arrays.

Fairly simple data structures today.

This is the beginning of several data structures we'll be talking about in the next few lectures.

But before we actually start with one, let me tell you slash remind you of the idea, the difference between an interface,

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.

These are useful distinctions.

The idea is that an interface says what you want to do.

A data structure says how you do it.

So you might call this a specification.

And in the context of data structures, we're trying to store some data.

So the interface will specify what data you can store,

whereas the data structure will give you an actual representation and tell you how to store it.

This is pretty boring.

Just storing data is really easy you just throw it in a file or something.

What makes it interesting is having operations on that data.

So in the interface, you specify what the operations do,

what operations are supported, and in some sense, what they mean.

And the data structure actually gives you algorithms.

This is where the algorithms come in for how to support those operations.

All right.

So in this class, we're going to focus on two main interfaces.

and various special cases of them.

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.

So last class, Jason talked about problems and defined what a problem was versus algorithmic solutions to the problem.

And this is the analogous notion for data structures, where we want to maintain some data according to various operations.

So the same problem can be solved by many different data structures.

And we're going to see that.

And different data structures are going to have different advantages.

They might support some operations faster than others.

And depending on what you actually use those data structures for, you choose the right data structure.

But you can maintain the same interface.

We're going to think about two data structures.

One is called a set and one is called a sequence.

These are highly loaded terms.

Set means something to a mathematician.

It means something else to a Python programmer.

Sequence, similarly.

I guess there's not a Python sequence data type built in.

The idea is we want to store n things.

The things will be fairly arbitrary.

Think of them as integers or strings.

And on the one hand, we care about their values.

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.

And on the other hand, we care about representing a particular sequence that we care about.

Maybe we want to represent the numbers 5, 2, 9, 7 in that order and store that in Python.

You could store that in a list, for example.

And it will keep track of that order.

And this is the first item, the second item, the last item.

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,

but we're going to be actually solving sequences today.

And in the next several lectures, we'll be bouncing back and forth between these.

They're closely related, pretty abstract at the moment.

On the other hand, we're going to have two main

Let's call them data structure tools or approaches.

One is arrays, and the other is pointers,

pointer -based or linked data structures.

You may have seen these.

They're used a lot in programming, of course.

But we're going to see both of these today.

I'll come back to this sort of highlight in a moment.

Let's jump into the sequence interface, which I conveniently have part of here.

There's a few different levels of sequences that we might care about.

I'm going to start with the static sequence interface.

This is where the number of items doesn't change, though the actual items might.

So here we have n items.

I'm going to label them x0 to xn minus 1, as in Python.

So the number of items is n.

And the operations I want to support are build, length, iteration, get, and set.

So what do these do?

Build is how you get started.

To build a data structure in this interface, you call build of x.

Exactly how you specify x isn't too important, but the idea is I give you some items in some order.

In Python, this would be an iterable.

I'm going to want to also know its length.

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.

So that's how you build one of these.

Because somehow we have to specify n to this data structure, because n is not going to be allowed to change.

I'm going to give you a length method.

These methods are the object -oriented way of thinking of operations that your interface supports.

So length will just return this fixed value n.

Iter sequence, this is the sense in which we want to maintain the order.

I want to be able to output x0 through xn minus 1 in the sequence order,

in that specified order that they were built in or that it was changed to.

So this is going to iterate through all the items.

So it's going to take at least linear time to output that.

But more interesting is we can dynamically access anywhere in the middle of the sequence.

We can get the ith item XI, given the value I, and we can change XI to a given new item.

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.

Скачать приложение

Всё для свободной речи

ИИ-оценка произношенияОценка каждой фразы

Практика IPAОсвойте каждый звук

СловарьСоберите свой словарный запас

Игра со словамиУчитесь играя

Сканировать QR

Download on theApp Store Get it onGoogle Play

Тот же канал

FOR YOU

Лексика и советы по произношению к этому уроку

Этот урок разговорной практики построен на видео «2. Data Structures and Dynamic Arrays». Чаще всего повторяются слова: array, size, insert, constant, item. В этом видео 666 предложений и 6917 слов для шедоуинга. Речь длится 49:57. Говорящий держит ровный темп — около 138 слов в минуту, удобный для шедоуинга. 82% слов входят в 3000 самых частых слов английского языка; остальные стоит разобрать перед занятием.

Ключевая лексика этого видео

15 слов из видео, которые стоит выучить, с произношением и значением:

Слово	Произношение	Значение
array существительное	/əˈɹeɪ/	убо́р, наря́д
insert глагол	/ɪnˈsɝt/	вставля́ть, вста́вить
sequence существительное	/ˈsiː.kwəns/	после́довательность, ряд
static прилагательное	/ˈstæt.ɪk/	стати́чный
linear прилагательное	/ˈlɪn.i.əɹ/	лине́йный
delete глагол	/dɪˈliːt/	удаля́ть, удали́ть
pointer существительное	/ˈpɔɪn.təɹ/	ука́зка
dynamic прилагательное	/daɪˈnæm.ɪk/	динами́чный
interface существительное	/ˈɪn(t)ɚˌfeɪs/	интерфе́йс
algorithm существительное	/ˈælɡəɹɪðm̩/	алгори́тм
solve глагол	/sɒlv/	реша́ть, реши́ть
node существительное	/noʊd/	утолще́ние, наро́ст
implement глагол	/ˈɪmpləmənt/	выполня́ть, осуществля́ть
lecture существительное	/ˈlɛk.t͡ʃə/	ле́кция, уро́к
element существительное	/ˈɛləmənt/	элеме́нт, звено́

Фразовые глаголы, которые вы услышите

Слово	Значение
throw away глагол	выбра́сывать, вы́бросить
go over глагол	хорошо́ принима́ться

Фразы, которые стоит повторять

Короткие законченные фразы из видео, которые пригодятся в повседневном разговоре:

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?

Грамматика в этом видео

Конструкции, которые говорящий использует чаще всего, с точными словами из видео:

Конструкция	В видео
Условные предложения if + предложение, will/would + глагол — условие и его результат	If you were a mathematician, you would say
Пассивный залог be + причастие прошедшего времени — важно, что происходит, а не кто это делает	are supported · can be solved · is called
Придаточные определительные who / which + предложение — уточнение о человеке или предмете	arrays, which is · ram, which is · consecutive, which means
Present Perfect have/has + причастие прошедшего времени — прошлое действие, важное сейчас	We've taken · we've just seen · we've seen

Произношение, на которое стоит обратить внимание

Говорящий использует 165 сокращённых и редуцированных форм, например we're, I'm, don't. Произносите их коротко, так, как слышите.

Звуки «th»: algorithm /ˈælɡəɹɪðm̩/, bother /ˈbɑðɚ/, theta /ˈθiːtə/, arithmetic /æɹɪθˈmɛtɪk/, mathematician /ˌmæθ.(ə.)məˈtɪʃ.ən/
Звуки «sh» и «zh»: allocation /ˌæl.əˈkeɪ.ʃən/, notion /ˈnoʊʃən/, efficient /ɪˈfɪʃənt/, representation /ˌɹɛp.ɹə.zɛnˈteɪ.ʃən/, assumption /əˈsʌm(p).ʃ(ə)n/
Длинные слова — следите за ударением: 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/

Звуки, трудные для русскоязычных:

/w/ — губы округлены, это не /v/: sequence /ˈsiː.kwəns/, whereas /(h)wɛɹˈæz/, straightforward /ˌstɹeɪtˈfɔː(ɹ)wə(ɹ)d/, afterwards /ˈæf.tɚ.wɚdz/, equally /ˈiːkwəli/
/h/ — лёгкий выдох, а не русское «х»: whereas /(h)wɛɹˈæz/, hash /ˈhæʃ/, helpful /ˈhɛlp.fl̩/, wherever /(h)wɛɹˈɛvɚ/, highlight /ˈhaɪˌlaɪt/
Звонкие согласные в конце слова — не оглушайте их: solve /sɒlv/, node /noʊd/, whereas /(h)wɛɹˈæz/, analyze /ˈæn.əˌlaɪz/, remind /ɹəˈmaɪnd/

Как заниматься с этим видео

Прослушайте всё видео один раз молча и выпишите незнакомые слова.
Повторяйте предложение за предложением на обычной скорости, пока ваш ритм не совпадёт с ритмом говорящего.
Запишите себя и сравните с оригиналом, обращая внимание на такие слова, как array, insert, sequence.

Что такое техника Shadowing?

Shadowing — это научно обоснованная техника изучения языка, изначально разработанная для подготовки профессиональных переводчиков и популяризированная полиглотом доктором Александром Аргуэльесом. Метод прост, но эффективен: вы слушаете аудио на английском от носителей языка и немедленно повторяете вслух — как тень, следующая за говорящим с задержкой в 1–2 секунды. В отличие от пассивного прослушивания или грамматических упражнений, Shadowing заставляет мозг и мышцы рта одновременно обрабатывать и воспроизводить реальные речевые паттерны. Исследования показывают, что это значительно улучшает точность произношения, интонацию, ритм, связную речь, понимание на слух и беглость речи — что делает его одним из самых эффективных методов для подготовки к IELTS Speaking и реального общения на английском.

Техника шедоуинга: читать полное пошаговое руководство →

Практика Shadowing: 2. Data Structures and Dynamic Arrays - Изучайте разговорный английский по видео

Выберите режим практики

Скачать приложение

Тот же канал

11. Introduction to Machine Learning

Lec 1 | MIT 18.06 Linear Algebra, Spring 2005

Independence, Basis, and Dimension

Big Picture: Derivatives

Lec 1: Introduction to Principles of Microeconomics and Supply & Demand

Рекомендуемое видео

Stack Data Structure In STL | C++ Tutorial

Microservices with Databases can be challenging...

Sec Growth DataScience staff meeting Sep 14 2022

what is a database index?

Differential equations, a tourist's guide | DE1

Distributed Systems 1.1: Introduction

1 7 What is Information

Anatomy & Physiology: The Ultimate Beginner's Guide | Dr. Bee's Tutorials

Heaps in 3 minutes — Intro

Database Sharding! Designing Data-Intensive Applications chapter 6

LTEC 782: Design-Based Research in Education (Session 01)

Лексика и советы по произношению к этому уроку

Ключевая лексика этого видео

Фразовые глаголы, которые вы услышите

Фразы, которые стоит повторять

Грамматика в этом видео

Произношение, на которое стоит обратить внимание

Как заниматься с этим видео

Что такое техника Shadowing?