Stack Overflow
Stack Overflow

Questions tagged [memoization]

In computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously-processed inputs.

In computing, memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

This tag should be used for programs that are using memoization.

Source

Wikipedia

1491 questions
493
votes
14 answers

What is memoization and how can I use it in Python?

I just started Python and I've got no idea what memoization is and how to use it. Also, may I have a simplified example?
blur959
  • 5,261
  • 5
  • 19
  • 6
356
votes
12 answers

What is the difference between memoization and dynamic programming?

What is the difference between memoization and dynamic programming? I think dynamic programming is a subset of memoization. Is it right?
Sanghyun Lee
  • 21,644
  • 19
  • 100
  • 126
269
votes
9 answers

What is the difference between bottom-up and top-down?

The bottom-up approach (to dynamic programming) consists in first looking at the "smaller" subproblems, and then solve the larger subproblems using the solution to the smaller problems. The top-down consists in solving the problem in a "natural…
Guest
  • 3,097
  • 5
  • 20
  • 16
251
votes
20 answers

Is there a decorator to simply cache function return values?

Consider the following: @property def name(self): if not hasattr(self, '_name'): # expensive calculation self._name = 1 + 1 return self._name I'm new, but I think the caching could be factored out into a decorator. Only I…
Tobias
  • 3,882
  • 2
  • 22
  • 25
235
votes
21 answers

How to determine the longest increasing subsequence using dynamic programming?

I have a set of integers. I want to find the longest increasing subsequence of that set using dynamic programming.
Tony
  • 2,503
  • 4
  • 16
  • 7
164
votes
5 answers

What is the difference between Caching and Memoization?

I would like to know what the actual difference between caching and memoization is. As I see it, both involve avoiding repeated function calls to get data by storing it. What's the core difference between the two?
John
  • 1,643
  • 2
  • 10
  • 4
149
votes
8 answers

Memoization in Haskell?

Any pointers on how to solve efficiently the following function in Haskell, for large numbers (n > 108) f(n) = max(n, f(n/2) + f(n/3) + f(n/4)) I've seen examples of memoization in Haskell to solve fibonacci numbers, which involved computing…
Angel de Vicente
  • 1,928
  • 3
  • 12
  • 16
134
votes
11 answers

Caching class attributes in Python

I'm writing a class in python and I have an attribute that will take a relatively long time to compute, so I only want to do it once. Also, it will not be needed by every instance of the class, so I don't want to do it by default in __init__. I'm…
mwolfe02
  • 23,787
  • 9
  • 91
  • 161
123
votes
4 answers

How is this fibonacci-function memoized?

By what mechanism is this fibonacci-function memoized? fib = (map fib' [0..] !!) where fib' 1 = 1 fib' 2 = 1 …
bjornars
  • 1,506
  • 2
  • 10
  • 13
112
votes
4 answers

When is memoization automatic in GHC Haskell?

I can't figure out why m1 is apparently memoized while m2 is not in the following: m1 = ((filter odd [1..]) !!) m2 n = ((filter odd [1..]) !! n) m1 10000000 takes about 1.5 seconds on the first call, and a fraction of that on subsequent…
Jordan
  • 1,121
  • 2
  • 8
  • 3
73
votes
3 answers

Options for caching / memoization / hashing in R

I am trying to find a simple way to use something like Perl's hash functions in R (essentially caching), as I intended to do both Perl-style hashing and write my own memoisation of calculations. However, others have beaten me to the punch and have…
Iterator
  • 20,250
  • 12
  • 75
  • 111
70
votes
5 answers

What's the difference between recursion, memoization & dynamic programming?

Related question: Dynamic programming and memoization: top-down vs bottom-up approaches I have gone through a lot of articles on this but can't seem to make sense of it. At times recursion and dynamic programming looks the same and at others…
Sakibul Alam
  • 1,731
  • 2
  • 21
  • 40
69
votes
4 answers

memoization library for python 2.7

I see that python 3.2 has memoization as a decorator in functools library. http://docs.python.org/py3k/library/functools.html#functools.lru_cache Unfortunately it is not yet backported to 2.7. Is there any specific reason as why it is not available…
balki
  • 26,394
  • 30
  • 105
  • 151
63
votes
5 answers

Writing Universal memoization function in C++11

Looking for a way to implement a universal generic memoization function which will take a function and return the memoized version of the same? Looking for something like @memo (from Norving's site)decorator in python. def memo(f): table = {} …
akrohit
  • 1,023
  • 1
  • 10
  • 14
62
votes
11 answers

memoize to disk - python - persistent memoization

Is there a way to memoize the output of a function to disk? I have a function def getHtmlOfUrl(url): ... # expensive computation and would like to do something like: def getHtmlMemoized(url) = memoizeToFile(getHtmlOfUrl, "file.dat") and then…
seguso
  • 2,024
  • 2
  • 18
  • 20
1
2 3
…
99 100