0% found this document useful (0 votes)

5 views91 pages

Average Numbers in Python Program

Chapter 4 discusses the limitations of single-value variables and introduces lists as a solution for storing multiple values efficiently. It explains how to create and manipulate lists in Python, including accessing elements, traversing lists, and building lists dynamically based on user input. The chapter also highlights the advantages of using lists over individual variables for handling larger datasets.

Uploaded by

kumudha326

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

5 views91 pages

Average Numbers in Python Program

Uploaded by

kumudha326

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

Chapter 4

Lists

The variables we have used to this point can assume only one value at a time. As we have seen, individual
variables can be used to create some interesting and useful programs; however, variables that can represent
only one value at a time do have their limitations. Consider Listing 9.1 ([Link]) which
averages five numbers entered by the user.

Listing 9.1: [Link]

1 def main():
2 print("Please enter five numbers: ")
3 # Allow the user to enter in the five values.
4 n1 = eval(input("Please enter number 1: "))
5 n2 = eval(input("Please enter number 2: "))
6 n3 = eval(input("Please enter number 3: "))
7 n4 = eval(input("Please enter number 4: "))
8 n5 = eval(input("Please enter number 5: "))
9 print("Numbers entered:", n1, n2, n3, n4, n5)
10 print("Average:", (n1 + n2 + n3 + n4 + n5)/5)
11
12 main()

A sample run of Listing 9.1 ([Link]) looks like:

Please enter five numbers:

Please enter number 1: 34.2
Please enter number 2: 10.4
Please enter number 3: 18.0
Please enter number 4: 29.3
Please enter number 5: 15.1
Numbers entered: 34.2 10.4 18.0 29.3 15.1
Average: 21.4

The program conveniently displays the values the user entered and then computes and displays their aver-
age.
Suppose the number of values to average must increase from five to 25. If we use Listing 9.1 ([Link])
as a guide, twenty additional variables must be introduced, and the overall length of the program necessarily
will grow. Averaging 1,000 numbers using this approach is impractical.
Listing 9.2 ([Link]) provides an alternative approach for averaging numbers that uses a
loop.

Listing 9.2: [Link]

1 def main():
2 sum = 0.0
3 NUMBER_OF_ENTRIES = 5
4 print("Please enter", NUMBER_OF_ENTRIES, " numbers: ")
5 for i in range(0, NUMBER_OF_ENTRIES):
6 num = eval(input("Enter number " + str(i) + ": ")
7 sum += num;
8 print("Average:", sum/NUMBER_OF_ENTRIES)
9
10 main()

Listing 9.2 ([Link]) behaves slightly differently from Listing 9.1 ([Link]),
as the following sample run using the same data shows:

Please enter 5 numbers:

Enter number 0: 34.2
Enter number 1: 10.4
Enter number 2: 18.0
Enter number 3: 29.3
Enter number 4: 15.1
Average: 21.4

Listing 9.2 ([Link]) can be modified to average 25 values much more easily than Listing 9.1
([Link]) that must use 25 separate variables—just change the value of NUMBER_OF_ENTRIES.
In fact, the coding change to average 1,000 numbers is no more difficult. However, unlike the original
average program, this new version does not display the numbers entered. This is a significant difference; it
may be necessary to retain all the values entered for various reasons:

• All the values can be redisplayed after entry so the user can visually verify their correctness.
• The values may need to be displayed in some creative way; for example, they may be placed in a
graphical user interface component, like a visual grid (spreadsheet).
• The values entered may need to be processed in a different way after they are all entered; for example,
we may wish to display just the values entered above a certain value (like greater than zero), but the
limit is not determined until after all the numbers are entered.

In all of these situations we must retain the values of all the variables for future recall.
We need to combine the advantages of both of the above programs; specifically we want

• the ability to retain individual values, and

• the ability to dispense with creating individual variables to store all the individual values

These may seem like contradictory requirements, but Python provides a standard data structure that simul-
taneously provides both of these advantages—the list.

9.1 Using Lists

A list refers to a collection of objects; it represents an ordered sequence of data. In that sense, a list is
similar to a string, except a string can hold only characters. We may access the elements contained in a list
via their position within the list. A list need not be homogeneous; that is, the elements of a list do not all
have to be of the same type.
Like any other variable, a list variable can be local or global, and it must be defined (assigned) before it
is used. The following code fragment declares a list named lst that holds the integer values 2, −3, 0, 4, −1:
lst = [2, -3, 0, 4, -1]

The right-hand side of the assignment statement is a literal list. The elements of the list appear within
square brackets ([ ]), the elements are separated by commas. The following statement:
a = []

assigns the empty list to a. We can print list literals and lists referenced through variables:
lst = [2, -3, 0, 4, -1] # Assign the list
print([2, -3, 0, 4, -1]) # Print a literal list
print(lst) # Print a list variable

The above code prints

[2, -3, 0, 4, -1]

We can access individual elements of a list using square brackets:

lst = [2, -3, 0, 4, -1] # Assign the list
lst[0] = 5 # Make the first element 5
print(lst[1]) # Print the second element
lst[4] = 12 # Make the last element 12
print(lst) # Print a list variable
print([10, 20, 30][1]) # Print second element of literal list

This code prints

-3
[5, -3, 0, 4, 12]
20
The number within the square brackets indicates the distance from the beginning of the list. The expression
list[0] therefore indicates the element at the very beginning (a distance of zero from the beginning), and
list[1] is the second element (a distance of one away from the beginning).
If a is a list with n elements, and i is an integer such that 0 ≤ i <n, then a[n] is an element in the list.
Figure 9.1 visualizes the list assigned as
lst = [5, -3, 12]

5 ‒3 12
lst

0 1 2

Figure 9.1: A simple list with three elements. The small number below a list element represents the index
of that element.
Listing 9.3 ([Link]) demonstrates that lists may be heterogeneous; that is, a list can hold
elements of varying types.
Listing 9.3: [Link]
1 collection = [24.2, 4, 'word', eval, 19, -0.03, 'end']
2 print(collection[0])
3 print(collection[1])
4 print(collection[2])
5 print(collection[3])
6 print(collection[4])
7 print(collection[5])
8 print(collection[6])
9 print(collection)

Listing 9.3 ([Link]) prints

24.2
4
word
<built-in function eval>
19
-0.03
end
[24.2, 4, ’word’, <built-in function eval>, 19, -0.03, ’end’]
We clearly see that a single list can hold integers, floating-point numbers, strings, and even functions. A list
can hold other lists; the following code
col = [23, [9.3, 11.2, 99.0], [23], [], 4, [0, 0]]
print(col)

prints

[23, [9.3, 11.2, 99.0], [23], [], 4, [0, 0]]

Four of the elements of the list col are themselves lists.

In an expression such as
a[3]

the expression within the square brackets is called an index or subscript. The subscript terminology is
borrowed from mathematicians who use subscripts to reference elements in a mathematical vector (for
example, V2 represents the second element in vector V). Unlike the convention often used in mathematics,
however, the first element in a list is at position zero, not one. The expression a[2] can be read aloud as
“ay sub two.” As mentioned above, the index indicates the distance from the beginning; thus, the very first
element is at a distance of zero from the beginning of the list. The first element of list a is a[0]. As a
consequence of a zero beginning index, if list a holds n elements, the last element in a is a[n − 1], not
a[n].
The elements of a list extracted with [] can be treated as any other variable; for example,
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
# Print the fourth element
print(nums[3])
# The third element is the average of two other elements
nums[2] = (nums[0] + nums[9])/2;
# Assign elements at indices 1 and 4 from user input
# using tuple assignment
nums[1], nums[4] = eval(input("Enter a, b: "))

The expression within [] must evaluate to an integer; some examples include

• an integer literal: a[34]

• an integer variable: a[x] (x must be an integer)

• an integer arithmetic expression: a[x + 3] (x must be an integer)

• an integer result of a function call that returns an integer: a[max(x, y)] (max must return an integer)

• an element of another list: a[b[3]] (element b[3] must be an integer)

The action of moving through a list visiting each element is known as traversal. The for loop is made
to iterate over aggregate types like lists. Listing 9.4 ([Link]) uses a for loop and behaves
identically to Listing 9.3 ([Link]).
Listing 9.4: [Link]

1 collection = [24.2, 4, 'word', eval, 19, -0.03, 'end']

2 for item in collection:
3 print(item) # Print each element

The built-in function len returns the number of elements in a list: The code segment

print(len([2, 4, 6, 8]))
a = [10, 20, 30]
print(len(a))

prints

4
3

The name len stands for length. We can print the elements of a list in reverse order as follows:

nums = [2, 4, 6, 8]
# Print last element to first (zero index) element
for i in range(len(nums) - 1, -1, -1):
print(nums[i])

This fragment prints

8
6
4
2

The plus (+) operator concatenates lists in the same way it concatenates strings. The following shows
some experiments in the interactive shell with list concatenation:
>>> a = [2, 4, 6, 8]
>>> a
[2, 4, 6, 8]
>>> a + [1, 3, 5]
[2, 4, 6, 8, 1, 3, 5]
>>> a
[2, 4, 6, 8]
>>> a = a + [1, 3, 5]
>>> a
[2, 4, 6, 8, 1, 3, 5]
>>> a += [10]
>>> a
[2, 4, 6, 8, 1, 3, 5, 10]
>>> a += 20
Traceback (most recent call last):
File "<pyshell#14>", line 1, in <module>
a += 20
TypeError: ’int’ object is not iterable

The statement
a = [2, 4, 6, 8]

assigns the given list literal to the variable a. The expression

a + [1, 3, 5]

evaluates to the list [2, 4, 6, 8, 1, 3, 5], but the statement does not change the list to which a refers.
The statement
a = a + [1, 3, 5]

actually reassigns a to the new list [2, 4, 6, 8, 1, 3, 5]. The statement

a += [10]

updates a to be the new list [2, 4, 6, 8, 1, 3, 5, 10]. Observe that the + will concatenate two lists,
but it cannot join a list and a non-list. The following statement
a += 20

is illegal since a refers to a list, and 20 is an integer, not a list. If used within a program under these
conditions, this statement will produce a run-time exception.
Listing 9.5 ([Link]) shows how to build lists as the program executes.

Listing 9.5: [Link]

1 # Build a custom list of non-negative integers specified by the user
2
3 def make_list():
4 '''
5 Builds a list from input provided by the user.
6 '''
7 result = [] # List to return is initially empty
8 in_val = 0 # Ensure loop is entered at least once
9 while in_val >= 0:
10 in_val = int(input("Enter integer (-1 quits): "))
11 if in_val >= 0:
12 result = result + [in_val] # Add item to list
13 return result
14
15 def main():
16 col = make_list()
17 print(col)
18
19 main()

A sample run of Listing 9.5 ([Link]) produces

Enter integer (-1 quits): 23

Enter integer (-1 quits): 100
Enter integer (-1 quits): 44
Enter integer (-1 quits): 19
Enter integer (-1 quits): 19
Enter integer (-1 quits): 101
Enter integer (-1 quits): 98
Enter integer (-1 quits): -1
[23, 100, 44, 19, 19, 101, 98]

If the user enters a negative number initially, we get:

Enter integer (-1 quits): -1

[]

There are several ways to build a list without explicitly listing every element in the list. We can use the
range function to produce a regular sequence of integers. The range object returned by range is not itself
a list, but we can make a list from a range using the list function, as Listing 9.6 ([Link])
demonstrates.

Listing 9.6 ([Link]) prints

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
[0, 10, 20, 30, 40, 50, 60, 70, 80, 90]
[-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5]

It is easy to make a list in which all the elements are the same or a pattern of elements repeat. The *
operator, with applied to a list and an integer, “multiplies” the elements of a list. The code
for i in range(0, n):
a += a

which effectively concatenates list a with itself n times, may be expressed more simply as
a * n

Listing 9.7 ([Link]) builds several lists using the * list multiplication operator.

The output of Listing 9.7 ([Link]) is

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[3.4, 3.4, 3.4, 3.4, 3.4]
[’ABC’, ’ABC’, ’ABC’]
[10, 20, 30, 10, 20, 30, 10, 20, 30, 10, 20, 30]

Observe that the integer multiplier may appear either to left or the right of the * operator, and the effects
are the same. This means the list multiplication * operator is commutative.
We now have all the tools we need to build a program that flexibly averages numbers while retaining all
the values the user enters. Listing 9.8 ([Link]) uses an list and a loop to achieve the generality
of Listing 9.2 ([Link]) with the ability to retain all input for later redisplay.

The output of Listing 9.8 ([Link]) is similar to the original Listing 9.1 ([Link])
program:

Please enter 5 numbers:

Enter number 0: 9.0
Enter number 1: 3.5
Enter number 2: 0.2
Enter number 3: 100.0
Enter number 4: 15.3
Numbers entered: 9.0 3.5 0.2 100.0 15.3
Average: 25.6

Unlike the original program, however, we now conveniently can extend this program to handle as many
values as we wish. We need to change only the definition of the NUMBER_OF_ENTRIES variable to allow the
program to handle any number of values. This centralization of the definition of the list’s size eliminates
duplicating a literal numeric value and leads to a program that is more maintainable. Suppose every oc-
currence of NUMBER_OF_ENTRIES were replaced with the literal value 5. The program would work exactly
the same way, but changing the size would require touching many places within the program. When dupli-
cate information is scattered throughout a program, it is a common mistake to update some but not all of
the information when a change is to be made. If all of the duplicate information is not updated to agree,
the inconsistencies result in logic errors within the program. By faithfully using the NUMBER_OF_ENTRIES
variable throughout the program instead of the literal numeric value, we can avoid the problems with this
potential inconsistency.
The first loop in Listing 9.8 ([Link]) collects all five input values from the user. The second
loop prints all the numbers the user entered.

9.2 List Assignment and Equivalence

Given the assignment

lst = [2, 4, 6, 8]

the expression lst is very different from the expression lst[2]. The expression lst is a reference to the
list, while lst[2] is a reference to a particular element in the list, in this case the integer 6. The integer 6 is
immutable (see Section 7.4); a literal integer cannot change to be another value. Six is always six. A vari-
able, of course, can change its value and its type through assignment. Variable assignment changes the ob-
ject to which the variable is bound. Recall Figure 2.2, and consider the Listing 9.9 ([Link]).

Listing 9.9: [Link]

1 a = [10, 20, 30, 40]
2 b = [10, 20, 30, 40]
3 print('a =', a)
4 print('b =', b)
5 b[2] = 35
6 print('a =', a)
7 print('b =', b)

Figure 9.2 shows the consequences of each of the assignment statements in Listing 9.9 ([Link]),

As Figure 9.2 illustrates, variables a and b refer to two different list objects; however, the elements of
both lists bind to the same (immutable) values. Reassigning an element of list b does not affect list a. The
output of Listing 9.9 ([Link]) verifies this analysis:

a = [10, 20, 30, 40]

b = [10, 20, 30, 40]
a = [10, 20, 30, 40]
b = [10, 20, 35, 40]

Now consider Listing 9.10 ([Link]), a subtle variation of Listing 9.9 ([Link]).
At first glance, the code in Listing 9.10 ([Link]) looks like it may behave exactly like Listing 9.9
([Link]).
Listing 9.10: [Link]
1 a = [10, 20, 30, 40]
2 b = a
3 print('a =', a)
4 print('b =', b)
5 b[2] = 35
10 20 30 40
a
a = [10, 20, 30]
0 1 2 3

0 1 2 3

b = [10, 20, 30] 10 20 30 40

0 1 2 3

35
b

0 1 2 3

b[2] = 35
10 20 30 40
a

0 1 2 3

Figure 9.2: State of Listing 9.9 ([Link]) as the assignment statements execute

6 print('a =', a)
7 print('b =', b)

As Figure 9.3 illustrates, the second assignment statement causes variables a and b to refer to the same
list object. We say that a and b are aliases. Reassigning b[2] changes a[2] as well, as Listing 9.10
([Link])’s output shows:
10 20 30 40
a
a = [10, 20, 30]
0 1 2 3

b = a 10 20 30 40
a

0 1 2 3

b[2] = 35 10 20 30 40
a

0 1 2 3

Figure 9.3: State of Listing 9.10 ([Link]) as the assignment statements execute

a = [10, 20, 30, 40]

b = [10, 20, 30, 40]
a = [10, 20, 35, 40]
b = [10, 20, 35, 40]
If a refers to a list, the statement
b = a

does not make a copy of a’s list. Instead it makes a and b aliases to the same list. Lists are mutable data
structures. Individual elements accessed through [] may be reassigned. If more than one variable is bound
to the same list, any element modification through one of the variables will affect the list from the point of
view of all the aliased variables.
The familiar == equality operator determines if two lists contain the same elements. The is operator
determines if two variables alias the same list. Listing 9.11 ([Link]) demonstrates the
difference between the two operators.

Listing 9.11: [Link]

1 # a and b are distinct lists that contain the same elements
2 a = [10, 20, 30, 40]
3 b = [10, 20, 30, 40]
4 print('Is ', a, ' equal to ', b, '?', sep='', end=' ')
5 print(a == b)
6
7 print('Are ', a, ' and ', b, ' aliases?', sep='', end=' ')
8 print(a is b)
9
10 # c and d alias are distinct lists that contain the same elements
11 c = [100, 200, 300, 400]
12 d = c # Makes d an alias of c
13 print('Is ', c, ' equal to ', d, '?', sep='', end=' ')
14 print(c == d)
15
16 print('Are ', c, ' and ', d, ' aliases?', sep='', end=' ')
17 print(c is d)

Listing 9.11 ([Link]) prints

Is [10, 20, 30, 40] equal to [10, 20, 30, 40]? True
Are [10, 20, 30, 40] and [10, 20, 30, 40] aliases? False
Is [100, 200, 300, 400] equal to [100, 200, 300, 400]? True
Are [100, 200, 300, 400] and [100, 200, 300, 400] aliases? True

When comparing lists lst1 and lst2, if the expression lst1 is lst2 evaluates to True, the expression
lst1 == lst2 is guaranteed to be True.
What if we wish to make a copy of an existing list? Listing 9.12 ([Link]) shows one way to
accomplish this.

The output of Listing 9.12 ([Link]) reveals:

a = [10, 20, 30, 40] b = [10, 20, 30, 40]

Is [10, 20, 30, 40] equal to [10, 20, 30, 40]? True
Are [10, 20, 30, 40] and [10, 20, 30, 40] aliases? False
a = [10, 20, 30, 40] b = [10, 20, 35, 40]

The list_copy function is Listing 9.12 ([Link]) makes an actual copy of a. Changing an element
of b does not affect list a.
In Section 9.4 we will see a more effective way to copy a list.

9.3 List Bounds

In the following code fragment:

a = [10, 20, 30, 40]

All of the following expressions are valid: a[0], a[1], a[2] and a[3]. The expression a[4] does not
represent a valid element in the list. An attempt to use this expression, as in
a = [10, 20, 30, 40]
print(a[4]) # Out-of-bounds access

results in a run-time exception. The interpreter will insist that the programmer use an integral value for
an index, but in order to prevent a run-time exception the programmer must ensure that the index used is
within the bounds of the list. Consider the following code:
# Make a list containing 100 zeros
v = [0] * 100
# User enters x at run time
x = int(input("Enter an integer: "))
v[x] = 1 # Is this OK? What is x?

©2011 Richard L. Halterman Draft date: November 13, 2011

Since the index may consist of an arbitrary integer expression whose value cannot be determined until run
time, the interpreter checks every attempt to access a list. If the interpreter detects an out-of-bounds index,
the interpreter raises an IndexError (list index out-of-bounds) exception. The programmer must ensure
the provided index is in bounds to prevent such a run-time error.
The above unreliable code can be helped with conditional access:
# Make a list containing 100 zeros
v = [0] * 100
# User enters x at run time
x = int(input("Enter an integer: "))
# Ensure index is within list bounds
if 0 <= x < len(v):
v[x] = 1 # This should be fine
else:
print("Value provided is out of range")

Listing 9.13 ([Link]) attempts to print the list’s elements in reverse order, but it fails to stay
inside the bounds of the list.

Listing 9.13: [Link]

1 def make_list():
2 '''
3 Builds a list from input provided by the user.
4 '''
5 result = [] # List to return is initially empty
6 in_val = 0 # Ensure loop is entered at least once
7 while in_val >= 0:
8 in_val = int(input("Enter integer (-1 quits): "))
9 if in_val >= 0:
10 result = result + [in_val] # Add item to list
11 return result
12
13 def main():
14 col = make_list()
15 # Print the list in reverse
16 for i in range(len(col), 0, -1):
17 print(col[i], end=" ")
18 print()
19
20 main()

The for statement

for i in range(len(col), 0, -1):
print(col[i], end=" ")

considers first the element at col[len(col)], which is one index past the end of the list. The corrected
for statement is
for i in range(len(col) - 1, -1, -1):
print(col[i], end=" ")
9.3. SLICING 197

A negative list index represents a negative offset from an imaginary element one past the end of the list.
For list lst, the expression lst[-1] represents the last element in lst. The expression lst[-2] repre-
sents the next to last element, and so forth. The expression lst[0] thus corresponds to lst[-len(lst)].
Listing 9.14 ([Link]) illustrates the use of negative indices to print a list in reverse.

9.4 Slicing

We can make a new list from a portion of an existing list using a technique known as slicing. A list slice is
an expression of the form

list [ begin : end ]

where

• list is a list—a variable referring to a list object, a literal list, or some other expression that evaluates
to a list,

• begin is an integer representing the starting index of a subsequence of the list, and
• end is an integer that is one larger than the index of the last element in a subsequence of the list.

If missing, the begin value defaults to 0. A begin value less than zero is treated as zero. If the end value is
missing, it defaults to the length of the list. An end value greater than the length of the list is treated as the
length of the list. The examples provided in Listing 9.15 ([Link]) best illustrate how list slicing
works.

Listing 9.15: [Link]

1 lst = [10, 20, 30, 40, 50, 60, 70, 80]
2 print(lst) # [10, 20, 30, 40, 50, 60, 70, 80]
3 print(lst[0:3]) # [10, 20, 30]
4 print(lst[4:8]) # [50, 60, 70, 80]
5 print(lst[2:5]) # [30, 40, 50]
6 print(lst[-5:-3]) # [40, 50]
7 print(lst[:3]) # [10, 20, 30]
8 print(lst[4:]) # [50, 60, 70, 80]
9 print(lst[:]) # [10, 20, 30, 40, 50, 60, 70, 80]
10 print(lst[-100:3]) # [10, 20, 30]
11 print(lst[4:100]) # [50, 60, 70, 80]

Slicing is the easiest way to make a copy of a list. The expression lst[:] evaluates to a copy of list lst.
Listing 9.16 ([Link]) prints all the prefixes and suffixes of the list [1, 2, 3, 4, 5, 6, 7, 8].

Listing 9.16 ([Link]) prints

Prefixes of [1, 2, 3, 4, 5, 6, 7, 8]
<[]>
<[1]>
<[1, 2]>
<[1, 2, 3]>
<[1, 2, 3, 4]>
<[1, 2, 3, 4, 5]>
<[1, 2, 3, 4, 5, 6]>
<[1, 2, 3, 4, 5, 6, 7]>
<[1, 2, 3, 4, 5, 6, 7, 8]>

Suffixes of [1, 2, 3, 4, 5, 6, 7, 8]
<[1, 2, 3, 4, 5, 6, 7, 8]>
<[2, 3, 4, 5, 6, 7, 8]>
<[3, 4, 5, 6, 7, 8]>
<[4, 5, 6, 7, 8]>
<[5, 6, 7, 8]>
<[6, 7, 8]>
<[7, 8]>
<[8]>
<[]>

When the slicing expression appears on the left side of the assignment operator it can modify the con-

©2011 Richard L. Halterman Draft date: November 13, 2011

tents of the list. This is known as slice assignment. A slice assignment can modify a list by removing or
adding a subrange of elements in an existing list. Listing 9.17 ([Link]) demonstrates how slice
assignment can be used to modify a list.

Listing 9.17: [Link]

1 lst = [10, 20, 30, 40, 50, 60, 70, 80]
2 print(lst) # Print the list
3 lst[2:5] = ['a', 'b', 'c'] # Replace [30, 40, 50] segment with ['a', 'b', 'c']
4 print(lst)
5 print('==================')
6 lst = [10, 20, 30, 40, 50, 60, 70, 80]
7 print(lst) # Print the list
8 lst[2:6] = ['a', 'b'] # Replace [30, 40, 50, 60] segment with ['a', 'b']
9 print(lst)
10 print('==================')
11 lst = [10, 20, 30, 40, 50, 60, 70, 80]
12 print(lst) # Print the list
13 lst[2:2] = ['a', 'b', 'c'] # Insert ['a', 'b', 'c'] segment at index 2
14 print(lst)
15 print('==================')
16 lst = [10, 20, 30, 40, 50, 60, 70, 80]
17 print(lst) # Print the list
18 lst[2:5] = [] # Replace [30, 40, 50] segment with []
19 print(lst)

Listing 9.17 ([Link]) displays:

[10, 20, 30, 40, 50, 60, 70, 80]

[10, 20, ’a’, ’b’, ’c’, 60, 70, 80]
==================
[10, 20, 30, 40, 50, 60, 70, 80]
[10, 20, ’a’, ’b’, 70, 80]
==================
[10, 20, 30, 40, 50, 60, 70, 80]
[10, 20, ’a’, ’b’, ’c’, 30, 40, 50, 60, 70, 80]
==================
[10, 20, 30, 40, 50, 60, 70, 80]
[10, 20, 60, 70, 80]

9.5 Lists and Functions

A list can be passed to a function, as shown in Listing 9.18 ([Link])

9.6 Prime Generation with a List

Listing 9.19 ([Link]) uses an algorithm developed by the Greek mathematician Eratosthenes
who lived from 274 B.C. to 195 B.C. Called the Sieve of Eratosthenes, the principle behind the algorithm
is simple: Make a list of all the integers two and larger. Two is a prime number, but any multiple of two
cannot be a prime number (since a multiple of two has two as a factor). Go through the rest of the list and
mark out all multiples of two (4, 6, 8, ...). Move to the next number in the list (in this case, three). If it is
not marked out, it must be prime, so go through the rest of the list and mark out all multiples of that number
(6, 9, 12, ...). Continue this process until you have listed all the primes you want.
Listing 9.19 ([Link]) implements the Sieve of Eratosthenes in a Python function.

Listing 9.19: [Link]

1 # Display the prime numbers between 2 and 500
2
3 # Largest potential prime considered
4 MAX = 500
5
6 def main():
7 # Each position in the Boolean list indicates
8 # if the number of that position is not prime:
9 # false means "prime," and true means "composite."
10 # Initially all numbers are prime until proven otherwise
11 nonprimes = MAX * [False] # Initialize to all False
12
13 # First prime number is 2; 0 and 1 are not prime
14 nonprimes[0] = nonprimes[1] = True
15
16 # Start at the first prime number, 2.
17 for i in range(2, MAX + 1):
18 # See if i is prime
19 if not nonprimes[i]:
20 print(i, end=" ")
21 # It is prime, so eliminate all of its
22 # multiples that cannot be prime
23 for j in range(2*i, MAX + 1, i)
24 nonprimes[j] = True
25 print() # Move cursor down to next line

How much better is the algorithm in Listing 9.19 ([Link]) than the square-root-optimized
version we saw in Listing 6.8 ([Link])? Listing 9.20 ([Link]) compares
the execution speed of the two algorithms.

Listing 9.20: [Link]

1
2 # Count the number of prime numbers less than
3 # 2 million and time how long it takes
4 # Compares the performance of two different
5 # algorithms.
6
7 from time import clock
8 from math import sqrt
9
10
11 def count_primes(n):
12 '''
13 Generates all the prime numbers from 2 to n - 1.
14 n - 1 is the largest potential prime considered.
15 '''
16 start = clock() # Record start time
17
18 count = 0
19 for val in range(2, n):
20 result = True # Provisionally, n is prime
21 root = int(sqrt(val) + 1)
22 # Try all potential factors from 2 to the square root of n
23 trial_factor = 2
24 while result and trial_factor <= root:
25 result = (val % trial_factor != 0 ) # Is it a factor?
26 trial_factor += 1 # Try next candidate
27 if result:
28 count += 1
29
30 stop = clock() # Stop the clock
31 print("Count =", count, "Elapsed time:", stop - start, "seconds")
32
33
34
35 def seive(n):
36 '''
37 Generates all the prime numbers from 2 to n - 1.
38 n - 1 is the largest potential prime considered.
39 Algorithm originally developed by Eratosthenes.
40 '''
41
42 start = clock() # Record start time
43
44 # Each position in the Boolean list indicates
45 # if the number of that position is not prime:
46 # false means "prime," and true means "composite."
47 # Initially all numbers are prime until proven otherwise
48 nonprimes = n * [False] # Global list initialized to all False
49
50
51 count = 0
52
53 # First prime number is 2; 0 and 1 are not prime
54 nonprimes[0] = nonprimes[1] = True
55
# Start at the first prime number, 2.
56 for i in range(2, n):
57 # See if i is prime
58 if not nonprimes[i]:
59 count += 1
60 # It is prime, so eliminate all of its
61 # multiples that cannot be prime
62 for j in range(2*i, n, i):
63 nonprimes[j] = True
64 # Print the elapsed time
65 stop = clock()
66 print("Count =", count, "Elapsed time:", stop - start, "seconds")
67
68
69 def main():
70 count_primes(2000000)
71 seive(2000000)
72
73 main()

Since printing to the screen takes up the majority of the time, Listing 9.20 ([Link]) counts the
number of primes rather than printing each one. This allows us to better compare the behavior of the two
approaches. The square root version has been optimized slightly more: the floating-point root variable is
not an integer. The less than comparison between two integers is faster than the floating-point equivalent.
The output of Listing 9.20 ([Link]) on one system reveals

Count = 148932 Elapsed time: 56.446094827055276 seconds

Count = 148933 Elapsed time: 0.8864909583615557 seconds

Our previous version requires almost a minute (56 seconds) to count the number of primes less than two
million, while the version based on the Sieve of Eratosthenes takes less than one second. The Sieve version
is over 60 times faster than the optimized square root version.

9.7 Summary

• A list represents an ordered sequence of objects

• An element in a list may be accessed via its index using []. The first element is at index 0. If the list
contains n elements, the index of the last element is n− 1.

• A positive list index is an offset from the beginning of the list. A negative list index is an offset back
from an imaginary element one past the end of the list.

• A list may elements of different types.

• List literals list their elements in a comma-separated list enclosed within square brackets ([]).

• The len function returns the length of the list

• A list index is sometimes called a subscript.
• A list subscript must evaluate to an integer. Integer literals, variables, and expressions can be used as
list indices.

• A for loop is a convenient way to traverse the contents of a list.

• Like other variables, a list variable can be local, global, or a function parameter.
• Direct list assignment produces an alias. A slice of a whole list makes an actual copy of the list.

• The == tests for equal contents within lists; the is operator tests for list aliases.
• A list may be passed to a function. The formal parameter within the function becomes an alias of the
actual parameter passed by the client. This means functions may modify the contents of a list, and
the modification will affect the client’s copy of the list.
• It is the programmer’s responsibility to stay within the bounds of a list. Venturing outside the bounds
of a list results in a run-time error.
• Lists are mutable objects. Integers, floating-point, and string values are immutable.
• Parts of lists can be expressed with slices. A slice is a copy of a subrange of elements in a list.
• List slices on the right side the assignment operator can modify lists by removing or adding a subrange
of elements in an existing list.

9.8 Exercises

1. Can a Python list hold a mixture of integers and strings?

2. What happens if you attempt to access an element of a list using a negative index?
3. Given the statement
lst = [10, -4, 11, 29]

(a) What expression represents the very first element of lst?

(b) What expression represents the very last element of lst?
(c) What is lst[0]?
(d) What is lst[3]?
(e) What is lst[1]?
(f) What is lst[-1]?
(g) What is lst[-4]?
(h) Is the expression lst[3.0] legal or illegal?

4. What Python statement produces a list containing contains the values 45, −3, 16 and 8?
5. What function returns the number of elements in a list?
6. Given the list
lst = [20, 1, -34, 40, -8, 60, 1, 3]

evaluate the following expressions:

(a) lst
(b) lst[0:3]
(c) lst[4:8]
(d) lst[4:33]
(e) lst[-5:-3]
(f) lst[-22:3]
(g) lst[4:]
(h) lst[:]
(i) lst[:4]
(j) lst[1:5]
7. An assignment statement containing the expression a[m:n] on the left side and a list on the right
side can modify list a. Complete the following table by supplying the m and n values in the slice
assignment statement needed to produce the indicated list from the given original list.
Slice indices
Original List Target List m n
[2, 4, 6, 8, 10] [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
[2, 4, 6, 8, 10] [-10, -8, -6, -4, -2, 0, 2, 4, 6, 8, 10]
[2, 4, 6, 8, 10] [2, 3, 4, 5, 6, 7, 8, 10]
[2, 4, 6, 8, 10] [2, 4, 6, ’a’, ’b’, ’c’, 8, 10]
[2, 4, 6, 8, 10] [2, 4, 6, 8, 10]
[2, 4, 6, 8, 10] []
[2, 4, 6, 8, 10] [10, 8, 6, 4, 2]
[2, 4, 6, 8, 10] [2, 4, 6]
[2, 4, 6, 8, 10] [6, 8, 10]
[2, 4, 6, 8, 10] [2, 10]
[2, 4, 6, 8, 10] [4, 6, 8]
8. Complete the following function that adds up all the positive values in a list of integers. For example,
if list a contains the elements 3, —
3, 5, 2, −
1, and 2, the call sum_positive(a) would evaluate to 12,
since 3 + 5 + 2 + 2 = 12. The function returns zero if the list is empty.
def sum_positive(a):
# Add your code...

9. Complete the following function that counts the even numbers in a list of integers. For example, if
list a contains the elements 3, 5, 2,−1, and 2, the call count_evens(a) would evaluate to 4, since
2 + 2 = 4. The function returns zero if the list is empty. The function does not affect the contents of
the list.
def count_evens(a):
# Add your code...

10. Write a function named print_big_enough that accepts two parameters, a list of numbers and a
number. The function should print, in order, all the elements in the list that are at least as large as the
second parameter.
11. Write a function named reverse that reorders the contents of a list so they are reversed from their
original order. a is a list. Note that your function must physically rearrange the elements within the
list, not just print the elements in reverse order
List Processing

Lists, introduced in Chapter 9, are convenient structures for storing large amounts of data. In this chapter we
examine several algorithms that allow us to rearrange the elements of a list in a regular way and efficiently
search for elements within a list.

10.1 Sorting

Sorting—arranging the elements within a list into a particular order—is a common activity. For example,
a list of integers may be arranged in ascending order (that is, from smallest to largest). A list of strings
may be arranged in lexicographical (commonly called alphabetical) order. Many sorting algorithms exist,
and some perform much better than others. We will consider one sorting algorithm that is relatively easy to
implement.
The selection sort algorithm is relatively easy to implement and easy to understand how it works. If A
is a list, and i represents a list index, selection sort works as follows:

1. Set n = length of list A.

2. Set i = 0.

3. Examine all the elements A[ j], where i < j < n. (This simply means to consider all the elements in
the list from index i to the end.) If any of these elements is less than A[i], then exchange A[i] with the
smallest of these elements. (This ensures that all elements after position i are greater than or equal to
A[i].)

4. If i is less than n− 1, set i equal to i + 1 and go to Step 2.

5. Done; list A is sorted.

The command to “go to Step 2” in Step 4 represents a loop. When the value of i in Step 3 equals n, the
algorithm terminates with a sorted list.
We can begin to translate the above description into Python as follows:
n = len(A)
for i in range(n - 1):
# Examine all the elements A[j], where i < j < n.
# If any of these A[j] is less than A[i],
# then exchange A[i] with the smallest of these elements.

The directive at Step 2 beginning with “Examine all the elements A[ j], where i < j < n” also must be
implemented as a loop. We continue refining our implementation with:
n = len(A)
for i in range(n - 1):
# Examine all the elements A[j], where i < j < n.
for j in range(i + 1, n):
# If any A[j] is less than A[i],
# then exchange A[i] with the smallest of these elements.

In order to determine if any of the elements is less than A[i], we introduce a new variable named small.
The purpose of small is to keep track of the position of the smallest element found so far. We will set
small equal to i initially, because we wish to locate any element less than the element located at position
i.
n = len(A)
for i in range(n - 1):
# small is the position of the smallest value we've seen
# so far; we use it to find the smallest value less than A[i]
small = i
for j in range(i + 1, n):
if A[j] < A[small]:
small = j # Found a smaller element, update small
# If small changed, we found an element smaller than A[i]
if small != i:
# exchange A[small] and A[i]

Listing 10.1 ([Link]) provides the complete Python implementation of the selection_sort
function within a program that tests it out.

Listing 10.1: [Link]

1 from random import randrange
2
3 def random_list():
4 '''
5 Produce a list of pseudorandom integers.
6 The list's length is chosen pseudorandomly in the
7 range 3-20.
8 The integers in the list range from -50 to 50.
9 '''
10 result = []
11 count = randrange(3, 20)
12 for i in range(count):
13 result += [randrange(-50, 50)]
14 return result
15
16 def selection_sort(lst):
17 '''
18 Arranges the elements of list lst in ascending order.

©2011 Richard L. Halterman Draft date: November 13, 2011

19 The contents of lst are physically rearranged.
20 '''
21 n = len(lst)
22 for i in range(n - 1):
23 # Note: i, small, and j represent positions within lst
24 # lst[i], lst[small], and lst[j] represent the elements at
25 # those positions.
26 # small is the position of the smallest value we've seen
27 # so far; we use it to find the smallest value less
28 # than lst[i]
29 small = i
30 # See if a smaller value can be found later in the list
31 # Consider all the elements at position j, where i < j < n
32 for j in range(i + 1, n):
33 if lst[j] < lst[small]:
34 small = j # Found a smaller value
35 # Swap lst[i] and lst[small], if a smaller value was found
36 if i != small:
37 lst[i], lst[small] = lst[small], lst[i]
38
39 def main():
40 '''
41 Tests the selection_sort function
42 '''
43 for n in range(10):
44 col = random_list()
45 print(col)
46 selection_sort(col)
47 print(col)
48 print('==============================')
49
50 main()

One run of Listing 10.1 ([Link]) produces:

[-23, 47, -3, 4, 5, -46, 26, -27]
[-46, -27, -23, -3, 4, 5, 26, 47]
==============================
[32, -10, -4, 41, 10, -1, -31, 3, 28, -31, -33, 46, -45, -6, 37]
[-45, -33, -31, -31, -10, -6, -4, -1, 3, 10, 28, 32, 37, 41, 46]
==============================
[11, -19, 20, 43, -19, 20, -18, -17]
[-19, -19, -18, -17, 11, 20, 20, 43]
==============================
[9, -22, -41, 35, 10, 48, 9, 14, -20]
[-41, -22, -20, 9, 9, 10, 14, 35, 48]
==============================
[-38, -3, -7, 41, -8, -11, -23, 9, -47, 38]
[-47, -38, -23, -11, -8, -7, -3, 9, 38, 41]
==============================
[-47, 1, -37, 16, -40, -14, 2, 38, 43, 19, 45]
[-47, -40, -37, -14, 1, 2, 16, 19, 38, 43, 45]
==============================
[8, 39, 35, -42]
[-42, 8, 35, 39]
==============================
[-8, -22, -13, 47, -28, -46, -21, -42, 27, 14, 47, -21, 2, -47]
[-47, -46, -42, -28, -22, -21, -21, -13, -8, 2, 14, 27, 47, 47]
==============================
[37, -21, -32, -7]
[-32, -21, -7, 37]
==============================
[33, -42, -26, 35, 37, 36, -1, 47, 24, 5, 41, -6, 48, 6, 43]
[-42, -26, -6, -1, 5, 6, 24, 33, 35, 36, 37, 41, 43, 47, 48]
==============================

Notice than in each case the elements in the pseudorandomly generated list are rearranged into correct
ascending order. To check the correctness of our sort we need to be sure that:

• the sorted list contains the same number of elements as the original, unsorted list,
• no elements in the original list are missing,
• no elements in the sorted list appear more frequently than they did in the original, unsorted list, and
• the elements appear in ascending order.

The output of Listing 10.1 ([Link]) provides evidence that our selection_sort function is
working correctly.

10.2 Flexible Sorting

What if want to change the behavior of the sorting function in Listing 10.1 ([Link]) so that it
arranges the elements in descending order instead of ascending order? It is actually an easy modification;
simply change the line
if lst[j] < lst[small]:

to be
if lst[j] > lst[small]:

What if instead we want to change the sort so that it sorts the elements in ascending order except that all
the even numbers in the list appear before all the odd numbers? This modification would be a little more
complicated, but it could accomplished in that if statement’s conditional expression.
The next question is more intriguing: How can we rewrite the selection_sort function so that, by
passing an additional parameter, it can sort the list in any way we want?
We can make our sort function more flexible by passing an ordering function as a parameter (see Sec-
tion 8.6 for examples of functions as parameters to other functions). Listing 10.2 ([Link])
arranges the elements in a list two different ways using the same selection_sort function.

Listing 10.2: [Link]

1 def random_list():
2 '''
3 Produce a list of pseudorandom integers.
4 The list's length is chosen pseudorandomly in the
5 range 3-20.
6 The integers in the list range from -50 to 50.
7 '''
8 from random import randrange
9 result = []
10 count = randrange(3, 20)
11 for i in range(count):
12 result += [randrange(-50, 50)]
13 return result
14
15
16 def less_than(m, n):
17 return m < n
18
19 def greater_than(m, n):
20 return m > n
21
22
23 def selection_sort(lst, cmp):
24 '''
25 Arranges the elements of list lst in ascending order.
26 The comparer function cmp is used to order the elements.
27 The contents of lst are physically rearranged.
28 '''
29 n = len(lst)
30 for i in range(n - 1):
31 # Note: i, small, and j represent positions within lst
32 # lst[i], lst[small], and lst[j] represent the elements at
33 # those positions.
34 # small is the position of the smallest value we've seen
35 # so far; we use it to find the smallest value less
36 # than lst[i]
37 small = i
38 # See if a smaller value can be found later in the list
39 # Consider all the elements at position j, where i < j < n.
40 for j in range(i + 1, n):
41 if cmp(lst[j], lst[small]):
42 small = j # Found a smaller value
43 # Swap lst[i] and lst[small], if a smaller value was found
44 if i != small:
45 lst[i], lst[small] = lst[small], lst[i]
46
47 def main():
48 '''
49 Tests the selection_sort function
50 '''
51 original = random_list() # Make a random list
52 working = original[:] # Make a working copy of the list
53 print('Original: ', working)
54 selection_sort(working, less_than) # Sort ascending
55 print('Ascending: ', working)
56 working = original[:] # Make a working copy of the list
57 print('Original: ', working)
58 selection_sort(working, greater_than) # Sort descending
59 print('Descending:', working)
60
61 main()

The output of Listing 10.2 ([Link]) is

Original: [-8, 24, -46, -7, -26, -29, -44]

Ascending: [-46, -44, -29, -26, -8, -7, 24]
Original: [-8, 24, -46, -7, -26, -29, -44]
Descending: [24, -7, -8, -26, -29, -44, -46]

The comparison function passed to the sort routine customizes the sort’s behavior. The basic structure of
the sorting algorithm does not change, but its notion of ordering is adjustable. If the second parameter
to selection_sort is less_than, the function arranges the elements ascending order. If the second
parameter instead is greater_than, the function sorts the list in descending order. More creative orderings
are possible with more elaborate comparison functions.
Selection sort is a relatively efficient simple sort, but more advanced sorts are, on average, much faster
than selection sort, especially for large data sets. One such general purpose sort is Quicksort, devised by
C. A. R. Hoare in 1962. Quicksort is the fastest known general purpose sort.

10.3 Search

Searching a list for a particular element is a common activity. We examine two basic strategies: linear
search and binary search.
10.3.1 Linear Search

Listing 10.3 ([Link]) uses a function named locate that returns the position of the first occur-
rence of a given element in a list; if the element is not present, the function returns None.

The output of Listing 10.3 ([Link]) is

100 44 2 80 5 13 11 2 110
ˆ
|
+-- 13

100 44 2 80 5 13 11 2 110
ˆ
|
+-- 2

100 44 2 80 5 13 11 2 110
(7 not in list)

100 44 2 80 5 13 11 2 110
ˆ
|
+-- 100

100 44 2 80 5 13 11 2 110
ˆ
|
+-- 110

The key function in Listing 10.3 ([Link]) is locate; all the other functions simply lead to a
more interesting display of locate’s results. If locate finds a match, the function immediately returns the
position of the matching element; otherwise, if after examining all the elements of the list it cannot find the
element sought, the function returns None. Here None indicates the function could not return a valid answer.
The client code, in this example the display function, must ensure that locate’s result is not None before
attempting to use the result as an index into a list.
The kind of search performed by locate is known as linear search, since a straight line path is taken
from the beginning of the list to the end of the list considering each element in order. Figure 10.1 illustrates
linear search.

lst = [100, 44, 2, 80, 5, 13, 11, 2, 110]

x = locate(lst, 13)

100 44 2 80 5 13 11 2 110
lst

0 1 2 3 4 5 6 7 8
13?
5

Figure 10.1: Linear search

10.3.2 Binary Search

Linear search is acceptable for relatively small lists, but the process of examining each element in a large
list is time consuming. An alternative to linear search is binary search. In order to perform binary search, a
list must be in sorted order. Binary search exploits the sorted structure of the list using a clever but simple
strategy that quickly zeros in on the element to find:

1. If the list is empty, return None.

2. Check the element in the middle of the list. If that element is what you are seeking, return its position.
If the middle element is larger than the element you are seeking, perform a binary search on the first
half of the list. If the middle element is smaller than the element you are seeking, perform a binary
search on the second half of the list.

This approach is analogous to looking for a telephone number in the phone book in this manner:

1. Open the book at its center. If the name of the person is on one of the two visible pages, look at the
phone number.

2. If not, and the person’s last name is alphabetically less the names on the visible pages, apply the
search to the left half of the open book; otherwise, apply the search to the right half of the open book.
3. Discontinue the search with failure if the person’s name should be on one of the two visible pages
but is not present.
The binary search algorithm can be implemented as a Python function as shown in Listing 10.4 ([Link]).

Listing 10.4: [Link]

1 def binary_search(lst, seek):
2 '''
3 Returns the index of element seek in list lst,
4 if seek is present in lst.
5 Returns None if seek is not an element of lst.
6 lst is the lst in which to search.
7 seek is the element to find.
8 '''
9 first = 0 # Initialize the first position in list
10 last = len(lst) - 1 # Initialize the last position in list
11 while first <= last:
12 # mid is middle position in the list
13 mid = first + (last - first + 1)//2 # Note: Integer division
14 if lst[mid] == seek:
15 return mid # Found it
16 elif lst[mid] > seek:
17 last = mid - 1 # continue with 1st half
18 else: # v[mid] < seek
19 first = mid + 1 # continue with 2nd half
20 return None # Not there
21
22
23 def show(lst):
24 '''
25 Prints the contents of list lst
26 '''
27 for item in lst:
28 print("%4d" % item, end='') # Print element right justifies in 4 spaces
29 print() # Print newline
30
31 def draw_arrow(value, n):
32 '''
33 Print an arrow to value which is an element in a list.
34 n specifies the horizontal offset of the arrow.
35 '''
36 print(("%" + str(n) + "s") % " ˆ ")
37 print(("%" + str(n) + "s") % " | ")
38 print(("%" + str(n) + "s%i") % (" +-- ", value))
39
40
41 def display(lst, value):
42 '''
43 Draws an ASCII art arrow showing where
44 the given value is within the list.
45 lst is the list.
46 value is the element to locate.
47 '''
48 show(lst) # Print contents of the list
49 position = binary_search(lst, value)
50 if position != None:
51 position = 4*position + 7; # Compute spacing for arrow
52 draw_arrow(value, position)
53 else:
54 print("(", value, " not in list)", sep='')
55 print()
56
57
58 def main():
59 a = [2, 5, 11, 13, 44, 80, 100, 110]
60 display(a, 13)
61 display(a, 2)
62 display(a, 7)
63 display(a, 100)
64 display(a, 110)
65
66 main()

In the binary_search function:

• The initializations of first and last:

first = 0 # Initialize the first position in list
last = len(lst) - 1 # Initialize the last position in list

ensure that first is less than or equal to last for a nonempty list. If the list is empty, first is zero,
and last is equal to len(lst) - 1 — =01− = 1. So in the case of an empty list the function will
skip the loop and return None. This is correct behavior because an empty list cannot possibly contain
any item we seek.

• The calculation of mid ensures that first ≤ mid ≤ last.

• If mid is the location of the sought element (checked in the first if statement), the loop terminates,
and returns the correct position.

• The elif and else clauses ensure that either last decreases or first increases each time through
the loop. Thus, if the loop does not terminate for other reasons, eventually first will be larger than
last, and the loop will terminate. If the loop terminates for this reason, the function returns None.
This is the correct behavior.

• The modification to either first or last in the elif and else clauses exclude irrelevant elements
from further search. The number of elements to consider is cut in half each time through the loop.

Figure 10.2 illustrates how binary search works.

The implementation of the binary search algorithm is more complicated than the simpler linear search
algorithm. Ordinarily simpler is better, but for algorithms that process data structures that potentially hold
large amounts of data, more complex algorithms employing clever tricks that exploit the structure of the
data (as binary search does) often dramatically outperform simpler, easier-to-code algorithms.
For a fair comparison of linear vs. binary search, suppose we want to locate an element in a sorted list.
That the list is ordered is essential for binary search, but it can be helpful for linear search as well. The
revised linear search algorithm for ordered lists is
# This version requires list lst to be sorted in
# ascending order.
def linear_search(lst, seek):
i = 0 # Start at beginning
lst = [10, 14, 20, 28, 29, 33, 34, 45, 48]
x = locate(lst, 33)

10 14 20 28 29 33 34 45 48
lst

0 1 2 3 4 5 6 7 8

33? 5

Figure 10.2: Binary search

n = len(lst) # Length of list

while i < n and lst[i] <= seek:
if lst[i] == seek:
return i # Return position immediately
return None # Element not found

Notice that, as in the original version of linear search, the loop will terminate when all the elements have
been examined, but this version will terminate early when it encounters an element larger than the sought
element. Since the list is sorted, there is no need to continue the search once the search has found an element
larger than the value sought; seek cannot appear after a larger element in a sorted list.
Suppose a list to search contains n elements. In the worst case—looking for an element larger than
any currently in the list—the loop in linear search takes n iterations. In the best case—looking for an
element smaller than any currently in the list—the function immediately returns without considering any
other elements. The number of loop iterations thus ranges from 1 to n, and so on average linear search
requires n2 comparisons before the loop finishes and the function returns.
Now consider binary search. After each comparison the size of the list left to consider is one-half the
original size. If the sought item is not found on the first probe, the number of remaining elements to search
is n2 . The next time through the loop, the number of elements left to consider drops to n4, then n8, and so
forth. The problem of determining how many times a set of things can be divided in half until only one
element remains can be solved with a base-2 logarithm. For binary search, the worst case scenario of not
finding the sought element requires the loop to make log2 n iterations.
How does this analysis help us determine which search is better? The quality of an algorithm is judged
by two key characteristics:

• How much time (processor cycles) does it take to run?

• How much space (memory) does it take to run?

In our situation, both search algorithms process the list with only a few extra local variables, so for large
lists they both require essentially the same space. The big difference here is speed. Binary search performs
more elaborate computations each time through the loop, and each operation takes time, so perhaps binary
search is slower. Linear search is simpler (fewer operations through the loop), but perhaps its loop executes
many more times than the loop in binary search, so overall it is slower.
We can deduce the faster algorithm in two ways: empirically and analytically. An empirical test is an
experiment; we carefully implement both algorithms and then measure their execution times. The analyt-
ical approach analyzes the source code to determine how many operations the computer’s processor must
perform to run the program on a problem of a particular size.
Listing 10.5 ([Link]) gives us some empirical results.

Listing 10.5: [Link]

1 def binary_search(lst, seek):
2 '''
3 Returns the index of element seek in list lst,
4 if seek is present in lst.
5 lst must be in sorted order.
6 Returns None if seek is not an element of lst.
7 lst is the lst in which to search.
8 seek is the element to find.
9 '''
10 first = 0 # Initially the first element in list
11 last = len(lst) - 1 # Initially the last element in list
12 while first <= last:
13 # mid is middle of the list
14 mid = first + (last - first + 1)//2 # Note: Integer division
15 if lst[mid] == seek:
16 return mid # Found it
17 elif lst[mid] > seek:
18 last = mid - 1 # continue with 1st half
19 else: # v[mid] < seek
20 first = mid + 1 # continue with 2nd half
21 return None # Not there
22
23 def ordered_linear_search(lst, seek):
24 '''
25 Returns the index of element seek in list lst,
26 if seek is present in lst.
27 lst must be in sorted order.
28 Returns None if seek is not an element of lst.
29 lst is the lst in which to search.
30 seek is the element to find.
31 '''
32 i = 0
33 n = len(lst)
34 while i < n and lst[i] <= seek:
35 if lst[i] == seek:
36 return i # Return position immediately
37 i += 1
38 return None # Element not found
39
40 def test_searches(lst):
41 from time import clock
42
43 # Find each element using ordered linear search
44 start = clock() # Start the clock
45 n = len(lst)
46 for i in range(n):
47 if ordered_linear_search(lst, i) != i:
48 print("error")
49 stop = clock() # Stop the clock
50 print("Linear elapsed time", stop - start)
51
52 # Find each element using binary search
53 start = clock() # Start the clock
54 n = len(lst)
55 for i in range(n):
56 if binary_search(lst, i) != i:
57 print("error")
58 stop = clock() # Stop the clock
59 print("Binary elapsed time", stop - start)
60
61 def main():
62 SIZE = 20000
63 test_list = list(range(SIZE))
64 test_searches(test_list)
65
66 main()

The test_searches function in Listing 10.5 ([Link]) searches for all the elements in a list
using first ordered linear search and then binary search. On one system, Listing 10.5 ([Link])
produces:

Linear elapsed time 72.68487246407194

Binary elapsed time 0.19088075623170653

The ordered linear search exercises take over one 72 seconds, while the binary search applied to the exact
same searches takes less than one-fifth of a second. Binary search is almost 400 times faster than ordered
linear search!
Table 10.1 lists the results for various sized lists. Empirically, binary search performs dramatically
better than linear search. Figure 10.3 plots the values in Table 10.1.
In addition to using the empirical approach, we can judge which algorithm is better by analyzing the
source code for each function. Each arithmetic operation, assignment, logical comparison, and list access
requires time to execute. We will assume each of these activities requires one unit of processor “time.” This
assumption is not strictly true, but it will give good results for relative comparisons. Since we will follow
the same rules when analyzing both search algorithms, the relative results for comparison purposes will be
fairly accurate.
We first consider linear search. We determined that, on average, the loop makes 2n iterations for a list of
size n. The initialization of i happens only one time during each call to linear_search. All other activity
involved with the loop except the return statements happens n2 times. Either i or None will be returned,
and only one return is executed during each call. Table 10.2 shows the breakdown for linear search. The
List Size Linear Search Binary Search
0 0.415 0.415
10 5.488 4.205
20 9.002 5.804
30 16.266 9.081
40 31.486 13.206
50 36.579 17.786
60 57.760 21.004
70 76.474 24.794
80 101.229 28.426
90 127.345 33.800

Table 10.1: Run-time behavior of linear and binary search on lists of different sizes. Time is listed in 10−5
seconds.

Operation Times Total

Action Operation(s) Count Executed Cost
i = 0 = 1 1 1
n = len(lst) =, len 2 1 2
n
while i < n and lst[i] <= seek: <, and, <=, [] 4 2 2n
n
if lst[i] == seek: [], == 2 2 n
1 1
return i return 1 2 2
1 1
return None return 1 2 2
Total time units 3n + 4

Table 10.2: Analysis of Linear Search Algorithm. The n2 loop iterations is based on average time to locate
an element. The function will execute exactly one of the two return statements during a given call, so each
is given a cost of 21 .
100
Time in Seconds

Linear Search
Binary Search

0
0 10 20 30 40 50 60 70 80 90

List Size

Figure 10.3: Linear vs. Binary Search

results in Table 10.2 indicate the running time of the linear_search function can be expressed as a simple
mathematical linear function: f (n) = 3n + 4.
Next, we consider binary search. We determined that in the worst case the loop in binary_search
iterates log2 n times if the list contains n elements. The two initializations before the loop are performed
once per call. Most of the actions within the loop occur log 2 n times, except that only one return statement
can be executed per call, and in the if/elif/else statement only one path can be chosen per loop iteration.
10.3 shows the complete analysis of binary search. Figure 10.4 shows the plot of the two functions 3n + 4
and 12 log2 n + 6. Note the similarity of these pure function curves to the curves in Figure 10.3.

250
Time in Seconds

200 Linear
Logarithmic
150

100

0
0 10 20 30 40 50 60 70 80 90

List Size

Figure 10.4: A graph of the functions derived from analyzing the linear and binary search routines

The bottom line is that binary search is fast even for large lists.
Operation Times Total
Action Operation(s) Count Executed Cost
first = 0 = 1 1 1
last = len(lst) - 1 =, len, - 3 1 3
while first <= last: <= 1 log2 n log2 n
mid=first+(last-first+1)//2 =, +, -, +, // 5 log2 n 5 log2 n
if lst[mid] == seek: [], == 2 log2 n 2 log2 n
return mid return 1 1 1
elif lst[mid] > seek: [], > 2 log2 n 2 log2 n
1
last = mid - 1 =, - 2 log2 n log2 n
2
else: 0 0
1
first = mid + 1 =, + 2 2
log2 n log2 n
return None return 1 1 1
Total time units 12 log2 n + 6

Table 10.3: Analysis of Binary Search Algorithm. Each time through the loop the function executes either
the elif or else statement, so each one is charged is charged 21 its actual cost.

10.4 List Permutations

Sometimes it is useful to consider all the possible arrangements of the elements within a list. A sorting
algorithm, for example, must work correctly on any initial arrangement of elements in a list. To test a sort
function, a programmer could check to see to see if it produces the correct result for all arrangements of a
relatively small list. A rearrangement of a collection of ordered items is called a permutation. Listing 10.6
([Link]) generates all the permutations of a given list.

Listing 10.6: [Link]

1 def permute(prefix, suffix):
2 '''
3 Recursively shifts all the elements in suffix into
4 prefix producing all the permutations of suffix.
5 Prints all permutations in lexicographical order.
6 '''
7 suffix_size = len(suffix)
8 if suffix_size == 0: # Have we considered all the elements?
9 print(prefix)
10 else:
11 for i in range(0, suffix_size):
12 new_pre = prefix + [suffix[i]]
13 new_suff = suffix[:i] + suffix[i + 1:]
14 permute(new_pre, new_suff)
15
16
17
18 def print_permutations(lst):
19 '''
20 Calls the recursive permute function to display
21 all the permutations of the elements of lst in
22 lexicographical order. The empty list is passed as
23 the first parameter to permute, and the list to
24 permute is passed as the second argument.
25 '''
26 permute([], lst)
27
28 def main():
29 a = [1, 2, 3, 4]
30 print_permutations(a)
31
32 main()

Listing 10.6 ([Link]) produces the following output:

[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 1, 3]
[2, 4, 3, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 1, 2, 3]
[4, 1, 3, 2]
[4, 2, 1, 3]
[4, 2, 3, 1]
[4, 3, 1, 2]
[4, 3, 2, 1]

Notice that every possible unique arrangement of the elements in the list [1, 2, 3, 4] appear in the
output.
The permute function in Listing 10.6 ([Link]) uses a loop and recursion to generate
all the possible orderings for a given list. Recursion can be difficult to follow, but we can better understand
the process by instrumenting the permute function as follows:
def permute(prefix, suffix, depth):
'''
Recursively shifts all the elements in suffix into
prefix producing all the permutations of suffix.
Prints all permutations in lexicographical order.
'''
suffix_size = len(suffix)
if suffix_size == 0: # Have we considered all the elements?
pass # print('>>>', prefix, '<<<')
else:
for i in range(0, suffix_size):
new_pre = prefix + [suffix[i]]
new_suff = suffix[:i] + suffix[i + 1:]
tab(depth)
print(new_pre, new_suff, sep=':')
permute(new_pre, new_suff, depth + 1)

This version of permute includes printing statements that reveal the algorithm’s process. The tab function,
def tab(n):
for i in range(n):
print(end=' ')

indents the output in proportion to the depth of the recursion. Notice that this version of permute accepts
an additional parameter named depth. This parameter represents the depth of the recursion. The first few
lines of output produced by the call
permute([], [1, 2, 3, 4], 0)

are:

[1]:[2, 3, 4]
[1, 2]:[3, 4]
[1, 2, 3]:[4]
[1, 2, 3, 4]:[]
[1, 2, 4]:[3]
[1, 2, 4, 3]:[]
[1, 3]:[2, 4]
[1, 3, 2]:[4]
[1, 3, 2, 4]:[]
[1, 3, 4]:[2]
[1, 3, 4, 2]:[]
[1, 4]:[2, 3]
[1, 4, 2]:[3]
[1, 4, 2, 3]:[]
[1, 4, 3]:[2]
[1, 4, 3, 2]:[]
[2]:[1, 3, 4]
[2, 1]:[3, 4]
[2, 1, 3]:[4]
[2, 1, 3, 4]:[]
[2, 1, 4]:[3]
[2, 1, 4, 3]:[]

(The complete output has more lines.) The initial depth is zero, and each recursive calls passes a depth
parameter that is one more than the current depth. A greater indentation in an output line indicates a deeper
level of recursion. Notice that the recursion stops (indicated by the indentation going no deeper) when the
suffix is empty.
While Listing 10.6 ([Link]) is a good exercise in recursive list processing, the Python
standard library provides a function named permutations in the itertools module that allows us to gen-
erate permutations with very little code. Listing 10.7 ([Link]) produces the same orderings
as Listing 10.6 ([Link]), but it produces the orderings in tuples instead of lists.

10.5 Randomly Permuting a List

Section 10.4 showed how we can generate all the permutations of a list in an orderly fashion. Often,
however, we need to produce one those permutations chosen at random. For example, we may need to
randomly rearrange the contents of an ordered list so that we can test a sort function to see if it will produce
the original list. We could generate all the permutations, put each one in a list, and select a permuta-
tion at random from that list. This approach is inefficient, especially as the length of the list to permute
grows larger. Fortunately, we can randomly permute the contents of a list easily and quickly. Listing 10.8
([Link]) contains a function named permute that randomly permutes the elements of a list.

Notice that the permute function in Listing 10.8 ([Link]) uses a simple un-nested loop and no
recursion. The permute function varies the i index variable from 0 to the index of the next to last element
in the list. An index greater than i is chosen pseudorandomly using randrange (see Section 6.4), and the
elements at position i and the random position are exchanged. At this point all the elements at position i
and smaller are fixed and will not change as the function’s execution continues. The index i is incremented,
and the process continues until all the i values have been considered.
Two be correct, our permute function must be able to generate any valid permutation of the list. It is
important that our permute function is able produce all possible permutations with equal probability; said
another way, we do not want our permute function to generate some permutations more often than others.
The permute function in Listing 10.8 ([Link]) is fine, but consider a slight variation of the
algorithm:
def faulty_permute(lst):
'''
An attempt to randomly permute the contents of list lst
'''
n = len(lst)
for i in range(n - 1):
pos = randrange(0, n) # 0 <= pos < n
lst[i], lst[pos] = lst[pos], lst[i]

Do you see the difference between faulty_permute and permute? In faulty_permute, the random index
is chosen from all valid list indices, whereas permute restricts the random index to valid indices greater
than or equal to i. This means that any element within lst can be exchanged with the element at position i
during any loop iteration. While this approach may superficially appear to be just as good as permute, it in
fact produces an uneven distribution of permutations. Listing 10.9 ([Link]) exercises
each permutation function 1,000,000 times on the list [1, 2, 3] and tallies each permutation. There are
exactly six possible permutations of this three-element list.

In Listing 10.9 ([Link])’s output, permute #1 corresponds to our original permute

function, and permute #2 is the faulty_permute function. The output of Listing 10.9 ([Link])
reveals that the faulty permutation function favors some permutations over others:

--- Random permute #1 -----

1,2,3: 166576
1,3,2: 167372
2,1,3: 166117
2,3,1: 166797
3,1,2: 166925
3,2,1: 166213
--- Random permute #2 -----
1,2,3: 222789
1,3,2: 111010
2,1,3: 222458
2,3,1: 221987
3,1,2: 110690
3,2,1: 111066

In one million runs, the permute function provides an even distribution of the six possible permutations
of [1, 2, 3]. The faulty_permute function generates the permutations [1, 2, 3], [2, 1, 3, and
[2, 3, 1] twice as many times as the permutations [1, 3, 2], [3, 1, 2], and [3, 2, 1].
To see why faulty_permute misbehaves, we need to examine all the permutations it can produce
during one call. Figure 10.5 shows a hierarchical structure that maps out how faulty_permute transforms
its list parameter each time through the for loop. The top of the tree shows the original list, [1, 2, 3].
The second row shows the three possible resulting lists after the first iteration of the for loop. The leftmost
list represents the element at index zero swapped with the element at index zero (effectively no change). The
second list on the second row represents the interchange of the elements at index 0 and index 1. The third
list on the second row results from the interchange of the elements at positions 0 and 2. The underlined
elements represent the elements most recently swapped. If only one item in the list is underlined, the
function merely swapped the item with itself.
123

123 213 321

213 123 132 123 213 231 231 321 312

Figure 10.5: A tree mapping out the ways in which faulty permute can transform the list [1, 2, 3] at each
iteration of its for loop

As Figure 10.5 shows, the lists [1, 2, 3], [2, 1, 3, and [2, 3, 1] each appear twice in the last
row, while [1, 3, 2], [3, 1, 2], and [3, 2, 1] each appear only once. This means, for example, that
the function is twice as likely to produce [1, 2, 3] as [1, 3, 2].

123

123 213 321

123 132 213 231 321 312

Figure 10.6: A tree mapping out the ways in which permute can transform the list [1, 2, 3] at each iteration
of its for loop

Compare Figure 10.5 to Figure 10.6. The second row of the tree for permute is identical to the second
row of the tree for faulty_permute, but the third rows are different. The second time through its loop
the permute function does not attempt to exchange the element at index zero with any other elements. We
see that none of the first elements in the lists in row three are underlined. The third row contains exactly
one instance of each of the possible permutations of [1, 2, 3]. This means that the correct permute
function is not biased towards any of the individual permutations, and so the function can generate all the
permutations with equal probability.
10.6 Reversing a List

Listing 10.10 ([Link]) contains a recursive function named rev that accepts a list as a parameter
and returns a new list with all the elements of the original list in reverse order.

Listing 10.10: [Link]

1 def rev(lst):
2 return [] if len(lst) == 0 else rev(lst[1:]) + lst[0:1]
3
4 print(rev([1, 2, 3, 4, 5, 6, 7]))

Python has a standard function, reversed, that accepts a list parameter. The reversed function does
not return a list but instead returns an iterable object that can be used like the range function within a for
loop (see Section 5.3). Listing 10.11 ([Link]) shows how reversed can be used to print the contents
of a list backwards.

Listing 10.11: [Link]

1 for item in reversed([1, 2, 3, 4, 5, 6, 7]):
2 print(item)

In Section 11.3 we will see how to reverse the elements in a list using a special funtion-like object called
a method.

10.7 Summary

• Various algorithms exist for sorting lists. Selection sort is a simple algorithm for sorting a list.
• A list formal parameter aliases the actual parameter passed by the client. This means any modifica-
tions a function makes to the contents of the list will affect the client’s own list. This concept allows
a sort or permutation routine to physically rearrange the elements in a list for the client’s benefit.
• Linear search is useful for finding elements in an unordered list. Binary search can be used on ordered
lists, and due to the nature of its algorithm, binary search is very fast, even on large lists.
• A permutation of a list is a reordering of its elements.
• Care must be taken when producing a random permutation of a list to ensure all the possible outcomes
are equally likely.

10.8 Exercises

1. Complete the following function that reorders the contents of a list so they are reversed from their
original order. For example, a list containing the elements 2, 6, 2, 5, 0, 1, 2, 3 would be transformed
into 3, 2, 1, 0, 5, 2, 6, 2. Note that your function must physically rearrange the elements within the
list, not just print the elements in reverse order.
def reverse(lst):
# Add your code...
2. Complete the following function that reorders the contents of a list of integers so that all the even
numbers appear before any odd number. The even values are sorted in ascending order with respect
to themselves, and the odd numbers that follow are also sorted in ascending order with respect to
themselves. For example, a list containing the elements 2, 1, 10, 4, 3, 6, 7, 9, 8, 5 would be trans-
formed into 2, 4, 6, 8, 10, 1, 3, 5, 7, 9 Note that your function must physically rearrange the elements
within the list, not just print the elements in the desired order.
def special_sort(lst):
# Add your code...

3. Create a special comparison function to be passed to our flexible selection sort function. The special
comparison function should enable the sort function to arrange the elements of a list in the order
specified in Exercise 2.

4. Complete the following function that filters negative elements out of a list. The function returns the
filtered list and the original list is unchanged. For example, if a list containing the elements 2, − 16,
2, —5, 0, 1, −2, 3−is passed to the function, the function would return the list containing 2, 2, 0, 1.
Note the original ordering of the non-negative values is unchanged in the result.
def filter(a):
# Add your code...

5. Complete the following function that shifts all the elements of a list backward one place. The last
element that gets shifted off the back end of the list is copied into the first (0th) position. For example,
if a list containing the elements 2, 1, 10, 4, 3, 6, 7, 9, 8, 5 is passed to the function, it would be
transformed into 5, 2, 1, 10, 4, 3, 6, 7, 9, 8 Note that your function must physically rearrange the
elements within the list, not just print the elements in the shifted order.
def rotate(lst):
# Add your code...

6. Complete the following function that determines if the number of even and odd values in an integer
list is the same. The function would return true if the list contains 5, 1, 0, 2 (two evens and two odds),
but it would return false for the list containing 5, 1, 0, 2, 11 (too many odds). The function should
return true if the list is empty, since an empty list contains the same number of evens and odds (0 for
both). The function does not affect the contents of the list.
def balanced(a):
# Add your code...

7. Complete the following function that returns true if a list lst contains duplicate elements; it returns
false if all the elements in lst are unique. For example, the list [2, 3, 2, 1, 9] contains dupli-
cates (2 appears more than once), but the list [2, 1, 0, 3, 8, 4] does not (none of the elements
appear more than once).
An empty list has no duplicates. The function does not affect the contents of the list.
def has_duplicates(lst):
# Add your code...

8. Can linear search be used on an unsorted list? Why or why not?

9. Can binary search be used on an unsorted list? Why or why not?

10. How many different orderings are there for the list [4, 3, 8, 1, 10]?
11. Complete the following function that determines if two lists contain the same elements, but not nec-
essarily in the same order. The function would return true if the first list contains 5, 1, 0, 2 and the
second list contains 0, 5, 2, 1. The function would return false if one list contains elements the other
does not or if the number of elements differ. This function could be used to determine if one list is a
permutation of another list. The function does not affect the contents of either list.
def is_permutation(a, b):
# Add your code...
Chapter 5
Objects

In the hardware arena, a personal computer is built by assembling

• a motherboard (a circuit board containing sockets for a microprocessor and assorted support chips),

• a processor and its various support chips,

• memory boards,

• a video card,

• an input/output card (USB ports, parallel port, and mouse port),

• a disk controller,

• a disk drive,

• a case,

• a keyboard,

• a mouse, and

• a monitor.

(Some of these components like the I/O, disk controller, and video may be integrated with the mother-
board.)
The video card is itself a sophisticated piece of hardware containing a video processor chip, memory,
and other electronic components. A technician does not need to assemble the card; the card is used as is
off the shelf. The video card provides a substantial amount of functionality in a standard package. One
video card can be replaced with another card from a different vendor or with another card with different
capabilities. The overall computer will work with either card (subject to availability of drivers for the
operating system), because standard interfaces allow the components to work together.
Software development today is increasingly component based. Software components are used like
hardware components. A software system can be built largely by assembling pre-existing software building
blocks. Python supports various kinds of software building blocks. The simplest of these is the function
that we investigated in Chapter 6 and Chapter 7. A more powerful technique uses software objects.
Python is object oriented. Most modern programming languages support object-oriented (OO) develop-
ment to one degree or another. An OO programming language allows the programmer to define, create, and
manipulate objects. Objects bundle together data and functions. Like other variables, each Python object
has a type, or class. The terms class and type are synonymous.
In this chapter we explore some of the classes available in the Python standard library.

11.1 Using Objects

An object is an instance of a class. We have been using objects since the beginning, but we have not taken
advantage of all the capabilities that objects provide. Integers, floating-point numbers, strings, lists, and
functions are all objects in Python. With the exception of function objects, we have treated these objects
as passive data. We can assign an integer and use its value. We can add two floating-point numbers and
concatenate two strings with the + operator. We can pass objects to functions and functions can return
objects.
Objects fuse data and functions together. A typical object consists of two parts: data and methods. An
object’s data is sometimes called its attributes or fields. Methods are like functions, and they also are known
as operations. The data and methods of an object constitutes its members. Using the same terminology as
functions, the code that uses an object is called the object’s client. Just as a function provides a service to its
client, an object provides a service to its client. The services provided by an object can be more elaborate
that those provided by simple functions, because objects make it easy to store persistent data.
The assignment statement
x = 2

binds the variable x to an integer object with the value of 2. The name of the class of x is int. To see some
of the capabilities of int objects, issue the command dir(x) or dir(int) in the Python interpreter:

>>> dir(x)
[’ abs ’, ’ add ’, ’ and ’, ’ bool ’, ’ ceil ’,
’ class ’, ’ delattr ’, ’ divmod ’, ’ doc ’, ’ eq ’,
’ float ’, ’ floor ’, ’ floordiv ’, ’ format ’,
’ ge ’, ’ getattribute ’, ’ getnewargs ’, ’ gt ’,
’ hash ’, ’ index ’, ’ init ’, ’ int ’, ’ invert ’,
’ le ’, ’ lshift ’, ’ lt ’, ’ mod ’, ’ mul ’,
’ ne ’, ’ neg ’, ’ new ’, ’ or ’, ’ pos ’, ’ pow ’,
’ radd ’, ’ rand ’, ’ rdivmod ’, ’ reduce ’, ’ reduce_ex ’,
’ repr ’, ’ rfloordiv ’, ’ rlshift ’, ’ rmod ’, ’ rmul ’,
’ ror ’, ’ round ’, ’ rpow ’, ’ rrshift ’, ’ rshift ’,
’ rsub ’, ’ rtruediv ’, ’ rxor ’, ’ setattr ’, ’ sizeof ’,
’ str ’, ’ sub ’, ’ subclasshook ’, ’ truediv ’, ’ trunc ’,
’ xor ’, ’bit_length’, ’conjugate’, ’denominator’, ’from_bytes’,
’imag’, ’numerator’, ’real’, ’to_bytes’]

The dir function, which is available to Python programs as well, lists the members of the class (or an
object’s class, if called with an object argument). Most of these names are methods and are not meant for
clients to use directly. Member names that begin and end with two underscores are supposed to be reserved
for the object’s own internal use, but we can experiment to see how methods work. Many of these methods
are mapped to Python operators.
add is a method in the int class, so it is available to all integer objects. The expression x. add (3)
is an example of a method invocation. A method invocation works like a function invocation, except we
must qualify the call with an object’s name (or sometimes a class name). The expression begins with the ob-
ject’s name, followed by a dot (.), and then the method name with any necessary parameters. The following
interactive sequence shows how we can use the add method:

>>> x = 2
>>> x
2
>>> x + 3
5
>>> x. add (3)
5
>>> int. add (x, 3)
5

Notice that x + 3, x. add (3) and int. add (x, 3) all produce identical results. In the expression
x. add (3) the interpreter knows that x is an int, so it calls the add method of the int class
passing both x and 3 as arguments. The expression int. add (x, 3) best represents the process the
interpreter uses to execute the method. The int class defines the add method, and the expression
int. add (x, 3) indicates the add method requires both an object (x) and an integer (3) to do its
job. The interpreter translates the expressions x + 3 and x. add (3) into the call int. add (x, 3).
When we use the expression x + 3 we are oblivious to details of the add method in the int class.
Compare the code fragment
s = "ABC"
print(s. add ("DEF"))
print(str. add (s, "DEF"))

The expressions s. add ("DEF") and str. add (s, "DEF") are equivalent to s + "DEF", which
we know is string concatenation. The interpreter translates the symbol for integer addition or string con-
catenation, +, into the appropriate method call, in this case str. add .
Clients are not meant to call directly methods that begin with two underscores ( ). The Python lan-
guage maps the binary + operator to the add method of the appropriate class. Most of the integer
methods correspond to arithmetic operators that are easier to use; for examples, gt for > and mul
for *. The int class does not offer too many other methods that we need to use right now. Other Python
classes like str, list, and Random do provide methods intended for clients to use.

11.2 String Objects

Strings are like lists is some ways because they contain an ordered sequence of elements. Strings are
distinguished from lists in three key ways:

• Strings must contain only characters, while lists may contain objects of any type.
• Strings are immutable. The contents of a string object may not be changed. Lists are mutable objects.

• If two strings are equal with == comparison, they automatically are aliases (equal with the is opera-
tor). This means two identical string literals that appear in the Python source code refer to the same
string object.

Consider Listing 11.1 ([Link]).

Listing 11.1: [Link]

1 word1 = 'Wow'
2 word2 = 'Wow'
3 print('Equality:', word1 == word2, ' Alias:', word1 is word2)

Listing 11.1 ([Link]) assigns word1 and word2 to two distinct string literals. Since the two string
literals contain exactly the same characters, the interpreter creates only one string object. The two variables
word1 and word2 are bound to the same object. We say the interpreter merges the two strings. Since in
some programs strings may be long, string merging can save space in the computer’s memory.
Objects bundle data and functions together. The data that comprise strings consist of the charac-
ters that make up the string. Any string object also has available a number of methods. Listing 11.2
([Link]) shows how a programmer can use the upper method available to string objects.

Listing 11.2: [Link]

1 name = input("Please enter your name: ")
2 print("Hello " + [Link]() + ", how are you?")

Listing 11.2 ([Link]) capitalizes (converts to uppercase) all the letters in the string the user
enters:

Please enter your name: Rick

Hello RICK, how are you?

The expression
[Link]()

within the print statement represents a method call. The general form of a method call is

[Link] ( parameterlist )

• object is an expression that represents object. In the example in Listing 11.2 ([Link]),
name is a reference to a string object.
• The period, pronounced dot, associates an object expression with the method to be called.
• methodname is the name of the method to execute.
• The parameterlist is comma-separated list of parameters to the method. For some methods the pa-
rameter list may be empty, but the parentheses always are required.
Except for the object prefix, a method works just like a function. The upper method returns a string. A
method may accept parameters. Listing 11.3 ([Link]), uses the rjust string method to right justify
a string padded with a specified character.

Listing 11.3: [Link]

1 word = "ABCD"
2 print([Link](10, "*"))
3 print([Link](3, "*"))
4 print([Link](15, ">"))
5 print([Link](10))

The output of Listing 11.3 ([Link]):

******ABCD
ABCD
>>>>>>>>>>>ABCD
ABCD

shows

• [Link](10, "*") right justifies the string "ABCD" within a 10-character field padded with *
characters.

• [Link](3, "*") does not return a different string from the original "ABCD" since the specified
width (3) is less than or equal to the length of the original string (4).

• [Link](10) shows that the default padding character is a space.

str Methods
upper
Returns a copy of the original string with all the characters converted to uppercase
lower
Returns a copy of the original string with all the characters converted to lower case
rjust
Returns a string right justified within a field padded with a specified character which de-
faults to a space
ljust
Returns a string left justified within a field padded with a specified character which defaults
to a space
center
Returns a copy of the string centered within a string of a given width and optional fill
characters; fill characters default to spaces
strip
Returns a copy of the given string with the leading and trailing whitespace removed; if
provided an optional string, the strip function strips leading and trailing characters found
in the parameter string
startswith
Determines if the string is a prefix of the string
endswith
Determines if the string is a suffix of the string
count
Determines the number times the string parameter is found as a substring; the count in-
cludes only non-overlapping occurrences
find
Returns the lowest index where the string parameter is found as a substring; returns −1 if
the parameter is not a substring
format
Embeds formatted values in a string using 1, 2, etc. position parameters (see Listing 11.4
([Link]) for an example) parameter is found as a substring; returns −1 if the
parameter is not a substring

Table 11.1: A few of the methods available to str objects

Listing 11.4 ([Link]) demonstrates two of the string methods.

Listing 11.4: [Link]

1 # Strip leading and trailing whitespace and count substrings
2 s = " ABCDEFGHBCDIJKLMNOPQRSBCDTUVWXYZ "
3 print("[", s, "]", sep="")
4 s = [Link]()
5 print("[", s, "]", sep="")
6
7 # Count occurrences of the substring "BCD"
8 print([Link]("BCD"))

Listing 11.4 ([Link]) displays:

[ ABCDEFGHBCDIJKLMNOPQRSBCDTUVWXYZ ]
[ABCDEFGHBCDIJKLMNOPQRSBCDTUVWXYZ]
3

The [] index operator applies to strings as it does lists. The len function returns the number of char-
acters in a string. Listing 11.5 ([Link]) prints the individual characters that make up a
string.

The expression
s[i]

actually uses the string method getitem :

s. getitem (i)

The global function len calls the string object’s len method:
s = "ABCDEFGHIJK"
print(len(s) == s. len ()) # Prints True

As Listing 11.5 ([Link]) shows, strings may be manipulated in ways similar to lists. Strings
may be sliced:
print("ABCDEFGHIJKL"[2:6]) # Prints CDEF

Since strings are immutable objects, element assignment and slice assignment is not possible:
s = "ABCDEFGHIJKLMN"
s[3] = "S" # Illegal, strings are immutable
s[3:7] = "XYX" # Illegal, strings are immutable

String immutability means the strip method may not change a given string:
s = " ABC "
[Link]() # s is unchanged
print("<" + s + ">") # Prints < ABC >, not <ABC>

In order to strip the leading and trailing whitespace as far as the string bound to the variable s is concerned,
we must reassign s:
s = " ABC "
s = [Link]() # Note the reassignment
print("<" + s + ">") # Prints <ABC>

The strip method returns a new string; the string on whose behalf strip is called is not modified. Clients
must as in this example rebind their variable to the string passed back by strip.

11.3 List Objects

We introduced lists in Chapter 9, but there we treated them merely as enhanced data objects. We assigned
lists, passed lists to functions, returned lists from functions, and interacted with the elements of lists. List
objects provide more capability than we revealed earlier.
All Python lists are instances of the list class. Table ?? lists some of the methods available to list
objects.

list Methods
count
Returns the number of times a given element appears in the list. Does not modify the list.
insert
Inserts a new element before the element at a given index. Increases the length of the list
by one. Modifies the list.
append
Adds a new element to the end of the list. Modifies the list.
index
Returns the lowest index of a given element within the list. Produces an error if the element
does not appear in the list. Does not modify the list.
remove
Removes the first occurrence (lowest index) of a given element from the list. Produces an
error if the element is not found. Modifies the list if the item to remove is in the list.
reverse
Physically reverses the elements in the list. The list is modified.
sort
Sorts the elements of the list in ascending order. The list is modified.

Table 11.2: A few of the methods available to list objects

Since lists are mutable data structures, the list class has both getitem and setitem meth-
ods. The statement
x = lst[2]

behind the scenes becomes the method call

x = list. getitem (lst, 2)

and the statement

lst[2] = x
maps to
list. setitem (lst, 2, x)

The str class does not have a setitem method, since strings are immutable.
The code
lst = ["one", "two", "three"]
lst += ["four"]

is equivalent to
lst = ["one", "two", "three"]
[Link]("four")

but the version using append is more efficient.

11.4 Summary

• An object is an instance of a class.

• The terms class and type are synonymous.
• Integers, floating-point numbers, strings, lists, and functions are examples of objects we have seen in
earlier chapters.
• Typically objects are a combination of data (attributes or fields) and methods (operations)
• An object’s data and methods constitute its members.
• The code that uses the services provided by an object is known as the client of the object.
• Methods are like functions associated with a class of objects.
• Members that begin and end with two underscores are meant for internal use by objects; clients
usually do not use these members directly.
• Methods are called (or invoked) on behalf of objects or classes.

• The dot (.) operator associates an object or class with a member.

• Clients make not call a method without its associated object or class.

• The str class represents string objects.

• String objects are immutable. You may reassign a variable to another string object, but you may not
modify the contents of an existing string object. This means no str method may alter an existing
string object. When client code wishes to achieve the effect of modifying a string via one of the
string’s methods, the client code must reassign its variable with the result passed back by the method.

• The str class contains a number methods useful for manipulating strings.
• The list class represents all list objects.
• Unlike strings, list objects are mutable. The contents of a list object may be changed, removed, or
inserted.
Custom Types

Consider the task of writing a program that manages accounts for a bank. A bank account has a number of
attributes:

• Every account has a unique identifier, the account number.

• Every account has an owner that can be identified by a social security number.

• Each account’s owner has a name.

• Each account has a current balance.

• Each account is either active or inactive.

• Each account may have additional restrictions such as a minimum balance to remain active.

• Each account may be marked closed, meaning it will never be used again but by law information
about the account must be retained for some period of time.

The list of attributes easily could be much longer.

Based on our programming experience to this point, we conclude that the information pertinent to
accounts must be stored in variables. The situation gets messy when we consider that our program must be
able to process thousands of accounts. The data could be stored in a list, but would we have a list of account
numbers and a separate list for the customers’ social security numbers? Would we need to have a separate
list for every piece that makes up a bank account?
While it is possible to maintain separate lists and coordinate them somehow, it is more natural to think
of having a list of accounts, where each account contains all the necessary attributes. Python objects allow
us to model accounts in this more natural way.

12.1 Geometric Points

As an example to introduce simple objects, consider two-dimensional geometric points from mathematics.
We consider a single point object to consist of two real number coordinates: x and y. We ordinarily represent
a point by an ordered pair (x, y). In a program, we could model the point (2.5, 1) as a list:
point = [2.5, 6]
print("In", point, "the x coordinate is", point[0])

or as a tuple:
point = 2.5, 6
print("In", point, "the x coordinate is", point[0])

In either case, we must remember that the element at index 0 is the x coordinate and the element at index 1
is the y. While this is not an overwhelming burden, it would be better if we could access the parts of a point
through the labels x and y instead of numbers. Lists and tuples have another problem—the programmer
must take care to avoid an invalid index. This can happen accidentally with a simple typographical error or
when variables and expressions are used in the square brackets.
Python provides the class reserved word to allow the creation of new types of objects. We can create
a new type, Point, as follows:
class Point:
def init (self, x, y):
self.x = x
self.y = y

This code defines a new type. This Point class contains a single method named init . This special
method is known as a constructor, or initializer. The constructor code executes when the client creates an
object. The first parameter of this constructor, named self, is a reference to the object being created. The
statement
self.x = x

within the constructor establishes a field named xin the newly created Point object. The expression self.x
refers to the x field in the object, and the x variable on the right side of the assignment operator refers to the
parameter named x. These two x names represent different variables.
Once this new type has been defined in such a class definition, a client may create and use variables of
the type Point:
# Client code
pt = Point(2.5, 6) # Make a new Point object
print("(", pt.x, ",", pt.y, ")", sep="")

The expression Point(2.5, 6) creates a new Point object with an x coordinate of 2.5 and a y coordinate
of 6. The expression pt.x refers to the x coordinate of the Point object named pt. Unlike with a list or a
tuple, you do not use a numeric index to refer to a component of the object; instead you use the name of the
field (like x and y) to access a part of an object.
Figure 12.1 provides a conceptual view of a point object.
A definition of the form
class MyName:
# Block of method definitions

creates a programmer-defined type. Once the definition is available to the interpreter, programmers can
define and use variables of this custom type.
p1

x 2.5

y 1.0

Figure 12.1: A Point object

A component data element of an object is called a field. Our Point objects have two fields, x and y.
The terms instance variable or attribute sometimes are used in place of field. As with methods, Python
uses the dot (.) notation to access a field of an object; thus,
pt.x = 0

assigns zero to the x field of point pt.

Consider a simple employee record that consists of a name (string), an identification number (integer)
and a pay rate (floating-point number). Such a record can be represented by the class
class EmployeeRecord:
def init (n, i, r):
name = n
id = i
pay_rate = r

Such an object could be created and used as

rec = EmployeeRecord("Mary", 2148, 10.50)

Listing 12.1 ([Link]) uses our EmployeeRecord class to implement a simple database of employee
records.

Given a text file named [Link] containing the data

’Fred’, 324, 10.50

’Wilma’, 371, 12.19
’Betty’, 129, 15.45
’Barney’, 120, 16.00
’Pebbles’, 412, 9.34
’Bam-Bam’, 420, 9.15
’George’, 1038, 19.86
’Jane’, 966, 19.86
’Judy’, 1210, 15.61
’Elroy’, 1300, 14.32

Listing 12.1 ([Link]) uses a list of EmployeeRecord objects to implement a simple database.
The ordering imposed by the sort function is determined by the function passed as the second argument.
The code within the print_database function uses the format of the str class to beautify the output
of the data within a record:
print([Link]("{:>5}: {:<10} {:>6.2f}", \
[Link], [Link], rec.pay_rate))

The string "{:>5}: {:<10} {:>6.2f}" contains formatting control codes. Each cryptic expression within
the curly braces {} is a placeholder for a value in the list that follows. The expression within the {} indicates
how to format its associated parameter. The first placeholder, {:>5}. refers to the first argument that follows
the formatting string, [Link]. {:<10} refers to [Link], and {:>6.2f} refers to rec.pay_rate. The
colon (:) within the placeholder introduces the formatting code. < means left justify, and > specifies right
justification. The numbers indicate field width; that is, the number of spaces allotted for the value to print.
The .2f suffix will format a floating-point number with two explicit decimal places.
Our motivation at the beginning of the chapter was the need to build a database of bank account objects.
The class
class BankAccount:
def init (self):
self.account_number = 0 # Account number
[Link] = 123456789 # Social security number
[Link] = "" # Customer name
[Link] = 0.00 # Funds available in the account
self.min_balance = 100.00 # Balance cannot fall below this amount
[Link] = False # Account is active or inactive

defines the structure of such account objects. Notice that the constructor of our BankAccount objects does
not initialize any of the fields with client supplied values; instead, the constructor simply assigns default
values to a new BankAccount objects. Clients later must assign proper values to a bank account object. A
better definition would be
class BankAccount:
def init (self, acct, ss, name, balance):
self.account_number = acct # Account number
[Link] = ss # Social security number
[Link] = name # Customer name
[Link] = balance # Funds available in the account
self.min_balance = 100.00 # Balance cannot fall below this amount
[Link] = False # Account is active or inactive

In this version the client can specify the account number, the customer’s social security number and name,
and the account’s initial balance. The minimum balance and active flag are set to default values.

12.2 Methods

In modern object-oriented languages the power of objects comes from their ability to grant clients limited
access. Some parts of an object are meant to be private, while other parts are meant to be public. This gives
class designers the ability to hide the implementation details from clients. Knowledge of these details is not
necessary for a client to use the objects in their recommended manner.
Suppose, for example, you wish to represent a mathematical rational number, or fraction. A rational
number is the ratio of two integers. There is a restriction, however—the number on the bottom of a fraction
cannot be zero. The number on the top of the fraction is called the numerator, and the bottom number is
known as the denominator. A simple class such as
class RationalNum:
def init (self, num, den):
[Link], [Link] = num, den

There is nothing in this class definition that prevents a client from making a rational number like the fol-
lowing:
fract = RationalNum(1, 0)

In this case the variable fract represents an undefined integer. We can help matters with a different con-
structor:
class RationalNum:
def init (self, num, den):
[Link] = num
if den != 0:
[Link] = den
else:
print("Attempt to make an illegal rational number")
from sys import exit
exit(1) # Terminate program with an error code

While this new constructor will prevent illegal initialization, clients still can subvert our RationalNum
objects:
fract = RationalNum(1, 2) # This is OK
[Link] = 0 # This is bad!

At best, the programmer made an honest mistake introducing an error into the program. Perhaps it was a
careless “copy and paste” error. On the other hand, a clever programmer may be fully aware of how the
program works in the larger context and intentionally write such bad code to exploit a weakness in the
system that compromises its security.
Python uses a naming convention to protect a field. A field that with a name that begins with two
underscores ( ) is not accessible to clients using the normal dot operator.
Listing 12.2 ([Link]) uses protected fields.

Listing 12.2: [Link]

1 class Rational:
2 """
3 Represents a rational number (fraction)
4 """
5 def init (self, num, den):
6 self. numerator = num
7 if den != 0:
8 self. denominator = den
9 else:
10 print("Attempt to make an illegal rational number")
11 from sys import exit
12 exit(1) # Terminate program with an error code
13
14 def get_numerator(self):
15 """ Returns the numerator of the fraction. """
16 return self. numerator
17
18 def get_denominator(self):
19 """ Returns the denominator of the fraction. """
20 return self. denominator
21
22 def set_numerator(self, n):
23 """ Sets the numerator of the fraction to n. """
24 self. numerator = n
25
26 def set_denominator(self, d):
27 """
28 Sets the denominator of the fraction to d,
29 unless d is zero. If d is zero, the method
30 terminates the program with an error meesage.
31 """
32 if d != 0:
33 self. denominator = d
34 else:
35 print("Error: zero denominator!")
36 from sys import exit
37 exit(1) # Terminate program with an error code
38
39 def str (self):
40 """
41 Make a string representation of a Rational object
42 """
43 return str(self.get_numerator()) + "/" + str(self.get_denominator())
44
45 # Client code that uses Rational objects
46 def main():
47 fract1 = Rational(1, 2)
48 fract2 = Rational(2, 3)
49 print("fract1 =", fract1)
50 print("fract2 =", fract2)
51 fract1.set_numerator(3)
52 fract1.set_denominator(4)
53 fract2.set_numerator(1)
54 fract2.set_denominator(10)
55 print("fract1 =", fract1)
56 print("fract2 =", fract2)
57
58 main()

Notice in Listing 12.2 ([Link]) in the Rational class that the field names begin with . This
means that client code like

fract = Rational(1, 2)
print(fract. numerator) // Error, not possible

will not work. Clients no longer have direct access to the numerator and denominator fields of
Rational objects.
Clients may appear to change a protected field as
fract = Rational(1, 2)
fract. denominator = 0 # Legal, but what does it do?
print(fract.get_denominator()) # Prints 2, not 0
print(fract. denominator) # Prints 0, not 2

Surprisingly, the second statement (assignment of fract. denominator) does not affect the denominator
field used by the methods in the Rational class; it instead adds a new, unprotected field named denominator.
The client cannot get to the protected field by merely using the dot (.) operator. To avoid such confusion, a
client should not attempt to use fields of an object with names that begin with two underscores.
The str method may be defined for any class. The interpreter calls an object’s str method
when a string representation of an object is required. For example, the print function converts an object
into a string so it can display textual output.
In the main function of Listing 12.2 ([Link]) which contains code that uses Rational objects,
the call
fract1.set_numerator(2)

calls the set_numerator method of the Rational class on behalf of the object fract1. During the call
self is assigned fract1, and n is assigned 2. This means the code within set_numerator assigns 2
to the parameter n, and the name self. numerator within the method definition refers to fract1’s
numerator field. The method, therefore, reassigns the numerator member of fract1.
In comparison, consider the call
fract2.set_numerator(1)

This statement calls the set_numerator method of the Rational class on behalf of the object fract2.
self. numerator refers to fract2’s numerator, and parameter n is 1. This means the code within
set_numerator assigns 1 to the parameter n, and thus the method assigns 1 to the numerator fieldof
the fract2 object.
In OO-speak, we say the statement
fract1.set_numerator(2)

represents the client sending a set_numerator message to object fract1. In this message, it provides the
value 2. In this case frac1 is the message receiver. In the statement
fract2.set_numerator(1)

object fract2 receives the set_numerator message with the value 1.

When the values of one or more instance variables in an object change, we say the object changes its
state; for example, if we use an object to model the behavior of a traffic light, the object will contain some
instance variable that represents its current color: red, yellow, or green. When that field changes, the traffic
light’s color is changed. In the green to yellow transition, we can say the light goes from the state of being
green to the state of being yellow.
Armed with methods and protected fields, we can devise the starting point for a better bank account
class:
class BankAccount:
def init (self, number, ssn, name, balance):
self. account_number = number # Account number
self. ssn = ssn # Social security number
self. name = name # Customer name
self. balance = balance # Funds available in the account
self. min_balance = 100 # Balance cannot fall below this amount
self. active = True # Account is active or inactive

def deposit(self, amount):

"""
Add funds to the account, if possible
Return true if successful, false otherwise
"""
if self.is_active():
self. balance += amount
return True # Successful deposit
return False # Unable to deposit into an inactive account

def withdraw(self, amount)

"""
Remove funds from the account, if possible
Return true if successful, false otherwise
"""
result = False; # Unsuccessful by default
if self.is_active() and
self. balance - amount >= self. min_balance ):
self. balance -= amount;
result = True; # Success
return result

def set_active(self, act):

"""
Activate or deactivate the account
"""
self. active = act

bool is_active()
""""
Is the account active or inactive?
""""
return self. active

Clients interact with these bank account objects via the methods; thus, it is only through methods that clients
may alter the state of a bank account object.
In the BankAccount methods

• Clients may add funds via the deposit method only if the account is active. Notice that the deposit
method calls the is_active method using the parameter self. This means the receiver of the
is_active message is the same receiver of the deposit call currently executing; for example, in
the code
acct = BankAccount(31243, 123456789, "Joe", 1000.00)
[Link](100)

the acct object is the account object receiving the deposit message. Within that call to deposit,
acct is the receiver of the is_active method call.
• The withdraw method prevents a client from withdrawing more money from an account than some
specified minimum value. Withdrawals are not possible from an inactive account.

• The set_active method allows clients to activate and deactivate individual bank account objects.
• The is_active method allows clients to determine if an account object is currently active or inactive.

The following code will not work:

acct = BankAccount(31243, 123456789, "Joe", 1000.00)
[Link](100)
acct. balance -= 100; # Illegal

Clients instead must use the withdraw method. The withdraw method prevents actions such as
# New bank account object with $1,000.00 balance
acct = BankAccount(31243, 123456789, "Joe", 1000.00)
[Link](2000.00); // Method should disallow this operation

The operations of depositing and withdrawing funds are the responsibility of the object itself, not the client
code. The attempt to withdraw the $2,000 dollars above could, for example, result in an error message.
Consider a non-programming example. If I deposit $1,000.00 dollars into a bank, the bank then has
custody of my money. It is still my money, so I theoretically can reclaim it at any time. The bank stores
money in its safe, and my money is in the safe as well. Suppose I wish to withdraw $100 dollars from my
account. Since I have $1,000 total in my account, the transaction should be no problem. What is wrong
with the following scenario:

1. Enter the bank.

2. Walk past the teller into a back room that provides access to the safe.
3. The door to the safe is open, so enter the safe and remove $100 from a stack of $20 bills.
4. Exit the safe and inform a teller that you got $100 out of your account.
5. Leave the bank.

This is not the process a normal bank uses to handle withdrawals. In a perfect world where everyone is
honest and makes no mistakes, all is well. In reality, many customers might be dishonest and intentionally
take more money than they report. Even though I faithfully counted out my funds, perhaps some of the bills
were stuck to each other and I made an honest mistake by picking up six $20 bills instead of five. If I place
the bills in my wallet with other money that already be present, I may never detect the error. Clearly a bank
needs more controlled procedure for customer withdrawals.
When working with programming objects, in many situations it is better to restrict client access from
the internals of an object. Client code should not be able to change directly bank account objects for various
reasons, including:

• A withdrawal should not exceed the account balance.

• Federal laws dictate that deposits above a certain amount should be reported to the Internal Revenue
Service, so a bank would not want customers to be able to add funds to an account in a way to
circumvent this process.

• An account number should never change for a given account for the life of that account.

12.3 Custom Type Examples

This section contains a number of examples of code organization with functions.

12.3.1 Stopwatch

In 6.3 we saw how to use the clock function to measure elapsed time during a program’s execution. The
following skeleton code fragment
seconds = clock() # Record starting time
#
# Do something here that you wish to time
#
other = clock() # Record ending time
print(other - seconds, "seconds")

can be adapted to any program, but we can make it more convenient if we wrap the functionality into an
object. We can wrap all the messy details of the timing code into a convenient package. Consider the
following client code that uses an object to keep track of the time:
timer = Stopwatch() # Declare a stopwatch object

[Link]() # Start timing

#
# Do something here that you wish to time
#

[Link]() # Stop the clock

print([Link](), " seconds")

This code using a Stopwatch object is simpler. A programmer writes code using a Stopwatch in a similar
way to using an actual stopwatch: push a button to start the clock (call the start method), push a button
to stop the clock (call the stop method), and then read the elapsed time (use the result of the elapsed
method). Programmers using a Stopwatch object in their code are much less likely to make a mistake
because the details that make it work are hidden and inaccessible.
Given our experience designing our own types though Python classes, we now are adequately equipped
to implement such a Stopwatch class. Listing 12.3 ([Link]) defines the structure and capabilities
of our Stopwatch objects.

Four methods are available to clients: start, stop, reset, and elapsed. A client does not have to
worry about the “messy” detail of the arithmetic to compute the elapsed time.
Note that our design forces clients to stop a Stopwatch object before calling the elapsed method.
Failure to do so results in a programmer-defined run-time error report. A variation on this design might
allow a client to read the elapsed time without stopping the watch. This implementation allows a user to
stop the stopwatch and resume the timing later without resetting the time in between.
Listing 12.4 ([Link]) is a rewrite of Listing 10.5 ([Link]) that uses
our Stopwatch object.

Listing 12.4: [Link]

1 def binary_search(lst, seek):
2 '''
3 Returns the index of element seek in list lst,
4 if seek is present in lst.
5 lst must be in sorted order.
6 Returns None if seek is not an element of lst.
7 lst is the lst in which to search.
8 seek is the element to find.
9 '''
10 first = 0 # Initially the first element in list
11 last = len(lst) - 1 # Initially the last element in list
12 while first <= last:
13 # mid is middle of the list
14 mid = first + (last - first + 1)//2 # Note: Integer division
15 if lst[mid] == seek:
16 return mid # Found it
17 elif lst[mid] > seek:
18 last = mid - 1 # continue with 1st half
19 else: # v[mid] < seek
20 first = mid + 1 # continue with 2nd half
21 return None # Not there
22
23 def ordered_linear_search(lst, seek):
24 '''
25 Returns the index of element seek in list lst,
26 if seek is present in lst.
27 lst must be in sorted order.
28 Returns None if seek is not an element of lst.
29 lst is the lst in which to search.
30 seek is the element to find.
31 '''
32 i = 0
33 n = len(lst)
34 while i < n and lst[i] <= seek:
35 if lst[i] == seek:
36 return i # Return position immediately
37 i += 1
38 return None # Element not found
39
40 def test_searches(lst):
41 from stopwatch import Stopwatch
42
43 timer = Stopwatch()
44 # Find each element using ordered linear search
45 [Link]() # Start the clock
46 n = len(lst)
47 for i in range(n):
48 if ordered_linear_search(lst, i) != i:
49 print("error")
50 [Link]() # Stop the clock
51 print("Linear elapsed time", [Link]())
52
53 # Find each element using binary search
54 [Link]() # Reset the clock
55 [Link]() # Start the clock
56 n = len(lst)
57 for i in range(n):
58 if binary_search(lst, i) != i:
59 print("error")
60 [Link]() # Stop the clock
61 print("Binary elapsed time", [Link]())
62
63 def main():
64 SIZE = 20000
65 test_list = list(range(SIZE))
66 test_searches(test_list)
67
68 main()
This new, object-oriented version is simpler and more readable.

12.3.2 Automated Testing

We know that just because a program runs to completion without a run-time error does not imply that
the program works correctly. We can detect logic errors in our code as we interact with the executing
program. The process of exercising code to reveal errors or demonstrate the lack thereof is called testing.
The informal testing that we have done up to this point has been adequate, but serious software development
demands a more formal approach. We will see that good testing requires the same skills and creativity as
programming itself.
Until relatively recently in the software development world, testing was often an afterthought. Testing
was not perceived to be as glamorous as designing and coding. Poor testing led to buggy programs that
frustrated users. Also, tests were written largely after the program’s design and coding were complete.
The problem with this approach is major design flaws may not be revealed until late in the development
cycle. Changes late in the development process are invariably more expensive and difficult to deal with than
changes earlier in the process.
Weaknesses in the standard approach to testing led to a new strategy: test-driven development. In test-
driven development the testing is automated, and the design and implementation of good tests is just as
important as the design and development of the actual program. In pure test-driven development, tests
are developed before any application code is written, and any application code produced is immediately
subjected to testing.
Listing 12.5 ([Link]) defines the structure of a rudimentary test object.

Listing 12.5: [Link]

1 class Tester:
2 def init (self):
3 self. error_count = self. total_count = 0
4 print("+ --------------------------------------------------------------------- ")
5 print("| Testing ")
6 print("+ --------------------------------------------------------------------- ")
7
8 def check_equals(self, msg, expected, actual):
9 print("[", msg, "] ")
10 self. total_count += 1 # Count this test
11 if expected == actual:
12 print("OK")
13 else:
14 self. error_count += 1 # Count this failed test
15 print("*** Failed! Expected:", expected, " actual:", actual)
16
17 def report_results(self):
18 print("+ ------------------------------------------------------------------- ")
19 print("|", self. total_count, "tests run")
20 print("|", self. total_count - self. error_count, " passed")
21 print("|", self. error_count, " failed")
22 print("+ ------------------------------------------------------------------- ")

A simple test object keeps track of the number of tests performed and the number of failures. The client
uses the test object to check the results of a computation against a predicted result.
Listing 12.6 ([Link]) uses our Tester class.

The program’s output is

+---------------------------------------
| Testing
+---------------------------------------
[ Sort test #1 ]
*** Failed! Expected: [2, 3, 4] actual: [4, 2, 3]
[ Sort test #2 ]
OK
[ Sum test #1 ]
OK
[ Sum test #2 ]
*** Failed! Expected: 5 actual: 2
+--------------------------------------
| 4 tests run
| 2 passed
| 2 failed
+--------------------------------------
Notice that the sort function has yet to be implemented, but we can test it anyway. The first test is
bound to fail. The second test checks to see if our sort function will not disturb an already sorted vector,
and we pass this test with no problem.
In the sum function, the programmer was careless and used 1 as the beginning index for the vector.
Notice that the first test does not catch the error, since the element in the zeroth position (zero) does not
affect the outcome. A tester must be creative and even devious to try and force the code under test to
demonstrate its errors.

12.4 Class Inheritance

We can base a new class on an existing class using a technique known as inheritance. Recall our Stopwatch
class we defined in Listing 12.3 ([Link]). Our Stopwatch objects may be started and stopped
as often as necessary without resetting the time. Support we need a stopwatch object that records the
number of times the watch is started until it is reset. We can build our enhanced Stopwatch class from
scratch, but it would more efficient to base our new class on the existing Stopwatch class. Listing 12.7
([Link]) defines our enhanced stopwatch objects.

Listing 12.7: [Link]

1 from stopwatch import Stopwatch
2
3 class CountingStopwatch (Stopwatch):
4 def init (self):
5 # Allow superclass to do its initialization of the
6 # inherited fields
7 super(CountingStopwatch, self). init ()
8 # Set number of starts to zero
9 self. count = 0
10
11 def start(self):
12 # Let superclass do its start code
13 super(CountingStopwatch, self).start()
14 # Count this start message
15 self. count += 1
16
17 def reset(self):
18 # Let superclass reset the inherited fields
19 super(CountingStopwatch, self).reset()
20 # Reset new field
21 self. count = 0
22
23 def count(self):
24 return self. count

The line
from stopwatch import Stopwatch

indicates that the code in this module will somehow use the Stopwatch class from Listing 12.3 ([Link]).
The line
class CountingStopwatch (Stopwatch):
defines a new class named CountingStopwatch, but this new class is based on the existing class Stopwatch.
This single line means that the CountingStopwatch class inherits everything from the Stopwatch class.
CountingStopwatch objects automatically will have start, stop, reset, and elapsed methods.
We say stopwatch is the superclass of CountingStopwatch. Another term for superclass is base class.
CountingStopwatch is the subclass of Stopwatch, or, said another way, CountingStopwatch is a derived
class of Stopwatch.
Even though a subclass inherits all the fields and methods of its superclass, a subclass may add new
fields and methods and provide new code for an inherited method. The statement

super(CountingStopwatch, self). init ()

in the init method definition calls the constructor of the superclass. After executing the superclass
constructor code, the subclass constructor defines and initializes the new count field. The start and
reset methods in CountingStopwatch similarly invoke the services of their counterparts in the superclass.
The count method is a brand new method not found in the superclass.
Notice that the CountingStopwatch class has no apparent stop method. In fact, it inherits the stop
method as is from Stopwatch.
Listing 12.8 ([Link]) provides some sample client code that uses the CountingStopwatch
class.

Listing 12.8: [Link]

1 from countingstopwatch import CountingStopwatch
2 from time import sleep
3
4 timer = CountingStopwatch()
5 [Link]()
6 sleep(10) # Pause program for 10 seconds
7 [Link]()
8 print("Time:", [Link](), " Number:", [Link]())
9
10 [Link]()
11 sleep(5) # Pause program for 5 seconds
12 [Link]()
13 print("Time:", [Link](), " Number:", [Link]())
14
15 [Link]()
16 sleep(20) # Pause program for 20 seconds
17 [Link]()
18 print("Time:", [Link](), " Number:", [Link]())

Listing 12.8 ([Link]) produces

Time: 10.010378278632945 Number: 1

Time: 15.016618866378108 Number: 2
Time: 35.02881993198008 Number: 3
12.5 Summary

• The class reserved word introduces a programmer-defined type.

• Variables of a class are called objects or instances of that class.

• The dot (.) operator is used to access elements of an object.

• A data member of a class is known as a field. Equivalent terms include data member, instance
variable, and attribute.
• A function defined in a class that operates on objects of that class is called a method. Equivalent
terms include member function and operation.
• Encapsulation and data hiding offers several benefits to programmers:
– Flexibility—class authors are free to change the private details of a class. Existing client code
need not be changed to work with the new implementation.
– Reducing programming errors—if client code cannot touch directly the hidden details of an
object, the internal state of that object is completely under the control of the class author. With
a well-designed class, clients cannot place the object in an ill-defined state (thus leading to
incorrect program execution).
– Hiding complexity—the hidden internals of an object might be quite complex, but clients cannot
see and should not be concerned with those details. Clients need to know what an object can
do, not how it accomplishes the task.
• A field with a name that begins with two underscores ( ) is no meant to be used directly by clients.

12.6 Exercises

1. Given the definition of the Rational number class Listing 12.2 ([Link]), complete the func-
tion named add:
def add(r1, r2):
# Details go here

that returns the rational number representing the sum of its two parameters.

2. Given the definition of the geometric Point class, complete the function named distance:
def distance(r1, r2):
# Details go here

that returns the distance between the two points passed as parameters.

3. Given the definition of the Rational number class, complete the following function named reduce:
def reduce(r):
# Details go here

that returns the rational number that represents the parameter reduced to lowest terms; for example,
the fraction 10/20 would be reduced to 1/2.

4. What is the purpose of the init method in a class?

5. What is the parameter named self that appears as the first parameter of a method?

6. Given the definition of the Rational number class, complete the following method named reduce:
class Rational:
# Other details omitted here ...

# Returns an object of the same value reduced

# to lowest terms
def reduce(self):
# Details go here

that returns the rational number that represents the object reduced to lowest terms; for example, the
fraction 10/20 would be reduced to 1/2.

7. Given the definition of the Rational number class, complete the following method named reduce:
class Rational:
# Other details omitted here ...

# Reduces the object to lowest terms

def reduce(self):
# Details go here

that reduces the object on whose behalf the method is called to lowest terms; for example, the fraction
10/20 would be reduced to 1/2.

8. Given the definition of the geometric Point class, add a method named distance:
class Point:
# Other details omitted

# Returns the distance from this point to the

# parameter p
double distance(self, p):
# Details go here

that returns the distance between the point on whose behalf the method is called and the parameter
Handling Exceptions

In our programming experience so far we have encountered several kinds of run-time errors, such as integer
division by zero, accessing a list with an out-of-range index, using an object reference set to None, and
attempting to convert a non-number to an integer. To this point, all of our run-time errors have resulted in
the program’s termination. Python provides a standard mechanism called exception handling that allows
programmers to deal with these kinds of run-time errors and many more. Rather than always terminating
the program’s execution, a program can detect the problem and execute code to correct the issue or manage
it in other ways. This chapter explores Python’s exception handling mechanism.

13.1 Motivation

Algorithm design can be tricky because the details are crucial. It may be straightforward to write an algo-
rithm to solve a problem in the general case, but there may be a number of special cases that must all be
addressed within the algorithm for the algorithm to be correct. Some of these special cases might occur
rarely under the most extraordinary circumstances. For the code implementing the algorithm to be robust,
these exceptional cases must be handled properly; however, adding the necessary details to the algorithm
may render it overly complex and difficult to construct correctly. Such an overly complex algorithm would
be difficult for others to read and understand, and it would be harder to debug and extend.
Ideally, a developer would write the algorithm in its general form including any common special cases.
Exceptional situations that should arise rarely, along with a strategy to handle them, could appear elsewhere,
perhaps as an annotation to the algorithm. Thus, the algorithm is kept focused on solving the problem at
hand, and measures to deal with exceptional cases are handled elsewhere.
Python’s exception handling infrastructure allows programmers to cleanly separate the code that imple-
ments the focused algorithm from the code that deals with exceptional situations that the algorithm may
face. This approach is more modular and encourages the development of code that is cleaner and easier to
maintain and debug.
An exception is a special object that the executing program can create when it encounters an extraor-
dinary situation. Such a situation almost always represents a problem, usually some sort of run-time error.
Examples of exceptional situations include:

• attempting to read past the end of a file

• evaluating the expression lst[i] where lst is a list, and i > len(lst).
• attempting to convert a non-numeric string to a number, as in int("Fred")
• attempting to read data from the network when the connection is lost (perhaps due to a server crash
or the wire being unplugged from the port).

Many of these potential problems can be handled by the algorithm itself. For example, an if statement
can test to see if a list index is within the bounds of the list. However, if the list is accessed at many different
places within a function, the large number of conditionals in place to ensure the list access safety can quickly
obscure the overall logic of the function. Other problems such as the network connection problem are less
straightforward to address directly in the algorithm. Fortunately, specific Python exceptions are available
to cover problems such as these.
Exceptions represent a standard way to deal with run-time errors. In programming languages that
do not support exception handling, programmers must devise their own ways of dealing with exceptional
situations. One common approach is for functions to return an integer code that represents success or
failure. For example, consider a function named ReadFile that is to open a file and read its contents. It
returns an integer that is interpreted as follows:

• 0: Success; the function successfully opened and read the contents of the file
• 1: File not found error; the requested file does not exist
• 2: Permissions error; the program is not authorized to read the file
• 3: Device not ready error; for example, a DVD is not present in the drive
• 4: Media error; the program encountered bad sectors on the disk while reading the file
• 5: Some other file error

Notice that zero indicates success, and nonzero indicates failure. Client code that uses the function may
look like
if ReadFile("[Link]") == 0:
# Code to execute if the file was read properly
else:
# Code to execute if an error occurred while reading the file

The developers of ReadFile were looking toward the future, since any value above 4 represents some
unspecified file error. New codes can be specified (for example, 5 may mean illegal file format). Existing
client code that uses the updated class containing ReadFile will still work (5 > 4 just represents some kind
of file error), but new client code can explicitly check for a return value of 5 and act accordingly.
This kind of error handling has its limitations, however. The primary purpose of some functions is to
return an integer result that is not an indication of an error (for example, the int function). Perhaps a string
could be returned instead? Unfortunately, some functions naturally return strings (like the str function).
Also, returning a string would not work for a function that naturally returns an integer as its result. A
completely different type of exception handling technique would need to be developed for functions such
as these.
The return-value-as-error-status approach can be cumbersome to use for complicated programming
situations. Consider the situation where function A calls function B which calls function C which calls
function D which calls ReadFile:
A → B → C → D → ReadFile

Suppose function A is concerned about the file being opened correctly and read. The ReadFile function
returns an error status, but this value is returned to function D, the function that calls ReadFile directly.
If A really needs to know about how ReadFile worked, then all the functions in between in the call chain
(B, C, and D) must also return an error status. The process essentially passes the error status of ReadFile
back up the call chain to A. While this is inconvenient at best, it may be impossible in general. Suppose D’s
job is to read the data in the file (via ReadFile) and then pass each piece of data read to another function
called Process. Now Process also returns an integer value that indicates its error status. If the data passed
to Process is not of the proper format, it returns 1; otherwise, it returns 0. If function A needs to know
specifics about why the data file was not properly read in and processed (was it a problem reading the file
with ReadFile or a problem with the data format with Process?), it cannot distinguish the cause from the
single error indication passed up the call chain.
The main problem with these ad hoc approaches to exception handling is that the error handling facil-
ities developed by one programmer may be incompatible with those used by another. A comprehensive,
uniform exception handling mechanism is needed. Python’s exceptions provide such a framework. Python’s
exception handling infrastructure leads to code that is logically cleaner and less prone to programming er-
rors. Exceptions are used in the standard Python API, and programmers can create new exceptions that
address issues specific to their particular problems. These exceptions all use a common mechanism and are
completely compatible with each other.

13.2 Exception Examples

The following small Python program certainly will cause a run-time error if the user enters the word “five”
instead of typing the digit 5.
x = int(input("Please enter a small positive integer: "))
print("x =", x)

If the user enters “five,” this code results in the run-time environment reporting a ValueError exception
before killing the program.
We can wrap this code in a try/except construct as
try:
x = int(input("Please enter a small positive integer: "))
print("x =", x)
except ValueError:
print("Input cannot be parsed as an integer")

Now if the user enters “five” when this section of code is executed, the program displays

Input cannot be parsed as an integer

Notably, the program does not crash. The try block

try:
# Code that might raise an exception goes here . . .
wraps the code segment that has the potential to produce an exception. The except block
except ValueError:
# Code to execute if the except block produced an exception goes here . . .

provides the code to be executed only if the code within the try block does indeed produce a ValueError
exception. We say code within the except block handles the exception that code within the try block
raises. Code within the exception block constitutes “Plan B;” that is, what to do if the code in the try
block fails.
Consider Listing 13.1 ([Link]) which contains a common potential problem and two real prob-
lems.

Listing 13.1: [Link]

1 # I hope the user enters a valid Python integer!
2 x = int(input("Please enter a small positive integer: "))
3 print("x =", x)
4 if x < 5:
5 a = None
6 a[3] = 2 # Using None as a populated list!
7 elif x < 10:
8 a = [0, 1]
9 a[2] = 3 # Exceeding the list's bounds

Here are the problems with Listing 13.1 ([Link]):

• If the user enters a non-integer, the program crashes with a ValueError run-time error. We have
tolerated this behavior for too long enough, and it is time to defend against this possibility.

• If the user enters an integer less than five, the program attempts to use None as a list. The program
thus crashes with a TypeError error.
• If the user enters an integer in the range 6. . . 9, the program attempts to access a list with an index
outside the range of the list. This results in an IndexError run-time error.

Consider Listing 13.2 ([Link]) shows how to handle multiple exceptions in a section of
code.

Listing 13.2: [Link]

1 x = 0
2 while x < 100:
3 try:
4 # I hope the user enters a valid Python integer!
5 x = int(input("Please enter a small positive integer: "))
6 print("x =", x)
7 if x < 5:
8 a = None
9 a[3] = 2 # Using None as a populated list!
10 elif x < 10:
11 a = [0, 1]
12 a[2] = 3 # Exceeding the list's bounds
13 except ValueError:
14 print("Input cannot be parsed as an integer")
15 except TypeError:
16 print("Trying to use a None as a valid object")
17 except IndexError:
18 print("Straying from the bounds of the list")
19 print("Program continues")
20 print("Program finished")

In Listing 13.2 ([Link]), we finally address the issue of robust user numeric input. Up to this
point, if we wished to obtain an integer from the user, we wrote code such as
value = int(input("Enter an integer: "))

and hoped the user does not enter 2.45 or the word fred. Bad input in Listing 13.2 ([Link])
causes the program to scold the user but does not terminate the program.

13.3 Using Exceptions

Exceptions should be reserved for uncommon errors. For example, the following code adds up all the
elements in a list of numbers named lst:
sum = 0
for elem in range(len(lst)):
sum += elem
print("Sum =", sum)

This loop is fairly typical. Another approach uses exceptions:

sum = 0
int i = 0
try:
while True:
sum += lst[i]
i += 1
except IndexError:
pass
print("Sum =", sum)

Both approaches compute the same result. In the second approach the loop is terminated when the list access
is out of bounds. The statement is interrupted in midstream so sum’s value is not incorrectly incremented.
However, the second approach always throws and catches an exception. The exception definitely is not an
uncommon occurrence.
Exceptions should not be used to dictate normal logical flow. While very useful for its intended purpose,
the exception mechanism adds some overhead to program execution, especially when an exception is raised.
This overhead is reasonable when exceptions are rare but not when exceptions are part of the program’s
normal execution.
Exceptions are valuable aids for careless or novice programmers. A careful programmer ensures that
code accessing a list does not exceed the list’s bounds. Another programmer’s code may accidentally
attempt to access a[len(a)]. A novice may believe a[len(a)] is a valid element. Since no programmer
is perfect, exceptions provide a nice safety net.
As you develop more sophisticated classes you will find exceptions more compelling. You should
analyze your classes and methods carefully to determine their limitations. Exceptions can be valuable for
covering these limitations. Exceptions are used extensively throughout the Python standard class library.
Programs that make use of these classes must properly handle the exceptions they can throw.

Python Lists and Dictionaries Overview
No ratings yet
Python Lists and Dictionaries Overview
38 pages
Python Lists and Tuples Overview
No ratings yet
Python Lists and Tuples Overview
105 pages
Understanding Lists in Python Programming
No ratings yet
Understanding Lists in Python Programming
11 pages
Python Lists: Indexing and Operations
No ratings yet
Python Lists: Indexing and Operations
6 pages
Python Lists and Functions Overview
No ratings yet
Python Lists and Functions Overview
44 pages
Python Notes 2
No ratings yet
Python Notes 2
206 pages
Lists and Tuples
No ratings yet
Lists and Tuples
74 pages
Python Lists: Creation and Methods
No ratings yet
Python Lists: Creation and Methods
28 pages
BVM Global Schoollist in Python
No ratings yet
BVM Global Schoollist in Python
5 pages
Python Lists and Tuples Explained
No ratings yet
Python Lists and Tuples Explained
78 pages
Python List Basics and Operations
No ratings yet
Python List Basics and Operations
12 pages
s5 Intro To Python-List Tuples
No ratings yet
s5 Intro To Python-List Tuples
22 pages
Python Lists and For-Loops Explained
No ratings yet
Python Lists and For-Loops Explained
34 pages
AI Python 1
No ratings yet
AI Python 1
43 pages
Unit II
No ratings yet
Unit II
20 pages
Python Lists, Tuples, and Dictionaries Guide
No ratings yet
Python Lists, Tuples, and Dictionaries Guide
17 pages
Introduction to Python Programming Basics
No ratings yet
Introduction to Python Programming Basics
41 pages
Python Lists: Creation, Access, and Operations
No ratings yet
Python Lists: Creation, Access, and Operations
31 pages
All Notes Nptel
No ratings yet
All Notes Nptel
111 pages
Understanding Python Lists Basics
No ratings yet
Understanding Python Lists Basics
16 pages
BPP Unit 4
No ratings yet
BPP Unit 4
74 pages
Python Lists Overview for CSE 1001
100% (1)
Python Lists Overview for CSE 1001
16 pages
Python Data Types: Lists, Tuples, Sets, Dictionaries
No ratings yet
Python Data Types: Lists, Tuples, Sets, Dictionaries
132 pages
Understanding Python Lists and Their Properties
No ratings yet
Understanding Python Lists and Their Properties
19 pages
Python Lists and Tuples Explained
No ratings yet
Python Lists and Tuples Explained
38 pages
Arrays and Lists in Programming I
No ratings yet
Arrays and Lists in Programming I
59 pages
Its30705 L5 Ans
No ratings yet
Its30705 L5 Ans
38 pages
Python List Manipulation Guide
No ratings yet
Python List Manipulation Guide
50 pages
Python Lists: Creation and Usage Guide
No ratings yet
Python Lists: Creation and Usage Guide
3 pages
Python List Operations and Methods
No ratings yet
Python List Operations and Methods
23 pages
Python Lists: Creation and Manipulation
No ratings yet
Python Lists: Creation and Manipulation
37 pages
Python Lists: Creation and Operations
No ratings yet
Python Lists: Creation and Operations
12 pages
Python Lists and Tuples Overview
No ratings yet
Python Lists and Tuples Overview
77 pages
Python List Creation and Manipulation
No ratings yet
Python List Creation and Manipulation
34 pages
Python Lists: Class 11 Revision Notes
No ratings yet
Python Lists: Class 11 Revision Notes
5 pages
Revision Notes Class 11 Computer Science Chapter 9 2025-26 Free PDF
No ratings yet
Revision Notes Class 11 Computer Science Chapter 9 2025-26 Free PDF
5 pages
Python Basics: Syntax, Control, Data Structures
No ratings yet
Python Basics: Syntax, Control, Data Structures
17 pages
Python Lists: Structure & Operations
No ratings yet
Python Lists: Structure & Operations
64 pages
Handling List Index Errors in Python
No ratings yet
Handling List Index Errors in Python
26 pages
Understanding Python Tuples and Lists
No ratings yet
Understanding Python Tuples and Lists
10 pages
Python Lists: Structure & Methods
No ratings yet
Python Lists: Structure & Methods
67 pages
Python Lists: Creation and Management
No ratings yet
Python Lists: Creation and Management
11 pages
Python Lists, Tuples, and Dictionaries Guide
No ratings yet
Python Lists, Tuples, and Dictionaries Guide
20 pages
Python Lists Tuples and Dictionaries
No ratings yet
Python Lists Tuples and Dictionaries
17 pages
Lists vs Strings in Python
No ratings yet
Lists vs Strings in Python
5 pages
Python Basics: Lists and Variables
No ratings yet
Python Basics: Lists and Variables
51 pages
Python Module 2: Data Structures Overview
No ratings yet
Python Module 2: Data Structures Overview
34 pages
Python Lists: Structure and Operations
No ratings yet
Python Lists: Structure and Operations
32 pages
Python Lists and Tuples Explained
No ratings yet
Python Lists and Tuples Explained
12 pages
Unit 4-1
No ratings yet
Unit 4-1
26 pages
Python Programming Basics and Concepts
No ratings yet
Python Programming Basics and Concepts
37 pages
Python Data Types and Lists Explained
No ratings yet
Python Data Types and Lists Explained
90 pages
Python Data Types Overview
No ratings yet
Python Data Types Overview
23 pages
Python Lists Cheat Sheet for Beginners
No ratings yet
Python Lists Cheat Sheet for Beginners
2 pages
Working with Python Lists
No ratings yet
Working with Python Lists
19 pages
Class XI Notes-Python Lists
No ratings yet
Class XI Notes-Python Lists
27 pages
Understanding Python Lists and Operations
No ratings yet
Understanding Python Lists and Operations
12 pages
Python Arrays and Lists Explained
No ratings yet
Python Arrays and Lists Explained
16 pages
Python Programming Lab Exercises
No ratings yet
Python Programming Lab Exercises
110 pages
Office Automation: Computer Basics
No ratings yet
Office Automation: Computer Basics
72 pages
HTML Basics for Web Design
No ratings yet
HTML Basics for Web Design
224 pages
Introduction to Cloud Computing Basics
No ratings yet
Introduction to Cloud Computing Basics
35 pages
Cloud Computing Question Bank 2020-24
No ratings yet
Cloud Computing Question Bank 2020-24
30 pages
Java Programming Concepts and Techniques
No ratings yet
Java Programming Concepts and Techniques
89 pages
Blockchain Technology in Fintech Overview
100% (1)
Blockchain Technology in Fintech Overview
5 pages
Approaches to Language Testing Explained
100% (2)
Approaches to Language Testing Explained
41 pages
Counting Figures: Triangles, Squares, Rectangles
No ratings yet
Counting Figures: Triangles, Squares, Rectangles
46 pages
Relational Model: Domains and Constraints
No ratings yet
Relational Model: Domains and Constraints
27 pages
Communication Challenges in HUMSS Students
No ratings yet
Communication Challenges in HUMSS Students
8 pages
18th Century American Literature Overview
No ratings yet
18th Century American Literature Overview
9 pages
KV Guwahati Class XII Math Pre-Board Key
No ratings yet
KV Guwahati Class XII Math Pre-Board Key
9 pages
(Kali - Training) Managing Users and Groups
No ratings yet
(Kali - Training) Managing Users and Groups
6 pages
Understanding the 2300 Day Prophecy
No ratings yet
Understanding the 2300 Day Prophecy
145 pages
Information Technology Sample Paper 2025-26 - Information Technology - Class 10 CBSE Sample Papers
No ratings yet
Information Technology Sample Paper 2025-26 - Information Technology - Class 10 CBSE Sample Papers
5 pages
Constructivist Teaching Methods Overview
100% (1)
Constructivist Teaching Methods Overview
9 pages
Childhood Memories and Upbringing Insights
No ratings yet
Childhood Memories and Upbringing Insights
5 pages
Dustin Griffin - Satire - A Critical Reintroduction-University Press of Kentucky (1994)
100% (1)
Dustin Griffin - Satire - A Critical Reintroduction-University Press of Kentucky (1994)
280 pages
Exploring Myths and Legends in Class
No ratings yet
Exploring Myths and Legends in Class
9 pages
Curriculum Vitae of Amar Singh
No ratings yet
Curriculum Vitae of Amar Singh
4 pages
Genghis Khan: Birth and Legacy
No ratings yet
Genghis Khan: Birth and Legacy
34 pages
Payroll System Design and Requirements
100% (1)
Payroll System Design and Requirements
15 pages
Best Practices For SAP BTP
75% (4)
Best Practices For SAP BTP
106 pages
Writing Biomedical Manuscripts: Key Tips
No ratings yet
Writing Biomedical Manuscripts: Key Tips
11 pages
Class 9 English Tenses Worksheet
No ratings yet
Class 9 English Tenses Worksheet
2 pages
CBSE Class 9 Maths Sample Paper Set 3 For 2025-26
No ratings yet
CBSE Class 9 Maths Sample Paper Set 3 For 2025-26
25 pages
Year of Miss Agnes Overview
No ratings yet
Year of Miss Agnes Overview
5 pages
Buy BEETEL ABS Telephone Instrument Single Push Button Online - Government e Marketplace (GeM)
No ratings yet
Buy BEETEL ABS Telephone Instrument Single Push Button Online - Government e Marketplace (GeM)
4 pages
Whittington - Structuration Theory and Strategy As Practice
No ratings yet
Whittington - Structuration Theory and Strategy As Practice
21 pages
Access to Water: Design Patterns
No ratings yet
Access to Water: Design Patterns
2 pages
Discussion Questions for Chapters 1-9
No ratings yet
Discussion Questions for Chapters 1-9
10 pages
Utest Acronyms
No ratings yet
Utest Acronyms
8 pages
Zitter and Hoeve - Hybrid Learning
No ratings yet
Zitter and Hoeve - Hybrid Learning
28 pages
NSSB 2025 Exam Syllabus Overview
No ratings yet
NSSB 2025 Exam Syllabus Overview
3 pages
Understanding Faith and Hope in Christianity
No ratings yet
Understanding Faith and Hope in Christianity
4 pages
Grammar Assessment Task Guidelines
No ratings yet
Grammar Assessment Task Guidelines
9 pages

Average Numbers in Python Program

Uploaded by

Average Numbers in Python Program

Uploaded by

Chapter 4

Listing 9.1: [Link]

A sample run of Listing 9.1 ([Link]) looks like:

Please enter five numbers:

Listing 9.2: [Link]

Please enter 5 numbers:

• the ability to retain individual values, and

9.1 Using Lists

The above code prints

[2, -3, 0, 4, -1]

We can access individual elements of a list using square brackets:

This code prints

Listing 9.3 ([Link]) prints

[23, [9.3, 11.2, 99.0], [23], [], 4, [0, 0]]

Four of the elements of the list col are themselves lists.

The expression within [] must evaluate to an integer; some examples include

• an integer literal: a[34]

• an integer variable: a[x] (x must be an integer)

• an integer arithmetic expression: a[x + 3] (x must be an integer)

• an element of another list: a[b[3]] (element b[3] must be an integer)

1 collection = [24.2, 4, 'word', eval, 19, -0.03, 'end']

This fragment prints

assigns the given list literal to the variable a. The expression

actually reassigns a to the new list [2, 4, 6, 8, 1, 3, 5]. The statement

Listing 9.5: [Link]

A sample run of Listing 9.5 ([Link]) produces

Enter integer (-1 quits): 23

If the user enters a negative number initially, we get:

Enter integer (-1 quits): -1

Listing 9.6: [Link]

Listing 9.6 ([Link]) prints

Listing 9.7: [Link]

The output of Listing 9.7 ([Link]) is

Listing 9.8: [Link]

Please enter 5 numbers:

9.2 List Assignment and Equivalence

Given the assignment

Listing 9.9: [Link]

a = [10, 20, 30, 40]

b = [10, 20, 30] 10 20 30 40

a = [10, 20, 30, 40]

Listing 9.11: [Link]

Listing 9.11 ([Link]) prints

Listing 9.12: [Link]

The output of Listing 9.12 ([Link]) reveals:

a = [10, 20, 30, 40] b = [10, 20, 30, 40]

9.3 List Bounds

In the following code fragment:

©2011 Richard L. Halterman Draft date: November 13, 2011

Listing 9.13: [Link]

The for statement

Listing 9.14: [Link]

list [ begin : end ]

Listing 9.15: [Link]

Listing 9.16: [Link]

Listing 9.16 ([Link]) prints

©2011 Richard L. Halterman Draft date: November 13, 2011

Listing 9.17: [Link]

Listing 9.17 ([Link]) displays:

[10, 20, 30, 40, 50, 60, 70, 80]

9.5 Lists and Functions

A list can be passed to a function, as shown in Listing 9.18 ([Link])

Listing 9.18: [Link]

9.6 Prime Generation with a List

Listing 9.19: [Link]

Listing 9.20: [Link]

Count = 148932 Elapsed time: 56.446094827055276 seconds

• A list represents an ordered sequence of objects

• A list may elements of different types.

• The len function returns the length of the list

• A for loop is a convenient way to traverse the contents of a list.

1. Can a Python list hold a mixture of integers and strings?

(a) What expression represents the very first element of lst?

evaluate the following expressions:

1. Set n = length of list A.

4. If i is less than n− 1, set i equal to i + 1 and go to Step 2.