Lectures‎ > ‎

Week12

Dictionaries

  • A Python built-in compound type
  • A mapping type
  • Keys are mapped to values
  • Keys must be immutable (e.g., numbers, strings, tuples)
  • Values can be any Python value

Example - Color Maps

See English to Spanish example in book.

color_map = {}
color_map['BLACK'] = (0, 0, 0)
color_map['WHITE'] = (255, 255, 255)
color_map['GREEN'] = (0, 255, 0)

Another way to create:

color_map = {'BLACK': (0, 0, 0),
             'WHITE': (255, 255,255),
             'GREEN': (0, 255, 0) }


Accessing and setting keys/values:

color_map['BLACK']

color_map['RED'] = (255, 0, 0)

Print the dictionary (notice the order)

print color_map

Remove a key/value pair:

del color_map['GREEN']

Number of key/value pairs:

len(color_map)


Dictionary Methods

Keys

print color_map.keys()

Use in a loop:

for color in color_map.keys():
    print color

Values

print color_map.values()

Items

print color_map.items()

You can also use the values and items methods in loops.

Using 'in' to determine if a key exists

if 'RED' in color_map:
    print 'RED exists'

Using the get method

print color_map.get('GREEN')

print color_map.get('GREEN', (0, 0, 0))



Aliasing and copying

color_map_alias = color_map
color_map_copy = color_map.copy()
color_map_alias['RED'] = (255, 1, 1)
print color_map_alias
print color_map_copy


Sparse Matricies

See book example.


Computational Complexity

O(1), O(n), O(log n), O(n^2)


Factorial Using Iteration


def fact_iter(n):
    """Compute the factorial of n using iteration.
       Assume n is >= 0.
       The complexity is O(n).
    """

    prod = 1
    while n > 1:
       prod = prod * n
       n = n - 1
    return prod

Factorial Using Recursion


def fact_rec(n):
    """Compute the factorial of n using iteration.
       Assume n is >= 0.
       The complexity is O(n).
    """
   
    if n <= 1:
        return 1
    else:
        return n * fact_rec(n - 1)
   

Sum List Using Iteration


def sum_iter(nums):
    """Compute the sum of all the numbers in the given nums list using iteration.
       The complexity is O(n).
    """
   
    total = 0
    size = len(nums)
    i = 0
    while i < size:
       total = total + nums[0]
       i = i + 1
    return total

Sum List Using Recursion


def sum_rec(nums):
    """Compute the sum of all the numbers in the given nums list using recursion.
       The complexity is O(n).
    """
   
    if len(nums) == 0:
        return 0
    else:
        return nums[0] + sum_rec(nums[1:])
 

Binary Search

Binary search is a technique speedup search for an element in a sequence if we know the sequence elements are sorted.

Here is the implementation of binary search we developed in class:

def binary_search(x, nums):
    """Find the value x in the nums list using binary search.
       The complexity is O(lg n).
    """
    if nums == []:
        return False
    elif len(nums) == 1:
        return x == nums[0]
    else:
        midindex = len(nums) / 2
        midvalue = nums[midindex]
        if x == midvalue:
            return True
        elif x < midvalue:
            return binary_search(x, nums[0:midindex])
        elif x > midvalue:
            return binary_search(x, nums[midindex + 1:])


numlist = [0,1,2,3,5,6,7,8,9,10,11,13,14,15,16,17]

print binary_search(14, numlist)
print binary_search(4, numlist)
Comments