4 ms·
This only works in specific cases (namely those where dynamic programming algorithms suffice), and does not avoid the recursion limit in general.
by kqr 9y ago
This only works in specific cases (namely those where dynamic programming algorithms suffice), and does not avoid the recursion limit in general.
- abhirag 9y agoDon't dismiss one of my favorite higher order functions so soon :) "Recursion + memoization provides most of the benefits of dynamic programming, including usually the same running time." -- Steven Skiena lru_cache decorator is great for people who are happy to let the language handle the caching of results for them, and often leads to code which is much more concise than the dynamic programming approach. The limitation you are referring to is that the decorator uses a dictionary to cache results and that dictionary uses the arguments as keys so the arguments need to be hashable. That limitation can be avoided by using immutable data structures (Clojure also has a higher order function called memoize which does the same thing and has no limitations because the core data structures in Clojure are immutable) and although Python not having structural sharing can mean that this approach can hurt memory and GC efficiency a bit, but that trade-off is at least worth considering :) Still have to keep the stack depth less than sys.getrecursionlimit() so no substitute for tail recursion but surely a substitute for dynamic programming in a lot of cases.
- deleted 9y ago[deleted]
- daveFNbuck 9y agoYou can only avoid the recursion limit in cases where dynamic programming would also work, as you have to explicitly call the function in reverse stack order to avoid having the stack build up. If you want fib(10000) you need to call fib(1) through fib(9999) first, as if you were implementing a dynamic programming solution. This isn't dismissive. lru_cache is one of my favorites too, but it has limitations.
- abhirag 9y agoBut that isn't a limitation of lru_cache, for example the same higher order function when used in Clojure i.e. memoize with recur for tail recursion will not cause stack overflow. The stack build up is because python doesn't support tail call optimization, not a limitation of lru_cache, just wanted to make it clear because you can use similar higher order functions in other languages which support tail call optimization without any limitations. Deep recursion in Python without sys.setrecursionlimit() is probably not a good idea, memoization can't help you in that. My point was geared towards presenting this pattern of memoization using a higher order function + recursion as an alternative to dynamic programming and in languages with tco and immutable data structures it works beautifully :)
- daveFNbuck 9y agoI agree that this isn't a limitation of the Platonic ideal of an lru_cache function. I thought we were talking about actual Python code.
- e12e 9y agoIt's worth pointing out that python expands the datatype of numbers as needed (ending up at BigInt or similar, I belive). So any stack rewriting would have to accommodate an accumulator that starts as an integer and expands to arbitrarily many bits. It might be easily handled as I guess all arguments are references to python objects, and the regular code for expanding numbers could switch out the reference - but the point remains that proper tail call optimization in python needs to deal with objects as arguments.
- kqr 9y agoThis does not seem to me like a big hurdle. Surely this is the sort of thing that should be hidden in the Integer class?