Memory

Loading...

Do curso por Princeton University

Algorithms, Part I

4601 classificações

Princeton University

Algorithms, Part I

4601 classificações

This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers elementary data structures, sorting, and searching algorithms. Part II focuses on graph- and string-processing algorithms. All the features of this course are available for free. It does not offer a certificate upon completion.

Na lição

Analysis of Algorithms

The basis of our approach for analyzing the performance of algorithms is the scientific method. We begin by performing computational experiments to measure the running times of our programs. We use these measurements to develop hypotheses about performance. Next, we create mathematical models to explain their behavior. Finally, we consider analyzing the memory usage of our Java programs.

Analysis of Algorithms Introduction8:15

Observations10:06

Mathematical Models12:48

Order-of-Growth Classifications14:39

Theory of Algorithms11:35

Conheça os instrutores

Kevin Wayne
Phillip Y. Goldman '86 Senior Lecturer
Computer Science
Robert Sedgewick
William O. Baker *39 Professor of Computer Science
Computer Science

So far we've be talking about running time,

now we have to talk about the memory requirements of our programs as well.

While the basics are we want to know how many bits the program use or

bytes, 8 bytes at a time.

And actually we'll be talking in terms of millions of bytes or billions of bytes.

And actually surprisingly there is a controversy about even these basic

definitions.

Computer scientist think of a million bits as 2 to the 20th and

a billion is 2 to the 30th because that's the number of possible things that you

can fit into the 30 bytes and everything is consistent with our calculations.

Other scientists stick to one million and one billion for lot of reasons.

I will usually use a 2 to the 20th to mean a megabyte.

Now on old computers for many years use the 32 bytes machine so

that pointers were four bytes.

Just in recent years, we've mostly switched to a model where machines

are 64 bits, and pointers are 8 bytes.

That allows us to address much more memory, but pointers use much more space.

And actually, this transition caused a lot of problems initially,

because programs were using way more space than people thought they should.

You're not going to have to go through this kind of transition the way that we

did because 64-bits is definitely enough to address anything that you might

need to address.

Two to the 64th is really a huge number.

So in terms of bytes we have to start out with typical memory usage.

Now again this is very dependent on machine and implementation but

these numbers are reasonable and are found on typical implementations.

So a boolean, it would be nice if a boolean just took a bit, because it's just

true or false, but actually usually we have to count for a byte for a boolean.

One byte is a byte, character nowadays is 2 bytes, 16 bit characters.

Not that long ago, we used 8 bits for chars.

Integer, a regular int is 4.

Bytes or 32 bits and float is also 4 bytes, long int is 8 and a double is 8.

Usually we use doubles for a floating point and ints for

integers in most applications.

So that's for primitive types.

And then for arrays there is a certain amount of overhead for making an array and

then if there's N items it's whatever the cost of the primitive type times N.

So, in array of doubles is say 8N + 24.

And two-dimensional array.

Then well, we can go ahead and compute the exact thing,

but now it's time to use the tilde notation.

Even for arrays, we could say a double is tilde 8N, for one-dimensional.

For two-dimensional, two-dimensional array of doubles is tilde 8 M N.

And there's extra terms for the overhead but for

large M and N that's going to be pretty accurate.

So that's our basic usage for primitive types and

arrays in a typical job implementation.

Now a lot of our programs use objects like Linklys and so forth, so

we also have to factor in object overhead.

The cost of reference and also there's padding built-in in typical

implementations to make it so that each object has to use a multiple of 8 bytes.

So for example if you had a date object that had three int instance variables,

then that object would take a total of 32 bytes each int takes 4 bytes.

Object overhead is 16 bytes.

I need 4 bytes for padding, so it's a total of 32 bytes.

So, and the other one that often comes up is a string.

And a string is a little bit more complicated than an array but

the typical implementation of a string in Java has a reference

out to an array of characters and then it's got int values for

offset, count and hash value and then some padding.

And adding it all together.

The [COUGH] cost of a string is about two N plus 64 bytes.

So these are the basics that we need to analyze

the memory usage for a typical Java program.

So for data type value, if it's a primitive type it's 4 for an int,

8 for a double and so forth.

If it's a reference it's going to be 8 bytes, that's what a pointer takes.

Array, 24 bytes plus the memory for each entry, and an object, 16 bytes.

Plus the memory for the incidence variable plus if there's an inner class that's

another eight bytes as we talked about with nodes for linked lists, and

then there's the padding.

So then we have to think about who's responsible for

referenced objects In some cases.

And we'll take care of that when we get to these situations.

So as an example, a simple example of memory use analysis,

let's take a look at how much memory our WeightedQuickUnionUF

function from a few lectures ago uses as a function of N.

And there's only a couple of memory elements, and

each one of them are easily analyzed using the basics that we just gave.

It's an objects so the 16 bytes of object overhead.

There's two int arrays.

Each one of them have an array overhead

of 24 plus 4N for the N entries.

Each of the N entries takes four bytes.

And then there's four bytes for the count, and there's four bytes for the padding,

and if you add it all together.

It's 8N + 88 which tilde 8N.

Again, all that saying is when N is large all we are going to care about

in terms of analyzing the memory is that we've got [COUGH] two N integers.

Two arrays of size N, each one of which takes 4 bytes for

grand total of 8 N bytes.

Okay, so in summary, we really can figure out

how many times we have to turn the crank on modern computers.

We can do it with empirical analysis where we actually execute the programs to do

experiments and use assume power law, formulate hypothesis and make predictions.

But we can do more, we can do mathematical analysis where we can identify the most

costly operations, analyze the frequency of execution of those operations.

And using the tilde notation to simplify analysis,

we can actually explain the behavior, not just predict it.

And this is a fine example of the use of the scientific method to

understand artifacts that we're studying, algorithms.

Our mathematical models are usually independent of a particular

computer system and even applied to machines that are not yet built.

But we always validate our mathematical models by running experiments on real

machines, so that we can be confident when we're making predictions and

analyzing algorithms.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2019 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play