PROGRAMMING

m9/ PYTHON
REMEMBERS




Efficiency

p197 In fibonacci function the bigger the argument, the longer the function runs. This is an inefficient solution, and its gets wors as the argument gets bigger.
 
def fibonacci(n):
    global loops
    loops += 1
    if n == 0: return 0
    if n == 1: return 1
    return fibonacci(n-1) + fibonacci(n-2)

loops = 0; print(fibonacci(4), loops)  # 3 9
loops = 0; print(fibonacci(5), loops)  # 5 15
loops = 0; print(fibonacci(6), loops)  # 8 25
loops = 0; print(fibonacci(30), loops)  # 832040 2692537
... 4 lines
 
One solution is to keep track of values and store them in a dictionary.
 
def fibonacci(n):

    global loops; loops += 1
    if n in known: 
        return known[n]

    res = fibonacci(n-1) + fibonacci(n-2)
    known[n] = res
    return res

loops = 0; known = {0:0, 1:1}; print(fibonacci(4), loops)   # 3 7
loops = 0; known = {0:0, 1:1}; print(fibonacci(5), loops)   # 5 9
loops = 0; known = {0:0, 1:1}; print(fibonacci(6), loops)   # 8 11
loops = 0; known = {0:0, 1:1}; print(fibonacci(30), loops)  # 832040 59
... 5 lines
 
Task

 
"""
Write a function that reads words in words.txt and ...
store them in a dictionary

Use the in operator as a fast way to check
Compare the speed of impelemtation with the bisection search 

https://github.com/AllenDowney/ThinkPython2/blob/master/code/words.txt
https://gist.github.com/minte9/4c411d0c83cfdfa718085f792f810a18 """

# SOLUTION

# Dictionary search
     ???

solution code
Questions    
Tuples

        A B C D E F
🔔
1/1