List-based Mapping

Loading...

Do curso por University of California San Diego

Data Structures

1463 classificações

University of California San Diego

Data Structures

1463 classificações

Curso 2 de 6 em Specialization Data Structures and Algorithms

A good algorithm usually comes together with a set of good data structures that allow the algorithm to manipulate the data efficiently. In this course, we consider the common data structures that are used in various computational problems. You will learn how these data structures are implemented in different programming languages and will practice implementing them in our programming assignments. This will help you to understand what is going on inside a particular built-in implementation of a data structure and what to expect from it. You will also learn typical use cases for these data structures. A few examples of questions that we are going to cover in this class are the following: 1. What is a good strategy of resizing a dynamic array? 2. How priority queues are implemented in C++, Java, and Python? 3. How to implement a hash table so that the amortized running time of all operations is O(1) on average? 4. What are good strategies to keep a binary tree balanced? You will also learn how services like Dropbox manage to upload some large files instantly and to save a lot of storage space!

Na lição

Hash Tables

In this module you will learn about very powerful and widely used technique called hashing. Its applications include implementation of programming languages, file systems, pattern search, distributed key-value storage and many more. You will learn how to implement data structures to store and modify sets of objects and mappings from one type of objects to another one. You will see that naive implementations either consume huge amount of memory or are slow, and then you will learn to implement hash tables that use linear memory and work in O(1) on average! In the end, you will learn how hash functions are used in modern disrtibuted systems and how they are used to optimize storage of services like Dropbox, Google Drive and Yandex Disk!

Applications of Hashing2:37

Analysing Service Access Logs7:52

Direct Addressing7:21

List-based Mapping8:10

Hash Functions3:18

Chaining Scheme6:08

Chaining Implementation and Analysis5:59

Hash Tables6:27

Conheça os instrutores

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering

Hi, in this video we will study another approach to the IP addresses problem.

In the last video we understood that the direct addressing scheme sometimes

requires too much memory.

And why is that?

Because it tries to store something for

each possible IP address while we're only interested in the active IP addresses.

Those from which at least some user has accessed our service during the last hour.

So the first idea for improvement of the memory consumption

is let's just store the active IP's and nothing else.

Another idea is that if our error based approach from the last video has failed,

then lets try to use list instead of an error.

So let's store all the IP addresses which are active in a list.

Sorted by the time of access.

So that the first element in the list corresponds to the oldest access time

during the last hour, and the last element in the list corresponds to the latest,

newest access from some IP address to our service.

Let's jump from here right into the pseudo code, because it's pretty simple.

We're going to have our procedure update access list which takes in

the log file log.

It also takes in i which is the index of the first

log line which hasn't been processed yet.

And also it has input L which is the list and

instead of some abstract data structure see from the first videos and

instead of the area a from the direct addressing scheme.

We put parameter L which is a list into this procedure and

this is the list with active IP addresses.

So our code have to pass first deals with new lines and second deals with old lines.

We just go searching from the first unprocessed line.

And if we need to added to our list because it was processed

during the last hour, we just append it to the end of the list.

And now again, the last element of the list corresponds to the latest,

newest access from some IP address.

And note that in our list we will start not just the IP address but,

both IP address and the time of the axis.

And then we will go to the next element in the log file and go and go while we

still have some log lines which we need to add to the end of our list.

And then the second part we just look at the oldest event during the last hour,

which is corresponding to the first element of the list.

And if that is actually before the start of the last hour,

then we need to remove it from the list.

And so we just do L.Pop.

And we do that while the head of the list is still too old.

And when we stop, it means that all the elements in the list are actually

with time during the last hour.

Why is that?

Because the list is always kept in the order by increasing time of access.

When we add new log lines to the list.

We add only those which have time even more than last element of the list

currently, and we remove something from the list.

We remove the oldest entries.

So, all the entries are always sorted, and as soon as we removed everything from

the start which is too old, all the entries in the list are not too old.

They are made during the last hour.

So this is pretty simple and now we need to answer questions like, whether my IP

address was used during the last hour to access the service and how many times.

To answer the first one we just need to

find out whether there is an element in our list with the given IP address.

And that is done by find by ID, which is different from the standards

find procedure of the least by the fact that we search not by the whole object,

which is a log line, which contains both IP address and time.

But we search just by the first field, by the IP address.

So our list contains tuples of IP addresses and

times of access, and we only look by IP address.

But the implementation will be the same.

We'll just go from the head of the list to the end of the list, and

compare the IP field of the log lines with the IP address given as the input.

And if it coincides we will return this element,

otherwise we'll return that there is nothing with this IP address in the list.

And the reason we return some special [INAUDIBLE].

So then, in the AccessedLastHour, just compare the results with null.

If it's not null then this IP address is in the list, otherwise it's not.

And to count the number of times

our service was accessed from a particular IP address, we just need to

count the number of log lines in the list which have the same IP address.

And that can be done by procedure CountIP of the list which

again differs from the standard count procedure in the list by the fact that it

counts by the first field, not by the whole object which is a log line.

But it just goes from to the end of the list.

Compares the IP field with the given IP and if they coincide,

it increases the counter by 1.

And returns the counter in the end.

So this is all the implementation.

Now let's analyze it.

Let N be the number of currently active IPs,

then the memory consumption is bigger of N.

Because we only store the active IP addresses and the corresponding times

of X's, but the times of X's on the add constant memory per active IPs.

So it's all null linear in the number of active IPs which is much better than

the direct addressing scheme because it require an amount of memory

proportionally to the number of all possible IP addresses.

And here will only require amount memory proportional to the number of

currently active IP addresses.

What about running time?

We know the standards list procedures such as Append, Top and

Pop all working constant time and

that's why the UpdateAccessList works in constant time per log line.

Of course, any particular call to UpdateAccessList could take more than

constant number of operations if we need to add more new lines to the end of

the list or remove many many old lines from the start of the list.

But for each log line we will only append it at most once and

we will only removed from the beginning at most once.

So it's constant time per log line plus constant time per each call of

UpdateAccessList just to check whether we need to append something and

whether we need to remove something from the beginning.

But this amount of operations can be controlled by how

often do we actually call Update Access List.

What about answering the questions?

We know that Find By IP and

Count IP have to go through the whole list in the worst case and actually count.

IP has to go through the whole list all the time to find out how many

log lines have the same IP as the given one and so AccessLastHour and

AccessCountLastHour are both linear in the number of active IPs.

And that is actually now good because even without introducing

any additional data structures, we could just take the log file,

take the last line in it before the current time, and go back from it.

And just look through each log line and

compare its IP address with the IP address in the question.

And count how many times it occurs during the last hour and

just stop as soon as we go through the border of the last hour.

And that will take the same time without any additional data structure.

So this solution is not more clever than the trio approach.

So, we failed somewhat with direct addressing scheme and

we failed with this list based approach.

It is overall a failure?

Well no, in the next videos we'll combine the ideas from direct

addressing scheme with the list based approach.

And we'll come up with solution which is both good in terms of memory consumption

and is much faster than the trivial approach in terms of the running time.

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.

© 2018 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play