Lecture 4 - Compound data types

Lecture 4 - Compound data types#

Today we will practice working with sequence data types:

Tuple (defined using ())
- ordered sequence of elements
- immutable
- can handle mixed data types
List (defined uing [])
- ordered sequence of elements
- mutable
- can handle mixed data types
Set (defined using set() if empty, otherwise {})
- unordered sequence of unique elements
- the set itself may be modified, but its elements must be of an immutable type
- can handle mixed data types
Dictionary (defined using dict() or {key: value})
- ordered sequence of key:value pairs (Python3). In Python2 they are unordered
- mutable
- values can be any data type
- keys can be of any immutable type (int, str, float - I do not recommend float because the are difficult to compare) and MUST BE unique

Some important concepts to understand:

All compound data types are iterables – we can iterate through them (see comment below)
Mutable versus immutable objects
- mutable: allows you to change their value or data without affect the objects identity
- immutable: does not allow these kinds of changes
Each compound data type has various methods (will come back to that in lecture 6) that you can apply on them. append and extend are examples for lists.

Iterable versus iterator in Python:

An iterable is an object that contains a countable number of values. It is an object that can be iterated upon, meaning that you can traverse through all its elements.
- Examples: str, list, dict, set, tuple
An iterator is an object which implements the iterator protocol, which consist of the special methods __iter__() and __next__()
- Examples: zip, enumerate

# Run these commands to get information about the object type list and zip
# You will see that zip implements iter() and next() whereas a list does not. 
# You may need to open the full output data in a text editor in order to be able to see it.

help(list)
help(zip)

Help on class list in module builtins:

class list(object)
 |  list(iterable=(), /)
 |  
 |  Built-in mutable sequence.
 |  
 |  If no argument is given, the constructor creates a new empty list.
 |  The argument must be an iterable if specified.
 |  
 |  Methods defined here:
 |  
 |  __add__(self, value, /)
 |      Return self+value.
 |  
 |  __contains__(self, key, /)
 |      Return key in self.
 |  
 |  __delitem__(self, key, /)
 |      Delete self[key].
 |  
 |  __eq__(self, value, /)
 |      Return self==value.
 |  
 |  __ge__(self, value, /)
 |      Return self>=value.
 |  
 |  __getattribute__(self, name, /)
 |      Return getattr(self, name).
 |  
 |  __getitem__(...)
 |      x.__getitem__(y) <==> x[y]
 |  
 |  __gt__(self, value, /)
 |      Return self>value.
 |  
 |  __iadd__(self, value, /)
 |      Implement self+=value.
 |  
 |  __imul__(self, value, /)
 |      Implement self*=value.
 |  
 |  __init__(self, /, *args, **kwargs)
 |      Initialize self.  See help(type(self)) for accurate signature.
 |  
 |  __iter__(self, /)
 |      Implement iter(self).
 |  
 |  __le__(self, value, /)
 |      Return self<=value.
 |  
 |  __len__(self, /)
 |      Return len(self).
 |  
 |  __lt__(self, value, /)
 |      Return self<value.
 |  
 |  __mul__(self, value, /)
 |      Return self*value.
 |  
 |  __ne__(self, value, /)
 |      Return self!=value.
 |  
 |  __repr__(self, /)
 |      Return repr(self).
 |  
 |  __reversed__(self, /)
 |      Return a reverse iterator over the list.
 |  
 |  __rmul__(self, value, /)
 |      Return value*self.
 |  
 |  __setitem__(self, key, value, /)
 |      Set self[key] to value.
 |  
 |  __sizeof__(self, /)
 |      Return the size of the list in memory, in bytes.
 |  
 |  append(self, object, /)
 |      Append object to the end of the list.
 |  
 |  clear(self, /)
 |      Remove all items from list.
 |  
 |  copy(self, /)
 |      Return a shallow copy of the list.
 |  
 |  count(self, value, /)
 |      Return number of occurrences of value.
 |  
 |  extend(self, iterable, /)
 |      Extend list by appending elements from the iterable.
 |  
 |  index(self, value, start=0, stop=9223372036854775807, /)
 |      Return first index of value.
 |      
 |      Raises ValueError if the value is not present.
 |  
 |  insert(self, index, object, /)
 |      Insert object before index.
 |  
 |  pop(self, index=-1, /)
 |      Remove and return item at index (default last).
 |      
 |      Raises IndexError if list is empty or index is out of range.
 |  
 |  remove(self, value, /)
 |      Remove first occurrence of value.
 |      
 |      Raises ValueError if the value is not present.
 |  
 |  reverse(self, /)
 |      Reverse *IN PLACE*.
 |  
 |  sort(self, /, *, key=None, reverse=False)
 |      Sort the list in ascending order and return None.
 |      
 |      The sort is in-place (i.e. the list itself is modified) and stable (i.e. the
 |      order of two equal elements is maintained).
 |      
 |      If a key function is given, apply it once to each list item and sort them,
 |      ascending or descending, according to their function values.
 |      
 |      The reverse flag can be set to sort in descending order.
 |  
 |  ----------------------------------------------------------------------
 |  Class methods defined here:
 |  
 |  __class_getitem__(...) from builtins.type
 |      See PEP 585
 |  
 |  ----------------------------------------------------------------------
 |  Static methods defined here:
 |  
 |  __new__(*args, **kwargs) from builtins.type
 |      Create and return a new object.  See help(type) for accurate signature.
 |  
 |  ----------------------------------------------------------------------
 |  Data and other attributes defined here:
 |  
 |  __hash__ = None

Help on class zip in module builtins:

class zip(object)
 |  zip(*iterables) --> A zip object yielding tuples until an input is exhausted.
 |  
 |     >>> list(zip('abcdefg', range(3), range(4)))
 |     [('a', 0, 0), ('b', 1, 1), ('c', 2, 2)]
 |  
 |  The zip object yields n-length tuples, where n is the number of iterables
 |  passed as positional arguments to zip().  The i-th element in every tuple
 |  comes from the i-th iterable argument to zip().  This continues until the
 |  shortest argument is exhausted.
 |  
 |  Methods defined here:
 |  
 |  __getattribute__(self, name, /)
 |      Return getattr(self, name).
 |  
 |  __iter__(self, /)
 |      Implement iter(self).
 |  
 |  __next__(self, /)
 |      Implement next(self).
 |  
 |  __reduce__(...)
 |      Return state information for pickling.
 |  
 |  ----------------------------------------------------------------------
 |  Static methods defined here:
 |  
 |  __new__(*args, **kwargs) from builtins.type
 |      Create and return a new object.  See help(type) for accurate signature.

# Examples from lecture 4. 
from typing import Union

# "return" in a function always returns an object. When there are multiple values in the return statement, it returns a tuple 

def sum_and_difference(x: Union[float, int], y: Union[float, int])->tuple[Union[float, int], Union[float, int]]:
    """Calculate the sum and difference between two numbers

    Args:
        x (float | int): first number to use in calculation
        y (float | int): second number to use in calculation

    Returns:
        tuple[float | int, float | int]: tuple of sum and difference
    """
    sum = x + y
    difference = x - y
    return sum, difference

sum_and_diff = sum_and_difference(4,1)
print(sum_and_diff, type(sum_and_diff))

# Here we immediately unpack the tuple
sum, diff = sum_and_difference(4,1)
print(sum, diff, type(sum), type(diff))

(5, 3) <class 'tuple'>
5 3 <class 'int'> <class 'int'>

assert type(sum_and_diff) == tuple, error_message(type(sum_and_diff), tuple)
assert sum_and_diff == (5, 3), error_message(sum_and_diff, (5, 3))

# NOTE RERUN THESE CELLS TO NOT CONFUSE YOURSELF
# Write a 'for' loop using 'range' to generate a list of numbers from 1 to 10 called alist.

alist = []
for i in range(1, 11):
    alist.append(i)
    
print(alist)

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

assert type(alist) == list, error_message(type(alist), list)
expected = list(range(1,11))
assert alist == expected, f"{alist} != {expected}"

# NOTE RERUN THESE CELLS TO NOT CONFUSE YOURSELF
# Oh, we forgot to add the following numbers (see below) to the list. 
# Let us fix that with the built-in 'extend' method

forgot_start = [-1, 0]
forgot_end = [11, 12]

alist.extend(forgot_end)
print(forgot_start, alist)
forgot_start.extend(alist)
updated_list = forgot_start
print('Updated list: ', updated_list)

# Above we assigned the updated_list to forgot_start.
# Let us check what that means address-wise
 
print(hex(id(updated_list)), hex(id(forgot_start)))

# What happens to the elements of forgot_start if we change one of the elements in updated_list?
updated_list[0] = -2
print('Updated list with new first element: ', updated_list)

[-1, 0] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Updated list:  [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
0x7fba383dde40 0x7fba383dde40
Updated list with new first element:  [-2, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

assert type(alist) == list, error_message(type(alist), list)
expected = [i for i in range(1,13)]
assert alist == expected, f"{alist} != {expected}"

Indexing and slicing#

You can use indexing to access certain elements in the sequence data types.

Some examples with lists below:

alist[i] – returns the element of alist corresponding to index i
alist[-i] - returns the ith element from the end of the list. -1 being the last
alist[:] - returns a new list with all the elements (called cloning)
alist[i:j] - returns a new list with the elements from index i to index j-1
alist[:i] – returns a new list with all element before index i
alist[i:] – returns a new list with all elements corresponding to index i and onwards
alist[::2] – returns a new list with every second element
alist[::-1] - returns a new list with the reverse order of elements
alist[i:j:k] – returns a new list with every kth element between index i and j-1

NOTE The “returns” in all the above. In other words, a new list is outputted.

# The list used for the indexing examples

alist = [4, 2, 3, 5, 6, 1, 56, 3, 98, 10, 34, 65, 123]

# Given alist, extract the element corresponding to index 2. That is, replace None

alist_element = alist[2] 

assert alist_element == 3, error_message(alist_element, 3)

# Given alist, print the last element in the list. Replace None

alist_last = alist[-1] 

assert alist_last == 123, error_message(alist_last, 123)

# Given alist, extract the sublist between index 3 and 8. Replace None
alist_sublist = alist[3:8] 

assert alist_sublist == [5, 6, 1, 56, 3], error_message(alist_sublist, [5, 6, 1, 56, 3])

# Given alist, extract every 4th element. Replace None
alist_subsampling_four = alist[::4] 

assert alist_subsampling_four == [4, 6, 98, 123], error_message(alist_subsampling_four, [4, 6, 98, 123])

# Given alist, get a new list with the order of elements reversed. Replace None
alist_reversed = alist[::-1] 

assert alist_reversed == [123, 65, 34, 10, 98, 3, 56, 1, 6, 5, 3, 2, 4], error_message(alist_reversed, [123, 65, 34, 10, 98, 3, 56, 1, 6, 5, 3, 2, 4])

# Play around with examples on your own to make sure that you understand how it works and explore additional possibilities.

Iterables of iterables#

The compound data types can contain elements of any type. In other words, their elements could be another iterable. For example, list of lists are very useful in many cases.

Remember that some of the compound data types allow you to modify the elements (mutable), while others do not (immutable).

# Here we have a tuple_of_lists (list1, list2, list3). What happens if you attempt to change the 0-index element of the tuple?
# Recall that tuples are immutable objects
list1 = [1,2]
list2 = [3,4]
list3 = [5,6]

tuple_of_lists = (list1, list2, list3)

# Try the same but this time make it a list of lists. 
# Recall that lists are mutable objects.

list_of_lists = [list1, list2, list3]

Introducing iterable comprehensions#

Comprehensions in Python provide us with a short and concise way to construct new sequences (such as lists, set, dictionary etc.) using sequences which have been already defined.

Python supports four types:

List comprehensions
Set comprehensions
Dictionary comprehensions
Generator comprehensions (for more advanced course or self-study)
- In short, a generator is a function that returns an iterator using the yield statement instead of the return statement

Say for instance that you have a list of numbers and want to make a new list with the square of each of the numbers.

Instead of writing a for loop, you can use a list comprehension, which is much more compact.

The syntax

newlist = [expression for item in iterable if condition == True]

# Let's first take the example from above. Generate a list of numbers from 1 to 10.

alist = [x for x in range(1,11)]
print(alist)

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

assert type(alist) == list, error_message(type(alist), list)
expected = [i for i in range(1,11)]
assert alist == expected, f"{alist} != {expected}"

# Create a list called blist using a list comprehension which contains the squares of all the elements in alist

blist = [x * x for x in alist]
print(blist)

[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

expected = [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
assert blist == expected, f"{blist} != {expected}"

# But I only wanted the square of the even numbers. Let's name this list clist. 
# Combine list comprehensions and the modulus operator in order to filter

clist = [x * x for x in alist if x % 2 == 0]
print(clist)

[4, 16, 36, 64, 100]

expected = [4, 16, 36, 64, 100]
assert clist == expected, f"{clist} != {expected}"

# The iterable can also be a tuple (or any other iterable)

list_from_tuple = [x for x in (1,2,3,3)]
list_from_str = [x for x in 'COOL']

print(list_from_tuple)
print(list_from_str)

[1, 2, 3, 3]
['C', 'O', 'O', 'L']

# Test what happens if we do the similar set comprehension?
# Replace None to make test_a and test_b True

set_from_tuple = {x for x in (1,2,3,3)}
set_from_str = {x for x in 'COOL'}

test_a = set_from_tuple == {1, 2, 3} 
test_b = set_from_str == {'C', 'O', 'L'} 

assert test_a and test_b == True

# Let us try to make a nested list comprehension as a way to generate a list of lists
# Make a list (named nested_list) that is five elements long where each element is a list of integers from 0 to 4

nested_list = [[x for x in range(5)] for y in range(5)]
print(nested_list)

[[0, 1, 2, 3, 4], [0, 1, 2, 3, 4], [0, 1, 2, 3, 4], [0, 1, 2, 3, 4], [0, 1, 2, 3, 4]]

expected = [[0, 1, 2, 3, 4], [0, 1, 2, 3, 4], [0, 1, 2, 3, 4], [0, 1, 2, 3, 4], [0, 1, 2, 3, 4]]
assert nested_list == expected, f"{nested_list} != {expected}"

Generators#

We can do other cool stuff using so-called generators. We will not dive into details here, I just want to show you the use of two such examples.

Two very useful generators:

zip() - takes in iterables as arguments and returns an iterator of tuples.
- you can think of it as a way of travesing multiple iterables at the same time. If the iterables have different number of elements, the shortest will set the number of possible iterations!!!
- it returns a tuple. You can unpack the tuple into two variables immediately
enumerate() - takes in an iterable as argument and returns a tuple containing a count index (by default starting from 0) and the value obtained from iterating over the iterable

Below we are going to try them out on lists to generate dictionaries

# Print the output of looping over 'zip' applied to alist and blist of different length
# You should see that the shortest list will limit the number of possible iterations.

list_len_two = [2, 3]
list_len_three = [1, 2, 3]

for element in zip(list_len_two, list_len_three):
    print(element)

(2, 1)
(3, 2)

# Now assume that we have two lists containing associated information. 
# One could contain the names of students, the other could be their age.  
names = ['Alice', 'Bob', 'Charlie']
ages = [24, 40, 30]

# Use 'zip' to create a dictionary named student_dict with name: age value pairs.

student_dict = {}
for name, age in zip(names, ages):
    student_dict[name] = age

print(student_dict)

{'Alice': 24, 'Bob': 40, 'Charlie': 30}

expected = {'Alice': 24, 'Bob': 40, 'Charlie': 30}
assert student_dict == expected, f"{student_dict} != {expected}"

# We can use a dictionary comprehension to make it a one-liner
# Try to implement this in variable name student_dict_from_dict_comprehension

student_dict_from_dict_comprehension = {name: age for name, age in zip(names, ages)}

expected = {'Alice': 24, 'Bob': 40, 'Charlie': 30}
assert student_dict_from_dict_comprehension == expected, f"{student_dict_from_dict_comprehension} != {expected}"

# Or even shorter using the 'dict' mapping object directly on 'zip'
# This was to demonstrate more advanced shortcuts. Do not worry too about it at this point, just be curiuos (=explore) the many possibilities.

student_dict_from_zipgenerator = dict(zip(names, ages))
print(student_dict_from_zipgenerator)

{'Alice': 24, 'Bob': 40, 'Charlie': 30}

Dictionaries#

# Write a code that counts the number of times a given letter occurs in a string and returns it as a dictionary called dict_letters
# string.lower() or string.upper() may come in handy. Make sure that the code can handle spaces and punctuation

def count_letters(string: str)->dict:
    """Counts letters in string

    Args:
        string (str): string to be analyzed

    Returns:
        dict_letters: dictionary with key, value being letter, #occurrences
    """
    dict_letters = {}
    cleaned_string = ''
    for char in string.lower():
        if char in 'abcdefghijklmnopqrstuvwxyz':
            cleaned_string += char
    for char in cleaned_string:
        if char not in dict_letters:
            dict_letters[char] = 1
        else:
            dict_letters[char] += 1
    return dict_letters

test_string = 'From zero to Python hero!'
calculated = count_letters(test_string)
expected = {'f': 1, 'r': 3, 'o': 5, 'm': 1, 'z': 1, 'e': 2, 't': 2, 'p': 1, 'y': 1, 'h': 2, 'n': 1}
assert calculated == expected, f"{calculated} != {expected}"

test_string2 = "CCGGAAGAGCTTACTTAGGC" 
calculated = count_letters(test_string2)
expected = {"a": 5, "c": 5, "g": 6, "t": 4}
assert calculated == expected, f'{calculated} != {expected}'

Sorting a dictionary by values#

Knowing how to sort dictionaries according to their values can be very helpful.

We will be looking at two methods for sorting:

Using sorted() together with itemgetter() from the operator module (from operator import itemgetter)
Using sorted() together with lambda function

The built-in sorted() function builds a new sorted object for any iterable (list, dict, …)

has a key parameter to specify a function (should return a key to be used for sorting) to be called on each element (i.e., function takes single argument) prior to comparison

Read more here: https://docs.python.org/3/howto/sorting.html

Let us look at the use of both options and use the time module (import time) to print how long time it takes to do the sortings.

test_list = [{'name': 'Nanna', 'age': 37},
             {'name': 'Magnus', 'age': 11},
             {'name': 'Annett', 'age': 66},
             {'name': 'Kenneth', 'age': 53},
             {'name': 'Allan', 'age': 45},
             {'name': 'Jakob', 'age': 28},
             {'name': 'Noelle', 'age': 8},
             {'name': 'Hjalte', 'age': 8},
             {'name': 'Annabel', 'age': 7},
             {'name': 'Evi', 'age': 0},
             {'name': 'Geo', 'age': 2}
             ]

# First the itemgetter implementation
from operator import itemgetter
import time

start_time = time.time()
# List sorted by age
print(sorted(test_list, key=itemgetter("age")))
end_time = time.time()
print('time elapsed (in sec): ', end_time - start_time)

start_time = time.time()
# List sorted by age in reverse order
print(sorted(test_list, key=itemgetter("age"), reverse=True))
end_time = time.time()
print('time elapsed (in sec): ', end_time - start_time)

[{'name': 'Evi', 'age': 0}, {'name': 'Geo', 'age': 2}, {'name': 'Annabel', 'age': 7}, {'name': 'Noelle', 'age': 8}, {'name': 'Hjalte', 'age': 8}, {'name': 'Magnus', 'age': 11}, {'name': 'Jakob', 'age': 28}, {'name': 'Nanna', 'age': 37}, {'name': 'Allan', 'age': 45}, {'name': 'Kenneth', 'age': 53}, {'name': 'Annett', 'age': 66}]
time elapsed (in sec):  4.982948303222656e-05
[{'name': 'Annett', 'age': 66}, {'name': 'Kenneth', 'age': 53}, {'name': 'Allan', 'age': 45}, {'name': 'Nanna', 'age': 37}, {'name': 'Jakob', 'age': 28}, {'name': 'Magnus', 'age': 11}, {'name': 'Noelle', 'age': 8}, {'name': 'Hjalte', 'age': 8}, {'name': 'Annabel', 'age': 7}, {'name': 'Geo', 'age': 2}, {'name': 'Evi', 'age': 0}]
time elapsed (in sec):  3.528594970703125e-05

# And now to lambda functions
import time

start_time = time.time()
# List sorted by age
print(sorted(test_list, key = lambda i: i['age']))
end_time = time.time()
print('time elapsed (in sec): ', end_time - start_time)

start_time = time.time()
# List sorted by age in reverse order
print(sorted(test_list, key= lambda i: i['age'], reverse=True))
end_time = time.time()
print('time elapsed (in sec): ', end_time - start_time)

[{'name': 'Evi', 'age': 0}, {'name': 'Geo', 'age': 2}, {'name': 'Annabel', 'age': 7}, {'name': 'Noelle', 'age': 8}, {'name': 'Hjalte', 'age': 8}, {'name': 'Magnus', 'age': 11}, {'name': 'Jakob', 'age': 28}, {'name': 'Nanna', 'age': 37}, {'name': 'Allan', 'age': 45}, {'name': 'Kenneth', 'age': 53}, {'name': 'Annett', 'age': 66}]
time elapsed (in sec):  5.4836273193359375e-05
[{'name': 'Annett', 'age': 66}, {'name': 'Kenneth', 'age': 53}, {'name': 'Allan', 'age': 45}, {'name': 'Nanna', 'age': 37}, {'name': 'Jakob', 'age': 28}, {'name': 'Magnus', 'age': 11}, {'name': 'Noelle', 'age': 8}, {'name': 'Hjalte', 'age': 8}, {'name': 'Annabel', 'age': 7}, {'name': 'Geo', 'age': 2}, {'name': 'Evi', 'age': 0}]
time elapsed (in sec):  3.886222839355469e-05

Increasing efficiency of fibonacci using dictionaries#

Last time we implemented a function fibonacci to compute Fibonacci numbers. I have pasted my version in below.

We did so using recursion. We saw that the number of calls to the fibonacci grew very quickly and a lot of numbers have to be recalculated.

I try to demonstrate this below using my original implementation.

# Run the code below to see the individual fibonacci calls.

def fibonacci(x: int) -> int:
    """Calculate the next Fibonacci number for iteration n
    assuming x >= 0

    Args:
        x (int): iteration x

    Returns:
        int: Fibonacci of x, number of fibonacci calls
    """    
    global number_fibonacci_calls
    print('Calling fibonacci with x: ', x)
    number_fibonacci_calls += 1
    if x == 0 or x == 1:
        return 1
    else:
        return fibonacci(x-1) + fibonacci(x-2)
    
number_fibonacci_calls = 0
fibonacci(12)
print("Number of fibonacci calls with original implementation: ", number_fibonacci_calls)

Calling fibonacci with x:  12
Calling fibonacci with x:  11
Calling fibonacci with x:  10
Calling fibonacci with x:  9
Calling fibonacci with x:  8
Calling fibonacci with x:  7
Calling fibonacci with x:  6
Calling fibonacci with x:  5
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  5
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  6
Calling fibonacci with x:  5
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  7
Calling fibonacci with x:  6
Calling fibonacci with x:  5
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  5
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  8
Calling fibonacci with x:  7
Calling fibonacci with x:  6
Calling fibonacci with x:  5
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  5
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  6
Calling fibonacci with x:  5
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  9
Calling fibonacci with x:  8
Calling fibonacci with x:  7
Calling fibonacci with x:  6
Calling fibonacci with x:  5
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  5
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  6
Calling fibonacci with x:  5
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  7
Calling fibonacci with x:  6
Calling fibonacci with x:  5
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  5
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  10
Calling fibonacci with x:  9
Calling fibonacci with x:  8
Calling fibonacci with x:  7
Calling fibonacci with x:  6
Calling fibonacci with x:  5
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  5
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  6
Calling fibonacci with x:  5
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  7
Calling fibonacci with x:  6
Calling fibonacci with x:  5
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  5
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  8
Calling fibonacci with x:  7
Calling fibonacci with x:  6
Calling fibonacci with x:  5
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  5
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  6
Calling fibonacci with x:  5
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  4
Calling fibonacci with x:  3
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Calling fibonacci with x:  1
Calling fibonacci with x:  2
Calling fibonacci with x:  1
Calling fibonacci with x:  0
Number of fibonacci calls with original implementation:  465

As you just saw, fibonacci is called many times with the same argument.

This is double/triplet/quadruple/… work!!! We can do better than that using dictionaries because they allow us to store previously calculated values and then check if they have already been calculated.

New speedy algorithm:

First do a look-up in the dictionary in case of already calculated values
- Remember that at the start you have the base values in the dictionary
- If so, use the value in the dictionary (instead of recalculating it)
- If not, calculate the missing value and the add it to the dictionary

# Write the new speedy fibonacci function. Print the number of fibonacci calls and the final dictionary

def fibonacci_speedy(x: int, d: dict) -> int:
    """Calculate the next Fibonacci number for iteration n
    assuming x >= 0

    Args:
        x (int): iteration x
        d (dict): dictionary to hold previously calculated values

    Returns:
        int: Fibonacci of x, number of fibonacci calls
    """    
    global number_fibonacci_calls
    if x in d:
        return d[x]
    else:
        number_fibonacci_calls += 1
        fib_n_m1 = fibonacci_speedy(x-1, d)
        d[x-1] = fib_n_m1 
        fib_n_m2 = fibonacci_speedy(x-2, d) 
        d[x-2] = fib_n_m2
        return fib_n_m1 + fib_n_m2

fibonacci_dict = {0:1, 1:1}
number_fibonacci_calls = 0
fibonacci_speedy(12, fibonacci_dict)
print("Number of fibonacci calls with speedy implementation: ", number_fibonacci_calls)
print('The final dictionary: ', fibonacci_dict)

Number of fibonacci calls with speedy implementation:  11
The final dictionary:  {0: 1, 1: 1, 2: 2, 3: 3, 4: 5, 5: 8, 6: 13, 7: 21, 8: 34, 9: 55, 10: 89, 11: 144}

fibonacci_dict = {0:1, 1:1}
assert fibonacci_speedy(12, fibonacci_dict) == 233, error_message(fibonacci_speedy(12, fibonacci_dict), 233)

Mutables versus immutables and objects#

This is an introductory course to Python, so we will not dive deep into memory.

Yet, you need to understand:

Everything in Python is an object
Mutable vs immutable objects
- mutable: allows you to change their value or data without affect the objects identity
  - Examples: dict, list, set
- immutable: does not allow these kinds of changes
  - Examples: int, float, bool, str, tuple
Variables/names in Python

Keeping track of memory addressed

Use id() to keep check the memory address of a given object
Use hex() around id()to get the memory address as a hexidecimal number

# First, an immutable type: 
# Let us recall what happens when adding 1 to an integer.
# We are going to keep track of the object id by printing its memory address

i = 4
print('i before adding 1: ', i)
print('memory address of i before adding 1: ', hex(id(i)))
i += 1
print('i after adding 1: ', i)
print('memory address of i after adding 1: ', hex(id(i)))

# As you will see, the += 1 operation reassigned i. So now it has a different memory address.
# This is because it is immutable (=cannot be changed in place!)

i before adding 1:  4
memory address of i before adding 1:  0x7fba8802e990
i after adding 1:  5
memory address of i after adding 1:  0x7fba8802e9b0

# Next, a mutable type:
# Let us see what happens when appending 1 to a list?

alist = [2, 4]
print('alist before appending 1: ', alist)
print('memory address of alist before appending 1: ', hex(id(alist)))

alist.append(1)
print('alist after appending 1: ', alist)
print('memory address of alist after appending 1: ', hex(id(alist)))

# As you will see, the append operation DID NOT change the alist!
# This is because a list is mutable (=CAN BE changed in place!)

alist before appending 1:  [2, 4]
memory address of alist before appending 1:  0x7fba383fd200
alist after appending 1:  [2, 4, 1]
memory address of alist after appending 1:  0x7fba383fd200

# Now comes a tricky case.
# What happens if we add 1 to each element in the list?
# Now we need to recall that while a list is mutable, the numbers (int or float) are immutable.
# This gives rise to the following behavior.

alist = [2, 4]
print('alist before adding 1: ', alist)
print('memory address of alist before adding 1: ', hex(id(alist)))
print([hex(id(x)) for x in alist])

for i in range(len(alist)):
    alist[i] += 1

print('alist after adding 1: ', alist)
print('memory address of alist after adding 1: ', hex(id(alist)))
print([hex(id(x)) for x in alist])

# As you will see, the list maintained the same memory address following the addition - because it is mutable.
# However, the += 1 operation binds each element to a new value because the elements (int in this case) were immutable.

alist before adding 1:  [2, 4]
memory address of alist before adding 1:  0x7fba58c91600
['0x7fba8802e950', '0x7fba8802e990']
alist after adding 1:  [3, 5]
memory address of alist after adding 1:  0x7fba58c91600
['0x7fba8802e970', '0x7fba8802e9b0']

An extension of the above discussion to functions#

Why do I show you this?

Because this is very common surprise (a negative one, producing unexpected results) when you are new to programming in Python!

# Let us first recall the behavior of an immutable data type inside a function.
# Here we consider an integer argument that is incremented by one by the function 'increment_print'
# Study the code below and print the output of inputting i = 5

def increment_print(i: int):
    """Increments number by 1 and prints its value

    Args:
        i (int): number to increment
    """    
    i += 1
    print('Print i inside function call after increment: ', i)

i = 5
print('Print i before and outside function call:     ', i)
increment_print(i)
print('Print i after and outside function call:      ', i)

# What you should see is that i defined globally outside the function remains the same before and after the function call.
# The reason being: It is immutable!

Print i before and outside function call:      5
Print i inside function call after increment:  6
Print i after and outside function call:       5

# Now let us see what happens, if we write a function that does a similar thing but on a mutable data type.
# We are going to use a list and iterate over its elements
# Study the code below and print the output of inputting alist = [2,3]

def list_append_print(blist: list):
    """Appends 1 to the list and prints it

    Args:
        blist (list): list of integers
    """    
    blist.append(1)
    print('Print blist inside function call after increment: ', blist)

alist = [2,3]
print('Print alist before and outside function call:     ', alist)
list_append_print(alist)
print('Print alist after and outside function call:      ', alist)

# What you should see is that the scope of the blist INSIDE the function affected the value of alist OUTSIDE the function!!! 
# This happened without ever returning anything from the function or using global (for global scope) in the function!

Print alist before and outside function call:      [2, 3]
Print blist inside function call after increment:  [2, 3, 1]
Print alist after and outside function call:       [2, 3, 1]

# Now let us see what happens, if we write a function that does a similar thing but on a mutable data type.
# We are going to use a list and iterate over its elements
# Study the code below and print the output of inputting alist = [2,3]

def list_increment_print(alist: list):
    """Increments the integers of a list by 1 and prints the list

    Args:
        alist (list): list of integers
    """    
    for i in range(len(alist)):
        alist[i] += 1
    print('alist inside function after increment: ', alist)

alist = [2,3]
print('Before function call')
print('Memory ID of alist:    ', hex(id(alist)))
for i in range(len(alist)):
    print(f'Memory ID of alist[{i}]: ', hex(id(alist[i])))
print('alist outside function call:           ', alist)

print('-----------')
list_increment_print(alist)

print('-----------')
print('After function call')
print('alist outside function call:           ', alist)
print('Memory ID of alist:    ', hex(id(alist)))
for i in range(len(alist)):
    print(f'Memory ID of alist[{i}]: ', hex(id(alist[i]))) 

# What you should see is that the memory locations of the elements of the lists have been changed because the elements were immutable
# However, the memory address of the list remains the same because it is mutable.

Before function call
Memory ID of alist:     0x7fba58c83540
Memory ID of alist[0]:  0x7fba8802e950
Memory ID of alist[1]:  0x7fba8802e970
alist outside function call:            [2, 3]
-----------
alist inside function after increment:  [3, 4]
-----------
After function call
alist outside function call:            [3, 4]
Memory ID of alist:     0x7fba58c83540
Memory ID of alist[0]:  0x7fba8802e970
Memory ID of alist[1]:  0x7fba8802e990