Transcript Tutorial 14, Wednesday 7th February

Computing Science 1P
Large Group Tutorial 14
Simon Gay
Department of Computing Science
University of Glasgow
2006/07
If d = { "John" : 5, "Helen" : 7 }, what do we call
"John" ?
• A key
• A value
• Don't know
2006/07
Computing Science 1P Tutorial 14 - Simon Gay
2
Question
Suppose we define a dictionary by
d = { "Fred":10, "Joe":15, "Anne": 23, "Clare":14 }
and then run the following code:
for x in d.keys():
print x
In which order will the keys of the dictionary appear?
2006/07
Computing Science 1P Tutorial 14 - Simon Gay
3
What is the order?
•
•
•
•
•
Alphabetical order of keys
Numerical order of values
We can't tell; it looks random
The order in the definition
Don't know
2006/07
Computing Science 1P Tutorial 14 - Simon Gay
4
Calculating the mode
In statistics, the most frequently occurring element of a list of
data is called the mode. It's a kind of average which does not
require the data to have any structure at all.
We want to define a function to calculate the mode of a list of
numbers.
e.g. mode([1,2,1,1,3,4,3,2]) should return 1.
We can do this by combining two ideas we already know:
- frequency analysis
- finding the largest value among data
2006/07
Computing Science 1P Tutorial 14 - Simon Gay
5
Calculating the mode
To calculate the mode, we need to calculate how many times
each number occurs in the data.
How should we do this? (Example: [1,2,1,1,3,4,3,2] )
1. Use a list in which position i contains the number of
occurrences of i
Example: [ 0,3,2,2,1 ]
2. Use a dictionary in which an item with key i has a value
which is the number of occurrences of i
Example: { 1:3, 2:2, 3:2, 4:1 }
2006/07
Computing Science 1P Tutorial 14 - Simon Gay
6
What is your preferred data structure for this
problem?
• The list
• The dictionary
• Don't know
2006/07
Computing Science 1P Tutorial 14 - Simon Gay
7
Discussion
Think about what will happen in the following function call:
mode([1,2,1,1,3,4,3,2,1000000])
Do you still like your choice of data structure?
Discuss it with your neighbours.
2006/07
Computing Science 1P Tutorial 14 - Simon Gay
8
When a dictionary is better
When keys are integers and the set of keys is sparse
(i.e. there is a large range of possible keys but relatively few
are actually used), a dictionary is better than a list.
When keys are some other type (e.g. strings), so that we can't
use positional lookup, a dictionary is better than a nested list
because lookup is faster.
2006/07
Computing Science 1P Tutorial 14 - Simon Gay
9
Mode: counting occurrences
def mode(x):
d = {}
for n in x:
if d.has_key(n):
d[n] = d[n] + 1
else:
d[n] = 1
# now find the most common number
2006/07
Computing Science 1P Tutorial 14 - Simon Gay
10
What do you think of this code?
•
•
•
•
It's correct: in fact, ideal
It's correct but can be simplified
It contains errors
Don't know
2006/07
Computing Science 1P Tutorial 14 - Simon Gay
11
Mode: counting occurrences
The code is correct but it can be simplified a little by using
the technique from page 76 of the book:
def mode(x):
d = {}
for n in x:
d[n] = d.get(n,0)+1
# now find the most common number
Exercise: complete the definition so that the most common
number is returned.
2006/07
Computing Science 1P Tutorial 14 - Simon Gay
12
Using nested lists to represent a matrix
A matrix (plural: matrices) is a rectangular grid of numbers.
1 2 3
2 4 5
3 1 2
Represent it by a list of lists:
[ [1,2,3], [2,4,5], [3,1,2] ]
Let's think about an n  n matrix: n rows and n columns,
represented by a list of n lists, each of n elements.
2006/07
Computing Science 1P Tutorial 14 - Simon Gay
13
Opposite diagonal of an n  n matrix
Which of the following code fragments prints the "opposite"
diagonal of an n  n matrix m ?
1 3 2 5
1
4 1 0 2
n = len(m)
for i in range(n):
2 2 3 4
print m[i][i]
5 1 2 3
2
n = len(m)
for i in range(n):
print m[i][n-i]
n = len(m)
3
for i in range(n):
print m[i][n-i-1]
2006/07
4
n = len(m)
for i in range(n):
print m[i][n-i+1]
Computing Science 1P Tutorial 14 - Simon Gay
14
Which piece of code?
•
•
•
•
•
•
1
2
3
4
None of them
Don't know
2006/07
Computing Science 1P Tutorial 14 - Simon Gay
15