A crash course in Python - Lesson 6: Object-oriented programming

Python allows the programmer to define classes that encapsulate:

• attributes (i.e., data that describe the status of the instantiated object)
• methods (i.e., functions that describe the behavior of the instantiated object)

Suppose we want to create a class that describes a set of elements (although, as we saw in a previous lesson, Set is already a built-in Python data structure.

The behavior that we may apply on such class is as follows:

• adding items
• removing items from it
• check whether it contains a certain value

Here is a possible implementation of such class:

class Set:
    def __init__(self, values=None):  # constructor
        self.dict = {}
        if values is not None:
            for value in values:
                self.add(value)

    def __repr__(self):  # toString() method
        return "Set: " + str(self.dict.keys())

    def add(self, value):
        self.dict[value] = True

    def contains(self, value):
        return value in self.dict

    def remove(self, value):
        del self.dict[value]

Then we can use such class as follows:

s = Set([1,2,3])

s.add(4)
print s.contains(4)  # True

s.remove(3)
print s..contains(3)  # False

A crash course in Python - Lesson 4: other data structures

Tuple

A tuple is an immutable list. Technically, you can do on/with tuples whatever you can do on a list that does not involve modifying it.

A tuple can be specified by using parentheses (or nothing) instead of square brackets:

my_tuple = (1, 2)
other_tuple = 3, 4

try:
    my_tuple[1] = 3
except TypeError:
    print "cannot modify a tuple"

A tuple is a convenient way of returning multiple values from functions:

def sum_and_product(x, y):
    return (x + y), (x * y)

sp = sum_and_product(2, 3)  # equals (5,6)
s, p = sum_and_product(5, 10) # s = 15, p = 50

Consequently, tuples can be used for multiple assignments too:

x, y = 1, 2  # x = 1, y = 2
x, y = y, x  # swap: x = 2, y = 1

Set

A set represents a collection of distinct elements. It can be declared, modified and manipulated as follows:

s = set()
s.add(1)  # s = {1}
s.add(2)  # s = {1, 2}
s.add(2)  # s = {1, 2}
x = len(s)  # x = 2
y = 2 in s  # y = True
z = 3 in s  # z = False

Sets perform very well when one has to check if they contain a specific value: in is a very fast operation! So, if we have a large collection of items that we want to use for a membership test, a set is more appropriate than a list.
Moreover, if one builds a set starting from a list, what he obtains is the set of distinct values in that list:

my_list = [1, 2, 3, 2, 1, 3]
item_set = set(my_list)  # {1, 2, 3}
distinct_elements = list(item_set) # [1, 2, 3]

A crash course in Python - Lesson 3: Dictionaries

Data structure: the map

A fundamental data structure in computer science is the map. A map associates a key (usually a string) with a value (which usually can be any object).

Here is an example of a map construction and usage.
Suppose we would like to count the number of words in a document, in order to build a histogram of frequencies. Let's assume we use the following map to store the histogram:

"word1" -> frequency1
"word2" -> frequency2
....
"wordN" -> frequencyN

On the left side, I listed the words of the documents, without duplicates. These represent the keys of the map. Whenever a key is provided (say, word1), the corresponding value (in our example, frequency1) is retrieved.
In order to build the aforementioned map, we can use the following algorithm (written in pseudo-code):

for (aWord in document)
    map[aWord] = map[aWord] + 1

In this pseudo-code, map[aWord] retrieves the value associated with the word aWord. In this way, every time the word aWord is encountered in the document, the frequency associated with that word and stored in the map is incremented.
Where is the pro in all this?

• Accessing the map given a word takes O(1)
• With an algorithm of time complexity O(N) we built the histogram of frequencies

Almost every programming language has its own implementation of such data structure (e.g., HashMap is the Java implementation).

Moreover, there are many products based on it. If you are fond of NodeJS, for instance, you could know Redis, an in-memory data structure stored, which can be used as a cache, and is fully integrated with NodeJS. In this case, keys and values are both stored as strings.

From map to Python's dictionary

Python has its own "map-like" data structure, called dictionary. A dictionary associates values with keys, and is declared as follows:

empty_dict1 = {}
empty_dict2 = dict()
grades = {"Joel": 80, "Tim": 95}

Properties of keys

Dictionary keys must be immutable. In particular, you cannot use lists as keys! If you need a multipart key, then you should use a tuple, or figure out a way to turn the key into a string.

Retrieving a value

You can look up the value for a specific key using square brackets:

joel_grade = grades["Joel"]

Obviously, it could be the case that a key does not exist in the map. Thus, you may want to cast an exception that cover such case:

try:
    kates_grade = grades["Kate"]
except KeyError:
    print "No grade for Kate"

Instead of casting an exception, one may want to check if a key exists by doing the following operation:

joel_has_grade = "Joel" in grades   # True

In this case, we are using the operator in to check if the specified value is contained in the dictionary. This reminds lists and the membership check on an element... (check my previous Python lesson on lists).

However, to avoid the whole fuss and muss that could be created by the absence of a key, you can use the get() method, which:

• in case the key exists, returns the associated value
• in case the key does not exist, returns a default value

Here are some examples:

joel_grade = grades.get("Joel",0)  # equals 80, default is 0
no_one_grade = grades.get("No one")  # default is None

Adding a new value

It is possible to assign key-value pairs using the square brackets notation:

grades["Tim"] = 99

Going back to our word histogram example

We are going to create a dictionary where the keys are words and the values are word counts.

word_counts = {}
for word in document:
    if word in word_counts:
        word_counts [word] += 1
    else:
        word_counts[word] = 1

A second (and equivalent) approach is the following, which uses exceptions to handle the special case in which the word is not in the dictionary:

word_counts = {}
for word in document:
    try:
        word_counts [word] += 1
    except KeyError:
        word_counts[word] = 1

A third approach uses the get() method:

word_counts = {}
for word in document:
    previous_count = word_counts.get(word, 0)
    word_counts[word] = previous_count + 1

defaultdict

A defaultdict (i.e., "default dictionary") is a regular dictionary that handles particularly the case in which someone tries to look up a key it does not contain. In this case, the dictionary adds a value for it, using a zero-argument function you provide when you create it.

To use a default dictionary, you have to import it:

from collections import defaultdict

Going back to our example, we can use default dictionaries to store the histogram of words:

word_counts = defaultdict(int)    # int() produces 0
for word in document:
    word_counts[word] += 1

You can use a default dictionary to initialize several objects:

def_list_dict = defaultdict(list)  # list() produces an empty list
def_list_dict[2]. append(1)  # {2:[1]}

default_dict = defaultdict(dict) # dict() produces an empty dict
default_dict["Joel"]["City"] = "Seattle"  # {"Joel":{"City":"Seattle"}}

default_pair = defaultdict(lambda: [0,0])
default_pair[2][1] = 1  # {2:[0,1]}

Counter

A counter turns a sequence of values into a defaultdict(int)-like object, mapping keys to counts. It can be used for histograms.

from collections import Counter
c = Counter([0, 1, 2, 0])  # {0:2, 1:1, 2:1}

The output shows that:

• the number "0" appeared 2 times in the sequence
• the number "1" appeared 1 time in the sequence
• the number "2" appeared 1 time in the sequence

We can use a Counter to solve the problem of counting words in a document, too:

word_counts = Counter(document)

In the Counter object there is the possibility of using the most_common method:

# print the 10 most common words and their counts
for word, count in word_counts.most_common(10)
    print word, count

A crash course in Python - Lesson 2: Lists

A fundamental data structure is the list. A list is an ordered collection of data. This does NOT mean that values are ordered in a specific order (i.e., either ascending or descending). Instead, it means that elements can be accessed in an ordered way, starting from index 0 to index (length-1).

A list can be seen as an array with some added functionality, and a great (and very important!) difference: while an array stores homogeneous values (i.e., values having the same type), a list can store heterogeneous values.

Instantiating a list

The following two lines show how to declare:

• a homogeneous list (i.e., a list containing values having the same data type);
• a heterogeneous list (i.e., a list containing values having different data types).

homogeneous_list_of_integers = [1, 2, 3]
heterogeneous_list = ["string", 0.1, True]

A list can also be generated via the range function, which includes all the values in a range:

list = range(10) # [0,1,...,9]

Element types

Note: list elements can be lists too:

list_of_lists = [homogenous_list, heterogeneous_list, []]

Accessing to elements

It is possible to access to list elements in the following way:

first = list[0]  # first element in the list
last = list[-1]  # last element of the list
next_to_last = list[-2]  # next_to_last element of the list

Check if a list contains an element

Python has an in operator to check for list membership:

1 in [0, 1, 2]  # True
3 in [0, 1, 2]  # False

Slicing lists

You can use square brackets to slice lists:

first_three_elements = list[:3]  #index 3 is EXCLUDED
three_to_end = list[3:]  #index 3 is INCLUDED
one_to_four = list[1:5]  #index 1 is included, 
                         # index 5 is excluded
without_first_and_last = list[1:-1] # 0 and -1 are excluded
last_three = list[-3:]
copy_of_x = list[:]

Concatenate lists

It is easy to concatenate lists together:

x = [1, 2, 3]
x.extend([4, 5, 6])  # Now x is [1,2,3,4,5,6]

However, one can decide to avoid the modification of the original list, by using list addition:

x = [1, 2, 3]
y = x + [4, 5, 6]
# Now y = [1, 2, 3, 4, 5, 6]
# while x is unchanged

It is also possible to append lists one item at a time:

x = [1, 2, 3]
x.append(0)

Store the list content in separate variables

It is often convenient to unpack lists if you know exactly how many elements they contain:

x, y = [1, 2]  # Now x = 1 and y = 2

Notice that if you are not interested in extracting and storing all the values in the list, you can decide to ignore some values:

_, y = [1, 2]  #Now y = 2 and we did not care about the first element

Some special functionalities

Lists have specific functionalities that allow one to manipulate easily their data.

For instance, the following computes the length of a list:

list_length = len(list)

The following, instead, computes the sum of the elements of the list:

list_sum = sum(list)

Creating lists via for loops

You may want to transform a list into another list, by choosing only certain elements, or by transforming elements, or both. This operation is called list comprehension. You may do this by doing the following:

even_numbers = [x for x in range(5) id x % 2 == 0]
squares = [x * x for x in range(5)]
even_squares = [x * x for x in even_numbers]

The same thing applies for dictionaries or sets: you can transform a list into one of them.

If you do not need the value from the list, you can use an underscore as the variable:

zeroes = [0 for _ in even_numbers]

Finally, you may use multiple for to populate the list:

pairs = [(x, y)
           for x in range(10)
           for y in range(10)]
# 100 pairs: (0,0) (0,1)...(9,8) (9,9)

Sorting lists

Don't implement your own (bubble sort??) sorting algorithm: Python already provides a sorting method for lists!

• the sort() method is applied on a list x via dot notation (i.e., x.sort()) and sorts the list in place meaning that x will be modified so that its elements will be ordered in ascending order
• the sorted(L) method takes a list L as parameter and returns a new list, which is a copy of list L, only with ordered elements (in ascending ordered)

x = [4, 1, 2, 3]
y = sorted(x)  # y = [1, 2, 3, 4], x unchanged
x.sort()  # x = [1, 2, 3, 4]

There are a couple of things that you can apply to the sorted function:

• to sort elements in descending order, you can specify a reverse=True parameter
• you can compare the results of a function that you specify with the key parameter; the sorted function will order such results instead of the actual elements of the list

x = sorted([-4,1,-2,3], key=abs, reverse=True)  
# result: [-4, 3, -2, 1]

# sort the words and counts from highest count to lowest
wc = sorted(word_counts.items(),
                   key = lambda (word, count): count,
                   reverse=True)

Iterating over elements and indexes: enumerate

You may want to iterate over a list and use both its elements and their indexes. The solution is the enumerate() function which produces tuples of the form

(index, element)

Note: to have further details about what is a tuple and how to use it, see Lesson 4.

To extract such tuples:

for i, anElement in enumerate(myCollection):
    do_something(i, anElement)

Instead, if you just want the indexes:

for i, _ in enumerate(myCollection): do_something(i)

Zipping and unzipping lists

Zipping lists

One may need to zip lists together, i.e., transform multiple lists into a single list of tuples, where each tuple contains elements from the lists having the same index.

list1 = ['a', 'b', 'c']
list2 = [1, 2, 3]
zip(list1, list2)  # [('a',1), ('b',2), ('c',3)]

Unzipping lists 

You can also unzip a list in multiple lists:

pairs = [('a',1), ('b',2), ('c',3)]
letters, numbers = zip(*pairs)

Here, the asterisk performs an argument unpacking, meaning that we will use the elements of pairs as individual arguments to the zip function. This results in the same outcome that you'd obtain by calling:

zip(('a',1), ('b',2), ('c',3))
# result: [('a','b','c'), (1,2,3)]

You can decide to use argument unpacking with any function, as follows:

def add(a,b):
    return a + b

add(1,2)  # returns 3
add([1,2])  # TypeError
add(*[1,2])  # returns 3