Data Structures and Algorithms with Python by Kent D. Lee & Steve Hubbard

Author:Kent D. Lee & Steve Hubbard
Language: eng
Format: epub, pdf
Publisher: Springer International Publishing, Cham

5.8.1 A Memoized Fibonacci Function

The memoized fib function in Sect. 5.8.1 records any value returned by the function in its memo. The memo variable is accessed from the enclosing scope. The memo is not created locally because we want it to persist from one call of fib to the next. Each time fib is called with a new value of n the answer is recorded in the memo. When fib(n) is called a subsequent time for some n, the memoized result is looked up and returned. The result: the memoized fib function now has O(n) complexity and it can compute fib(100) almost instantly. Without memoization, it would take 1,146,295,688,027,634,168,201 calls to the fib function to compute fib(100). Assuming each function call completed in 10 microseconds, it would take roughly 363 million years to compute fib(100). With memoization it takes 100 calls to fib and assuming 10 microseconds per call, that’s 1000 microseconds or 1/1000 of a second.

This is an extreme example of the benefit of memoization, but it can come in handy in many situations. For instance, in the tic tac toe problem of Chap. 4 the minimax function is called on many boards that are identical. The minimax function does not care if an X is placed in the upper-right corner first followed by the lower-left corner or vice-versa. Yet, the way minimax is written it will be called to compute the value of the same board multiple times. Memoizing minimax speeds up the playing of tic tac toe.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.