Many values under one name
A weather station records the temperature at noon every day: 18, 21, 19, 24, 22, 17 and 20 in its first week. Seven numbers fit in seven names, mon to sun. A year gives 365, and a judge problem can give 100,000. Writing 100,000 names is impractical, and a loop cannot step from mon to tue.
Python keeps the week in order as one value, a list: temps = [18, 21, 19, 24, 22, 17, 20]. Each value inside is an element, and its position is its index, counted from 0. A list is a sequence, like the strings and tuples that come later, and most of what this lesson does with lists works on every sequence.
Writing a list and selecting by index
You write a list as its elements between square brackets, separated by commas. Square brackets after the name select one element by its index:
nums = [3, 8, 1, 6]
print(nums[0])
print(nums[3])
print(len(nums))
nums[1] = 5
print(nums)
print(nums + [2, 7])
print([0] * 3)Python details
A list can hold values of different types. nums.append(x) adds an element at the end, nums.pop() removes the last one, del nums[i] removes the one at index i, and nums.remove(x) removes the first element equal to x.
nums[0] is the first element, 3, and nums[3] is the fourth, 6. len(nums) gives the length, 4. nums[1] = 5 replaces the 8 at index 1 and leaves the other elements alone.
+ between two lists makes a new list with the elements of the first followed by those of the second, and * with a number repeats the elements. Neither changes nums.
Definition
A sequence is an ordered collection of values with a finite length. Each element is selected by its index, a whole number from 0 to the length minus one.
| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Element | 3 | 5 | 1 | 6 |
An index counts the elements before it: none before the first, three before the fourth. So the last index is one less than the length:
There is no element at index 4, so nums[4] stops with IndexError. A negative index counts from the end and stands for the length plus that number: nums[-1] is nums[4 - 1], the last element 6, and nums[-4] is the first, 3. nums[-5] is out of range too.
Selecting by index takes one step however long the list is. A list keeps its elements in a row of equal-sized slots in memory, so Python finds nums[i] with one calculation, the start of the list plus times the size of one slot, and reading nums[99999] takes as long as reading nums[0]. Adding or removing at the end is also quick on average. Inserting or removing at the front is slow, because every other element shifts one place: on a list of elements, one nums.insert(0, x) or nums.pop(0) makes about moves.
Nested lists and grids
An element can be any value, including another list. A grid of numbers is usually stored as a list of its rows.
grid = [[1, 2, 3], [4, 5, 6]]
print(grid[1])
print(grid[1][0])
print(len(grid), len(grid[0]))grid[1][0] is two selections, read from the left: grid[1] is the second row, [4, 5, 6], and [0] selects its first element, 4. len(grid) counts the rows and len(grid[0]) the elements of one row.
Deeper read: copying a list or a vector
b = a does not copy a list. It gives the same list a second name, so a change made through b shows through a:
a = [1, 2, 3]
b = a
b[0] = 99
print(a)To copy a list, write b = a.copy() or b = a[:], a slice.
Visiting every element with for
Most list problems visit every element once, the job the seven names mon to sun could not do. A while loop does it with an index i that goes up by 1 until it reaches the length; the for statement visits the elements without an index. Here is a total computed both ways:
nums = [3, 8, 1, 6]
total = 0
i = 0
while i < len(nums):
total = total + nums[i]
i = i + 1
print(total)
total = 0
for x in nums:
total = total + x
print(total)Python runs for x in nums: by evaluating nums once, then binding x to each element in order and running the body. There is no index to forget to increase and no way to read past the end, and with an empty list the body does not run at all.
Keeping a running maximum
To find the largest element, keep the largest value seen so far in best and compare each element with it. An element that is larger becomes the new best. The first input below is [3, 8, 1, 6]; the other two are a list of negative numbers, [-4, -2, -9], and a list of one element, [5].
The starting value of best
Starting best at 0 fails on [-4, -2, -9]: no element beats 0, and the program prints 0, which is not in the list.
Starting from the first element, nums[0], keeps best a value from the list. It works for every list with at least one element, including [5], where the loop compares 5 with itself.
An empty list has no first element, and nums[0] stops with IndexError, so a problem that allows needs a separate check.
Unpacking each element into several names
When every element is a short sequence of the same length, the loop can name its parts. Here each of four throws of two dice is a pair of numbers, and the program counts the doubles, the throws where both dice match:
throws = [[1, 2], [3, 3], [5, 4], [6, 6]]
doubles = 0
for a, b in throws:
if a == b:
doubles = doubles + 1
print(doubles)for a, b in throws: binds two names on every pass. The first element is [1, 2], so a is 1 and b is 2, as a, b = 1, 2 would bind them. Taking a sequence apart into names this way is unpacking. The number of names must match each element's length: a throw [2, 5, 1] stops the loop with ValueError: too many values to unpack (expected 2, got 3).
Looping over indexes with range
for x in nums gives you each element but not its position. Some problems need the position: to compare an element with its neighbor, or to say where something is. For those, loop over the indexes instead. range(1, n + 1) is a range of consecutive whole numbers, and range(len(nums)) gives the indexes of nums, 0 up to the length minus one.
nums = [3, 8, 1, 6]
print(list(range(2, 6)))
for i in range(len(nums)):
print(i, nums[i])
print(list(range(3, -1, -1)))
for _ in range(3):
print('again')Python details
list(...) turns a range into a list so that print shows its numbers.
_ is an ordinary name. By convention it says that the loop never reads the number it is given, as when you only need to repeat something three times.
A range includes its start and stops just before its end. So range(2, 6) is 2, 3, 4 and 5, and the number of values is a subtraction:
range(len(nums)) is range(0, 4) here, 4 values, one for each index. A third number sets the step: range(3, -1, -1) counts down by 1 and, still leaving out its end, stops after 0.
To visit a grid's cells with their positions, use two index loops, one inside the other: for r in range(len(grid)): picks a row, and for c in range(len(grid[r])): inside it picks a position in that row, so the body sees every cell with its row and column. Beautiful Matrix is practice for this. It gives a 5 by 5 grid of zeros with a single 1 and asks for the fewest swaps of neighboring rows or columns that move the 1 to the center, which is the distance from its row index to 2 plus the distance from its column index to 2.
Comparing each element with the one before it
With indexes, one pass can read two elements at each step, an element and the one before it. A run of consecutive elements is a subarray. Maximum Increase gives up to 100,000 numbers and asks for the longest subarray in which each element is strictly greater than the one before it.
In 1 7 2 11 15 the increasing runs are 1, 7 and 2, 11, 15, so the answer is 3. Six copies of 100 never increase, so every run has length 1.
Walk the indexes once with two counts: run, the length of the increasing run that ends at the current element, and best, the longest run so far. Each element either extends the run, when it is greater than the one before it, or starts a new run of length 1.
n = int(input())
a = list(map(int, input().split()))
best = 1
run = 1
for i in range(1, n):
if a[i] > a[i - 1]:
run += 1
else:
run = 1
best = max(best, run)
print(best)Python details
list(map(int, input().split())) reads a whole line of numbers into a list, the way map(int, input().split()) reads two numbers. The map and filter part below explains map.
The loop starts at index 1 because each step reads a[i - 1], and the first element has nothing before it. On 1 7 2 11 15, run becomes 2 at the 7, drops to 1 at the 2, then becomes 2 and 3, so best ends at 3.
Building a new list with a list comprehension
Many programs build a new list from an old one. Five students scored 72, 45, 90, 38 and 66, and the teacher adds 5 points to every score. You can build the new list the way you built a total: start from an empty list and append one value on each pass. Python also has a shorter way to write that loop, as one expression called a list comprehension. The listing does it both ways, then keeps only the scores of 50 or more:
scores = [72, 45, 90, 38, 66]
curved = []
for s in scores:
curved.append(s + 5)
print(curved)
print([s + 5 for s in scores])
print([s for s in scores if s >= 50])The comprehension [s + 5 for s in scores] holds the same parts as the loop above it. for s in scores is the loop, and s + 5 is the value that goes into the new list on each pass. An if at the end keeps only the elements that pass its test: in the last line, 45 and 38 fail s >= 50 and are left out. The general form is [<value> for <name> in <sequence> if <test>], with the if part optional.
The new list is separate, and scores stays as it was.
To make a grid of zeros, write [[0] * 3 for _ in range(2)], which evaluates [0] * 3 twice and makes two rows. [[0] * 3] * 2 repeats one row, as b = a gave one list two names, so after grid[0][0] = 1 it prints [[1, 0, 0], [1, 0, 0]].
The map and filter functions
Python also has a built-in function for each of a comprehension's two jobs. map(f, s) applies the function f to every element of s, and filter(f, s) keeps the elements for which f returns true. Both take a function as an argument. The input line map(int, input().split()) applies int to every word.
def curve(s):
return s + 5
def passing(s):
return s >= 50
scores = [72, 45, 90, 38, 66]
print(list(map(curve, scores)))
print(list(filter(passing, scores)))
words = '3 8 1 6'.split()
print(words)
print(list(map(int, words)))Python details
map and filter hand back their results one at a time, as they are asked for. list(...) collects them; printing map(curve, scores) directly shows <map object at 0x...>.
map(curve, scores) gives the same list as [curve(s) for s in scores], and filter(passing, scores) the same as [s for s in scores if passing(s)]. When the function already exists, such as int, map is shorter. For a small expression such as s + 5, a comprehension needs no def.
Combining a sequence into one value
Some processing goes the other way and turns a whole sequence into one value. This is aggregation. Python's sum, max and min take a whole sequence:
scores = [72, 45, 90, 38, 66]
print(sum(scores))
print(sum(scores) / len(scores))
print(max(scores) - min(scores))
print(len([s for s in scores if s >= 50]))The scores add up to 311, so the average is , the spread from lowest to highest is , and 3 scores pass.
Each of these reads every element once, about steps on a list of elements. One call is cheap, but the cost adds up when the call sits inside a loop over the same list. Asking for the maximum on every pass of a loop over scores costs steps per pass:
The maximum does not change while the loop runs, so compute it once before the loop and keep it in a name.
Deeper read: combining the elements with your own function
sum combines the elements by adding them. reduce, from the functools module, combines them with any function of two arguments that you give it, one element at a time, from a starting value you choose. Here the function multiplies:
def multiply(a, b):
return a * b
nums = [3, 8, 1, 6]
print(reduce(multiply, nums, 1))The product starts from 1 and multiplies in each element, left to right:
The starting value is the answer for an empty list, which is why it is 0 for adding and 1 for multiplying.
Membership tests and slices
Two more operations work on every sequence. in and not in test whether a value is one of the elements, and a slice, nums[start:end], is the elements between two positions.
nums = [3, 8, 1, 6]
print(8 in nums)
print(5 not in nums)
print(nums.index(1))
print(nums[1:3])
print(nums[:2])
print(nums[2:])
print(nums[::-1])Python details
nums.index(x) gives the index of the first element equal to x. When there is none, it stops with ValueError, so check x in nums first.
8 in nums looks like one step, but Python compares 8 with the elements one at a time until one matches: up to comparisons on a list of elements.
AtCoder's problem titled "^{-1}" (ABC 277 A) gives each of the numbers 1 to once and asks for the position of , counting from 1. index answers it in one call, plus one.
A slice follows the rule of a range: nums[1:3] includes index 1 and stops before 3, so it holds elements. Leaving out the start means from the beginning and leaving out the end means to the last element, so nums[:2] and nums[2:] split the list with nothing lost or repeated. A third number is a step, as in a range, so nums[::-1] steps backward through the whole list and gives it reversed. A slice is a new list; changing it leaves nums alone.
Tuples: sequences that cannot change
A tuple is a sequence written with parentheses instead of square brackets, or with only commas. It supports everything this lesson did with a sequence: length, indexing, slicing, unpacking and in. Unlike a list, a tuple is immutable: its elements cannot be replaced once it is made. It suits a small group of values that belong together, such as the two coordinates of a point.
point = (3, 4)
print(point[0], len(point))
x, y = point
print(x * x + y * y)
print(4 in point, point[1:])
single = (10,)
print(len(single), len(()))Python details
(10,) is a tuple with one element. Without the comma, (10) is the number 10 in parentheses. () is the empty tuple.
>>> point = (3, 4)
>>> point[0] = 5
TypeError: 'tuple' object does not support item assignmentx, y = point unpacks the tuple, so . point[1:] is a slice of a tuple, so it is a tuple too, (4,).
Tuples compare part by part from the left: (3, 4) < (3, 9) is True because the first parts tie and 4 is less than 9. Sorting a list of tuples puts them in this order.
Python lets a tuple of numbers or strings be a dictionary key because its elements cannot change after it is stored; a list cannot be a key. A key such as (3, 4) can name a point on a grid.
Common mistakes
Reading past the last index, such as
nums[4]on a list of four elements.- Where it breaks
- Python stops with
IndexError: list index out of range. C++ does not check: it reads the memory past the vector, which can print garbage, crash, or seem to work on your machine. - The fix
- Indexes run from 0 to the length minus one. In C++,
nums.at(4)checks the index and stops with an error.
Starting a maximum at 0.
- Where it breaks
- For
[-4, -2, -9]the program prints 0, a number that is not in the list. - The fix
- Start from the first element,
nums[0].
Comparing with
a[i + 1]whileiruns to the last index.- Where it breaks
- For
1 7 2 11 15, ati = 4the loop readsa[5], one past the end. Python stops withIndexError; C++ reads whatever memory follows the vector. - The fix
- Compare with the element before,
a[i - 1], and start at , as Maximum Increase does.
Python only: printing the result of
maporfilterdirectly,print(map(int, words)).- Where it breaks
- Python prints
<map object at 0x...>instead of the numbers. - The fix
- Collect the results first:
print(list(map(int, words)))prints[3, 8, 1, 6].
Python only: writing a one-element tuple without its comma,
single = (10).- Where it breaks
singleis the number 10, solen(single)stops withTypeError: object of type 'int' has no len().- The fix
- Write
(10,): the comma makes the tuple.
Recall In a list of 10 elements, what are the first and last indexes?
0 and 9. Indexes start at 0, so the last one is the length minus one.
Recall How many elements does `nums[2:7]` hold when `nums` has 10 elements, and what does `list(range(2, 7))` print?
Five, the elements at indexes 2, 3, 4, 5 and 6, since . The range prints [2, 3, 4, 5, 6]: slices and ranges both include the start and stop just before the end.
Recall Why does the Maximum Increase loop start at `i = 1`?
Each step compares a[i] with a[i - 1]. The first element has nothing before it, so on its own it is a run of length 1, and the comparisons start with the second element.
Key terms
| Term | Meaning |
|---|---|
| list | Python's ordered collection of values: [3, 8, 1, 6]. |
| vector | C++'s ordered collection of values of one type: vector<int>. |
| sequence | An ordered collection with a length, whose elements are selected by index. |
| element | One value in a sequence. |
| index | An element's position, counted from 0: nums[0] is the first. |
| length | How many elements there are: len(nums) or nums.size(). |
| unpacking | Binding several names to the parts of a value: for a, b in throws, auto [a, b]. |
| range | The consecutive whole numbers from a start up to, not including, an end. |
| subarray | A run of consecutive elements, such as 2, 11, 15 in 1 7 2 11 15. |
| list comprehension | An expression that builds a list from a sequence: [s + 5 for s in scores if s < 50]. |
| aggregation | Combining all the elements of a sequence into one value, as sum, max and min do. |
| slice | The elements between two indexes, as a new sequence: nums[1:3]. |
| tuple | An immutable sequence: (3, 4). C++ has pair and tuple. |
