Video 2-5: §2.5 Symbol tables

0:00 Intro

0:02 so in this section we'll talk about the second big abstract data type that you should know about these are called symbol tables and they have a couple of other names in particular they're called symbol tables or dictionaries or maps or associative arrays or key value stores it's all pretty much the same thing you may know that python has a built-in type dict what do you write these curly braces and colons that's a dictionary in python it's a built-in type so you can use this very conveniently in java it's not a built-in type but it's part of the standard library so you can use it as well without much hassle

0:43 and it's it's an abstraction of what you do in a in a physical dictionary as a book hence this question but we want to be a bit more a bit more abstract than that

0:54 so uh if you haven't voted on the question yet then let's pause this for a second because that's the important part a symbol table has the following operation you can put in a key with a certain value which means you associate that value with this key and in a python dictionary you can do this like this you say this dictionary at the position k should have this value v but k doesn't need to be a position it could be a string or an arbitrary object indeed another way to say it is you take a key value pair and store that you can also retrieve the value that you stored with the key earlier that's the way how you express this in python

1:40 and that just gives you back the last key you inserted if you call put several times it just overwrites like as you would expect to happen in an array and you can also delete elements and you can check whether something is contained but get input is the most most interesting part okay

1:59 yeah i would say this is this is one off if not the most fundamental basic building block that python has this built in as a type is is a signal for that and it's it's very often that by using a map a dictionary a symbol table you can make your code much more readable and you should basically use these frequently because they are fairly cheap and can be implemented very efficiently

2:28 Symbol Tables vs Mathematical Functions

2:31 i want to contrast the notion of a symbol table from something that sounds very similar but has um a big important distinction that's mathematical functions we often write well i'm talking about functions f of x equals and then some value these these things right what do you do in real analysis they look quite similar in that both associate some value to a given other input and this this part they do have in common the thing is that mathematical functions should be seen as a static thing they're not changed they're immutable is another way to say this if you change a function then you really get back a new function so you can have separate functions they differ in some points but you can't really change a function in the mathematical sense you can only talk about a different function whereas a symbol table is a dynamic mapping both the set of keys that have some value attached to it as well as the values that you do attach they can change over time that's why we have this put operation and so we still talk about the same the the dictionary doesn't change identity it's the same dictionary we had before but we change it that's the fundamental difference between between math and and data

3:44 structures and computer science we deal with things that change over time because this idea of of a mathematical function where you change a small thing and you just get a copy that is a new function we couldn't really implement that efficiently on a computer we don't want to to be forced to implement it like that all the time so instead we allow it to change things

4:08 Building Symbol Tables

4:12 so just keep these two things separate there's some very easy ways how you can build symbol tables one easy option is to use an unordered linked list or an unordered array it's easy to put things in you can just add a new key value entry at the end but if you want to find something you have to linearly scan and find the last entry for a given key so that's uh okay but it's not very interesting now we've had this discussion with heaps before so maybe it helps if we sort things a bit how about if we if we sort them but here the catches use a linked list so that we can still easily insert things and remember if you if you want to keep a list sorted you will have to be able to insert in the middle so this sounds like a linked list is smart for that because we can do this inserting things in the middle but it turns out it's actually no good here because

5:13 we we can't really make use of the sordidness if it's a linked list the best thing we can do with the linked list is just still walk through there's no way to jump at to a certain position so it seems like sortedness doesn't help us in linked lists but of course it does help us in general if we use an array instead and now this is maybe the most basic algorithm that people also use if they operate a physical dictionary where things are sorted um if you have an english dictionary there's the let the alphabet uh the the words are sorted alphabetically and then you can find a certain word by a smart way to do it would be binary search so let's briefly see how this works on an example but i really think you probably have seen this before in the general case we always have a range from l to r that we currently look at so it's an array and it has a start and end range now we want to find the key 69 so what we do is we compare 69 with this middle point so m [Music] is in the middle of lnr

5:29 Binary Search

6:35 and we find that here 69 is bigger what does that mean well the list is sorted so everything that comes before 63 is even smaller than 63 which was already too small so all of these guys are not relevant for our search i can eliminate those from the further discussion if 69 is in the dictionary if it is if it is associated with some key it will be found in the right half okay and so we move l to this point after m uh we don't change r and we update m and we keep going so 80 in this case is too big

7:16 i should start with the search key so in this case we can eliminate that part and continue with these three in the middle that was not what i wanted

7:29 sorry i jumped to the back and i have to flip through all the slides again ah all those memories okay there we are again so we eliminated this right hand part so what's remaining is these three elements um well and we could just keep going right so another round eliminates these two and then we're left with a single position in this case we find that the key we were looking for is the single key at this position and then we can return whatever was stored at that point so for a dictionary you would have a second array this is the array of keys and we would have a second array of values which is not sorted but which it just means um the key that's stored at position 7 has a value in a different array also at position 7. so you can take the same position and get the key out of there all right so that was binary searching very quick but i think that's that's all we need for here because i suspect you've seen this before so the key step here was we cut things in half each time and so you can show how often do you have to cut n in half before you get down to one that's

8:53 roughly log n and if you count precisely you see that log n rounded down plus one is the worst case number of comparisons you need if you're lucky it's one less like it's a it's not much of a difference the the crucial thing here was we needed random access all of binary search relies on the fact that we can jump in the middle and get the middle key right now if we were to make this a dynamic data structure suppose we wanted to insert a key 70 then we would find it does belong between position 8 and 9 but it's no good to make the array contain this new element we would have to copy the second half over or start with a new array or move a lot of elements around and then we have linear time again in the worst case so this is not going to work in a dynamic setting binary search is just for static arrays