Deques can be FASTER than lists in Python

in this video we're going to be talking about something I've talked about on the channel before but surprisingly not in a huge amount of detail and that is decks decks are part of the collections module so I would have talked about them a little bit maybe like 2 years ago or something but they are actually really useful they have a lot of cool features they're incredibly performant especially in pop and insert operations I'm going to be showing you later and they really are something you need to know if you're going to master python the performance isn't the only thing I want to focus on today though uh I want to take you on a little bit of a tour of decks kind of show you what they do how they work they are very similar to lists in a lot of ways but you can append to and pop to the left as well as the right and it also has a few nice little extra features that I want to show you as well of course if you find this video helpful at any point then consider liking to let me know and maybe subscribe if you want to see more videos like it if you're feeling particularly generous you could become either a member or a patron by using the information in the description below but with that other way let's finally talk about decks before we start a few things so I've got a whole new setup got a new microphone a new way of recording so hopefully everything sounds okay fingers crossed second thing there's going to be a lot of jump Cuts I've been ill over the last week and a bit and I've still got a bit of a cough so sorry about that but before we get into the actual you meat of the video in terms of the title I want to show you how decks work and a few cool little features with decks so decks um are short and yes they are pronounced like that short for double-ended Q what that means is that you can append to either the left or the right and pop from the left or the right uh so if we do from collections import import there we go deck and if we use our rung guard uh we could do fruits as an example is a deck say of an empty list and then yeah it can take any collection uh my P is going to complain because when you do this it says it needs a type annotation so we're going to give it one you could just do a deck string like that because we're just going to have a series of fruits and you could say aend uh fruits well actually let's let's give it some let's give it apple and orange and a banana and say fruits. pend let's use a tomato as an example not typically considered a fruit but technically is one but you can also do friend fruits do append left say mango and append it to the left of list as well and then if you were to print fruits as it currently stands you would get uh mango Apple orange banana and tomato Apple orange and banana were what we started out with and then mango is what we appended to the left and tomato is what we appended to the right which is the default you can also pop from the left and the right so if you do fruits. pop actually if I do print uh and then pop left and then print fruits you'll see that we uh pop from the right by default so we get tomato we pop left we get a mango and then we can see that we are left with our original deck much like this you can also remove things so if we wanted to do fruits. remove Apple we could we can also Dell uh or delete items from the list so if you wanted to delete orange we could do that if we then bring back fruits we could see that we just have a deck of banana left the one thing we can't do is we can't pop at a specific index so if we were to do fruits. pop again we could see that it doesn't take any arguments and this is what I want to talk about later because decks actually have a much more efficient way to do that than you know something like lists do we'll talk about that in a bit because I first want to show how I found out about decks to begin with and that is the max Len property which can turn out to be quite helpful so if I create a new file max. PI from collections import deck like that uh do the wrong guards it's always good practice there we go and then we create a new deck um not called that say belt uh and then we have a deck that's an empty list let's say let's say an empty Tuple let's mix it up and we could do a Max Len of say five we'll say five and this means that deck can only be um five elements long if I just give it it type in there to get my P to shut up so what this means is that when you append to the deck if the deck is already five elements in Le length you'll get a pop left effect if you append to the left you'll get a pop effect if it's already at five elements and this is particularly useful in certain situations one that I'm going to show you today is about simulating a conveyor belts so conveyor belts are only so long so if we we had a series of components say that was just a list a b uh if I could type and x and do from random import choice and if we say for I just done underscore in range 50 we then choose uh to append a choice of components like that and if we print the belt uh let's call Max Len this one we can see that the length of the deck never exceeds five so if we go up here we start oh my God it did Three A's in a row that's interesting uh random generation you see it's element one we have two elements three elements four elements five elements and now it has five elements it can't exceed that so when it adds this extra B you'll see this series of Three A's becomes the series of 2 A's because this a has been taken off the end of the belt um and when I say it's a pop left Behavior I don't believe it returns uh the value that's been popped though we could always check I suppose cuz I genuinely don't know no it doesn't okay so it's not a pop left it's more like a delete off the uh off the deck and the reason it's able to do all this including being able to pop left pop right a pen left a pen right uh feeds very nicely into why decks are so much faster than list when it comes to popping and inserting this because of the way that decks operate so list hold all their values sequentially in memory so say if the first element of a list was in uh memory address zero the next element will always be Memory address one the element after that would always be Memory address 2 etc etc etc until you get to the end of the list with decks that's not true decks have their elements spread all over the place and they're connected by a series of pointers anyone that knows what a link list is you've got the right idea now the difference is here is that when a list um pops an element that say element number two all of the elements after it have to be shifted over in memory which is a very expensive operation when decks do it all they have to do is update the pointers so the one preceding and the one after uh both point to each other instead of the one that was popped I'm not 100% sure why exactly this is but that means that you can only pop from the left and the right despite the fact that you can delete from anywhere so if you were to pop an element by its index you would need to rotate it first and this is going to seem somewhat unnecessary and it's going to seem like it's a lot slower than doing it by list but while I'm doing this remember that it is genuinely faster and I'm going to prove it uh so if we have our run guard in here and then we have our for you know I'm just going to copy paste this I don't particularly want to type it out all over again and say if we wanted to get the second element we could do if we didn't want to remove it we could do something like this um and it would get orange but if we wanted to pop it what we would need to do is we need to do fruits. rotate minus the index uh and then we can print fruits uh you don't need to print it we just want to show that it is um popping the correct element and then if we wanted to restore the original order that we would need to return the deck back uh by giving it the same index again and if we print fruits we can see that if I just run the file again we can see that we get orange so we've printed orange again but we're popping orange the second time around and our deck is in the same order as it was you know just without the orange so we have mango apple banana if you would have follow this it'd be mango apple and banana the orange isn't there this is a three line operation to perform a pop but if I were to go into our benchmarks and do benchmark pop this is a particularly weird and complicated thing but it is programmed properly so two very important things before I run these one The Collection being used is quite large 250,000 in this case obviously the effects or the performance difference is going to be reduced on a smaller collection the second thing to keep in mind is that due to the way the Benchmark is programmed there are always 250 pop operations for both the list and the deck and then the list and the deck I don't think it would matter in this case but they have exactly the same numbers you know the deck is just created through the numbers list so if we were to run P benchmarks and then benchmarks pop we will see that decks are an awful lot faster and you'll also see something quite strange in that decks get slower or as decks get slower lists actually gets slightly faster and that's because the further along the list you have to go the less items you have to move into pip so if you had a list that was 100 elements long if you pop the second thing you would have to move the other 97 elements across if you pop the 98 thing you'd only need to pop two um or you'd only need to move two sorry not pop so that's why lists uh speed up over time but even in the deck's worst case it's still significantly faster than the list the effect is actually even more pronounced if you do insert so I will show The Benchmark off very quick it's just the same thing we're just inserting the number into the particular position and you would do your rotate uh and a pen left or you could a pen right if you wanted to but you'd need to do some extra maths on the number uh to get it in the right place and you'll be able to see that the effect is actually even greater with inserts than it is with pops um I'm not entirely sure what this is I guess insertion operations are more complicated than pop operations but everything is having to be moved out out of the way before something can be inserted in a list with a deck you're just saying all right this points to this and this points to this and this final thing here for index 25,000 so this will be the absolute final element of the list so even when there's nothing to move lists are still quite a bit slower than their deck counterparts um I don't know why that is but that's true if we then run the append benchmarks we'll see this is a slightly weirder Benchmark um but list are actually faster when it comes to append so if you're only ever going to be appending stuff to the right of the collection then list may be the way to go but in pretty much any other situation decks are faster but that's everything I wanted to discuss with decks if you have any questions about what you've seen or any ideas of videos you want me to do in the future make sure to leave a comment down below I read every single one so your feedback is greatly appreciated I'd also like to thank my amazing members and patrons on screen now for their support especially mazard Russi and the third for being so generous and I will see you in the next video where we learn how to create Jupiter notebooks so I've talked a little bit on the channel about that before a good number of years ago but I'm going to do an updated one for those just getting into data science for the first time so I'll see you for that

Channel: Carberra

Views: 25,773

Keywords: pyfhon, pytho, pytbon, pytjon, ptyhon, pytyon, ptthon, pyyhon, pythn, pythoh, pythpn, ython, pytgon, pyhon, pytohn, phthon, oython, pthon, pyghon, pythoj, pythno, pythkn, ypthon, pytuon, lython, pyrhon, pythom, pythob, puthon, pgthon, python, pyhton, pythln, pythin, pytnon, pyton

Id: 5tkZvjtmUs0

Length: 12min 16sec (736 seconds)

Published: Mon Feb 12 2024