Python 3.6 - Dictionary Ordering

Hi. I want to talk a little bit about dictionary ordering in Python 3.6. A new implementation of DICT came out in 3.6 and one of the features of that, apart from being supposedly faster and more compact, is that key ordering is retained. And what does that mean? That just means that the order in which the keys are brought back when we iterate through the keys or the items or the values is in the same order in which the keys were inserted, the elements were inserted into the dictionary. So basically this replaces the ordered dict, which is in the collections module in the standard library, and I'll come back to that as well and take a look at order dict and see if we can actually do everything we need using just plain dictionaries. But a few caveats. First, this is in 3.6 only, so it's going to have to be 3.6 and higher. Secondly. In 3.6. It's not an official fact. In other words, it wasn't guaranteed that Keyes would remain, that dictionaries would be ordered. It's you know, it doesn't guarantee that in 3.7. However, it does it does guarantee that if you iterate a dictionary, you will get it back in the same order in which you added keys to the dictionary and it supports deletions as well. So if your code is going to be 3.6 or higher, then you can certainly leverage that feature. But if your code has to run on both 3.6 and higher and lower than 3.6 and you need to rely on ordering in dictionaries, then you still need to use the order dict, otherwise your code will break in versions prior to 3.6. So just be careful with that. But as long as you're writing for 3.6 and higher, this is safe. Even though it's not official for 3.6, it will become official for 3.7. And I have a link to that also in the Jupyter Notebook. So it's not official official yet. It's it was just a discussion that happened, I guess, in the Python developers email kind of threads. Okay. So the first thing is to make sure that we're running the correct version of Python. So you should check that if you're not absolutely sure. So we're just going to import version info from Sis and then just look at what version info says. And in this case you can see I'm running 3.6.2. All right, so now let's see, what do I mean by the dictionary keys being having the order preserved? Let's say I have a dictionary and let's put two keys in that dictionary and I'm going to put them like B is one and A is two. Okay. So now if I look at D dot items, let's say, or I can also look at D dot keys and dot values. Okay? And then D dot items if I type it correctly. So you'll notice that the keys are in the order in which I specified them in the dictionary B and A and the values are in the same order as well. And then the items are in the same order as well. Now let's say that I go ahead and add an item, okay? And I say let's say X is three. Now I can look at D keys again, D values again and D items, and you can see that X shows up as the last key in the keys. The three shows up as the last value and x comma three shows up as the last item. In other words, we're getting our order preserved. Now, what happens if I delete one? Let's say I'm going to delete A so I'm going to delete a okay. And now I'm going to say delete A from D. Okay, so now I'm just going to copy this. Actually, I'm just going to look at items. That's good enough. Well, if I can type it, maybe I should pick something I can type. Okay, so A is gone, right? A was the second element. A is gone. Now what happens if I insert it back again? So I'm going to put back a is one and let's look at D dot items again and you can see a is at the end. So it does preserve that. You know that that order I removed a from the middle of the dictionary I read it re added it back in and it added it to the end of the dictionary. So we have essentially inherent ordering in those dictionaries, hence why we don't need an ordered dict. Now, I want to point out something that's kind of weird, and it caught me by surprise. I wasn't aware of this because it doesn't do that in the Python interpreter, but Jupyter Notebook plays around when you display your dictionary, so let's see what I mean. Okay, so if we look at the items, you'll notice that we have B, X and A look what happens if I just bring back D via Jupyter? I get A then B, then X? So I think what it's doing, it's basically ordering the keys, it's sorting the keys lexicographically alphabetically if you want. It's sorting those keys. In this case I've got strings, so lexicographically and then displaying it. So be careful. Do not use this as you do not use the output of just looking at the representation of D in Jupyter based on the output here that is now incorrect. Before, it doesn't really matter because we didn't have order guaranteed, so we didn't really care how it was being displayed, you know, And so it ordered the keys before displaying them, which was pretty nice. In fact, I think the print function, the pretty print function does the same thing. The pretty print function will order your keys before it pretty prints. And there was actually a fairly lengthy discussion about that and things got a little heated, but people were discussing whether pretty print should now honor the order of the dictionaries or whether it should, you know, sort the keys and then print out and it's pretty print. And so the consensus was finally that it will it will be backward compatible. It will sort the keys. So most likely Jupyter is doing something similar or maybe they're using pretty print. So we saw how we can add and remove items and it preserves the order. So let's look at our dictionary again. So again, I can do print D, that's still fine. Print D will still keep, you know, and show the correct order so you can see that B, x and A so A is the last item. So if we say D dot pop item, it pops the rightmost item. Right? It popped a which was that key here. Now if we print D of course that value is gone. Okay so this is kind of like a stack. Of course, I wouldn't really recommend using a dictionary as a stack. You'll get probably better performance using a list. So certainly not using a dictionary. There's. There's no real reason to do that. So now what I'm wondering, of course, is, well, how do I pick a random item from the dictionary? Because it's ordered and it's not like you could pick a random item from previous dictionaries because the keys were not truly randomly ordered. Right? There was hash values involved and it wasn't truly a random. So I'll come back to that. Actually, I'll probably do a short video on how to pick a random item from a dictionary. Now what about the update method? You know that you can update one dictionary using another dictionary. So what do I mean by this? Well, let's go ahead and create this dictionary. A is one, and B, let's say is 200 and let's call it D two. Let's make that another dictionary. Let's say A is 100 and D is 300 and let's say C is 400. So I'm just keeping the DNC not ordered just so we can see if there's any kind of idiosyncrasies with that. So here's D one and D two. Now what you can do is you can say D one dot update D two And what it does is essentially it merges D two into D one. So any existing keys, it will replace the value, any keys that are not in D one but that are in D two will get merged into D one. So what I'm interested in knowing is does the order get preserved? And I'm guessing that when we merge D two into D one it's going to replace a A is going to stay in its first position and then D is going to get added in the third position and C is going to get added in the fourth position. In other words, the merge is going to respect the order of the keys in D two when it adds them to D one. So let's see. So we've done that. So this is an in-place mutation of D one. So now let's go ahead and print D one and let's see what we get. And yeah, indeed we get that. So as you can see, the order was preserved. So that's great. All right, so now, how about all the dict? Can we truly get rid of all the dict? Well, all the dict has a few methods that are not available in the regular dict. For example, the move to end method and you specify the key that you want to move to the end and then you specify optionally what the end is. Is the end the beginning of the dictionary or is the end the end of the dictionary? So is it the last item or not? So if you say last equals true, it's going to move it to the right side. The right most element of the dictionary in this ordered dict. And if you say last equals false, it's going to move it to the beginning. And then similarly there's also a pop item. So pop item also takes the last equals true. And basically it's going to remove an item from the dictionary. Now we saw with the regular standard dictionary 93.6, it just removes the last element. Well, that's what pop item does by default. But if you want to remove the first element, then you can say last equals false and then it will remove the first element of the dictionary, not the last one. Again, if all you're looking for is some kind of list where you can add and remove items easily from both the front and the and the end of the list, you should look at deck. That's in the collections module. Okay. So those are the two main items. Now, it also supports reversed so you can actually pass reversed to reverse the iteration or you can call reversed on the ordered dict to reverse the iteration. So so when you iterate and order dict normally you iterate from left to right. If you want to iterate from right to left, you just use reversed instead. So let's take each one of those one by one and let's see if we can build an equivalent using just plain dict now in 3.6. So the first one I want to look to is the move to end. So move to end. And let's see if somehow we can do that. So let's start with a dictionary. So let's say A is one and B is two and C is three. So simple dictionary. And let me go ahead and print what our start state is for the dictionary. Now, what do I want to do? I want to take an element. Let's say I want to take a and I want to remove it from the beginning and move it to the end. So essentially what I'm going to do is I'm going to pop it right. I'm going to pop the item with key. A pop is going to return the value. So now all I need to do is just set it to the key. And remember now when I set the key because the ordering is preserved, it should actually add it to the end of the dictionary. So in effect, what I've done here is moved A to the end of the dictionary. So that would be equivalent to move to end with. With. Let me just write that in with last equal to true. Okay. That would be equivalent to that. So let's see now let's go ahead and print moved a to end and let's just see what the state of the dictionary is. And yeah, that worked right A in the beginning was here and now A is at the end. So we can do at least the move to end last equals true of the ordered dict. Now how about move to front. Okay so by move to front what I mean is move to end last equals false. So let's see how we might do that. Now that was not as easy because we want to put something in the beginning. We don't really have a way to do that with the standard dict. We can only basically add to the end, but we can't add to the beginning. So what we're going to have to do is we're going to let me start off with this dictionary and I'm just going to copy paste that from my notes. You can download the notebook. Um, let's start with this and let's say that I want to move, um, c to the beginning. So the first thing that I'm going to do, let me just show you kind of manually what I'm going to do. The first thing I'm going to do is I'm going to move C to the end, okay? So I'm going to take C and I'm going to move it to the end of the dictionary. That's going to be the first step. And then what am I going to do? I'm going to iterate in the dictionary and now I know that I can iterate in an ordered fashion. So I know I can start with the first key. I'm going to take that key. I'm going to pop it and move it to the end, and then I'm going to do the same thing again with B, I'm going to iterate again and pop it to the end and I'm going to do that again. I'm going to take that and move it to the end by popping and re adding. And I'm going to do the same thing with Y, remove it and put it back at the end. And so now that I've done this, you'll notice that C is now in the beginning and then the remaining keys, A, B, X and Y have remained in their ordering. So that's the approach that I'm going to take here. So let's go ahead and print what the stout is the stout state of the dictionary. D Now I'm going to pop and move basically. So I'm going to pop C and then re add it back immediately to the dictionary. So that is now that has moved C to the end of the dictionary. Okay, so let's go ahead and print that moved C to end. Okay. So let's see if that worked. Yeah. Okay. So C is at the end. So we just use this technique here of move to end last equals true. Now what we have to do is we have to iterate for I in range and we want to iterate from what? From the first element, this one up to but not including the last element. So we're going to go to the length minus one essentially. So in terms of indexes, we're going to to iterate from zero up to and including length minus two. So we're going to iterate up to length of D minus one, okay. Because we actually want to go to minus two inclusive and we're going to then take each one and move it to the end. So we're going to do exactly what I showed you in that kind of manual process. So let's go ahead and do this. So I'm going to get an iterator on the keys. Keys is not a list. It's a view. So I need to get an iterator and I just want to get the first one right. That's all I'm interested in. I just want to get the first item in that keys. So now that I have the key, I know what the key is. I need to move that item to the end of the dictionary so I can say D dot key equals D dot pop key. Okay. And let's go ahead and say print, move C to front. If this works correctly, we should have moved C to the front by essentially moving everything in front of C to the back. Okay. And let's take a look. Yeah, we got C in front and then you'll notice that everything else here, the order was preserved. So that's working great. All right. So the next one is pop. Last item. How are we going to do pop? Last item? Well, that's really straightforward. Well, we have to do. Let me again copy this dictionary over here to pop the last item and we'll copy that as well to pop the last item. All I have to say is just dot pop item. That's the default behavior. So pop last item and you'll see that if I don't get a syntax error, you'll see that indeed we removed y from the dictionary. Okay, it's gone. Okay, cool. Now how about pop? First item. And that one actually is quite easy as well. It's not going to be any more difficult almost than pop. Last item. We already know how to find the first key in the dictionary, so all we need to do, let me copy and paste this again and all we need to do is just find the first key. Well, the key that we want to pop is going to be what? Well, it's going to be we first have to get our keys. Okay. And there's different ways you can do it here. You could convert it to a list. Okay. And then get the first item. You could do that. Or you could actually just use something like get the iterator on the keys and then just get the first one by calling next. So now we have the first key. Okay. Just to show you, that's what we get, right? A is the first key. So we have that. And all we need to do now is just to say pop key, okay? And then we should have after pop first item. And as you can see, A is gone. So pretty neat, right? That's that's really neat. Um, so basically, I'm not sure that we need an ordered dict anymore and it's probably going to remain in the standard library for backward compatibility, but most likely it's going to leverage now the dict, it's going to be a thin wrapper around a regular dict because most of the functionality is already there in DICT. If you want to find out how the dictionary was actually implemented in this version of 3.6, then you can go to this website. It's really good. It's basically a python, a pure python implementation of the dictionary of the new implementation of dictionary that Raymond Hettinger did. And so he wrote this in Python to basically show as a proof of concept and to show how it works. Now, obviously, you know, it's it's in the built in it's in C Python it's going to be written in C but you can certainly see how it works. And it's kind of standalone. If you go to Pypi and you try and take a look at it there because that implementation is there, almost that implementation is there. It's quite a bit more difficult to follow. This one is nice and self-contained, but I will do a video later on in this course when I get into the section on dictionaries and we'll look at that in detail and see how it works. That will help us understand hash maps and things like that. All right. Thanks for watching.