Card 06/ 08
A Linear Cost Hidden Inside a Built-In Call
Slicing a list, searching it with in, or growing a string inside a loop hides linear work.
Some built-in calls read as one step but do work proportional to the list or string they act on. Inside a loop over n items, one of them turns an O(n) loop into an O(n²) one. This card counts the commonest, checking whether a list contains an item, in Python, Java and TypeScript, and names three others.
A checkout checks each entered discount code against a list of valid codes. The loop runs once per code entered, so it reads as linear. Each listing below runs it with 1,000 codes in both lists, once against the list and once against a set built from it, and counts the elements each version touches.
Before the output: with 1,000 codes in both lists, how many elements does the list version touch, against 1,000 for the set?
500,500: each search stops at its match, so code k costs k + 1 comparisons, and 1 + 2 + … + 1,000 = 500,500.
The three listings count the same thing, one tab per language.
Checking 1,000 codes against a list and against a set
from dataclasses import dataclass
touched = 0
@dataclass(frozen=True, eq=False)
class Code:
value: int
def __eq__(self, other: object) -> bool:
global touched
touched += 1
return isinstance(other, Code) and other.value == self.value
def __hash__(self) -> int:
return hash(self.value)
def count_valid_with_list(entered: list[Code], valid: list[Code]) -> int:
count = 0
for code in entered:
if code in valid:
count += 1
return count
def count_valid_with_set(entered: list[Code], valid: list[Code]) -> int:
valid_set = set(valid)
count = 0
for code in entered:
if code in valid_set:
count += 1
return count
n = 1_000
valid = [Code(value) for value in range(n)]
entered = [Code(value) for value in range(n)]
print(f"n = {n}")
touched = 0
with_list = count_valid_with_list(entered, valid)
print(f"with a list: {with_list} valid, {touched} elements touched")
touched = 0
with_set = count_valid_with_set(entered, valid)
print(f"with a set: {with_set} valid, {touched} elements touched")n = 1000
with a list: 1000 valid, 500500 elements touched
with a set: 1000 valid, 1000 elements touchedimport java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class ValidCodes {
static long touched = 0;
record Code(int value) {
@Override
public boolean equals(Object other) {
touched++;
return other instanceof Code code && code.value == value;
}
@Override
public int hashCode() {
return Integer.hashCode(value);
}
}
static int countValidWithList(List<Code> entered, List<Code> valid) {
int count = 0;
for (Code code : entered) {
if (valid.contains(code)) {
count++;
}
}
return count;
}
static int countValidWithSet(List<Code> entered, List<Code> valid) {
Set<Code> validSet = new HashSet<>(valid);
int count = 0;
for (Code code : entered) {
if (validSet.contains(code)) {
count++;
}
}
return count;
}
public static void main(String[] args) {
int n = 1_000;
List<Code> valid = new ArrayList<>();
List<Code> entered = new ArrayList<>();
for (int value = 0; value < n; value++) {
valid.add(new Code(value));
entered.add(new Code(value));
}
System.out.println("n = " + n);
touched = 0;
int withList = countValidWithList(entered, valid);
System.out.println("with a list: " + withList + " valid, " + touched + " elements touched");
touched = 0;
int withSet = countValidWithSet(entered, valid);
System.out.println("with a set: " + withSet + " valid, " + touched + " elements touched");
}
}n = 1000
with a list: 1000 valid, 500500 elements touched
with a set: 1000 valid, 1000 elements touchedlet touched = 0;
function counted(values: number[]): number[] {
return new Proxy(values, {
get(target: number[], key: string | symbol, receiver: unknown): unknown {
if (typeof key === "string" && /^\d+$/.test(key)) {
touched++;
}
return Reflect.get(target, key, receiver);
},
});
}
function countValidWithList(entered: number[], valid: number[]): number {
let count = 0;
for (const code of entered) {
if (valid.includes(code)) {
count++;
}
}
return count;
}
function countValidWithSet(entered: number[], valid: number[]): number {
const validSet = new Set(valid);
let count = 0;
for (const code of entered) {
if (validSet.has(code)) {
count++;
}
}
return count;
}
const n = 1_000;
const codes: number[] = Array.from({ length: n }, (_, value) => value);
console.log(`n = ${n}`);
touched = 0;
const withList = countValidWithList(codes, counted(codes));
console.log(`with a list: ${withList} valid, ${touched} elements touched`);
touched = 0;
const withSet = countValidWithSet(codes, counted(codes));
console.log(`with a set: ${withSet} valid, ${touched} elements touched`);n = 1000
with a list: 1000 valid, 500500 elements touched
with a set: 1000 valid, 1000 elements touchedEvery language touched 500,500 elements with the list. A list keeps no index of its contents, so in, contains and includes compare the target with each element in turn until one matches. Code k sits at position k and costs k + 1 comparisons, so 1,000 codes cost 1 + 2 + … + 1,000 = 500,500. A set files each element under a number worked out from its value, its hash, so a lookup goes straight to the elements filed under the target's hash; the set version touched 1,000. In Python and Java that is one comparison per lookup; in TypeScript it is the reads that built the set, since has reads no list element.
Three more calls hide a scan or a copy:
- A slice such as
items[1:]copies every item it keeps. pop(0)on a Python list shifts every remaining item one place left.- Building a string with
+in a loop copies the whole string built until then on every pass in Java, because a JavaStringcannot change. Python's+=may copy too: CPython, the standard Python interpreter, sometimes extends a string in place, but nothing guarantees it.
The cost is a loop that is O(n²) while reading as O(n): about 500 times the work at 1,000 items, and 50,000 times at 100,000.
Before calling a loop linear, ask how much of its argument each call in the body touches. Keep a set beside a list you search, use collections.deque to remove from the front, pass an index instead of a slice, and build strings with "".join or a StringBuilder, which copy each piece once.
← → move through sections and cards