Dictionaries
Jake Shoudy
Oct 14, 2022
CSCI 110 - Lecture 23
Announcements
Project 2: Part 1
Build a simple search engine using 1D lists :)
Two notes:
Due tonight at 11:59pm!
Project 2: Part 2
More search engine things using 2D Lists :)
Will be released tomorrow!
Due Sunday October 23rd at 11:59pm
HW8
Posted on Ed
Big O Practice and Coding problems using Sets
Due next Wednesday (Oct 19th)
Exam 2
Wednesday 10/26
Will cover all material through Dictionaries (today) but with a focus on material since midterm #1
Grading Rubrics
All grading rubrics available on class website
https://drive.google.com/corp/drive/folders/1mHYxvMOzYoVztKcIc0qOg9dFSmIfw1WO
Reminder: Feedback
Recap
Sets
An unordered, and unique collection of values.
Lookup times are fast!
Create a set via:
my_set = set() or
my_set = {‘a’, ‘b’, ‘c’}
Set Operators
Set operation | Runtime |
s.add(item) | O(1) |
s.remove(item) | O(1) |
s.pop() | O(1) |
in operator (ex: item in s) | O(1) |
iteration (ex: for item in s) | O(n) |
s1.union(s2) * | O(s + t) where s and t are the size of each set |
s1.intersection(s2) * | O(min(s, t)) where s and t are the size of each set |
s1.difference(s2) * | O(t) where t is the size of the second set |
* operation does not mutate the set
Practice: Sets (adding and removing)
states = {‘WA’, ‘TN’, ‘OR’}
states.add(‘NC’)
len(states)
states.add(‘WA’)
states.remove(‘OR’)
states.remove(‘SC’)
states.pop()
{‘WA’, ‘TN’, ‘NC’, ‘OR’}
4
{‘WA’, ‘TN’, ‘NC’, ‘OR’}
{‘WA’, ‘TN’, ‘NC’}
KeyError
{‘WA’, ‘NC’} (removed a random one)
Practice: Sets (set math)
states_1 = {‘WA’, ‘NC’, ‘SC’, ‘OR’}
states_2 = {‘NC’, ‘TN’}
‘WA’ in states_1
states_1.union(states_2)
states_1.intersection(states_2)
states_1.difference(states_2)
states_2.difference(states_1)
True
{‘WA’, ‘TN’, ‘NC’, ‘SC’, ‘OR’}
{‘NC’}
{‘WA’, ‘SC’, ‘OR’}
{‘TN’}
Dictionaries
Intro to Dictionaries
Like physical dictionary, Python dictionaries are used for look-up
Physical dictionary: look up definitions for word
Programming dictionary: look up value using a key
Dictionaries
dictionary: ordered* collection of key:value pairs
Also known as map, because maps keys to values
prices = {'taco': 3.50, 'burrito': 8.00, 'enchilada': 6.99}
key
value
* ordered as of python 3.7 (2018) so be careful about your version. Maps are usually not ordered in most languages
Dictionaries
What?
unordered collection of key:value pairs
Why?
Useful for random access: accessing items out of order and key:value pairs
Lists are good for ordered data and for data without keys:value pairs
Syntax
cars = {
"Corolla": "Toyota",
"Accord": "Honda",
"Model 3": "Tesla",
"Prius": "Toyota"
}
Key
Value
Empty Dictionary
My_dictionary = dict() or…
my_dictionary = {}
Not a Set
empty_set = set()
Dictionaries, AKA...
Lookup tables
Maps
Hashmaps
Hash tables
Valid Types
What types can be in a dictionary?
movie_info = { 'title': 'Your Name', 'year': 2016, 'rating': 'PG', 'running_time': 112, 'actors': ['Ryunosuke Kamiki', 'Mone Kamishiraishi'], 'score': 96, } |
Dictionary operations
Indexing O(1)
cars = {
"Corolla": "Toyota",
"Accord": "Honda",
"Model 3": "Tesla",
"Prius": "Toyota"
}
Index into dictionary using keys
cars["Corolla"]
cars["Accord"]
cars["Model 3"]
cars["Prius"]
"Toyota"
"Honda"
"Tesla"
"Toyota"
Indexing O(1)
cars = {
"Corolla": "Toyota",
"Accord": "Honda",
"Model 3": "Tesla",
"Prius": "Toyota"
}
Index into dictionary using keys
cars["Corolla"]
cars["Accord"]
cars["Model 3"]
cars["Prius"]
cars["Rav4"]
"Toyota"
"Honda"
"Tesla"
"Toyota"
KeyError
cars = {
"Corolla": "Toyota",
"Accord": "Honda",
"Model 3": "Tesla",
"Prius": "Toyota"
}
Index into dictionary using keys
cars["Corolla"]
cars["Accord"]
cars["Model 3"]
cars["Prius"]
cars["Rav4"]
"Toyota"
"Honda"
"Tesla"
"Toyota"
Traceback (most recent call last):
File "<stdin>", line 5, in <module>
KeyError: 'Rav4'
Use in operator to check keys
cars = {
"Corolla": "Toyota",
"Accord": "Honda",
"Model 3": "Tesla",
"Prius": "Toyota"
}
Index into dictionary using keys
cars["Corolla"]
cars["Accord"]
cars["Model 3"]
cars["Prius"]
"Toyota"
"Honda"
"Tesla"
"Toyota"
in operator only checks keys of the dictionary.
if "Rav4" in cars:
print(cars["Rav4"])
in operator O(1)
To check whether a key exists, use in operator
in operator only checks keys of dictionary
On average runs in O(1) (constant time!)
if 'Rav4' in cars:
print(cars['Rav4'])
else:
print('who made the Rav4?')
Mutation: Add an item O(1)
Insert new key:value pairs by assigning to new keys
On average runs in O(1) (constant time!)
cars = {
"Corolla": "Toyota",
"Accord": "Honda",
"Model 3": "Tesla",
"Prius": "Toyota"
}
cars['Rav4'] = 'Toyota'
Mutation: Add an item O(1)
Insert new key:value pairs by assigning to new keys
On average runs in O(1) (constant time!)
cars = {
"Corolla": "Toyota",
"Accord": "Honda",
"Model 3": "Tesla",
"Prius": "Toyota",
"Rav4": "Toyota"
}
cars['Rav4'] = 'Toyota'
Mutation: Change an item O(1)
Keys are unique, so assigning to an existing one replaces it
On average runs in O(1) (constant time!)
cars = {
"Corolla": "Toyota",
"Accord": "Honda",
"Model 3": "Tesla",
"Prius": "Toyota",
"Rav4": "Toyota"
}
cars['Corolla'] = 'Ferrari'
Mutation: Change an item O(1)
cars = {
"Corolla": "Ferrari",
"Accord": "Honda",
"Model 3": "Tesla",
"Prius": "Toyota",
"Rav4": "Toyota"
}
Keys are unique, so assigning to an existing one replaces it
On average runs in O(1) (constant time!)
cars['Corolla'] = 'Ferrari'
Mutation: Delete an item O(1)
Delete key:value pairs by passing the key to pop()
On average runs in O(1) (constant time!)
cars = {
"Corolla": "Ferrari",
"Accord": "Honda",
"Model 3": "Tesla",
"Prius": "Toyota",
"Rav4": "Toyota"
}
cars.pop('Model 3')
Mutation: Delete an item O(1)
Delete key:value pairs by passing the key to pop()
On average runs in O(1) (constant time!)
cars = {
"Corolla": "Ferrari",
"Accord": "Honda",
"Model 3": "Tesla",
"Prius": "Toyota",
"Rav4": "Toyota"
}
cars.pop('Model 3')
Iteration O(n)
Remember, dictionaries are ordered
Can iterate with for loop. Runs in O(n)
for key in dictionary:
print(key) # print current key
print(dictionary[key]) # print value at that key
Iterates over keys of dictionary
Keys are ordered in the same order that they were added
Ordered Dictionaries?
New versions of Python are released every so often!
Currently on 3.10
As of 3.7 (2018), dictionaries in python are ordered in the same order that they were added to the dictionary
In python, you may depend on the order of a dictionary but be careful about doing this in other languages (or if you are using an older version of python)
Iteration: Example
abbreviations = {'Louisiana': 'LA', 'Utah': 'UT', 'Oregon': 'OR'}
for state in abbreviations:
print('State: ', state)
print('Postal abbreviation: ', abbreviations[state])
Tracing Dictionary Iteration
abbreviations = {
'Louisiana': 'LA',
'Utah': 'UT',
'Oregon': 'OR'
}
for state in abbreviations:
print('State: ', state)
print('Postal abbreviation: ', abbreviations[state])
state
Tracing Dictionary Iteration
abbreviations = {
'Louisiana': 'LA',
'Utah': 'UT',
'Oregon': 'OR'
}
for state in abbreviations:
print('State: ', state)
print('Postal abbreviation: ', abbreviations[state])
'Louisiana'
state
Tracing Dictionary Iteration
abbreviations = {
'Louisiana': 'LA',
'Utah': 'UT',
'Oregon': 'OR'
}
for state in abbreviations:
print('State: ', state)
print('Postal abbreviation: ', abbreviations[state])
State: Louisiana
'Louisiana'
state
Tracing Dictionary Iteration
abbreviations = {
'Louisiana': 'LA',
'Utah': 'UT',
'Oregon': 'OR'
}
for state in abbreviations:
print('State: ', state)
print('Postal abbreviation: ', abbreviations[state])
State: Louisiana
Postal abbreviation: LA
'Louisiana'
state
Tracing Dictionary Iteration
abbreviations = {
'Louisiana': 'LA',
'Utah': 'UT',
'Oregon': 'OR'
}
for state in abbreviations:
print('State: ', state)
print('Postal abbreviation: ', abbreviations[state])
'Utah'
state
State: Louisiana
Postal abbreviation: LA
Tracing Dictionary Iteration
abbreviations = {
'Louisiana': 'LA',
'Utah': 'UT',
'Oregon': 'OR'
}
for state in abbreviations:
print('State: ', state)
print('Postal abbreviation: ', abbreviations[state])
State: Louisiana
Postal abbreviation: LA
State: Utah
'Utah'
state
Tracing Dictionary Iteration
abbreviations = {
'Louisiana': 'LA',
'Utah': 'UT',
'Oregon': 'OR'
}
for state in abbreviations:
print('State: ', state)
print('Postal abbreviation: ', abbreviations[state])
State: Louisiana
Postal abbreviation: LA
State: Utah
Postal abbreviation: UT
'Utah'
state
Tracing Dictionary Iteration
abbreviations = {
'Louisiana': 'LA',
'Utah': 'UT',
'Oregon': 'OR'
}
for state in abbreviations:
print('State: ', state)
print('Postal abbreviation: ', abbreviations[state])
State: Louisiana
Postal abbreviation: LA
State: Utah
Postal abbreviation: UT
'Oregon'
state
Tracing Dictionary Iteration
abbreviations = {
'Louisiana': 'LA',
'Utah': 'UT',
'Oregon': 'OR'
}
for state in abbreviations:
print('State: ', state)
print('Postal abbreviation: ', abbreviations[state])
State: Louisiana
Postal abbreviation: LA
State: Utah
Postal abbreviation: UT
State: Oregon
'Oregon'
state
Tracing Dictionary Iteration
abbreviations = {
'Louisiana': 'LA',
'Utah': 'UT',
'Oregon': 'OR'
}
for state in abbreviations:
print('State: ', state)
print('Postal abbreviation: ', abbreviations[state])
'Oregon': 'OR'
state
State: Louisiana
Postal abbreviation: LA
State: Utah
Postal abbreviation: UT
State: Oregon
Postal abbreviation: OR
Iterate Over Keys
abbreviations = {
'Louisiana': 'LA',
'Utah': 'UT',
'Oregon': 'OR'
}
for state in abbreviations:
print('State: ', state)
print('Postal abbreviation: ', abbreviations[state])
State: Louisiana
Postal abbreviation: LA
State: Utah
Postal abbreviation: UT
State: Oregon
Postal abbreviation: OR
Iterate Over Values
abbreviations = {
'Louisiana': 'LA',
'Utah': 'UT',
'Oregon': 'OR'
}
for abbreviation in abbreviations.values():
print('Postal abbreviation: ', abbreviation)
Postal abbreviation: LA
Postal abbreviation: UT
Postal abbreviation: OR
Iterate Over Key, Value
abbreviations = {
'Louisiana': 'LA',
'Utah': 'UT',
'Oregon': 'OR'
}
for state, abbreviation in abbreviations.items():
print('State: ', state)
print('Postal abbreviation: ', abbreviation)
State: Louisiana
Postal abbreviation: LA
State: Utah
Postal abbreviation: UT
State: Oregon
Postal abbreviation: OR
Accumulation
Dictionaries are often used for accumulation
Keep running count of information
Example:
How many of which letter is used in a sentence? That is, how many times is the letter 'a' used in a sentence? What about 'b'? 'c'? 'd'? 'e'? …?
Accumulation: Letter Count
sentence = 'Hello how are you today'
letter_count = {}
for letter in sentence:
if letter in letter_count:
letter_count[letter] = letter_count[letter] + 1
else:
letter_count[letter] = 1
print(letter_count)
Let’s Code!
https://replit.com/team/csci110-01
Dictionaries!
Dictionaries
What?
ordered* collection of key:value pairs
Can add, change, delete items from dictionary
Can iterate over dictionary, use accumulator pattern to keep running count
Why?
Useful for random access: accessing items out of order and key:value pairs
Lists are better for ordered data and for data without keys:value pairs
Questions?