Data, data structures and algorithms, and why speed depends on them

Everything is bits

Computers store everything as bits: binary digits that are either 0 or 1. Physically a bit might be a tiny electrical charge, a magnetic region on a disk or a pulse of light in a fibre, but to software it is just one of two values. Eight bits make a byte, which can hold 2⁸ = 256 different patterns, from 00000000 to 11111111.

Sizes build up from there. A kilobyte is about a thousand bytes, a megabyte about a million, a gigabyte about a billion and a terabyte about a trillion. (Strictly, the standard prefixes kilo, mega and giga mean powers of 1,000; memory is often measured in powers of 1,024, for which the units kibibyte, mebibyte and gibibyte exist. The difference rarely matters for design but explains why a "1 TB" disk shows less in some file managers.) A page of plain text is a few kilobytes, a phone photo a few megabytes, an hour of high-definition video a few gigabytes.

Bits mean nothing on their own. The pattern 01000001 could be the number 65, the letter A, part of a colour in a photo or part of an instruction for the CPU. What gives bits meaning is the agreement about how to read them, which is the idea of a data type.

Data types: numbers, text and true or false

A data type tells a program what kind of value a piece of data is, and therefore what operations make sense. Every programming language has a few basic types, and Python's are typical.

Integers are whole numbers such as 3, 0 or -42, used for counting things: items in a basket, seats on a flight. Floating-point numbers (floats) such as 12.5 or 0.2 represent decimals approximately, in binary. Because many decimals have no exact binary form, 0.1 + 0.2 in Python gives 0.30000000000000004. That is fine for physics and graphics but wrong for money, which is why financial systems store amounts as whole numbers of pence or cents, or use a decimal type (Python has decimal.Decimal). Booleans have just two values, True and False, and record yes-or-no facts such as "has this order been paid?". Strings are text, such as a customer's name. Real systems add more types on top: dates and times, money, and binary data such as images.

Types matter beyond a single program. When two systems exchange data, they must agree on types as well as on values: is a postcode a number or text (text: some begin with letters, and some numeric codes begin with zero)? Is a date in day-month or month-day order, and in which time zone? Many expensive integration bugs are type disagreements.

Text and UTF-8

Text is stored by giving every character a number and then storing the numbers as bytes. The international standard Unicode assigns a number, called a code point, to well over a hundred thousand characters from the world's writing systems, plus symbols and emoji. An encoding then decides how those numbers become bytes. Today the dominant encoding, on the web and in most new systems, is UTF-8.

UTF-8 uses a variable number of bytes per character: one byte for the basic English letters, digits and punctuation (so text that uses only these characters is byte-for-byte identical in UTF-8 to the much older ASCII encoding), two bytes for characters such as é, three for characters such as € and most Chinese, Japanese and Korean characters, and four for emoji and some rarer scripts. This has a practical consequence: the number of characters in a string and the number of bytes it occupies can differ. A database column limited to 50 bytes may not hold a 50-character name written in Greek.

The classic text bug is garbled characters (for example Café instead of Café), which appears when bytes written in one encoding are read as another. The cure is simple to state: use UTF-8 everywhere, and say so explicitly whenever text crosses a boundary, such as a file, a database or a network message.

Data structures: ways of arranging data

Programs rarely deal with one value at a time. A data structure is a way of organising many values in memory so that the operations you need are quick. The right choice can make the difference between a page that loads instantly and one that never loads. Each has an everyday analogy.

A list (called an array in many languages) keeps items in order, like a numbered shopping list. Getting the fifth item is instant, because the computer can calculate where it is. Finding an item by its value means checking items one by one. A dictionary (also called a map or hash table) stores values under unique keys, like a coat check: hand over ticket C377 and you get the right coat at once, without looking at every coat. A set is a collection with no duplicates, like a guest list, and answers "is this person on it?" quickly.

A queue works like a line at a post office counter: first in, first out. Systems use queues for work waiting to be done, such as orders waiting for a kitchen. A stack works like a pile of plates: last in, first out. Your browser's Back button uses one: the page you visited most recently is the first one you return to. A tree has a single root with branches beneath it, like a family tree or the folders on your computer; trees are also how databases keep data sorted for fast searching. A graph is items (nodes) joined by links (edges) in any pattern, like a road map or a social network, and answers questions such as "what is the shortest route?" or "who are friends of friends?".

basket = ["pizza", "cola", "pizza"]            # list: ordered, duplicates allowed
print(basket[0])                                # by position: "pizza"

customers = {"C102": "Ana", "C377": "Chen"}      # dictionary: key to value
print(customers["C377"])                        # by key: "Chen"

voted = {"ana@example.com", "ben@example.com"}   # set: no duplicates
print("ana@example.com" in voted)              # True

from collections import deque
kitchen = deque(["order 1", "order 2"])         # queue
kitchen.append("order 3")                       # joins at the back
print(kitchen.popleft())                        # served first: "order 1"

Algorithms

An algorithm is a precise, step-by-step method for solving a problem that always finishes: like a recipe, but with no room for interpretation. Sorting a list of names, finding the shortest route between two addresses, checking whether a password matches and deciding which advert to show are all done by algorithms.

There is usually more than one algorithm for the same problem, and they can differ enormously in how much work they do. Consider finding a name in a printed telephone directory. You could start at page one and read every entry until you find it: correct, but slow. Or you could open the book in the middle, see whether the name comes before or after that page, discard the half that cannot contain it and repeat. Because the directory is sorted, each look halves the remaining pages. This second method is called binary search, and for a directory of a million names it needs about 20 looks instead of up to a million.

Big-O: how work grows with data

Engineers describe how an algorithm's cost grows using Big-O notation. It ignores the exact time on a particular machine and asks one question: if the amount of data, called n, gets ten or a thousand times larger, how much more work is there? It describes the worst case unless someone says otherwise, and it ignores constant factors, which is both its strength (it captures the shape of growth) and its weakness (two O(n) algorithms can still differ by a factor of ten in practice).

O(1), constant time: the work does not depend on n. Looking up a key in a dictionary is O(1) on average. O(log n), logarithmic: the work grows by one step each time n doubles, like binary search. O(n), linear: double the data, double the work, like scanning a list. O(n log n): slightly worse than linear; good general-purpose sorting algorithms work at this rate. O(n²), quadratic: double the data, four times the work. This typically appears when, for every item, a program loops over every other item, such as comparing each customer with every other customer to find duplicates.

Read the last column carefully. At a billion simple steps per second, a million-squared algorithm needs a trillion steps: around a quarter of an hour of pure computation, and in practice far longer. The same job done with an O(n log n) method takes a small fraction of a second. Code that looked fine in testing with 1,000 customers can grind to a halt with a million, and no amount of extra hardware will rescue a quadratic algorithm for long.

Space versus time

The dictionary in the worked example is faster because it uses extra memory to organise the data in advance. This is one of the most common trade-offs in computing: you can often buy speed with space, or save space by spending time.

An index is extra data, kept beside the main data, that answers a particular kind of question quickly, like the index at the back of a book. It speeds up reads, but it takes storage and must be updated on every write, so a table with ten indexes is slow to insert into. A cache keeps a copy of the answer to an expensive question somewhere fast, such as in memory, so the next person to ask gets it immediately. Caches are why a popular product page loads quickly even when the database behind it is busy, but they raise a hard question: when the underlying data changes, how quickly must the copy change too? Showing a stale price for a few seconds may be acceptable; showing a stale bank balance may not.

Compression is the opposite trade: spend CPU time to squeeze data into fewer bytes, which saves storage and network transfer time.

Why this matters for architecture

Architects rarely write sorting algorithms, but they constantly make decisions whose consequences are exactly these. Which questions will the system need to answer quickly, and does the data have the indexes to answer them? How large will the data grow in three years, and which parts of the design are linear or worse in that growth? Where is caching worth its complexity, and how stale may cached data be? When data volume grows tenfold, which component breaks first?

These are questions about performance and scalability, which Chapter 2 makes precise, and about caching and database choice, which Chapter 7 treats in depth. The next section turns from data to code, and to how code is organised so that people can understand and change it.