Elementary Implementations

Loading...

Del curso dictado por Princeton University

Algorithms, Part I

4815 calificaciones

Princeton University

Algorithms, Part I

4815 calificaciones

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.

De la lección

Elementary Symbol Tables

We define an API for symbol tables (also known as associative arrays, maps, or dictionaries) and describe two elementary implementations using a sorted array (binary search) and an unordered list (sequential search). When the keys are Comparable, we define an extended API that includes the additional methods min, max floor, ceiling, rank, and select. To develop an efficient implementation of this API, we study the binary search tree data structure and analyze its performance.

Symbol Table API21:30

Elementary Implementations9:03

Ordered Operations6:26

Binary Search Trees19:57

Ordered Operations in BSTs10:31

Deletion in BSTs9:53

Conoce a los instructores

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

Next we'll look at some elementary symbol table implementations.

These are so simple that we won't go in too much detail, but

still it's worthwhile to take a look at them to set the stage for

the more advanced implementations we'll consider next.

Well, one thing we could do is maintain a linked list.

We could keep it in order or keep it unordered.

This version keeps it unordered.

So we're going to have nodes in the linked list that have key value pairs.

They have every key in the symbol table and a value associated with that key.

For search, we have to, since it's unordered,

scan through the whole list to find a match, a key that's there.

For insert, I would also have to scan through all keys to find

the place to update a value, if it's a value that's already there.

And if there's no match, we could add it to the front.

So here's our simple client for traces,

so if we associate S with zero, we just had it.

That's our one node linked list that's got that information.

Associate E with 1, that's not there, so we just add it to the beginning

of list A with 2 R, with 3C, with 4 H, with 5 and so forth.

So now when we associate E with 6,

we have to search through the list to see if there's an E.

And in this case, there is.

And then we just update that value.

That's the associative array abstraction.

It's possible to implement symbol tables that allow multiple values with

the same key and so forth.

And that leads to different types of clients,

different types of implementations.

We're going to stick to this associative array abstraction and

no duplicate keys in the symbol table,

because it both simplifies implementations and leads to simpler client code.

Okay, X7 is a new value.

A8, we found A in there and update the value 8.

And then, M9 and P10, L11 are all not there and they go at the beginning.

And then the last one changes the value at E, again, 12.

So implementing this is a simple example

of linked list processing, a slight modification of our stack and queue code.

And we will skip the details.

And just note that what's the cost of implementing this,

well if there's been, if there are N things on the symbol table,

you have to for both search and insert, look all the way through.

And if everything's random,

then on average you only have to look halfway through for a successful search.

Well, you still have to insert.

Another issue is, for many clients, if the keys are ordered,

it's nice to be able to iterate through the symbol table and order.

And this one, by definition, doesn't provide that.

And this one just uses equals, so the keys don't have to be comparable for this.

It just uses equals.

So our challenge is to look for methods that

give us more efficient implementations for these search and insert operations.

And we've already looked at an algorithm that can do this, and

that's binary search.

So, for binary search, [COUGH] what

we're going to do is use an ordered array and

actually use parallel arrays, one for the keys and one for the values.

And the idea is to keep the array of keys in sorted order.

And then find the index associated with the key that we're searching for

using binary search.

And then use that index to get the value that's associated with that key,

that's stored in a parallel array.

And we looked at the binary search algorithm earlier in the course.

And so, for example, if these are the keys in our symbol table and

we're doing a search for the index where P is stored, we look at the middle.

P is bigger than L, so we look to the right.

Look in the middle of the right half.

P is less than R, so we look to the left.

Continue until we find P.

When we find P, we return its index and

we use that index to get us the value that we need.

Or another way to look at this is it implements the function,

how many keys are there that are less than K.

So, for example, for Q, that's an unsuccessful search.

You can figure out from the last index

when you don't find your element that you're seeking.

You can figure out the return value which is the number of

keys that are less than it.

So that's a trace of implementing binary search to find the rank of a key in

ordered array.

And again, for successful, you can use that rank to return the value.

And if it's unsuccessful,

you can use that rank to figure out where to insert the new key.

[COUGH] All right, so this is the code for

the get operation and this rank which is binary search.

So this is precisely the binary search code that we looked at before.

So let's look at the gap.

So if the whole table is empty, return null.

Otherwise, we call rank and

that gives us a number of keys less than the current key.

And so, that is where we look to check to see if that key is there.

If it's there, then we return the value with the same index and parallel array.

If it's not there, then we return null, saying the key's not there.

Now, the problem with binary search is, well, not necessarily the problem,

but the situation is that when it's time to insert a new element,

we have to move everything larger over one position, just like an insertion sort.

So if the table has A, E, R, and S, and we have to insert the value C,

then we have to move the E, R, and S over one position to put the C.

And then put the value associated with C.

You'll have to do the same thing in the vals array.

Move all the values associated with those keys over in one position and

put the associated value in.

So this is a trace of what would happen for our trace.

And again, every insertion involves

making a new position by moving all the larger keys over one position.

Do the same thing in the vals array.

[COUGH] And if it's changing the value

associated with a key that's already there, then it's just a matter of

finding where the key is and changing the value at that index.

So from that trace,

it's pretty easy to see what's involved for the code.

And we'll skip that code and

just take a look at the comparison between this elementary implementation for

symbol tables with the sequential search in an unordered list.

So, one thing is we're using a different key interface.

We're taking advantage of the fact that the keys are comparable

to give us an efficient search.

We can do search in worst case, in average case, in time proportional to log N.

That's what binary search provides for us.

And this is a fine data structure for symbol tables where there is,

[COUGH] that are relatively static,

where the values don't change much, and most of the operations are search.

It's hard to beat binary search.

On the other hand, in a dynamic situation where there are a lot of inserts,

this method is going to be problematic, because the cost of its insert is linear.

It's proportional to N over 2.

If you have a huge number of operations and

every one of them is proportional to the symbol table size,

then you're just not going to be able to support huge numbers of keys.

What we want is sufficient implementations of both search and insert.

Those are elementary implementations.

Next, we'll look at more advanced ones.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2019 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play