Video 2-5: §2.5 Symbol tables

0:00 Intro

0:03 so welcome back uh in this next subsection of our fundamental data structures unit still I will talk about symbol tables maybe the single most important abstract data type in my view because it's so versatile uh first of all a little wake-up question just because this is It's a metaphor that people often use uh you can replace printed dictionary with printed telephone book it's just that there are the chances are even Slimmer that we still have one at home I mean some of you are old enough to have seen one but and printed dictionaries I have seen some printed dictionaries still exists they're sometimes handy right in exams maybe you're not allowed to bring in devices uh and so I guess most of you have have used one it's not super relevant to the first bit but it'll come up we'll come back to this

0:16 Clicker Question

0:59 Symbol table ADT

1:04 the key notion here is the abstract data type of a symbol table now if you haven't heard about symbol tables you might still know what I'm talking about because it comes under at least four different names hold on that's five right I know it's four counting is hard if uh no it's four it's four slashes it's five counting is hard it's a symbol table sometimes called a dictionary in Python you call it dictionary that's the thing you put in curly braces and with the colon to represent mappings other languages called it a map Java specifically does that associative array is another name for the same thing and key Value Store maybe is more if you think about this as a database as a a bigger middleware system but it's really the same thing so what's what's a symbol table as every abstract data type it's defined by its operations and the key operation here is we can associate a key okay with a value and put that in the dictionary so we store a mapping that says when I ask you later with get when I just give you the key I want you to give me this value back that I associated with this key earlier or if there's uh if you call get with a

2:22 key that hasn't ever been put in the dictionary then the answer should be there is no such key a few other things you can delete Keys again and you can ask just uh instead of a lightweight of gets you can just ask if it's in there and get a yes no answer instead of retrieving the values usually the implementation of these two are usually the same uh and a few few other helpers as we've seen before now I might have said something like this before that whatever we discuss next is the is a very fundamental building block but I think this is the single most fundamental right this is uh is used everywhere because it's so useful uh there are many many places where you would like to assign things to names uh the oldest implement the oldest way is why this is called symbol table is because people use this to build compilers when a compiler or an interpreter like Java uh understands your program it has to know that there's a variable with a certain name and it has to remember where that's stored in memory and a few other things like its type for example in in some languages at least and a symbol table was was basically the key invention that made that possible that

3:39 that's why it still Bears this name but if you think about it you can use it in in many many places just to uh make make their code a little more higher level you often want to associate one thing to another uh physical dictionaries are one way where you see this in Real Worlds or in the physical world say uh you have the keys are just the words and then the value is is all the explanatory text or maybe just a single word in another language dictionaries come in in different forms right so the one shown here is uh it's just an English dictionary showing you pronunciation and the meaning and so on

4:24 okay um yeah I haven't I haven't made a programming language that is serious like not there's uh languages like excuse that's the real name brain and and other esoteric languages maybe they they are not so taken not to be taken too seriously apart from these all seriously used languages have some symbol table implementation

4:50 Symbol tables vs. mathematical functions

4:53 symbol tables are somewhat similar to what mathematicians would call a function or a mapping a function also has some domain and it has a a range and so it takes some value from the domain and Maps it to Something in the range that's very similar in spirit there are a few differences though um first of all uh symbol tables are always partial functions in in math lingo so it's fine for a simple table not to map every key to a value it can have a subset of the of the universe only whereas mathematical functions the default is you assume that there's a mapping from every possible element in the domain uh that's that's a minor thing uh this interface otherwise looks similar but mathematical functions don't change they are fixed value the whole function can be seen as one value one datum and so if you if you change the function by replacing the value it maps to for some of the the elements then it really becomes just a new function and in computer science we're thinking of this differently in data structures we're thinking of things as Dynamic objects that can change that's why we have update operations so in uh in this sense uh symbol tables are Dynamic functions functions where you can change the

6:11 mapping over time and there's mathematical functions they they're usually supposed to not not change they're immutable as always I'm asking you when you when you see a new thing we we want to do a symbol table how can you realize this what's the simplest thing you could think of the simplest thing I listed is just some unordered linked list now you might ask a linked list of what so that's that's another little caveat again as for heaps um where we or for for priority queues where we had the object and the priority uh here we have the key and the value but if you think about it we're really just interested in storing a combined object a pair of key and value a key value mapping or an entry again many different names in different languages but most programming languages have a notion for that restoring just a set of these with the condition that there's no two entries with the same key that's what distinguishes it from just a set of of pairs but for the implementations It's usually the key difficulty is storing a set of keys and then adding a value a pointer to some value is somewhere in the middle is is the easy bit that you can do in the

6:23 Elementary implementations

7:35 same way for all implementations so I'll probably also slightly make the transition to dropping values when I describe things and just talk about the keys because that's the the essence laughs so what can you do you can just store the keys in an unordered linked list and keep a pointer to the value put is easy I mean it's unordered so you can just put it at the end or at the beginning whatever you find more convenient uh get this painful because you have to go through the entire list there's no other way to find find out whether a key is contained in the list so that's that's not useful really um again the other obvious thing you can do well if unordered is not convenient let's sort it sorting worked fine before but oops uh if it's a linked list it doesn't seem to help help at all so put is expensive because you have to find the position where you put it maybe you can be smart about that but then uh how do you get there you have to follow pointers to get to this position and get has the same problem uh the elements are sorted but just to navigate the pointers in the linked list takes you the same time so somehow this this didn't help right

8:53 it's even worse and the the problem here was that the the stress uh is on linked list that's why that's bold I don't didn't want to cross it out

9:06 Binary search

9:10 uh we can make use of sordidness that's why I asked you about the physical dictionaries if you open up a dictionary how do you find the words you don't scan start reading if you're looking for a tree you don't start a and go through the entire book you do something like binary search or slightly sophisticated versions thereof so uh how does this work um many of you will have seen this but uh it's a quick recap if you like here's our sorted list of keys again I'm only showing the keys somewhere there's uh another array with the values with the pointers to values if you want and the important bit here is it's an array so we can access things by index and you can do the same with book pages more or less uh so if we search for 69 it's there obvious right as a human you just see it how would a computer do it you start looking at the middle and so this m value is just the middle between L and r um round it round it down you compare 69 to this element

10:25 and it's bigger so what does that mean um it it means that all the elements to the left of that which are smaller than 63. cannot possibly be the location of 69 if it's in there right that's why you can exclude half of the array in one go you would do this in the dictionary open it in the middle and see well the middle of the alphabet but in a dictionary I don't know maybe maybe it's m something like that no idea uh so you would find a word with M but you're looking for tree so you know it can't be in any of the first half of the book same principle here so you can narrow down your range you do the same thing again this time you find that the value you're looking for is too small so you can exclude all the range up to and including m to the right so we're left with these three now if you execute it all the way down we would again compare with this and find it smaller than 77 so these two are also out and we're left with a single element and at that point we could say let's let's just check if it's in there if yes then we found it if not we have proven that

11:39 it's not in the list it's not part of our dictionary all right okay um how good is this by and large we cut the remaining number of elements in half with one comparison there's a plus minus one because we have to round so in the worst case it's a plus one cut in half and Round Up if you work this out the the worst case the bad most expensive case you can have is log to the base 2 of n rounded down but then a plus one so it's really very close to login right uh and well to State the obvious login is good that's that's really fast if you compare linear to logarithmic that's an exponential Improvement I know people the you know the use of exponential to describe any kind of change is growing exponentially people just use this in an arbitrary way I might I'm meaning it here in a very concrete quantitative precise way log n is really exponentially smaller than n in the literal sense 2 to the log n is n okay

12:56 of course this hinge is very much on random axis what I need is a way to jump in the middle and compare with the middle element otherwise binary search cannot work question

13:10 um well it's fine in the word Ram model right um yeah it kind of yeah so uh I think I think the short answer is yes if your model doesn't allow a race and there are sensible models that don't allow arrays you can't do this kind of binary search but the whole point of today will be to show that you can get essentially as good as this without arrays