Sandbox: Difference between revisions
Memoization; killed the TT section
(Memoization; killed the TT section) |
|||
Line 113:
(Probably this is an obfuscated language :-))
</lang>
==Whitespace test with unicode ZERO WIDTH NO-BREAK SPACE character (U+FEFF)==
Line 197 ⟶ 194:
The same without the "Requires" text:
{{#ask: [[Mutex]] [[Implemented in language::Unlambda]] | format=template | template=ignore | default={{#ask: [[Mutex]] | ?requires =}}}}
----
=Memoization=
Memoization is a method used to reduce function calls in recursive functions or other functions that are called very frequently. The basic idea behind memoizing is to store results for new sets of inputs (typically in a key-value style) so that the function will not have to re-compute those results later.
Functions which can be memoized are ones that give the same answer for a set of inputs each time those inputs are used. [[Fibonacci sequence|Fibonacci number functions]] are often memoized to reduce their call trees and calculation times over time. The basic operation of a memoized function would look something like this:
function a with inputs
if inputs have been seen before
return a stored answer from when they were seen
else
compute the answer for inputs
store that (inputs, answer) pair
return that answer
end function
Some programs may negate the condition in the "if" and swap the operations.
The overall benefit is that a function frequently called with the same set of inputs can save time by remembering the answer after computing it once -- sacrificing memory for computation time. In systems where memory (or storage depending on the implementation of storing old results) comes at a premium, memoization is not a good option. As long as memory is available and input sets are used repeatedly, memoization can save lots of computation time.
For tasks that use/can benefit from/(whatever) memoization, see [[:Category:Memoization]]
<nowiki>[[Encyclopedia]][[Category:Memoization]]</nowiki>
| |||