|
Memoization is a technique used to speed up computer programs by storing the results of functions for later reuse, rather than recomputing them. Memoization is a characteristic of dynamic programming. A computer program (often simply called a program) is an example of computer software that prescribes the actions (computations) that are to be carried out by a computer. ...
In computer science, dynamic programming is a method for reducing the runtime of algorithms exhibiting the properties of overlapping subproblems and optimal substructure, described below. ...
Functions can only be memoized if they are referentially transparent -- that is, if they will always return the same result given the same arguments. Operations which are not referentially transparent, but whose results are not likely to change rapidly, can still be cached with methods more complicated than memoization. In general, memoized results are not expired or invalidated later, while caches generally are. In imperative languages, both memoization and more general caching are typically implemented using some form of associative array. In computer programming, a referentially transparent function is one that, given the same parameter(s), always returns the same result. ...
Look up cache in Wiktionary, the free dictionary. ...
An associative array (also dictionary, finite map, map, lookup table, and in query-processing an index or index file) is an abstract data type composed of a collection of keys and a collection of values, where each key is associated with one value. ...
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. Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions. ...
In mathematics and computer science, higher-order functions are functions which can take other functions as arguments, and may also return functions as results. ...
Memoization is well-described in Paradigms of Artificial Intelligence Programming, by Peter Norvig, pp269-275.
Etymology "Memoization" is derived from the Latin word memorandum, meaning what must be remembered. In common parlance, a memorandum is abbreviated as memo, and thus "memoization" means "to turn (a function) into a memo". Latin is an ancient Indo-European language originally spoken in the region around Rome called Latium. ...
Look up Memorandum in Wiktionary, the free dictionary A memorandum is a written form of communication most often employed in business environments. ...
The word memoization is often confused with memorization, which, although a good description of the process, is not limited to this specific meaning.
Example A naïve program to compute Fibonacci numbers is fib(n) { if n is 1 or 2, return 1; return fib(n-1) + fib(n-2); } (This is not meant to be an efficient implementation: it is only intended to illustrate the concept of memoization. Fibonacci numbers can be computed in logarithmic time via a closed form expression; see Fibonacci numbers.) In mathematics, the Fibonacci numbers, named after Leonardo of Pisa, known as Fibonacci, form a sequence defined recursively by: In other words, each number is the sum of the two numbers before it. ...
Because fib() is recomputed over and over for the same argument, run time for the above is O(1.6n). If instead we memoize (save) the value of fib(n) the first time we compute it, the run time is O(n). It has been suggested that Landau notation be merged into this article or section. ...
It has been suggested that Landau notation be merged into this article or section. ...
allocate array for memo, setting all entries to zero; initialize memo[1] and memo[2] to 1; fib(n) { if memo[n] is not zero, return memo[n]; memo[n] = fib(n-1) + fib(n-2); return memo[n]; } In a language with closures and higher-order functions, the memoization of any function can be automatically defined. Here "memoize" constructs and returns another function which serves as the memoization of the argument f. In programming languages, a closure is a function that refers to free variables in its lexical context. ...
memoize(f) { allocate array for memo, setting all entries to zero; construct a new function called "temp": temp(*args) { if args not in memo { memo[args] = f(*args) } return memo[args] } return temp } The notation *args is meant to represent a rest argument as in Python or Common Lisp. This solution relies on returning a closure over the variable memo, which serves as a cache for the returned function. Python is an interpreted programming language created by Guido van Rossum in 1990. ...
Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, standardised by ANSI X3. ...
This function "memoize" can be used to construct a memoized version of "fib":
memofib = memoize(fib)
History The term "memoization" was coined by Donald Michie in his 1968 paper "Memo functions and machine learning" in Nature. 1968 (MCMLXVIII) was a leap year starting on Monday (the link is to a full 1968 calendar). ...
First title page, November 4, 1869 Nature is one of the oldest and most reputable scientific journals, first published on 4 November 1869. ...
Some uses A search engine or search service is a program designed to help find information stored on a computer system such as the World Wide Web, inside a corporate or proprietary network or a personal computer. ...
Source code (commonly just source or code) is any series of statements written in some human-readable computer programming language. ...
To meet Wikipedias quality standards, this article or section may require cleanup. ...
A digital image is a representation of a two-dimensional image as a finite set of digital values, called picture elements or pixels. ...
In cryptography, encryption is the process of obscuring information to make it unreadable without special knowledge. ...
In computer science and information theory, data compression or source coding is the process of encoding information using fewer bits (or other information-bearing units) than an unencoded representation would use through use of specific encoding schemes. ...
Speech recognition (in many contexts, also known as automatic speech recognition, computer speech recognition or voice recognition) is the process of converting a speech signal to a set of words, by means of an algorithm implemented as a computer program. ...
In game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. ...
External links - Memoize - Memoize is a small library for performing memoization in Common Lisp. It was written by Tim Bradshaw.
- Memoize.pm - a Perl module that implements memoized subroutines
- Java memoization - an example in Java using dynamic proxy classes to create a generic memoization pattern.
- memoize - a Ruby module that implements memoized methods.
- Python memoization - a Python example of memoization.
- OCaml memoization implemented as a Camlp4 syntax extension.
- a C# 2.0 example of memoization
- Memoization in Lua - two example implementations of a general memoize function in Lua
Note: This article contains material taken from a public domain entry within the NIST Dictionary of Algorithms and Data Structures at http://www.nist.gov/dads/HTML/memoize.html Perl, also Practical Extraction and Report Language (a backronym, see below) is a dynamic procedural programming language designed by Larry Wall and first released in 1987. ...
A Perl module is a discrete component of software for the Perl programming language. ...
Ruby is a reflective, object-oriented programming language. ...
Camlp4 is a software system for writing extensible parsers for programming languages. ...
The NIST Dictionary of Algorithms and Data Structures is a reference work maintained by the U.S. National Institute of Standards and Technology. ...
| 
Feeds |
Contact