Arrays, records and tuples

Arrays in one, two and three dimensions, records and fields, tuples and lists, and static structures.

A3.1Data structuresA level20 min

A data structure is a way of organising data in memory so a program can use it efficiently. At GCSE you met lists as one-dimensional arrays, two-dimensional arrays for the depth grid, and records for the robot's readings (module F3). At A level you need to say exactly what each structure is, how it is laid out in memory, and why you would choose it. This module works through the structures on the specifications, starting with the simplest: arrays, records and tuples.

Arrays

An array is a fixed-size, ordered collection of elements of the same data type, each reached by an index. Because every element is the same size and they sit next to each other in memory, the computer can work out where element i is without looking at the others:

address of element i = address of element 0 + i × size of one element

That is why reading readings[500] takes the same time as reading readings[0]: arrays give direct (random) access. The price is that an array's size is set when it is created. It is a static data structure.

Python's lists are not true arrays: they can grow, shrink and hold mixed types. When an exam says array, you can model one in Python by making a list of the right size once and never changing its length:

readings = [0] * 8          # an array of 8 integers, all 0
readings[3] = 42            # assign by index
print(readings)
print(len(readings), "elements, index 0 to", len(readings) - 1)

Run this in the simulator

Two and three dimensions

A two-dimensional array has rows and columns, and needs two indexes. BugBot's depth sensor sees an 8 by 8 grid: grid[row][col]. In memory the rows are usually stored one after another (row-major order), so element [r][c] of an array with C columns is at position r × C + c from the start. tof_grid() hands its 64 distances back in exactly that form, one flat list, row after row, as you saw in F3.5.

A three-dimensional array needs three indexes. Keep several depth scans and you have one: scans[scan][row][col]. Think of a stack of grids, one per scan.

A three-dimensional array: three scans, each 4 rows by 4 columns

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

scans = []
for s in range(3):
    flat = tof_grid()                        # 64 distances in row-major order
    grid = []
    for r in range(8):
        grid.append(flat[r * 8 : r * 8 + 8]) # row r is elements r × 8 to r × 8 + 7
    scans.append(grid)
    turn_right(30, angle=20)

print("scans:", len(scans), "rows:", len(scans[0]), "columns:", len(scans[0][0]))
print("scan 2, row 3, column 4:", scans[2][3][4], "cm")
print("the same reading in the flat list:", flat[3 * 8 + 4], "cm")

Run this in the simulator

len(scans) is the size of the first dimension, len(scans[0]) the second and len(scans[0][0]) the third. To visit every element you need one loop per dimension, nested.

A trap when you make a 2D array in Python: [[0] * 3] * 2 makes a list holding the same row twice, so changing one row changes both. Build each row separately:

wrong = [[0] * 3] * 2
wrong[0][1] = 5
print(wrong)                         # [[0, 5, 0], [0, 5, 0]]

right = [[0] * 3 for r in range(2)]
right[0][1] = 5
print(right)                         # [[0, 5, 0], [0, 0, 0]]

Run this in the simulator

Records and fields

A record groups related values of different types under one name. Each value is a field with its own name and type. A reading might have a scan number (integer), a heading (real), and a flag for whether the way was clear (Boolean). Where an array says "many of the same thing", a record says "one thing, described several ways".

Exam papers often declare a record type like this before using it:

RECORD Reading
    scan    : Integer
    heading : Real
    clear   : Boolean
ENDRECORD

Python has no record keyword. A dataclass is the closest match: named fields with stated types.

from dataclasses import dataclass

@dataclass
class Reading:
    scan: int
    heading: float
    clear: bool

log = [Reading(0, 0.0, True), Reading(1, 20.0, False), Reading(2, 40.0, True)]
for r in log:
    if r.clear:
        print("scan", r.scan, "was clear at", r.heading, "degrees")

Run this in the simulator

An array of records, like log, is how most programs hold a table of data. A file of records is the same idea kept on storage: every record has the same fields in the same order. Lesson A3.8 looks at how such files are organised.

Tuples and lists

A tuple is an ordered collection of elements, possibly of different types, that is immutable: once made, it cannot be changed. BugBot's position() returns a tuple, because an (x, y) pair belongs together and should not be edited half at a time.

p = (12.5, 30.0)
x, y = p                     # unpacking: one variable per element
print("x is", x, "and y is", y)
try:
    p[0] = 0.0
except TypeError as e:
    print("TypeError:", e)

Run this in the simulator

A list, in the A level sense, is an ordered collection that can change size and hold mixed types: Python's list. So the three differ like this:

Structure	Size	Elements	Can change?
Array	fixed	one type	elements yes, size no
List	can grow and shrink	any types	yes
Tuple	fixed	any types	no (immutable)
Record	fixed set of named fields	a type per field	fields yes

Immutability is useful: a tuple can be a dictionary key (lesson A3.6), and a function given a tuple cannot change the caller's data by accident.

In the exam

Questions ask you to define arrays, records and tuples, to write or trace code that loops over a 2D or 3D array, to give the index of an element, and to choose a suitable structure for some data and justify it. Remember that an array holds one data type and has a fixed size.

OCR A level 1.4.2

OCR lists arrays of up to three dimensions, records, lists and tuples. In the exam reference language an array is declared with its size and indexed from 0, with commas between the indexes:

array scans[3, 8, 8]
scans[2, 3, 4] = 30
for s = 0 to 2
    print(scans[s, 0, 0])
next s

AQA A level 4.2.1.1 4.2.1.2 4.2.1.3

AQA asks you to be familiar with the concept of data structures, to use single- and multi-dimensional arrays (or their equivalent in your language) in the design of solutions to simple problems, and to understand fields, records and files, including reading and writing text and binary files (lesson A3.8).

Eduqas A level 1.1

Eduqas asks you to describe, interpret and manipulate data structures, including multi-dimensional arrays and records, and to choose an appropriate structure for a given situation.

Task: the depth cube

scans is a 3D array of three saved 4 by 4 depth scans, indexed scans[scan][row][col], each value a whole number of centimetres from 1 to 100. Using nested loops and len(), print:

size: 3 x 4 x 4, working the three sizes out with len().
For each scan s from 0 to 2, scan <s> average: <mean>, the mean of its 16 values rounded to 1 decimal place with round(value, 1), for example scan 0 average: 56.0.
nearest: <cm> cm at [<scan>][<row>][<col>], the smallest value and its three indexes. The smallest value appears only once.

The robot does not move.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

# scans[scan][row][col]: three saved 4 by 4 depth scans, in cm
scans = [
    [[45, 44, 43, 50], [40, 38, 39, 41], [60, 58, 57, 59], [80, 79, 81, 82]],
    [[44, 42, 41, 49], [39, 36, 12, 40], [61, 57, 56, 60], [78, 80, 80, 83]],
    [[46, 43, 42, 51], [41, 37, 38, 42], [59, 59, 55, 58], [81, 78, 82, 80]],
]

Challenges

The array is stored in row-major order, scan by scan. At what position from the start is scans[2][1][3]? Check your answer by flattening the array into a 1D list.
Print the average of each row position across all three scans, so you can see which row of the view is usually nearest.
Write Reading as a tuple instead of a dataclass. What can you no longer do, and when would that be an advantage?