Dictionaries

• So far, can store using separate lists for every info:

  names =  ['Agrim', 'Gagan', 'Tanish', 'Punj']
  grade =  ['B',     'A-',    'A',      'A']
  course = ['COL100','MTL100','PHL100', 'HUL100']
  

  For example, Gagan scored an A- in MTL100.
• a separate list for each item
• each list must have the same length
• info stored across lists at same index, each index refers to info for a different person
• How to update/retrieve student info?

  def get_grade(student, name_list, grade_list, course_list):
    i = name_list.index(student)
    grade = grade_list[i]
    course = course_list[i]
    return (course, grade)
  

  • messy if have a lot of different info to keep track of
  • must maintain many lists and pass them as arguments
  • must always index using integers
  • must remember to change multiple lists (on an update)

A better and cleaner way: a dictionary

• nice to index item of interest directly (not always int)
• nice to use one data structure, no separate lists
• A list

  0 --> Elem1
  1 --> Elem2
  2 --> Elem3
  3 --> Elem4
  ...
  

  Index (int) maps to element.
• A dictionary

  Key1 --> Elem1
  Key2 --> Elem2
  Key3 --> Elem3
  Key4 --> Elem4
  ...
  

  Custom index (by label) maps to element.

A Python dictionary

• store pairs of data
  • key
  • value

my_dict = {}  # empty dictionary
grades = {'Agrim':'B', 'Gagan':'A-', 'Tanish':'A', 'Punj':'A'}  #'Agrim' is a key, 'B' is a value (element)
coursegrades = {'Agrim': {'COL100':'B', 'MTL100':'A'}, 'Gagan':{'MTL100':'A-'}, 'Tanish':{'PHL100':'A'}, 'Punj':{'HUL100':'A'}}  #'Agrim' is a key, dictionary {'COL100':'B', 'MTL100':'A'} is a value (element)

Dictionary lookup

• similar to indexing a list
• looks up the key
• returns the value associated with the key
• if key isn't found, get an error

grades = {'Agrim':'B', 'Gagan':'A-', 'Tanish':'A', 'Punj':'A'}  #'Agrim' is a key, 'B' is a value (element)
grades['Gagan']  # evaluates to 'A-'
grades['Ashish']  # gives a KeyError

Dictionary operations

grades = {'Agrim':'B', 'Gagan':'A-', 'Tanish':'A', 'Punj':'A'}  #'Agrim' is a key, 'B' is a value (element)

• add an entry

  grades['Asmit'] = 'A'
  

• test if key in dictionary

  'Gagan' in grades  # evaluates to true
  'Lakshay' in grades  # evaluates to false
  

• delete entry

  del(grades['Tanish'])
  

More dictionary operations

grades = {'Agrim':'B', 'Gagan':'A-', 'Tanish':'A', 'Punj':'A'}  #'Agrim' is a key, 'B' is a value (element)

• get an iterable that acts like a tuple of all keys (no guaranteed order)

  grades.keys()  # returns ['Gagan', 'Agrim', 'Tanish', 'Punj']
  

• get an iterable that acts like a tuple of all values (no guaranteed order)

  grades.values()  # returns ['A-', 'B', 'A', 'A']
  

Dictionary keys and values

• values
  • any type (immutable and mutable)
  • can be duplicates
  • dictionary values can be lists, even other dictionaries!
• keys
  • must be unique
  • immutable type (int, float, string, tuple, bool)
    • actually need an object that is hashable, but think of immutable as all immutable types are hashable
  • careful with float type as key, as float computations are often approximate
• no order to keys and values!

  d = {4:{1:0}, (1,3):"twelve", 'const':[3.14,2.7,8.44]}
  

list vs. dict

list	dict
ordered sequence of elements	matches keys to values
look up elements by an integer index	look up one item (value) by another item (key)
indices have an order	no order is guaranteed
index is an integer	key can be any immutable type

Example: Three functions to analyze song lyrics

1. create a frequency dictionary mapping str:int
2. find word that occurs the most and how many times
   • use a list, in case there is more than one word
   • return a list (list, int) for (words_list, highest_freq).
   • find the words that occur at least X times
     • let user choose "at least X times", so allow as parameter
     • return a list of tuples, each tuple is a (list, int) containing the list of words ordered by their frequency
     • IDEA: From song dictionary, find most frequent word. Delete most common word. Repeat. It works because you are mutating the song dictionary.

Creating a dictionary

def lyrics_to_frequency(lyrics):
  myDict = {}
  for word in lyrics:  #can iterate over list
    if word in myDict:  #check if word in dictionary
      myDict[word] += 1  #update value associated with word
    else:
      myDict[word] = 1
  return myDict

Using the dictionary

def most_common_words(freqs):
  values = freqs.values()
  best = max(values)  # values is an iterable, so can apply built-in function max
  words = []
  for k in freqs:  #can iterate over keys in dictionary
    if freqs[k] == best:
      words.append(k)
  return (words, best)

Leveraging dictionary properties

def words_often(freqs, minTimes):
  result = []
  done = False
  while not done:
    temp = most_common_words(freqs)
    if temp[1] >= minTimes:
      result.append(temp)
      for w in temp[0]:
        del(freqs[w])  #can directly mutate dictionary; makes it easier to iterate
    else:
      done = True
  return result

beatles = "....."
print words_often(beatles, 5)

Fibonacci Recursive Code

def fib(n):
  if n == 1:
    return 1
  elif n == 2:
    return 2
 else:
    return fib(n-1) + fib(n-2)

• two base cases
• calls itself twice
• this code is inefficient

This recursive implementation is inefficient

• Show the computation tree
• Recalculating the same values many times!
• Could keep track of already calculated values

Fibonacci with a dictionary

def fib_efficient(n, d):
  if n in d:
    return d[n]
  else:
    ans = fib_efficient(n-1, d) + fib_efficient(n-2, d) #method sometimes called "memoization"
    d[n] = ans
    return ans

d = {1:1, 2:2}
print(fib_efficient(6, d))

• do a lookup first in case already calculated the value
• modify dictionary as progress through function calls
• Efficiency gains:
  • Calling fib(34) results in 11,405,773 recursive calls to the procedure
  • Calling fib(34) results in 65 recursive calls to the procedure
  • Using dictionaries to capture intermediate results can be very efficient
  • But note that this only works for procedures without side effects (i.e., the procedure will always produce the same result for a specific argument independent of any other computations between calls).