<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 This is based on the previous dojo-20150131-memoization notebook.
Step1:  We start with a function that calculates fibonacci numbers. 
Its code is very much like the definition of Fibonacci numbers.
Step2:  It is correct. Check the output in the following cell.
Step3:  However, it takes an exponential amount of time to calculate fibonacci numbers. This is not so bad for small values, but exponential things become big quickly.
Step4:  The problem is that the naïve function recalculates Fibonacci numbers. 
Some code is added to keep track of how many times the function is called for each input value.
Step5:  No wonder it is so slow. By the way, do you see a pattern in the numbers?
By the way, here's another way of sorting and iterating through the counts.
Step6:  The above output has parentheses, because item is a tuple. We can avoid the parentheses, by explicitly indexing the elements of the tuple as in the next cell.
Step7:  Another example of how to avoid the parentheses, without having to explicitly index each element of the tuple, is to use a leading '*' to unpack the tuple into separate arguments to the print function.
Step8:  We can make the function quicker, by calculating each Fibonacci number only once. 
When a previously calculated value is needed, we just return that previously calculated number.
Step9:  That is over 40,000 times faster than the naïve version. Let's look at the details.
Step10:  Now let's clean up the code. First, let's remove the counting stuff, since we know the answer for that now.
Step11:  Taking out the diagnostic counting code made it faster yet. 
The caching code makes the fib() function ugly and I don't 
like needing to remember to initialize the cache, 
so let's separate the caching into a separate function. 
Note that memoize() doesn't know anything about the fib() function, 
except that it takes a single argument.
memoize() can be applied to many single argument functions.
Step12:  That yielded yet another big speed increase. It's now over a million times faster than the original function.
Step13:  That's faster yet, but perhaps deceptively so. 
%timeit did fib(n) many times, but initialized the results cache only once.
Next, let's use the syntactic sugar of a function decorator to eliminate the fib = memoize(fib) statement.
The @memoize decorator can be used for many single argument functions.
Step14:  That yielded about the same speed. The code is now both simple and fast.
How would one measure the speed of starting with an empty cache each time?
Review
What are the limitations of memoize() and @memoize?
Only works for functions that accept a single argument.
The function argument must be acceptable as a dictionary key.
Only works for functions, not generators.
Size of results dictionary might become too large.
How would you work around those limitations?
Only works for functions that accept a single argument.
Try args and *kwargs stuff.
The function argument(s) must be acceptable as a dictionary key.
Might try a partial solution. Save the result when the input can be used as a dictionary key, otherwise, just calculate the result.
Only works for functions, not generators.
Could use cache internal to generator (but would lack elegant general wrapper function or decorator like memoize).
Size of results dictionary might become too large.
Might limit the size of the dictionary.
Beyond that, just calculate the result.
Might also save only the results for the most common input, or the results which are the most "expensive" to calculate.
Might have multi-stage caching, where first cache is dictionary within Python, and secondary or tertiary caches are saved outside of Python, such as in a file, a database, or a server.
Step15:  After the 2015-02-23 CohPy presentation of the above, it was suggested to use the .get() method of dictionaries to avoid the if statement inside helper(). The point is to make the code simpler and more elegant. Unfortunately, the .get() method would not change the dictionary, so the return value from the .get() method would have to be saved. That new memoize function would look like the following. It does succeed in getting rid the if statement, but the 'results[x] = results' looks ugly. Even worse, f(x) is always called, defeating the memoization.
Step16:  Using the .setdefault() method instead of the .get() method looks better, but suffers the same flaw of defeating the memoization by always calling f(x).
<ASSISTANT_TASK:>
Python Code:
from __future__ import print_function
Explanation: This is based on the previous dojo-20150131-memoization notebook.
End of explanation
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)
Explanation: We start with a function that calculates fibonacci numbers. 
Its code is very much like the definition of Fibonacci numbers.
End of explanation
[fib(i) for i in range(10)]
Explanation: It is correct. Check the output in the following cell.
End of explanation
n = 33
%timeit fib(n)
fib(n)
Explanation: However, it takes an exponential amount of time to calculate fibonacci numbers. This is not so bad for small values, but exponential things become big quickly.
End of explanation
from collections import Counter
def fib(n):
    global c
    
    c[n] += 1
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)
c = Counter()
fib(n)
for i in sorted(c, reverse=True):
    print(i, c[i])
print()
print(sum(c.values()))
Explanation: The problem is that the naïve function recalculates Fibonacci numbers. 
Some code is added to keep track of how many times the function is called for each input value.
End of explanation
for item in sorted(c.items(), key=(lambda x: x[0]), reverse=True):
    print(item)
print()
print(sum(c.values()))
Explanation: No wonder it is so slow. By the way, do you see a pattern in the numbers?
By the way, here's another way of sorting and iterating through the counts.
End of explanation
for item in sorted(c.items(), key=(lambda x: x[0]), reverse=True):
    print(item[0], item[1])
print()
print(sum(c.values()))
Explanation: The above output has parentheses, because item is a tuple. We can avoid the parentheses, by explicitly indexing the elements of the tuple as in the next cell.
End of explanation
for item in sorted(c.items(), key=(lambda x: x[0]), reverse=True):
    print(*item)
print()
print(sum(c.values()))
Explanation: Another example of how to avoid the parentheses, without having to explicitly index each element of the tuple, is to use a leading '*' to unpack the tuple into separate arguments to the print function.
End of explanation
def fib(n):
    global c
    global cache
    
    c[n] += 1
    if n in cache:
        return cache[n]
    if n == 0:
        f = 0
    elif n == 1:
        f = 1
    else:
        f = fib(n-1) + fib(n-2)
    cache[n] = f
    return f
# just to make them global
c = None
cache = None
def foo(n):
    global c
    global cache
    
    c = Counter()
    cache = {}
    fib(n)
%timeit foo(n)
Explanation: We can make the function quicker, by calculating each Fibonacci number only once. 
When a previously calculated value is needed, we just return that previously calculated number.
End of explanation
c = Counter()
cache = {}
fib(n)
for i in sorted(c.keys(), reverse=True):
    print(i, cache[i], c[i])
print()
print(sum(c.values()))
Explanation: That is over 40,000 times faster than the naïve version. Let's look at the details.
End of explanation
def fib(n):
    global cache
    
    if n in cache:
        return cache[n]
    if n == 0:
        f = 0
    elif n == 1:
        f = 1
    else:
        f = fib(n-1) + fib(n-2)
    cache[n] = f
    return f
def foo(n):
    global cache
    
    cache = {}
    fib(n)
%timeit foo(n)
Explanation: Now let's clean up the code. First, let's remove the counting stuff, since we know the answer for that now.
End of explanation
def memoize(f):
    results = {}
    def helper(x):
        if x not in results:
            results[x] = f(x)
        return results[x]
    return helper
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)
fib = memoize(fib)
def foo(n):
    def fib(n):
        if n == 0:
            return 0
        elif n == 1:
            return 1
        else:
            return fib(n-1) + fib(n-2)
    fib = memoize(fib)
    %timeit -n 1 fib(n)
for i in range(20):
    foo(n)
Explanation: Taking out the diagnostic counting code made it faster yet. 
The caching code makes the fib() function ugly and I don't 
like needing to remember to initialize the cache, 
so let's separate the caching into a separate function. 
Note that memoize() doesn't know anything about the fib() function, 
except that it takes a single argument.
memoize() can be applied to many single argument functions.
End of explanation
%timeit fib(n)
Explanation: That yielded yet another big speed increase. It's now over a million times faster than the original function.
End of explanation
@memoize
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)
%timeit fib(n)
Explanation: That's faster yet, but perhaps deceptively so. 
%timeit did fib(n) many times, but initialized the results cache only once.
Next, let's use the syntactic sugar of a function decorator to eliminate the fib = memoize(fib) statement.
The @memoize decorator can be used for many single argument functions.
End of explanation
# By the way, this computer is modest.
!lscpu
Explanation: That yielded about the same speed. The code is now both simple and fast.
How would one measure the speed of starting with an empty cache each time?
Review
What are the limitations of memoize() and @memoize?
Only works for functions that accept a single argument.
The function argument must be acceptable as a dictionary key.
Only works for functions, not generators.
Size of results dictionary might become too large.
How would you work around those limitations?
Only works for functions that accept a single argument.
Try args and *kwargs stuff.
The function argument(s) must be acceptable as a dictionary key.
Might try a partial solution. Save the result when the input can be used as a dictionary key, otherwise, just calculate the result.
Only works for functions, not generators.
Could use cache internal to generator (but would lack elegant general wrapper function or decorator like memoize).
Size of results dictionary might become too large.
Might limit the size of the dictionary.
Beyond that, just calculate the result.
Might also save only the results for the most common input, or the results which are the most "expensive" to calculate.
Might have multi-stage caching, where first cache is dictionary within Python, and secondary or tertiary caches are saved outside of Python, such as in a file, a database, or a server.
End of explanation
def memoize(f):
    results = {}
    def helper(x):
        results[x] = results.get(x, f(x))
        return results[x]
    return helper
@memoize
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)
%timeit fib(n)
fib(n)
Explanation: After the 2015-02-23 CohPy presentation of the above, it was suggested to use the .get() method of dictionaries to avoid the if statement inside helper(). The point is to make the code simpler and more elegant. Unfortunately, the .get() method would not change the dictionary, so the return value from the .get() method would have to be saved. That new memoize function would look like the following. It does succeed in getting rid the if statement, but the 'results[x] = results' looks ugly. Even worse, f(x) is always called, defeating the memoization.
End of explanation
def memoize(f):
    results = {}
    def helper(x):
        return results.setdefault(x, f(x))
    return helper
@memoize
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)
%timeit fib(n)
fib(n)
Explanation: Using the .setdefault() method instead of the .get() method looks better, but suffers the same flaw of defeating the memoization by always calling f(x).
End of explanation
<END_TASK>