6 ms·

Author here. Sorry, If it feels misleading. I have no intention to mislead anybody. If you can suggest alternative title, I am happy to change title.

shankysingh 6y ago
Thanks for article Just a side note: with Fibonacci + caching it solidly become Dynamic programming problem so Time complexity reduces from quadratic to o(n), IIRC . There is a whole class of problems where recursion + memoization(caching) = Top Down Dynamic programming , The other way to Increase performance and actually reduce call stack in these class of problems including Fibonacci would be Bottom Up Dynamic Programming Some gists I found on it https://gist.github.com/trtg/4662449 https://gist.github.com/trtg/4662449
- Immortal333 6y ago
  Yes, I have mentioned DP in my article as just reference. The Purpose of article was to show that how easy it is to implement caching in python using lru_cache decorator which is in std lib. So, We don't have to install any 3rd party lib.
  - shankysingh 6y ago
    oh sorry , somehow I missed it :)
- anandoza 6y ago
  the simple recursive solution is actually O(fib(n)), which is exponential
- akdas 6y ago
  Plugging my own writing, but I did a deep dive on top-down vs. bottom-up dynamic programming on my blog: https://avikdas.com/2019/04/15/a-graphical-introduction-to-dynamic-programming.html https://avikdas.com/2019/04/15/a-graphical-introduction-to-d... The follow-up posts go into even more detail on individual problems that can be solved using either form of dynamic programming, including some real-world problems like content-aware image resizing.
  - eindiran 6y ago
    Thank you for the link, I enjoyed the post a lot. The drawings you've done add a lot to the explanation. Do you have any other deep dives you've done in the same style that you'd recommend?
    - akdas 6y ago
      Thanks! I'm glad the drawings were helpful. Most of my writing can be found at my blog (https://avikdas.com/ https://avikdas.com/), but here are some from the same dynamic programming series: - Deep-dive into the Chain Matrix Multiplication Problem - https://avikdas.com/2019/04/25/dynamic-programming-deep-dive-chain-matrix-multiplication.html https://avikdas.com/2019/04/25/dynamic-programming-deep-dive... - Real-world applications of DP: https://avikdas.com/2019/05/14/real-world-dynamic-programming-seam-carving.html https://avikdas.com/2019/05/14/real-world-dynamic-programmin... and https://avikdas.com/2019/07/29/improved-seam-carving-with-forward-energy.html https://avikdas.com/2019/07/29/improved-seam-carving-with-fo... - Another real-world application, this time in machine learning - https://avikdas.com/2019/06/24/dynamic-programming-for-machine-learning-hidden-markov-models.html https://avikdas.com/2019/06/24/dynamic-programming-for-machi... If you look on my blog, you'll also see my recent series is on scalability, things like read-after-write consistency and queues for reliability.
Denvercoder9 6y ago
I'd suggest something along the lines of "Speeding up functions [in Python] by caching results" :)
fwip 6y ago
"python memoization in one line" Edit: I don't actually have much of a problem with the article headline as it is now. It depends a lot on your target audience! For Hacker News, yeah, we know what memoization is because we learned it in CS 102, right after we learned about recursion. But for a lot of people who would get the most value from the article, the word "memoization" isn't going to mean much, and wouldn't read the article. Maybe something like: "Memoization in Python, or how I learned to speed up function calls in just one line"

shankysingh 6y ago

Thanks for article Just a side note: with Fibonacci + caching it solidly become Dynamic programming problem so Time complexity reduces from quadratic to o(n), IIRC . There is a whole class of problems where recursion + memoization(caching) = Top Down Dynamic programming , The other way to Increase performance and actually reduce call stack in these class of problems including Fibonacci would be Bottom Up Dynamic Programming Some gists I found on it https://gist.github.com/trtg/4662449 https://gist.github.com/trtg/4662449

Immortal333 6y ago
Yes, I have mentioned DP in my article as just reference. The Purpose of article was to show that how easy it is to implement caching in python using lru_cache decorator which is in std lib. So, We don't have to install any 3rd party lib.
- shankysingh 6y ago
  oh sorry , somehow I missed it :)
anandoza 6y ago
the simple recursive solution is actually O(fib(n)), which is exponential
akdas 6y ago
Plugging my own writing, but I did a deep dive on top-down vs. bottom-up dynamic programming on my blog: https://avikdas.com/2019/04/15/a-graphical-introduction-to-dynamic-programming.html https://avikdas.com/2019/04/15/a-graphical-introduction-to-d... The follow-up posts go into even more detail on individual problems that can be solved using either form of dynamic programming, including some real-world problems like content-aware image resizing.
- eindiran 6y ago
  Thank you for the link, I enjoyed the post a lot. The drawings you've done add a lot to the explanation. Do you have any other deep dives you've done in the same style that you'd recommend?
  - akdas 6y ago
    Thanks! I'm glad the drawings were helpful. Most of my writing can be found at my blog (https://avikdas.com/ https://avikdas.com/), but here are some from the same dynamic programming series: - Deep-dive into the Chain Matrix Multiplication Problem - https://avikdas.com/2019/04/25/dynamic-programming-deep-dive-chain-matrix-multiplication.html https://avikdas.com/2019/04/25/dynamic-programming-deep-dive... - Real-world applications of DP: https://avikdas.com/2019/05/14/real-world-dynamic-programming-seam-carving.html https://avikdas.com/2019/05/14/real-world-dynamic-programmin... and https://avikdas.com/2019/07/29/improved-seam-carving-with-forward-energy.html https://avikdas.com/2019/07/29/improved-seam-carving-with-fo... - Another real-world application, this time in machine learning - https://avikdas.com/2019/06/24/dynamic-programming-for-machine-learning-hidden-markov-models.html https://avikdas.com/2019/06/24/dynamic-programming-for-machi... If you look on my blog, you'll also see my recent series is on scalability, things like read-after-write consistency and queues for reliability.

Denvercoder9 6y ago

I'd suggest something along the lines of "Speeding up functions [in Python] by caching results" :)

fwip 6y ago

"python memoization in one line" Edit: I don't actually have much of a problem with the article headline as it is now. It depends a lot on your target audience! For Hacker News, yeah, we know what memoization is because we learned it in CS 102, right after we learned about recursion. But for a lot of people who would get the most value from the article, the word "memoization" isn't going to mean much, and wouldn't read the article. Maybe something like: "Memoization in Python, or how I learned to speed up function calls in just one line"