Talk:Memoization

Memoization recently survived vfd. See: Talk:Memoization/Delete -- Wile E. Heresiarch 09:18, 19 Jun 2004 (UTC)

Shouldn't this just be merged with caching? It's just caching of function return values, and the only reason this article is so long is the frankly not particularly useful "Some other considerations" section. --Halcy (talk) 17:45, 14 August 2020 (UTC)

Undoubtedly, this article (and this word) must be removed. Because a (very) simple analysis shows that really are no differences between memorization and the (invented) word "memoization" . Both means just memory! Just read Wiki about memory . —Preceding unsigned comment added by 187.104.217.98 (talk) 21:17, 6 March 2011 (UTC)

Memoization (without the R) is an important concept in Computer Science, not a mispelling of "memorization." The article explains this in the first paragraph. Please do not mistakenly "correct" the word to "memorization." Google memoization if you don't believe me. There's a reason this article hasn't been deleted.

Memoization In my opinion the Ethymology section is wrong and should be corrected. This would the article maybe prevent from being deleted. For me it seems quite obivious, that "memoization" is constructed by the words "memory" and "optimization". This interpretation would be a much better connection of the meaning of this word. --Mario 28 February 2011 — Preceding unsigned comment added by Maulimaulwurf84 (talk • contribs) 09:39, 28 January 2011 (UTC)

Better tell Donald Mtchie that. Oh, wait; he's dead. — Preceding unsigned comment added by 125.239.231.49 (talk) 12:49, 15 March 2012 (UTC)

The following is wrong, isn't it?

In a functional programming language it is possible to construct a higher-order function memoize which will create a memoized function for any referentially transparent function. In languages without higher-order functions, memoization must be implemented separately in each function that is to benefit from it.

How do you memoize a recursive, immutable function using a HOF? --Martin Jambon 12:36, 12 February 2006 (UTC)

By something like "let whatever = memo(whatever)". You redefine the function as the memo function applied to the original function. I remember doing this in ML many years ago.

The memoize(fib) example is very misleading, as well. Since recursive calls will not go through the memoized version, it still has a exponential running time. -- Sebastian Kanthak, 9 August 2006

OK, it seems I am not crazy then :-) I think am going to write something about memoizing recursive functions although I am far from being an expert. --Martin 01:02, 9 September 2006 (UTC)

Actually it's like the whole page should be rewritten. I am probably not going to do it. I am just adding an "expert needed" banner. --Martin 23:11, 13 September 2006 (UTC)

The memoize(factorial) example is a bad example too, because recursive calls never hit a pre-computed result. It only catches cached values on subsequent independent invocations. A much better example is ackermann's function, which I thought was given here before, but seems to be gone now.

---

I've always felt this was such a bad neologism. How do you pronounce this word anyway? -- Orz 06:25, 3 March 2006 (UTC)

Um, like "memo" followed by "ization"? --Doradus 22:04, 1 May 2006 (UTC)

Shouldn't we state that the word itself is built out of these two, while memo in turn is derived from memorandum but is a synonym for note? Otherwise it whould be memorization, whouldn't it? —Preceding unsigned comment added by 89.245.116.115 (talk) 06:10, 21 April 2009 (UTC)

Revised Boldly

Well, I didn't cover all of the above subtopics, but I did do a bold rework. -- QTJ 02:21, 23 October 2006 (UTC)

Please note that some of the pseudocode examples introduced show what happens overall -- in some languages some of the steps explicit in the pseudocode would be implicit. This was intentional, for clarity to the lay reader, and not noted in the text of the article. -- QTJ 03:45, 23 October 2006 (UTC)

referential transparency versus pure function

Only "pure functions" can be memoized. (Article states that functions must be referentially transparent, but that statement has problems. See referential transparency discussion.)

--Joe Wiki 07:40, 15 July 2007 (UTC)

Synonym for Lemmas

In mathematics and automated theorem proving, stored intermediate results are called lemmas. This synonym is perhaps worth mentioning. Pgr94 (talk) 22:15, 28 April 2008 (UTC)

Lua overemphasized?

I find the text mentioning Lua in a few places where there are other older alternatives with the same properties, such as Common Lisp and the various Schemes. Feels biased in my opinion.

For example:

In those programming languages where functions are first or second-class objects (such as Lua, with its first-class functions, or Perl [1]), automatic memoization can be implemented by replacing (at runtime) a function with its calculated value once a value has been calculated for a given set of parameters.

—Preceding unsigned comment added by Srikumarks (talk • contribs) 06:22, 26 March 2009 (UTC)

better example

IMO the factorial is not a good example, it does not give any speedup for /one/ calculation, e.g. of 100! (Of course it helps if you need to calculate k! for k=1,...,100; but in that case you do store the values yourself, so I think this somehow misses the point.

I suggest calculation of the n-th Fibonacci number (or any similar recurrent sequence) as a better example, here this technique is really useful. As an example of an implementation, one could mention Maple's "option remember":

> F:=proc(n) if n>1 then F(n-1)+F(n-2) else n fi end:
> time(F(30));
                               4.186

> F:=proc(n) option remember; if n>1 then F(n-1)+F(n-2) else n fi end:
> time(F(30));
                                 0.

— MFH:Talk 22:27, 25 September 2009 (UTC)