Don't forget that "premature optimization is ... (something bad)" Brevity is good, and using more efficient constructs where appropriate is good, but step one is to achieve correct results ... then figure out what needs to be optimized.
Thanks for the awesome content (as always!). To answer your question about why deques are faster at inserting on the left than the right, here's one viable reason-'deque' in Python is implemented as a doubly linked list of fixed-size blocks. The way these blocks are managed and how pointers are updated can impact performance. If the implementation is slightly more optimized for operations on one end, it could make a difference due to common usage patterns or other reasons. Nevertheless, inserting to the left and the right, both operations are theoretically O(1).
You're welcome! It seems strange to me how LHS operations would be prioritised over just making both ends equally performant, but I guess given the benchmarks it's viable!
Now I'm curious how slicing would do if you first had to run a len() check. eg if you were passing in the str as a variable that you don't know the length of. 🤔
@@Carberra In CPython, len() is not a method call for instances of built-in types, but a field read from a C-struct, so there should not be an added overhead. But of course this is implementation-dependent.
My opinion on why appending to the right is faster w/ lists than w/ deques in your case: You do it only 10 times, so the general size of the list is not changed (or changed like once). If you were to append more times, the list would have to get more memory and therefore take more time. (i didn't test it tho, just assuming since i remember that lists use memory like this)
Doesn't seem to make difference using bigger lists, though interestingly the results do seem to be linear, in that deques don't get much slower (or any slower at all) than lists as the collection size increases.
The caching example is impressive as well as somewhat misleading because this recursive implementation is far from ideal since each "level" includes two more function calls leading to millions of calls once you reach the criterion for stopping. And since this is largely redundant, caching helps. However, you might just as well implement it the way most people would go about solving it. Starting with [1, 1] and appending the sum of the last two elements in a loop which I'd expect to be a lot fast than the naive recursion. There are probably many more optimizations even in this case. Point here being: If caching provides such a speed boost, one should first ask oneself if calling the same function so many times is even necessary.
Presumably for deque left it is faster since you don't need to know where the end is. For string comparison false if it is iterating over characters, it can fail fast as soon as the first mismatch is reached.
4:20 That's not surprising, lists are always slower than sets for collection searches! The trade off is more memory use but much faster "in" lookups than lists. The tuple takes the same time as a list but uses less memory. Sets are basically a hash table - so a "dictionary", the key is the element the value is the memory address, a pointer basically. Lists are made up for a descriptive block and then an ordered list of pointers which exist sequentially in memory. So if you want to put one in the middle you have to loop through the memory and move everything about and worse, you might have to change the size of the list which could involve moving it entirely. With sets you can just whack one on the end. You don't have that issue with tuples because they're immutable so you can just throw them into memory and be done. Sorry, waffling...
Waffle away my guy! People will find these detailed descriptions like this helpful. Hell, I've learned things from extra insights from commenters before. It's a good resource!
Would adding to the left of a deques not be faster because you do not need to follow the chain in memory to the end to find the element to update the link to? From the left you need to update the prev_link of the first item.
@@Carberra Sure, but appending to the left of a deque is faster than to the right because you need to find the end of the deque first before adding to the right. At time 10:30
@@christolabuschagne4382i think you're mistaking deque for queue, deque should have a pointer to tail and head, thereby making pop/append on left and right efficient middle is however inefficient as it needs to loop into the middle deque is basically just a combined stack and queue collection
@@thomaseb97 Interesting. Ok, might be. I must admit that I actually have no idea, just added it as a possible explanation. I'm more a c programmer dabbling in python. Thanks for the correction
That's not really why numpy is faster. A lot of loops in python call to c routines. Numpy is faster because it calls functions which actually use the vector registers on your cpu through blas and lapack calls. And if you're using conda, then you're using MKL calls to those routines. But I have a love/hate relationship with conda.
You call the verbose version "if len(numbers) > 0" more readable that "if numbers" .. .but we aren't writing for a first-term intern. Programmers should have some knowledge about their language. It's as if you tested "if boolean_variable == True" ... that's silly, and words get in the way of understanding what you are doing is asking "if boolean_variable".
I probably should've said it was more explicit than readable, as I actually agree with you in that I find the latter more readable as there's less to parse. I made that comment more for the benefit of beginners to Python really.
I totally agree with the var == True thing. But for some reason I get a lot of pushback when I bring this up even with experienced dev’s. I think that if and compare are somehow so connected in peoples mind that they don’t really think about it.
I also think that the easier it is to write slow code, the more you should be aware of how to optimise it. Great work!
100% agree, and thanks!
Don't forget that "premature optimization is ... (something bad)" Brevity is good, and using more efficient constructs where appropriate is good, but step one is to achieve correct results ... then figure out what needs to be optimized.
Nice video! Numpy is something that everyone should know whether or not they are doing numerical computation.
Thanks for the awesome content (as always!).
To answer your question about why deques are faster at inserting on the left than the right, here's one viable reason-'deque' in Python is implemented as a doubly linked list of fixed-size blocks. The way these blocks are managed and how pointers are updated can impact performance. If the implementation is slightly more optimized for operations on one end, it could make a difference due to common usage patterns or other reasons. Nevertheless, inserting to the left and the right, both operations are theoretically O(1).
You're welcome! It seems strange to me how LHS operations would be prioritised over just making both ends equally performant, but I guess given the benchmarks it's viable!
It always warms my heart to see people who know that multiline fstrings are a thing.
Maybe I will be doing more benchmarks for my projects than before to get the most optimized version of code. Thanks Carberra
Now I'm curious how slicing would do if you first had to run a len() check. eg if you were passing in the str as a variable that you don't know the length of. 🤔
I imagine it'd probably end up slower as you're introducing a function call, but then startswith is a function call anyways so idk actually.
It would be 2 function calls so I'd expect it to be slower
@@Carberra In CPython, len() is not a method call for instances of built-in types, but a field read from a C-struct, so there should not be an added overhead. But of course this is implementation-dependent.
My opinion on why appending to the right is faster w/ lists than w/ deques in your case:
You do it only 10 times, so the general size of the list is not changed (or changed like once). If you were to append more times, the list would have to get more memory and therefore take more time. (i didn't test it tho, just assuming since i remember that lists use memory like this)
Doesn't seem to make difference using bigger lists, though interestingly the results do seem to be linear, in that deques don't get much slower (or any slower at all) than lists as the collection size increases.
The caching example is impressive as well as somewhat misleading because this recursive implementation is far from ideal since each "level" includes two more function calls leading to millions of calls once you reach the criterion for stopping. And since this is largely redundant, caching helps. However, you might just as well implement it the way most people would go about solving it. Starting with [1, 1] and appending the sum of the last two elements in a loop which I'd expect to be a lot fast than the naive recursion. There are probably many more optimizations even in this case. Point here being: If caching provides such a speed boost, one should first ask oneself if calling the same function so many times is even necessary.
Presumably for deque left it is faster since you don't need to know where the end is. For string comparison false if it is iterating over characters, it can fail fast as soon as the first mismatch is reached.
Right yeah, that does make sense actually now you've said it!
4:20 That's not surprising, lists are always slower than sets for collection searches! The trade off is more memory use but much faster "in" lookups than lists. The tuple takes the same time as a list but uses less memory.
Sets are basically a hash table - so a "dictionary", the key is the element the value is the memory address, a pointer basically. Lists are made up for a descriptive block and then an ordered list of pointers which exist sequentially in memory. So if you want to put one in the middle you have to loop through the memory and move everything about and worse, you might have to change the size of the list which could involve moving it entirely. With sets you can just whack one on the end. You don't have that issue with tuples because they're immutable so you can just throw them into memory and be done.
Sorry, waffling...
Waffle away my guy! People will find these detailed descriptions like this helpful. Hell, I've learned things from extra insights from commenters before. It's a good resource!
Make a tutorial about decorators
Also the video is awesome thank you man
I already have, though admittedly it's quite old. I do need to get round to making an updated one: ruclips.net/video/I7xKZsVHTi8/видео.html
It would be awesome if a @cache existed that would take in some time as input, like ttl=60 for caching for a minute
Yeah definitely, that's the only thing it's really missing.
Can someone guide me what is the color theme name used in VSCode showed by Carberra?
There's links in the description for it (:
Can you give me a list of plugins you have in your vscode
There's a link to a video I made on my VS Code setup in the description -- idk if it covers absolutely everything but should be a start.
Would adding to the left of a deques not be faster because you do not need to follow the chain in memory to the end to find the element to update the link to? From the left you need to update the prev_link of the first item.
Exactly yeah. You also don't need to shift a load of elements in memory with a deque.
@@Carberra Sure, but appending to the left of a deque is faster than to the right because you need to find the end of the deque first before adding to the right. At time 10:30
Oh right, sorry misread your initial comment lmao. That's cool to know, thanks for explaining that!
@@christolabuschagne4382i think you're mistaking deque for queue, deque should have a pointer to tail and head, thereby making pop/append on left and right efficient
middle is however inefficient as it needs to loop into the middle
deque is basically just a combined stack and queue collection
@@thomaseb97 Interesting. Ok, might be. I must admit that I actually have no idea, just added it as a possible explanation. I'm more a c programmer dabbling in python. Thanks for the correction
That's not really why numpy is faster. A lot of loops in python call to c routines. Numpy is faster because it calls functions which actually use the vector registers on your cpu through blas and lapack calls. And if you're using conda, then you're using MKL calls to those routines. But I have a love/hate relationship with conda.
Huh, that's interesting to know -- thanks for sharing that!
That speed may be because of, we don’t have to create another string object in case of false!
Should t6 be t[:2]
Yes, that's exactly why startswith is better
Thankfully it shouldn't affect the benchmark, but yeah, feeds right into this whole "optimisation at a cost" thing 😅
You call the verbose version "if len(numbers) > 0" more readable that "if numbers" .. .but we aren't writing for a first-term intern. Programmers should have some knowledge about their language. It's as if you tested "if boolean_variable == True" ... that's silly, and words get in the way of understanding what you are doing is asking "if boolean_variable".
I probably should've said it was more explicit than readable, as I actually agree with you in that I find the latter more readable as there's less to parse. I made that comment more for the benefit of beginners to Python really.
@@Carberra I do agree there's a balance between brevity and using "golfing" tricks in production.
Huh never heard that term before, cool little thing to have in my vocab 😄
@@Carberra especially in languages like Perl which are good at brevity, they have competitions to achieve something in as few keystrokes as possible
I totally agree with the var == True thing. But for some reason I get a lot of pushback when I bring this up even with experienced dev’s. I think that if and compare are somehow so connected in peoples mind that they don’t really think about it.
Surely the most optimal decision you can make is not to use Python?