Slight correction: deques are not ALWAYS faster as I insinuated -- they're much, _much_ faster when working with the left side of collections, but not necessarily the right. Interestingly, deques are almost always faster for inserts though!
Wow, I actually couldn't believe collections.deque's were linked lists. I had to check the C source code to see with my own eyes. Raymond knows more than me and probably has good reasons, but I've always seen double ended queues implemented as circular buffers with a dynamic array. Cache locality and all, in exchange for more memory reallocation.
@@QwDragon yeah. I thought about it more and I think I do get it. I guess the point is that indexed access doesn't really matter much for deques because the intended use case is to always insert and pop from the ends, not for arbitrary indexes in the middle. For popping, linked lists are also O(1) like dynamic arrays (python lists), so no problem there. For inserting at the beginning, linked lists beat dynamic arrays, since you don't have to move everything already in it (that's in the naive implementation, there are ways around this, of course). Also, the collections.deque implementation gets some benefits of cache locality by being a "linked list of arrays", so the cache can load a big "chunk" at once. TL;DR: linked list (and collections.deque, by extension) is good if you are only dealing with pushing/popping from the ends. If you want random access/indexed operations, use lists. (Yes, this is basically just a repeat of the top-level comment from the video creator)
I recommend watching Bjarne Stroustrap’s talk about why anrrays are nearly always better than linked lists. Linked lists are only better if you have a small amount of data and you don’t need to insert or delete anywhere but the ends. Even with having to shift everything in an array, the performance loss of cache misses on the randomly located elements while searching to find the location to be modified of the linked list make it so much slower that the array is still faster.
People who missed a class in Data Structures : a Deque or a doubly ended Queue will allow only to pop or add at both ends. And a linked list based implementation will make it faster and memory efficient, because one, you only need to update the head and the tail pointers (or node references) and two, you only pop from both sides. Removing at an index will be slower because linked lists aren't designed for random access. Linked List is a sequential access data structure. Python lists are slow. It's by design. If you need something faster use numpy arrays.
Hopefully it is obvious for all viewers but might be worth mentioning that if you don’t change the size of your list/array (but you could update the values inside) then they are usually faster especially if the values inside are primitive values stored on the stack and it may be worth talking about cache locality in this case - it can be extremely fascinating!
@@SkyyySi yeah you’re right, for CPython at least, not sure on the rest. I’ve been writing a lot of Rust and JavaScript lately and had forgotten about the “everything is an object” / “reference counting” model in python! All the other points I made are still valid and if you use any python libraries that wrap Rust/C/C++ (there are a lot nowadays) then I imagine it would still (at least somewhat) apply. Cache locality is really fascinating.
If you had done this: l = list(range(10000)) d = deque(range(10000)) Then timed the operation l[5000] + l[0] and d[5000] + d[0] you would've discovered that lists are a lot faster than deques. You should really only use deques if you need fast double-ended insertion and/or deletion. Otherwise, lists will be not discernibly different, or will be faster.
@@Micaeljm - Another thing you can do that shows a difference in an interesting case is this: l = list() d = deque() for i in range(1000000): l.append(i) d.append(i) Then time sum(d) vs sum(l) and you'll discover a significant difference with a deque being noticeably slower. So, even in-order traversal of a deque is slower because it's not contiguous memory. And that's even with all the entries being indirect themselves.
The use-case I have in mind is some calendar/scheduling software, where I want to maintain queues one for events that haven’t started yet in the order that they will start, and the other of events that have started but haven’t ended yet, ordered by when they will end. ... well, I guess maybe the latter of those doesn’t quite work as a queue, so much as... ... a min-heap?? (Because they aren’t necessarily being added in the same order as they are removed.) Please advise. Should I be using min-heaps for both of these, or what? I also want to periodically add a cluster of not-necessarily-sorted-yet items to the “events that haven’t started yet” data structure, when I load in a new day’s events (which should be before unloading the previous day’s, because events can cross the threshold between days)
@@drdca8263 - I would use a list and `sort` for this application. The reason I'd do this is that it's unlikely you're going to have thousands of elements, and it also seems like you wouldn't need to be inserting or deleting items more than (at most) a few times a second. Certainly not hundreds or thousands. And the simplicity of using list and sort outweighs the completely useless speed increase you might get from using a more complicated data structure. Now, if what you were scheduling was a set of events as part of a generic event system for handling IO events or something like that, then using a more complicated data structure, like a min-heap, would be warranted.
I might be missing something here, but it seems to me that you are only iterating over the first tenth of the array indices in the benchmarks. Therefore, what you refer to as the "worst-case" (index 25,000) is actually still a comparably "good case" for the deque and the real worst-case would be index 249,999. I would expect that the performance of the deque is comparable or slower than the list for indices in the second half of the array (>250,000/2), though I did not test this. Please correct me if I'm wrong.
Looks like you're right, but only for pop operations on very large collections. Inserts are always faster, no matter where the element is being inserted.
@Carberra it might be that the way you create the list allocates a capacity of exactly 250,000 elements, and adding to that list requires expanding the list to a size of 500,000 to make room. Usually that cost amortizes over time (because the next 250,000 inserts are fast again), but if you only measure a few inserts it has no chance to amortize
Without testing, I would think it's probably much faster to access element n (any random location) from a large list than from a deque. That's another consideration for choosing a list over a deque. Plus, lists take up less RAM.
... you can remove elements from the middle? Huh. I expected it to just be a like, queuestack , where you can only access the ends. If it were, then you wouldn’t need a bunch of pointers, and you could just have the items arranged almost sequentially in memory, except potentially wrapping around at the boundaries of the region allocated. Like, you would keep track of the index of the left-most and right-most elements, and update those when pushing or popping on either end.
I guess the problem there is if you wanted to rotate it, the left or right would be smack bang in the middle. There is a Queue object, though I can't remember if it's exclusive to asyncio that may work more similarly to what you're describing -- may look into that! Never used them before.
All the info you need is in the description if you haven't found it already (: It's the only theme I've used that colours _everything_, and I'd be lying if I said I wasn't completely dependent on them!
You'd be surprised how often you can use sets instead of lists. Obviously they're not ordered and don't repeat so they're not for every case but it's built in, very quick and easy. The thing is having these options in your mind when you're fully focused on the code.
@@Carberra Yeah, I've watched so many videos and thought "oh yeah, I should definitely use that" and then never do! Some features like this are great but often better for a later optimisation pass rather than the first write where it's all about delivery. I find anyway. Yeah, sets are a built-in gem. Rather than make a list and check for duplicates a set just is. So you can end up with more performant code which is more concise, productive and simpler. Beautiful.
The best way to make code faster is to change to another preferably compiled language like C/C++. If you understand the underlying memory models of linked-lists, doubly linked-list, memory-contiguous element array (buffer), circular buffer with start and end pointers, trees, balanced-trees, hash-tables etc. then it is usually clear which data structure is most efficient based on the operations you need. Sometimes a bit more work at insertion saves you a lot at retrieval or deletion. Then it depends on how often you perform the various operations. If speed is not a concern a list is the most readable data structure allowing others to more quickly understand your code.
Or you could make existing Python code more efficient? I hate this argument that if you want to optimise your code you should switch to another language -- there are plenty of situations where speed isn't priority one where Python might be the ideal choice. There's no harm in making optimisations therein.
@@Carberra I have used Python for over 15 years and I used to do too much Python optimization. Then I found that C/C++ with for example the STL library is not hard and often orders of magnitude faster. I still use Python a lot maybe with a mini-optimization here and there but if performance is important then you normally win both performance and development time if you change (part of the code) to C/C++. I have wasted too much time optimizing Python in the past. You can integrate compiled C/C++ code in Python without too much hassle. I also found that Numba just-in-time compiler in Python sometimes is a huge improvement. Maybe you hate my argument but maybe you could try a bit more C/C++ and find out yourself that sticking to Python and trying to increase performance there is often not ideal. I do agree that for very algorithmic code (for example solving Sudoku's, adversarial games, NP-complete approximations, complex search algorithms) it is important to choose the right data structures (sets, list, deque, heap, etc.). Choosing the wrong one can indeed cost orders of magnitude too. In practice I do not encounter such algorithmically heavy code daily. Finally, If you start off focusing on cases where performance is not important then it is a bit strange to subsequently focus on performance optimization. But fine, I agree there is a gray zone where you just want to optimize a little bit.
What's are deks ? Deques are an extension to queues (aka, a double-ended queue) and are pronounced as such. If we continue to use self-invented names we soon don't understand each other anymore.
It’s actually pronounced like cheque, note the missing “ue” at the end. If you’re wondering why they didn’t call it DEQueue it’s probably because dequeue already has a meaning.
Slight correction: deques are not ALWAYS faster as I insinuated -- they're much, _much_ faster when working with the left side of collections, but not necessarily the right. Interestingly, deques are almost always faster for inserts though!
Wow, I actually couldn't believe collections.deque's were linked lists. I had to check the C source code to see with my own eyes. Raymond knows more than me and probably has good reasons, but I've always seen double ended queues implemented as circular buffers with a dynamic array. Cache locality and all, in exchange for more memory reallocation.
@@rupen42 but link lists are never faster for indexed access, are they?
@@QwDragon yeah. I thought about it more and I think I do get it. I guess the point is that indexed access doesn't really matter much for deques because the intended use case is to always insert and pop from the ends, not for arbitrary indexes in the middle. For popping, linked lists are also O(1) like dynamic arrays (python lists), so no problem there. For inserting at the beginning, linked lists beat dynamic arrays, since you don't have to move everything already in it (that's in the naive implementation, there are ways around this, of course).
Also, the collections.deque implementation gets some benefits of cache locality by being a "linked list of arrays", so the cache can load a big "chunk" at once.
TL;DR: linked list (and collections.deque, by extension) is good if you are only dealing with pushing/popping from the ends. If you want random access/indexed operations, use lists. (Yes, this is basically just a repeat of the top-level comment from the video creator)
@@QwDragon check out skip lists...
Also banana is technically/ botanically considered a berry from a scientific perspective, so don't worry about tomato.
I hereby decree that bananas are now biscuits to avoid confusion in the long run.
I recommend watching Bjarne Stroustrap’s talk about why anrrays are nearly always better than linked lists. Linked lists are only better if you have a small amount of data and you don’t need to insert or delete anywhere but the ends. Even with having to shift everything in an array, the performance loss of cache misses on the randomly located elements while searching to find the location to be modified of the linked list make it so much slower that the array is still faster.
Little correction, its Bjarne Stroustrup.
People who missed a class in Data Structures : a Deque or a doubly ended Queue will allow only to pop or add at both ends. And a linked list based implementation will make it faster and memory efficient, because one, you only need to update the head and the tail pointers (or node references) and two, you only pop from both sides. Removing at an index will be slower because linked lists aren't designed for random access. Linked List is a sequential access data structure.
Python lists are slow. It's by design. If you need something faster use numpy arrays.
Hopefully it is obvious for all viewers but might be worth mentioning that if you don’t change the size of your list/array (but you could update the values inside) then they are usually faster especially if the values inside are primitive values stored on the stack and it may be worth talking about cache locality in this case - it can be extremely fascinating!
Isn't everything stored on the heap in Python?
@@SkyyySi yeah you’re right, for CPython at least, not sure on the rest. I’ve been writing a lot of Rust and JavaScript lately and had forgotten about the “everything is an object” / “reference counting” model in python! All the other points I made are still valid and if you use any python libraries that wrap Rust/C/C++ (there are a lot nowadays) then I imagine it would still (at least somewhat) apply. Cache locality is really fascinating.
If you had done this:
l = list(range(10000))
d = deque(range(10000))
Then timed the operation l[5000] + l[0] and d[5000] + d[0] you would've discovered that lists are a lot faster than deques. You should really only use deques if you need fast double-ended insertion and/or deletion. Otherwise, lists will be not discernibly different, or will be faster.
I believe you mean `d = deque(range(...))` on the second line.
@@Micaeljm - Indeed I do. *sigh* Thanks!
@@Micaeljm - Another thing you can do that shows a difference in an interesting case is this:
l = list()
d = deque()
for i in range(1000000):
l.append(i)
d.append(i)
Then time sum(d) vs sum(l) and you'll discover a significant difference with a deque being noticeably slower. So, even in-order traversal of a deque is slower because it's not contiguous memory. And that's even with all the entries being indirect themselves.
The use-case I have in mind is some calendar/scheduling software, where I want to maintain queues one for events that haven’t started yet in the order that they will start, and the other of events that have started but haven’t ended yet, ordered by when they will end.
... well, I guess maybe the latter of those doesn’t quite work as a queue, so much as...
... a min-heap?? (Because they aren’t necessarily being added in the same order as they are removed.)
Please advise.
Should I be using min-heaps for both of these, or what?
I also want to periodically add a cluster of not-necessarily-sorted-yet items to the “events that haven’t started yet” data structure, when I load in a new day’s events (which should be before unloading the previous day’s, because events can cross the threshold between days)
@@drdca8263 - I would use a list and `sort` for this application. The reason I'd do this is that it's unlikely you're going to have thousands of elements, and it also seems like you wouldn't need to be inserting or deleting items more than (at most) a few times a second. Certainly not hundreds or thousands.
And the simplicity of using list and sort outweighs the completely useless speed increase you might get from using a more complicated data structure.
Now, if what you were scheduling was a set of events as part of a generic event system for handling IO events or something like that, then using a more complicated data structure, like a min-heap, would be warranted.
Deques are ultra cool!
I might be missing something here, but it seems to me that you are only iterating over the first tenth of the array indices in the benchmarks. Therefore, what you refer to as the "worst-case" (index 25,000) is actually still a comparably "good case" for the deque and the real worst-case would be index 249,999. I would expect that the performance of the deque is comparable or slower than the list for indices in the second half of the array (>250,000/2), though I did not test this. Please correct me if I'm wrong.
Looks like you're right, but only for pop operations on very large collections. Inserts are always faster, no matter where the element is being inserted.
@Carberra it might be that the way you create the list allocates a capacity of exactly 250,000 elements, and adding to that list requires expanding the list to a size of 500,000 to make room. Usually that cost amortizes over time (because the next 250,000 inserts are fast again), but if you only measure a few inserts it has no chance to amortize
Great video :)
Without testing, I would think it's probably much faster to access element n (any random location) from a large list than from a deque. That's another consideration for choosing a list over a deque. Plus, lists take up less RAM.
... you can remove elements from the middle? Huh. I expected it to just be a like, queuestack , where you can only access the ends. If it were, then you wouldn’t need a bunch of pointers, and you could just have the items arranged almost sequentially in memory, except potentially wrapping around at the boundaries of the region allocated. Like, you would keep track of the index of the left-most and right-most elements, and update those when pushing or popping on either end.
I guess the problem there is if you wanted to rotate it, the left or right would be smack bang in the middle. There is a Queue object, though I can't remember if it's exclusive to asyncio that may work more similarly to what you're describing -- may look into that! Never used them before.
Ouh I have to switch my VS Code Design. This looks so cool
All the info you need is in the description if you haven't found it already (: It's the only theme I've used that colours _everything_, and I'd be lying if I said I wasn't completely dependent on them!
You'd be surprised how often you can use sets instead of lists. Obviously they're not ordered and don't repeat so they're not for every case but it's built in, very quick and easy.
The thing is having these options in your mind when you're fully focused on the code.
Oh yeah, that is 100% the tricky part 😅 I still don't think I've made a full video on sets you know -- I should if I haven't.
@@Carberra Yeah, I've watched so many videos and thought "oh yeah, I should definitely use that" and then never do! Some features like this are great but often better for a later optimisation pass rather than the first write where it's all about delivery. I find anyway.
Yeah, sets are a built-in gem. Rather than make a list and check for duplicates a set just is. So you can end up with more performant code which is more concise, productive and simpler. Beautiful.
@@davidmurphy563gems are for ruby though? In Python I think they are just called packages or modules.
(/j)
@@drdca8263 :)
Thanks dude, love your videos!🔥🔥🔥
"run guard" should totally be called "runder"
I am in favour of this.
The best way to make code faster is to change to another preferably compiled language like C/C++. If you understand the underlying memory models of linked-lists, doubly linked-list, memory-contiguous element array (buffer), circular buffer with start and end pointers, trees, balanced-trees, hash-tables etc. then it is usually clear which data structure is most efficient based on the operations you need. Sometimes a bit more work at insertion saves you a lot at retrieval or deletion. Then it depends on how often you perform the various operations. If speed is not a concern a list is the most readable data structure allowing others to more quickly understand your code.
Or you could make existing Python code more efficient? I hate this argument that if you want to optimise your code you should switch to another language -- there are plenty of situations where speed isn't priority one where Python might be the ideal choice. There's no harm in making optimisations therein.
@@Carberra I have used Python for over 15 years and I used to do too much Python optimization. Then I found that C/C++ with for example the STL library is not hard and often orders of magnitude faster.
I still use Python a lot maybe with a mini-optimization here and there but if performance is important then you normally win both performance and development time if you change (part of the code) to C/C++. I have wasted too much time optimizing Python in the past.
You can integrate compiled C/C++ code in Python without too much hassle. I also found that Numba just-in-time compiler in Python sometimes is a huge improvement.
Maybe you hate my argument but maybe you could try a bit more C/C++ and find out yourself that sticking to Python and trying to increase performance there is often not ideal.
I do agree that for very algorithmic code (for example solving Sudoku's, adversarial games, NP-complete approximations, complex search algorithms) it is important to choose the right data structures (sets, list, deque, heap, etc.). Choosing the wrong one can indeed cost orders of magnitude too. In practice I do not encounter such algorithmically heavy code daily.
Finally, If you start off focusing on cases where performance is not important then it is a bit strange to subsequently focus on performance optimization. But fine, I agree there is a gray zone where you just want to optimize a little bit.
Why you deliver words in buffer?
Speak synchronously!!!
pop Mango 😮
Oh god, I'm sorry! 😱
What font and editor do you use? Is that VS code?
Got a setup video in the description 😄
deck cleaner
code link?
github.com/Carberra/python-is-awesome/tree/main/2404-deques
What's are deks ?
Deques are an extension to queues (aka, a double-ended queue) and are pronounced as such.
If we continue to use self-invented names we soon don't understand each other anymore.
"Deck" is the official pronunciation: docs.python.org/3/library/collections.html#collections.deque
It’s actually pronounced like cheque, note the missing “ue” at the end. If you’re wondering why they didn’t call it DEQueue it’s probably because dequeue already has a meaning.
ur hairs
Technically a bananna is a herb not a fruit
Banana _plants_ are herbs, the bananas themselves are fruits (and also berries).
Personally my definition ends at not bacon
lol @ “decks”….
"Deck" is the official pronunciation: docs.python.org/3/library/collections.html#collections.deque
@@Carberra fair enough. That is incredibly stupid imo. It’s a queue, call it a queue
@@Dubs3 Deque = Double-ended queue
@@NeetCodeIOOh hello NeetCode, love your vids, keep it up!