IT 117: Intermediate Scripting

IT 117: Intermediate Scripting
Class 6

Microphone

Quiz 1

I have posted the answers to Quiz 1 here.

Homework 3

I have posted homework 3 here.

It is due this coming Sunday at 11:59 PM.

Questions

Are there any questions before I begin?

Tips and Examples

Hashbang Problem with Windows Text Files

If you use Windows you may come across the following error message ...

when running a script on Unix

./ex20.py /usr/bin/python3^M bad interpreter: No such file or directory

The problem is that Unix and Windows have different ways ...
of marking the end of a line
Unix uses the single newline character which in Python is written \n
Windows uses two characters to indicate the end of a line
- A carriage return - \r
- A newline - \n
It is the carriage return character that Unix prints as ^M above
Unix reads this extra carriage return character as part of the filename ...
for the Python interpreter
There is no file with this filename
So Unix give you the error above
There is a simple fix for this problem
Unix provides the utility dos2unix
It converts Windows text files into Unix text files
The command takes one argument
The file you are trying to convert
```
dos2unix FILENAME
```

Review

Sequences

Sequences are Python objects that hold more than one value
The values are stored one right after the other in memory
In IT 116 you encountered three types of sequences
- Lists
- Tuples
- Strings
A list contains a series of values that can be changed at any time
A tuple is also a series of values
But a tuple is immutable
That means it cannot be changed
A string is a sequence of characters
It is also immutable
But you can make a new string from a previously created string
Strings also have special methods that deal with characters

Dictionaries

Dictionaries can also contain multiple entries
But each entry has two parts
The first part is the key
The second is a value associated with that key
You use the key to get the value
An entry in a Python dictionary is a key-value pair

Dictionary Literals

Dictionary literals contain a list of entries separated by commas
The entries consist of a key-value pairs enclosed in curly braces, { }

The key and value are separated by a colon, :

>>> digit_names = {1 : "one", 2 : "two", 3 : "three"} 
>>> digit_names
{1: "one", 2: "two", 3: "three"}

Getting Values from a Dictionary

To get the value associated with a key we use the square bracket operator, [ ]
This operator follows the variable that points to the dictionary
Inside the [ ] lies the key

So if I have the following dictionary

>>> students = {"023413" : "Alan Smith", "01234" : "John Doe"}

I can get the name of the student with ID 01234 like this
```
>>> students["01234"]
"John Doe"
```

If the key the doesn't exist you will get a KeyError exception

email_addresses["Waldo"]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: "Waldo"

Empty Dictionaries

An empty dictionary is represented by { }
```
>>> empty = {}
>>> empty
{}
```

Adding Entries to a Dictionary

Just as with lists, there are two ways to create a dictionary
- Use a dictionary literal
- Add entries to an empty dictionary
The second method is more common
We define an empty dictionary like this
```
email_addresses = {}
```
Dictionaries have no methods to add entries to them
Instead you use the [ ] operator to create an entry

You create a new entry in a dictionary using [ ] with a new key

>>> email_addresses = {}                           # create empty dictionarey
>>> email_addresses["Alan"]  = "alanh@gmail.com"   # add first entry
>>> email_addresses["Chris"] = "chrisk@yahoo.com"  # add first entry
>>> email_addresses                                # print the dictionary
{'Chris': 'chrisk@yahoo.com', 'Alan': 'alanh@gmail.com'}

Changing a Dictionary Value

To change the value associated with a key we use [ ] operator and an assignment statement
The key goes inside the square brackets

Like this

>>> students
{"01234": "John Doe", "023413": "Alan Smith"}
>>> students["023413"] = "Al Smith"
>>> students
{"01234": "John Doe", "023413": "Al Smith"}

Dictionaries Are Not Sequences

Lists are sequences
So you can use the position of element in the sequence to get it's value
Dictionaries are not sequences
You do not get the value of a dictionary entry using an index
Instead you use the key

Looping Through a Dictionary

The Python for loop has the following format

for LOOP_VARIABLE in SOME_SORT_OF_LIST:
    STATEMENT
    STATEMENT
    ...

When looping through a sequences the loop variable gets each value ...
in the order it appears in the list
The LOOP_VARIABLE is assigned each value in the SOME_SORT_OF_LIST ...

as it works through the loop code

>>> nonsense
("foo", "bar", "bletch")
>>> for word in nonsense:
...   print(word)
... 
foo
bar
bletch

for loops also work with dictionaries
But here the loop variable gets the value of each key

And you can use the key to get the value

>>> digit_names = {"one":1, "two":2, "three":3, "four":4, "five":5 }
>>> digit_names
{'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5}
>>> for key in digit_names:
...     print(key, digit_names[key])
... 
one 1
two 2
three 3
four 4
five 5

Tuples As Dictionary Values

Entries in a dictionary are key-value pairs
If you want to store more than one piece of information for each key you can use a tuple
If I wanted to store
- First name
- Last name
- Unix username
- Email address

With the student ID as the key, I would write

student_data["09329034"] = ("Jane", "Adams", "jadams",    "jadams@yahoo.com")

When To Use a Dictionary

When should we use a dictionary instead of a list or tuple?
Lists and tuples are used when the elements are not particularly unique
If we create a list of quiz scores, there is nothing special about a specific score
But every student is different
Each one has a unique identity
When you need to store information about unique things, use a dictionary

Attendance

New Material

Creating Lists

When we studied lists, we mentioned two ways to create a list

You could use a list literal

>>> numbers = [1, 2, 3, 4, 5]
>>> numbers
[1, 2, 3, 4, 5]

Or we can start with an empty list
```
>>> numbers = []
```

And then use the append method to add elements

>>> numbers = []
>>> numbers.append(1)
>>> numbers.append(2)
>>> numbers.append(3)
>>> numbers.append(4)
>>> numbers.append(5)
>>> numbers
[1, 2, 3, 4, 5]

The append method of a list object adds elements to the end of a list
To change the value of an element we use the [ ] operator
```
>>> numbers[0] = 47
>>> numbers
[47, 2, 3, 4, 5]
```

Lists versus Dictionaries

Both lists and dictionaries are objects that hold multiple values
In a list you access a value by its index
In a dictionary, you access a value by its key
Here is one way to think of the difference
A list is a collection of values
But a dictionary is a collection of variables
A variable is a place in memory with a name ...
that hold a value

The `in` And `not in` Operators

We can learn if a value is contained in a list by using the in operator

>>> numbers
[1, 2, 3, 4, 5]
>>> 5 in numbers
True
>>> 6 in numbers
False

Similarly, the not in operator tells us whether a value is not found in a list
```
>>> 5 not  in numbers
False
>>> 6 not  in numbers
True
```
The two words not and in together make a single operator
These two operators also work with dictionaries ..
but they only look at keys ...

not values

>>> words_integers
{"three": 3, "five": 5, "two": 2, "one": 1, "four": 4}
>>> "three" in words_integers
True
>>> 3 in words_integers
False

Deleting Elements from A Dictionary

To delete an entry in a dictionary you use a del statement

The general format of such a statement is

del DICTIONARY_VARIABLE[KEY]

where DICTIONARY_VARIABLE is a variable that points to the dictionary object

>>> words_integers
{"three": 3, "five": 5, "two": 2, "one": 1, "four": 4}
>>> del words_integers["five"]
>>> words_integers
{"three": 3, "two": 2, "one": 1, "four": 4}

If you use a key that does not exist, a KeyError exception is raised

del words_integers["six"]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: "six"

Getting the Number of Elements in a Dictionary

The len function can be used with a dictionary

It gives the number of entries in the dictionary

>>> email_addresses
{"Chris": "chrisk@yahoo.com", "Alan": "alanh@gmail.com"}
>>> len(email_addresses)
2
>>> words_integers
{"five": 5, "one": 1, "six": 6, "two": 2, "four": 4, "three": 3}
>>> len(words_integers)
6

Sorting Dictionary Keys

When you run a for loop on a list, the entries appear in list order

>>> numbs = [ 5, 4, 3, 2, 1]
>>> for value in numbs:
...    print(value)
... 
5
4
3
2
1

If you print the value in a dictionary the elements will appear ...

in the order in which they are entered

>>> email_addresses
{'Fred': 'fredsmith@hotmail.com', 'Chris': 'christhek@gmail.com', 'Alan': 'alanh@gmail.com'}
>>> for name in email_addresses:
...   print(name, email_addresses[name])
... 
Fred fredsmith@hotmail.com
Chris christhek@gmail.com
Alan alanh@gmail.com

But sometimes we want to loop through the dictionary in a particular order
We can do this by using the sorted built-in function
sorted take as its argument an object with multiple entries
It returns a new list with all the entries sorted by value
```
>>> numbs = [4,5,3,1,2]
>>> sorted(numbs)
[1, 2, 3, 4, 5]
```
sorted does not change the order of elements in the original list
It creates a new list
When the argument is a dictionary, the function returns a sorted list of keys
```
>>> sorted(email_addresses)
['Alan', 'Chris', 'Fred']
```
To print the values in a dictionary sorted by keys ...

you call sorted on the dictionary variable in the for header sorted

for name in sorted(email_addresses):
...     print(name, email_addresses[name])
... 
Alan alanh@gmail.com
Chris christhek@gmail.com
Fred fredsmith@hotmail.com

Hash Tables

Hash tables are a data structure used for storing data that has a unique identity
As an example of this kind of data think about a driver's license
Every driver's license is unique and has a unique license number
The Registry of Motor Vehicles has to keep records on all of us who have a driver's license
That record will contain certain information about each of us such as
- License number
- Name
- Address
- Date of birth
- Sex
We could think of an entry for a license looking like the picture below ...
where the number is the license number

There are millions of drivers licenses in this state
And the RMV needs to keep records on all of them
How should this data be stored?
Let's say we stored it in a list
Then it would look something like this

How long would it take to look up the entry for a given license number?
There different algorithms for searching a list like this
But in general, the longer the list, the longer the search
And there are millions of drivers licenses
Hash tables take a different approach
It does not store entries one right after the other
Instead, a hash table begins with a lot of empty slots

When a new entry is added, a special function is run on the key ...
the function determines which slot the entry will be stored in
The hash function is designed to spread out the entries among the slots in the table
So it is unlikely that any two keys will have the same slot
The hash table looks something like this

When you need to retrieve an entry you just run the hash function on the key ...
and it will give you the slot number
So retrieving an entry is very fast
But occasionally the hash function will give a slot number to a new entry ...
that is already occupied
When this happens the new entry is linked to the previous entry like this