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

Covers OCR H446 1.4.2 Data Structures · AQA 7517 4.2.1.1 Data structures · AQA 7517 4.2.1.2 Single- and multi-dimensional arrays (or equivalent) · AQA 7517 4.2.1.3 Fields, records and files · Eduqas A500QS 1.1 Data structures

Do this lesson in the simulator

Print it: worksheet (PDF) · answers (PDF) · as a web page

Guide: Stacks and queues explained

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.

The array readings as eight equal cells side by side in memory, with the address of each0[0]10000[1]10040[2]100842[3]10120[4]10160[5]10200[6]10240[7]1028addressreadings, 8 integers of 4 bytes eachaddress of [3] = 1000 + 3 × 4 = 1012
Every element is the same size and they sit side by side, so the address of readings[3] is one sum: start + 3 × size. Here each integer takes 4 bytes and element 0 is at address 1000. The sum is just as quick for readings[500].

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.

An 8 by 8 grid and the same 64 values as one flat list, row after row0123456701234567rowcolumngrid[3][4]rows 0 to 2 come first: 3 × 8 = 24 valuesthen 4 more along row 3: 24 + 4 = 28so it is flat[28]the flat list from tof_grid(), positions 0 to 63row 0row 1row 2row 3row 4row 5row 6row 728
Row-major order lays the rows end to end. To reach row 3, column 4, skip 3 whole rows of 8, then go 4 along: position 3 × 8 + 4 = 28.

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.

Three 4 by 4 grids side by side, one per scan, with scans[2][1][3] picked out by its three indexesscans[0]0123scans[1]0123scans[2]01230123rowscans[2][1][3]2: which scan1: which row3: which column
The stack of scans laid out side by side. The first index picks the grid, then the row and column work as in a 2D array, so scans[2][1][3] is row 1, column 3 of scan 2.
# 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:

Two variables each holding two rows: in wrong both rows are one list, in right they are two listswrong = [[0] * 3] * 2wrong[0]wrong[1]050one row, two references to it:change it through wrong[0] andwrong[1] shows the change tooright: a new row for each rright[0]right[1]050000two separate rows: changingright[0] leaves right[1] alone
Multiplying a list of rows copies the reference to the row, not the row itself, so wrong has one row seen twice. Building each row in the loop gives right two rows of its own.
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.

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:

  1. size: 3 x 4 x 4, working the three sizes out with len().
  2. 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.
  3. 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

  1. 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.
  2. Print the average of each row position across all three scans, so you can see which row of the view is usually nearest.
  3. Write Reading as a tuple instead of a dataclass. What can you no longer do, and when would that be an advantage?