I wanted to memoize this:

    def fib(n: Int) = if(n &lt;= 1) 1 else fib(n-1) + fib(n-2)
    println(fib(100)) // times out

So I wrote this and this surprisingly compiles and works (I am surprised because `fib` references itself in its declaration):

    case class Memo[A,B](f: A =&gt; B) extends (A =&gt; B) {
      private val cache = mutable.Map.empty[A, B]
      def apply(x: A) = cache getOrElseUpdate (x, f(x))
    }
    
    val fib: Memo[Int, BigInt] = Memo {
      case 0 =&gt; 0
      case 1 =&gt; 1
      case n =&gt; fib(n-1) + fib(n-2) 
    }

    println(fib(100))     // prints 100th fibonacci number instantly

But when I try to declare fib inside of a `def`, I get a compiler error:

    def foo(n: Int) = {
      val fib: Memo[Int, BigInt] = Memo {
        case 0 =&gt; 0
        case 1 =&gt; 1
        case n =&gt; fib(n-1) + fib(n-2) 
      }
      fib(n)
    } 

Above fails to compile `error: forward reference extends over definition of value fib
case n =&gt; fib(n-1) + fib(n-2)`

Why does declaring the `val fib` inside a def fails but outside in the class/object scope works?

To clarify, why I might want to declare the recursive memoized function in the def scope - here is my solution to the subset sum problem:

  

    /**
       * Subset sum algorithm - can we achieve sum t using elements from s?
       *
       * @param s set of integers
       * @param t target
       * @return true iff there exists a subset of s that sums to t
       */
      def subsetSum(s: Seq[Int], t: Int): Boolean = {
        val max = s.scanLeft(0)((sum, i) =&gt; (sum + i) max sum)  //max(i) =  largest sum achievable from first i elements
        val min = s.scanLeft(0)((sum, i) =&gt; (sum + i) min sum)  //min(i) = smallest sum achievable from first i elements
    
        val dp: Memo[(Int, Int), Boolean] = Memo {         // dp(i,x) = can we achieve x using the first i elements?
          case (_, 0) =&gt; true        // 0 can always be achieved using empty set
          case (0, _) =&gt; false       // if empty set, non-zero cannot be achieved
          case (i, x) if min(i) &lt;= x &amp;&amp; x &lt;= max(i) =&gt; dp(i-1, x - s(i-1)) || dp(i-1, x)  // try with/without s(i-1)
          case _ =&gt; false            // outside range otherwise
        }
    
        dp(s.length, t)
      }

Is there a generic way to memoize in Scala?

So in Rails 3.2, ActiveSupport::Memoizable has been deprecated.

The message reads:

    DEPRECATION WARNING: ActiveSupport::Memoizable is deprecated and
    will be removed in future releases,simply use Ruby memoization
    pattern instead.

It refers to &quot;Ruby memoization pattern&quot; (singular) as if there&#39;s one pattern we should all know and refer to...

I presume they mean something like:

    def my_method
      @my_method ||= # ... go get the value
    end

or 
    
    def my_method
      return @my_method if defined?(@my_method)

      @my_method = # ... go get the value
    end

Is there something else I&#39;ve missed?

Which Ruby memoize pattern does ActiveSupport::Memoizable refer to?

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, &quot;file.dat&quot;)

and then call getHtmlMemoized(url), so as to do the expensive computation only once for each url.


memoize to disk - python - persistent memoization

The **bottom-up** approach (to dynamic programming) consists in first looking at the &quot;smaller&quot; subproblems, and then solve the larger subproblems using the solution to the smaller problems.

The **top-down** consists in solving the problem in a &quot;natural manner&quot; and check if you have calculated the solution to the subproblem before.

I&#39;m a little confused. What is the difference between these two?

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

I have a set of integers. I want to find the [longest increasing subsequence][1] of that set using dynamic programming.


  [1]: https://en.wikipedia.org/wiki/Longest_increasing_subsequence

How to determine the longest increasing subsequence using dynamic programming?

Consider the following:

    @property
    def name(self):
    
    	if not hasattr(self, &#39;_name&#39;):
    
    		# expensive calculation
    		self._name = 1 + 1
    
    	return self._name

I&#39;m new, but I think the caching could be factored out into a decorator. Only I didn&#39;t find one like it ;)

PS the real calculation doesn&#39;t depend on mutable values

Is there a decorator to simply cache function return values?

Any pointers on how to solve efficiently the following function in Haskell, for large numbers `(n &gt; 108)`

    f(n) = max(n, f(n/2) + f(n/3) + f(n/4))

I&#39;ve seen examples of memoization in Haskell to solve fibonacci
numbers, which involved computing (lazily) all the fibonacci numbers
up to the required n. But in this case, for a given n, we only need to
compute very few intermediate results.

Thanks

Memoization in Haskell?

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&#39;s the core difference between the two?

What is the difference between Caching and Memoization?

By what mechanism is this fibonacci-function memoized?

    fib = (map fib&#39; [0..] !!)                 
         where fib&#39; 1 = 1                                                        
               fib&#39; 2 = 1                                                        
               fib&#39; n = fib (n-2) + fib (n-1)                    

And on a related note, why is this version not?

    fib n = (map fib&#39; [0..] !! n)                                               
         where fib&#39; 1 = 1                                                        
               fib&#39; 2 = 1                                                        
               fib&#39; n = fib (n-2) + fib (n-1)                    

How is this fibonacci-function memoized?

I&#39;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&#39;t want to do it by default** in `__init__`.  

I&#39;m new to Python, but not to programming.  I can come up with a way to do this pretty easily, but I&#39;ve found over and over again that the &#39;Pythonic&#39; way of doing something is often much simpler than what I come up with using my experience in other languages.

Is there a &#39;right&#39; way to do this in Python?

Caching class attributes in Python

I can&#39;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 calls (presumably it caches the list), whereas m2 10000000 always takes the same amount of time (rebuilding the list with each call). Any idea what&#39;s going on? Are there any rules of thumb as to if and when GHC will memoize a function? Thanks.

When is memoization automatic in GHC Haskell?

I just started Python and I&#39;ve got no idea what [memoization][1] is and how to use it. Also, may I have a simplified example?

  [1]: http://en.wikipedia.org/wiki/Memoization


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

I am trying to find a simple way to use something like Perl&#39;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 packages for memoisation.  The more I dig, the more I find, e.g.`memoise` and `R.cache`, but differences aren&#39;t readily clear.  In addition, it&#39;s not clear how else one can get Perl-style hashes (or Python-style dictionaries) and write one&#39;s own memoization, other than to use the `hash` package, which doesn&#39;t seem to underpin the two memoization packages.

Since I can find no information on CRAN or elsewhere to distinguish between the options, perhaps this should be a community wiki question on SO: What are the options for memoization and caching in R, and what are their differences?

----
As a basis for comparison, here is a list of the options I&#39;ve found.  Also, it seems to me that all depend on hashing, so I&#39;ll note the hashing options as well.  Key/value storage is somewhat related, but opens a huge can of worms regarding DB systems (e.g. BerkeleyDB, Redis, MemcacheDB and [scores of others](http://en.wikipedia.org/wiki/Key-value_store)).

It looks like the options are:

### Hashing ###
 * [digest](http://cran.r-project.org/web/packages/digest/index.html) - provides hashing for arbitrary R objects.

### Memoization ###
 * [memoise](http://cran.r-project.org/web/packages/memoise/index.html) - a very simple tool for memoization of functions.
 * [R.cache](http://cran.r-project.org/web/packages/R.cache/index.html) - offers more functionality for memoization, though it seems some of the functions lack examples.

### Caching ###
 * [hash](http://cran.r-project.org/web/packages/hash/) - Provides caching functionality akin to Perl&#39;s hashes and Python dictionaries.

### Key/value storage ###
 These are basic options for external storage of R objects.

 * [stashr](http://cran.r-project.org/web/packages/stashR/index.html)
 * [filehash](http://cran.r-project.org/web/packages/filehash/index.html)

### Checkpointing ###
 * [cacher](http://cran.r-project.org/web/packages/cacher/index.html) - this seems to be more akin to [checkpointing](http://en.wikipedia.org/wiki/Application_checkpointing).
 * [CodeDepends](http://www.omegahat.org/CodeDepends/) - An OmegaHat project that underpins `cacher` and provides some useful functionality.
 * [DMTCP](http://dmtcp.sourceforge.net/) (not an R package) - appears to support checkpointing in a bunch of languages, and [a developer recently sought assistance testing DMTCP checkpointing in R](http://r.789695.n4.nabble.com/DMTCP-checkpoint-restart-for-R-td3735097.html).

### Other ###
 * Base R supports: named vectors and lists, row and column names of data frames, and names of items in environments. It seems to me that using a list is a bit of a kludge.  (There&#39;s also `pairlist`, but [it is deprecated](http://cran.r-project.org/doc/manuals/R-lang.html#Pairlist-objects).)
 * The [data.table](http://datatable.r-forge.r-project.org/) package supports rapid lookups of elements in a data table.

----
### Use case ###

Although I&#39;m mostly interested in knowing the options, I have two basic use cases that arise:

 1. Caching: Simple counting of strings.  [Note: This isn&#39;t for NLP, but general use, so NLP libraries are overkill; tables are inadequate because I prefer not to wait until the entire set of strings are loaded into memory.  Perl-style hashes are at the right level of utility.]
 2. Memoization of monstrous calculations.

These really arise because I&#39;m [digging in to the profiling of some slooooow code](https://stackoverflow.com/questions/7252602/digging-into-r-profiling-information) and I&#39;d really like to just count simple strings and see if I can speed up some calculations via memoization.  Being able to hash the input values, even if I don&#39;t memoize, would let me see if memoization can help.

----
Note 1: The [CRAN Task View on Reproducible Research](http://cran.r-project.org/web/views/ReproducibleResearch.html) lists a couple of the packages (`cacher` and `R.cache`), but there is no elaboration on usage options.

Note 2: To aid others looking for related code, here a few notes on some of the authors or packages.  Some of the authors use SO.  :)

 * Dirk Eddelbuettel: `digest` - a lot of other packages depend on this.
 * Roger Peng: `cacher`, `filehash`, `stashR` - these address different problems in different ways; see [Roger&#39;s site](http://www.biostat.jhsph.edu/~rpeng/software/index.html) for more packages.
 * Christopher Brown: `hash` - Seems to be a useful package, but the links to ODG are down, unfortunately.
 * Henrik Bengtsson: `R.cache` &amp; Hadley Wickham: `memoise` -- it&#39;s not yet clear when to prefer one package over the other.

Note 3: Some people use memoise/memoisation others use memoize/memoization.  Just a note if you&#39;re searching around.  Henrik uses &quot;z&quot; and Hadley uses &quot;s&quot;.

Options for caching / memoization / hashing in R

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 in 2.7? Is there any 3rd party library providing the same feature or should I write my own? 

memoization library for python 2.7

&gt; **Possible Duplicate:**  
&gt; [Dynamic programming and memoization: top-down vs bottom-up approaches](https://stackoverflow.com/questions/6164629/dynamic-programming-and-memoization-top-down-vs-bottom-up-approaches)  

&lt;!-- End of automatically inserted text --&gt;

I have gone through a lot of articles on this but can&#39;t seem to make sense of it. At times recursion and dynamic programming looks the same and at others memoization &amp; dynamic programming look alike. Can someone explain to me what&#39;s the difference?

P.S. It will also be helpful if you could point me to some code using the three approaches on the same problem. (e.g. the Fibonacci series problem, I think every article I read used recursion but referred to it as dynamic programming)

What&#39;s the difference between recursion, memoization &amp; dynamic programming?

What is the difference between memoization and dynamic programming? I think dynamic programming is a subset of memoization. Is it right?

What is the difference between memoization and dynamic programming?

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&#39;s site)decorator in python.

&lt;!-- language: lang-python --&gt;

    def memo(f):
        table = {}
        def fmemo(*args):
            if args not in table:
                table[args] = f(*args)
            return table[args]
        fmemo.memo = table
        return fmemo

Going more general, is there a way to express generic and reusable decorators in C++, possibly using the new features of C++11?


All Memoization Solutions on Gang of Coders

Total of 17 Memoization Solutions