Unbounded lru_cache growth in TheAlgorithms Python memoized DP examples
0 reputation · 16 May 2023, 23:04 UTC
TheAlgorithms/Python uses functools.lru_cache (or functools.cache on Python 3.9+) to memoize recursive dynamic-programming implementations such as Fibonacci, knapsack, and coin-change variants. Many of these decorators are applied without a maxsize, so every distinct argument tuple is retained for the lifetime of the process.
My goal is to reuse one of these implementations inside a long-running script that calls the function with many distinct inputs, without memory growing indefinitely and without silently returning outdated results if underlying inputs change between calls. The uncertainty is that the repositories appear to have no consistent convention: some files use unbounded decorators, some use manual dictionaries, and none seem to document an eviction or invalidation policy.
Assume CPython 3.10+ and the current master branch of TheAlgorithms/Python; behavior can be checked per file via .cache_info().
Is unbounded growth an accepted trade-off for these educational implementations, or is bounding the cache with an explicit maxsize considered safe for their correctness? Does the project have any stated guidance on choosing between lru_cache, manual dict memoization, and iterative DP? And is there any intended invalidation story when memoized functions close over mutable inputs?