Memoization Coding Pattern
(Redirected from Memoization)
Jump to navigation
Jump to search
A Memoization Coding Pattern is a coding pattern that uses function calls to avoid repeating the calculation of results for previously processed inputs.
- See: Computing, Optimization (Computer Science), Computer Programs, Subroutine, Mutual Recursion, Top-Down Parsing, Parsing, Left Recursion, Cache (Computing), Buffer (Computer Science), Page Replacement Algorithm, Logic Programming, Prolog#Tabling.
References
2014
- (Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/memoization Retrieved:2014-1-13.
- 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. Memoization has also been used in other contexts (and for purposes other than speed gains), such as in simple mutually recursive descent parsing[1] in a general top-down parsing algorithm[2] [3] that accommodates ambiguity and left recursion in polynomial time and space. Although related to caching, memoization refers to a specific case of this optimization, distinguishing it from forms of caching such as buffering or page replacement. In the context of some logic programming languages, memoization is also known as tabling;[4] see also lookup table.
- ↑ Norvig, Peter, "Techniques for Automatic Memoization with Applications to Context-Free Parsing," Computational Linguistics, Vol. 17 No. 1, pp. 91–98, March 1991.
- ↑ Frost, Richard, Hafiz, Rahmatullah, and Callaghan, Paul. “ Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars." 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE , Pages: 109 – 120, June 2007, Prague.
- ↑ Frost, Richard, Hafiz, Rahmatullah, and Callaghan, Paul. “ Parser Combinators for Ambiguous Left-Recursive Grammars." 10th International Symposium on Practical Aspects of Declarative Languages (PADL), ACM-SIGPLAN , Volume 4902/2008, Pages: 167–181, January 2008, San Francisco.
- ↑ Warren, David. “Tabling and Datalog Programming”. Accessed 29 May 2009.