Note: Click on "Kernel" > "Restart Kernel and Clear All Outputs" in JupyterLab before reading this notebook to reset its output. If you cannot run this file on your machine, you may want to open it in the cloud .

Chapter 9: Mappings & Sets (continued)¶

After introducing the dict type in the first part of this chapter, we first look at an extension of the packing and unpacking syntax that involves dict objects. Then, we see how mappings can help us write computationally more efficient implementations to recursive solutions of problems as introduced in Chapter 4 . In a way, this second part of the chapter "finishes" Chapter 4.

Packing & Unpacking (continued)¶

Just as a single * symbol is used for packing and unpacking iterables in Chapter 7 , a double ** symbol implements packing and unpacking for mappings.

Let's say we have to_words and more_words as below and want to merge the items together into a new dict object.

In [1]:

to_words = {
    0: "zero",
    1: "one",
    2: "two",
}

In [2]:

more_words = {
    2: "TWO",  # to illustrate a point
    3: "three",
    4: "four",
}

By unpacking the items with **, the newly created dict object is first filled with the items from to_words and then from more_words. The item with the key 2 from more_words overwrites its counterpart from to_words as it is mentioned last.

In [3]:

{**to_words, **more_words}

Out[3]:

{0: 'zero', 1: 'one', 2: 'TWO', 3: 'three', 4: 'four'}

Function Definitions & Calls (continued)¶

Both, * and ** may be used within the header line of a function definition, for example, as in print_args1() below. Here, positional arguments not captured by positional parameters are packed into the tuple object args, and keyword arguments not captured by keyword parameters are packed into the dict object kwargs.

For print_args1(), all arguments are optional, and ...

In [4]:

def print_args1(*args, **kwargs):
    """Print out all arguments passed in."""
    for index, arg in enumerate(args):
        print("position", index, arg)

    for key, value in kwargs.items():
        print("keyword", key, value)

... we may pass whatever we want to it, or nothing at all.

In [5]:

print_args1()

In [6]:

print_args1("a", "b", "c")

position 0 a
position 1 b
position 2 c

In [7]:

print_args1(first=1, second=2, third=3)

keyword first 1
keyword second 2
keyword third 3

In [8]:

print_args1("x", "y", flag=True)

position 0 x
position 1 y
keyword flag True

We may even unpack dict and list objects.

In [9]:

flags = {"flag": True, "another_flag": False}

In [10]:

print_args1(**flags)

keyword flag True
keyword another_flag False

In [11]:

print_args1(*[42, 87], **flags)

position 0 42
position 1 87
keyword flag True
keyword another_flag False

The next example, print_args2(), requires the caller to pass one positional argument, captured in the positional parameter, and one keyword argument, captured in keyword. Further, an optional keyword argument default may be passed in. Any other positional or keyword arguments are packed into either args or kwargs.

In [12]:

def print_args2(positional, *args, keyword, default=True, **kwargs):
    """Print out all arguments passed in."""
    print("required positional", positional)

    for index, arg in enumerate(args):
        print("optional positional", index, arg)

    print("required keyword", keyword)
    print("default keyword", default)

    for key, value in kwargs.items():
        print("optional keyword", key, value)

If the caller does not respect that, a TypeError is raised.

In [13]:

print_args2()

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[13], line 1
----> 1 print_args2()

TypeError: print_args2() missing 1 required positional argument: 'positional'

In [14]:

print_args2("p")

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[14], line 1
----> 1 print_args2("p")

TypeError: print_args2() missing 1 required keyword-only argument: 'keyword'

In [15]:

print_args2("p", keyword="k")

required positional p
required keyword k
default keyword True

In [16]:

print_args2("p", keyword="k", default=False)

required positional p
required keyword k
default keyword False

In [17]:

print_args2("p", "x", "y", keyword="k", flag=True)

required positional p
optional positional 0 x
optional positional 1 y
required keyword k
default keyword True
optional keyword flag True

In [18]:

print_args2("p", "x", "y", keyword="k", default=False, flag=True)

required positional p
optional positional 0 x
optional positional 1 y
required keyword k
default keyword False
optional keyword flag True

As above, we may unpack list or dict objects in a function call.

In [19]:

positionals = ["x", "y", "z"]

In [20]:

print_args2("p", *positionals, keyword="k", default=False, **flags)

required positional p
optional positional 0 x
optional positional 1 y
optional positional 2 z
required keyword k
default keyword False
optional keyword flag True
optional keyword another_flag False

Memoization¶

"Easy at first Glance" Example: Fibonacci Numbers (repeated)

The recursive implementation of the Fibonacci numbers in Chapter 4 takes long to compute for large Fibonacci numbers. For easier comparison, we show the old fibonacci() version here again.

In [21]:

def fibonacci(i):
    """Calculate the ith Fibonacci number.

    Args:
        i (int): index of the Fibonacci number to calculate

    Returns:
        ith_fibonacci (int)
    """
    if i == 0:
        return 0
    elif i == 1:
        return 1
    return fibonacci(i - 1) + fibonacci(i - 2)

In [22]:

fibonacci(12)

Out[22]:

Efficiency of Algorithms¶

Timing the code cells below with the %%timeit magic shows how doubling the input (i.e., 12 becomes 24) more than doubles how long it takes fibonacci() to calculate the solution. This is actually an understatement as we see the time go up by roughly a factor of $1000$ (i.e., from nano-seconds to milli-seconds). That is an example of exponential growth.

In [23]:

%%timeit -n 100
fibonacci(12)

40.1 µs ± 1.26 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [24]:

%%timeit -n 100
fibonacci(24)

12.1 ms ± 149 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

The computation graph below visualizes what the problem is and also suggests a solution: In the recursive implementation, the same function calls are made over and over again. For example, in the visualization the call fibonacci(3), shown as $F(3)$ , is made twice when the actual goal is to calculate fibonacci(5), shown as $F(5)$ . This problem "grows" if the initial argument (i.e., 5 in the example) is chosen to be larger as we see with the many fibonacci(2), fibonacci(1) and fibonacci(0) calls.

Instead of calculating the return value of the fibonacci() function for the same argument over and over again, it makes sense to cache (i.e., "store") the result and reuse it. This concept is called memoization .

"Easy at second Glance" Example: Fibonacci Numbers (revisited)

Below is a revision of the recursive fibonacci() implementation that uses a globally defined dict object, called memo, to store intermediate results and look them up.

To be precise, the the revised fibonacci() first checks if the ith Fibonacci number has already been calculated before. If yes, it is in the memo. That number is then returned immediately without any more calculations. As dict objects are optimized for constant-time key look-ups, this takes essentially "no" time! With a list object, for example, the in operator would trigger a linear search, which takes longer the more elements are in the list. If the ith Fibonacci number has not been calculated before, there is no corresponding item in the memo and a recursive function call must be made. The result obtained by recursion is then inserted into the memo.

In [25]:

memo = {
    0: 0,
    1: 1,
}

In [26]:

def fibonacci(i, *, debug=False):
    """Calculate the ith Fibonacci number.

    Args:
        i (int): index of the Fibonacci number to calculate
        debug (bool): show non-cached calls; defaults to False

    Returns:
        ith_fibonacci (int)
    """
    if i in memo:
        return memo[i]

    if debug:  # added for didactical purposes
        print(f"fibonacci({i}) is calculated")

    recurse = fibonacci(i - 1, debug=debug) + fibonacci(i - 2, debug=debug)
    memo[i] = recurse
    return recurse

When we follow the flow of execution closely, we realize that the intermediate results represented by the left-most path in the graph above are calculated first. fibonacci(1), the left-most leaf node $F(1)$ , is the first base case reached, followed immediately by fibonacci(0). From that moment onwards, the flow of execution moves back up the left-most path while adding together the two corresponding child nodes. Effectively, this mirrors the iterative implementation in that the order of all computational steps are identical (cf., the "Hard at first Glance" example in Chapter 4 .

We added a keyword-only argument debug that allows the caller to print out a message every time a i was not in the memo.

In [27]:

fibonacci(12, debug=True)

fibonacci(12) is calculated
fibonacci(11) is calculated
fibonacci(10) is calculated
fibonacci(9) is calculated
fibonacci(8) is calculated
fibonacci(7) is calculated
fibonacci(6) is calculated
fibonacci(5) is calculated
fibonacci(4) is calculated
fibonacci(3) is calculated
fibonacci(2) is calculated

Out[27]:

Now, calling fibonacci() has the side effect of growing the memo in the global scope. So, subsequent calls to fibonacci() need not calculate any Fibonacci number with an index i smaller than the maximum i used so far. Because of that, this fibonacci() is not a pure function.

In [28]:

fibonacci(12, debug=True)  # no more recursive calls needed

Out[28]:

In [29]:

memo

Out[29]:

{0: 0,
 1: 1,
 2: 1,
 3: 2,
 4: 3,
 5: 5,
 6: 8,
 7: 13,
 8: 21,
 9: 34,
 10: 55,
 11: 89,
 12: 144}

Efficiency of Algorithms (continued)¶

With memoization, the recursive fibonacci() implementation is as fast as its iterative counterpart, even for large numbers.

The %%timeit magic, by default, runs a code cell seven times. Whereas in the first run, new Fibonacci numbers (i.e., intermediate results) are added to the memo, fibonacci() has no work to do in the subsequent six runs. %%timeit realizes this and tells us that "an intermediate result is being cached."

In [30]:

%%timeit -n 1
fibonacci(99)

The slowest run took 252.65 times longer than the fastest. This could mean that an intermediate result is being cached.
6.68 µs ± 15.8 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [31]:

%%timeit -n 1
fibonacci(999)

The slowest run took 3603.20 times longer than the fastest. This could mean that an intermediate result is being cached.
85.1 µs ± 208 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)

The iterative implementation still has an advantage as the RecursionError shows for larger i.

In [32]:

%%timeit -n 1
fibonacci(9999)

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
Cell In[32], line 1
----> 1 get_ipython().run_cell_magic('timeit', '-n 1', 'fibonacci(9999)\n')

File ~/Repositories/intro-to-python/.venv/lib/python3.12/site-packages/IPython/core/interactiveshell.py:2541, in InteractiveShell.run_cell_magic(self, magic_name, line, cell)
   2539 with self.builtin_trap:
   2540     args = (magic_arg_s, cell)
-> 2541     result = fn(*args, **kwargs)
   2543 # The code below prevents the output from being displayed
   2544 # when using magics with decorator @output_can_be_silenced
   2545 # when the last Python token in the expression is a ';'.
   2546 if getattr(fn, magic.MAGIC_OUTPUT_CAN_BE_SILENCED, False):

File ~/Repositories/intro-to-python/.venv/lib/python3.12/site-packages/IPython/core/magics/execution.py:1189, in ExecutionMagics.timeit(self, line, cell, local_ns)
   1186         if time_number >= 0.2:
   1187             break
-> 1189 all_runs = timer.repeat(repeat, number)
   1190 best = min(all_runs) / number
   1191 worst = max(all_runs) / number

File /usr/lib64/python3.12/timeit.py:208, in Timer.repeat(self, repeat, number)
    206 r = []
    207 for i in range(repeat):
--> 208     t = self.timeit(number)
    209     r.append(t)
    210 return r

File ~/Repositories/intro-to-python/.venv/lib/python3.12/site-packages/IPython/core/magics/execution.py:173, in Timer.timeit(self, number)
    171 gc.disable()
    172 try:
--> 173     timing = self.inner(it, self.timer)
    174 finally:
    175     if gcold:

File <magic-timeit>:1, in inner(_it, _timer)

Cell In[26], line 17, in fibonacci(i, debug)
     14 if debug:  # added for didactical purposes
     15     print(f"fibonacci({i}) is calculated")
---> 17 recurse = fibonacci(i - 1, debug=debug) + fibonacci(i - 2, debug=debug)
     18 memo[i] = recurse
     19 return recurse

Cell In[26], line 17, in fibonacci(i, debug)
     14 if debug:  # added for didactical purposes
     15     print(f"fibonacci({i}) is calculated")
---> 17 recurse = fibonacci(i - 1, debug=debug) + fibonacci(i - 2, debug=debug)
     18 memo[i] = recurse
     19 return recurse

    [... skipping similar frames: fibonacci at line 17 (2969 times)]

Cell In[26], line 17, in fibonacci(i, debug)
     14 if debug:  # added for didactical purposes
     15     print(f"fibonacci({i}) is calculated")
---> 17 recurse = fibonacci(i - 1, debug=debug) + fibonacci(i - 2, debug=debug)
     18 memo[i] = recurse
     19 return recurse

RecursionError: maximum recursion depth exceeded

This exception occurs as Python must keep track of every function call until it has returned, and with large enough i, the recursion tree above grows too big. By default, Python has a limit of up to 3000 simultaneous function calls. So, theoretically this exception is not a bug in the narrow sense but the result of a "security" measure that is supposed to keep a computer from crashing. However, practically most high-level languages like Python incur such an overhead cost: It results from the fact that someone (i.e., Python) needs to manage each function call's local scope. With the for-loop in the iterative version, we do this managing as the programmer.

We could "hack" a bit with Python's default configuration using the sys module in the standard library and make it work. As we are good citizens, we reset everything to the defaults after our hack is completed.

In [33]:

import sys

In [34]:

old_recursion_limit = sys.getrecursionlimit()

In [35]:

old_recursion_limit

Out[35]:

In [36]:

sys.setrecursionlimit(99999)

Computational speed is not the problem here.

In [37]:

%%timeit -n 1
fibonacci(9999)

The slowest run took 50532.39 times longer than the fastest. This could mean that an intermediate result is being cached.
1.21 ms ± 2.97 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [38]:

sys.setrecursionlimit(old_recursion_limit)