Referecing, Data Structures and Advanced Functions#
Agenda#
Mutable vs. immutableFunctions vs. methodsData structures
|
Python references#
Assigning a variable in Python creates:
An object storing the value
A name variable holding a reference to the object.
Assigning a new variable to an existing variable copies the reference
Name variables can be redirected to point new objects
List references#
Example#
a=[1,2,3]
b=a
a.append(4)
print(a)
print(b)
[1, 2, 3, 4]
[1, 2, 3, 4]
Differnet kinds of functions#
Methods:#
Functions which are members of specific types (remember list’s methods from previous recitation)#
Call by: variable_name.method_name(arguments)
Examples:
“method-like” syntax
“function-like” syntax
my_string.upper()
str.upper(my_string)
my_list.append(7)
list.append(my_list, 7)
method-like == Object-Oriented. In a few weeks from now…
Write variable_name. Then type tab to get the list of variable members (press tab to choose one)
Built-in functions (colored in PyCharm).#
e.g., abs len
Data structures#
Tuples#
A tuple is just like a list, only it is immutable.
Syntax: parentheses instead brackets!
r = ('Rick', 'Sanchez', 'C', 137)
print(r)
('Rick', 'Sanchez', 'C', 137)
print(r[0])
print(r[-1])
print(r[1:3])
Rick
137
('Sanchez', 'C')
r[0]='Morty'
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
Cell In[5], line 1
----> 1 r[0]='Morty'
TypeError: 'tuple' object does not support item assignment
Dictionaries#
A dictionary maps keys to values.
Keys aren’t necessarily of the same type, and so are values.
# Define a new dictionary
rick_dict = {'Series': 137, 'Comic-book': 132}
print(rick_dict)
{'Series': 137, 'Comic-book': 132}
Add (or replace) a pair:#
rick_dict['Series'] = 137
print(rick_dict)
{'Series': 137, 'Comic-book': 132}
What is the values of ricks?#
print(rick_dict['Series'])
137
print(rick_dict['Comic-book'])
132
print(rick_dict['comic-book'])
---------------------------------------------------------------------------
KeyError Traceback (most recent call last)
Cell In[10], line 1
----> 1 print(rick_dict['comic-book'])
KeyError: 'comic-book'
Check if a key is in dict:#
'Series' in rick_dict
What can be used as a key?#
rick_dict[["evil", "tiny"]] = 99
print(rick_dict)
Immutable types only!#
Strings, numbers, booleans, tuples…
If a tuple contains ANY mutable objects (either directly or indirectly), it cannot be used as a key
rick_dict[("cool", "evil")] = 999
print(rick_dict)
rick_dict[("cool", "evil", ["tiny"])] = 9
Common Dictionary methods#
Method\(~~~~~~~~~~~~~~~\) |
Description |
|---|---|
dict.get(k, [d]) |
Returns dict[k] if dict has the key k, otherwise d (default: d=None) |
k in dict |
Returns True if dict has a key k, otherwise False (The same as with lists, strings, tuples). |
dict.pop(k,[d]) |
Removes from dict the specified (key, value) pair with key k, and returns its value. If k is not in dict, returns d. If d is not given and k is not in dict, an error is raised |
dict.keys() |
Iterable view of dict’s keys in arbitrary order |
dict.values() |
Iterable view of dict’s values in arbitrary order |
dict.items() |
Iterable view of dict’s (key, value) pairs in arbitrary order |
dict.update([other]) |
Updates dict with the (key, value) pairs from other (another dictionary object or an iterable of (key, value) pairs). Returns None. |
dict.copy() |
Creates a shallow copy of dict (constructs a new dictionary, and inserts references to the original keys/values) |
Arguments in square brackets are optional
See more: https://docs.python.org/3/library/stdtypes.html#dict
Examples for Dictionary usage#
Example 1: sparse matrix#
In this matrix there are only 3 non-zero entries.
Saving all zeros in a list is a waste of space.
As a dict: A key is a tuple indicating the row-column pair (i,j) whereas a value is the non-zero entry.
matrix = [[0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 2, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 3, 0]] # Long!
print(matrix[1][2])
print(matrix[0][3])
matrix = {(0, 3): 1, (2, 1): 2, (4, 3): 3} # Shorter!
print(matrix.get((1,2),0))
print(matrix.get((0,3),0))
Example 2: pangrams#
A pangram is a sentence that contains each letter of the English alphabet at least once.#
Write a function that determines if a sentence is a pangram:#
Using list
Using dict
Implementation using list#
def is_pangram_list(s):
l = [False]*26
for char in s:
if char.isalpha():
l[ord(char.lower())-97] = True
return all(l)
Implementation using dict#
def is_pangram_dict(s):
d = {}
for char in s:
if char.isalpha():
d[char.lower()] = True
return len(d) == 26
s = "The quick brown fox jumps over the lazy dog"
print(is_pangram_dict(s))
print(is_pangram_list(s))
s = "The quick brown fox jumps over the lazy Dog"
print(is_pangram_dict(s))
print(is_pangram_list(s))
s = "The quick brown fox jumps over the lazy Rick"
print(is_pangram_dict(s))
print(is_pangram_list(s))
Is it better to use here dict instead of list?#
Which implementation is more intutive (remember, readability)?#
Not sure…
Which implementation prone to errors?#
Probably the list…
Which implementation is more efficient?#
Because the English alphabet has only 26 letters, we can also solve this with a list (initialized as: [False] 26).
However, if the alphabet had 10,000 letters dict would certainly be better.
Example 3: two dice#
Task#
Rolling two backgammon dice yield 36 possible combinations.
We would like to know the probability to get each sum of the two dice
In other words, the fraction of combinations that sums to a certain result.
Therefore:
Collect all the combinations for every possible sum.
Find the probability of getting each sum.
Solution#
Create the following data structure:
Each combination of two dice is a tuple.
All combinations are held in a dict, where the key is the sum of the combinations.
Each value in the dictionary is a list of tuples – that is, all combinations that sum to key.
General outline#
Generate dictionary.
For each key: print key, length of its list.
Pseudo-code#
rolls = {}
Loop with d1 from 1 to 6:
\(~~~~\)Loop with d2 from 1 to 6:
\(~~~~\)\(~~~~\)key ← d1 + d2
\(~~~~\)\(~~~~\)newTuple ← (d1, d2)
\(~~~~\)\(~~~~\)oldList ← dictionary value for key
\(~~~~\)\(~~~~\)newList ← oldList + newTuple
\(~~~~\)\(~~~~\)update: dictionary[key] ← newList
(2) implement pseudo-code (two dice)#
rolls = {}
for dice1 in range(1, 7): # first dice
for dice2 in range(1, 7): # second dice
dices = (dice1, dice2)
dices_sum = dice1 + dice2
combinations = rolls.get(dices_sum, [])
combinations.append(dices)
rolls[dices_sum] = combinations
for dices_sum, combinations in rolls.items():
print(dices_sum,"\t",len(combinations)/36)
Note that we do not actually need the tuples themselves.#
Can we improve this code?
Count number of combination instead of store them in lists
Memory efficient
rolls = {}
for dice1 in range(1, 7):
for dice2 in range(1, 7):
dices_sum = dice1 + dice2
rolls[dices_sum] = rolls.get(dices_sum,0)+1
for dices_sum, n_combinations in rolls.items():
print(dices_sum,"\t",n_combinations/36)
Self learning#
Dictionaries#
Exercise 1#
implement the function count_grades:
Input: A dictionary
gradesmapping from student name to grade.Goal: A dictionary counting how many student got each grade.
Example: count_grades({"Rick": 100, "Morty": 62, "Jerry": 62}) will return {100: 1, 62: 2}
# Solution 1
def count_grades(grades):
grades_counter = {}
for grade in grades.values():
if grade in grades_counter:
grades_counter[grade] += 1
else:
grades_counter[grade] = 1
# Solution 2 (better with get!)
def count_grades(grades):
grades_counter = {}
for grade in grades.values():
grades_counter[grade] = grades_counter.get(grade, 0) + 1
Exercise 2#
implement the function create_sparse_matrix:
Input: A matrix of numbers implemented by a list of lists.
Goal: A dictionary representing the sparse matrix (As shown above).
# Solution
def create_sparse_matrix(matrix):
matrix_dict = {}
for i in range(len(matrix)):
for j in range(len(matrix[i])):
if matrix[i][j] != 0:
matrix_dict[(i,j)] = matrix[i][j]
return matrix_dict
Advanced function examples#
Exercise 1#
implement the function students_with_max_grade:
Input: a list of grades, and a list of student names corresponding to the grades.
Output: a list of students with maximum grade
# Solution
def students_with_max_grade(grades, names):
'''return a list of the students with the maximal grade'''
max_grade = max(grades)
max_grade_students = []
for i in range(len(names)):
if grades[i] == max_grade:
max_grade_students.append(names[i])
return max_grade_students
grades = [100, 73, 71, 37]
names = ["Rick", "Morty", "Summer", "Jerry"]
print(students_with_max_grade(grades, names))
Exercise 2#
implement the function give_factor:
Input: a list of grades, a positive int representing a factor of y.
Goal: give non-failed grades a factor of y
No return statement!
Hint: Change the list inplace.
# Solution
def give_factor(grades, factor):
for i in range(len(grades)):
if grades[i] >= 60:
grades[i] += factor
if grades[i] > 100: # Can also be grades[i] > min(grade[i]+factor,100)
grades[i] = 100
grades = [100, 73, 71, 37]
print(grades)
give_factor(grades, 5)
print(grades)
Example 3#
What if we want to apply different factors?
Some factors are non linear, other factors may be applied to specific range of grades. For these reason, give_factor should be as general as possible, and the factor should be passed as a function
# Squared factor. e.g, 64->80, 81->90.
def sqrt_factor(grade):
if grade >= 60:
return int(10*(grade**0.5))
return grade
# Evil factor: Increases the average but none of the students is happy: Students who passes get the same grade. Students who failed get a higher grade, but they still fail.
def evil_factor(grade):
if grade < 59:
return 59
return grade
def give_factor(grades, factor_func):
for i in range(len(grades)):
grades[i] = min(factor_func(grades[i]), 100)
grades = [100, 73, 71, 37]
give_factor(grades, sqrt_factor)
print(grades)
give_factor(grades, evil_factor)
print(grades)