Card 04/ 08
Optimisation Example: The Most Common Air-Quality Reading
Three faster ways to find the reading that occurs most often: each removes the nested count, and each costs a different amount of memory.
A faster solution usually pays for its speed in memory, and stating that price is part of the optimisation, because two moves that reach the same time can need very different amounts of memory. An air-quality sensor logs readings between 0 and 500, and the task is the reading that occurs most often. Ten readings: 42, 57, 42, 61, 57, 42, 38, 61, 57, 42. The first answer counts each reading against every other, O(n²) time; step 1 of the procedure finds that nested count dominating, and there are three standard moves that remove it.
Of the four approaches, which needs the least extra memory?
The nested count, with O(1): it stores only the best reading and its count. Every faster approach stores something, and that memory is the price of its speed.
Sorting puts equal readings next to each other, so the longest run of equal values gives the answer in O(n log n), but the sort itself needs memory: Python's sort and V8's Array.prototype.sort are merge sorts of the Timsort family that can use a buffer of up to n/2 items, and Java's Arrays.sort on an int array uses an O(log n) stack for most inputs and, in JDK 25, a buffer of n ints when 4,096 or more values arrive as a few long sorted runs. A hash map of counts takes O(n) time on average and O(d) memory for d distinct readings. A counting array works only because readings are whole numbers from 0 to 500: one slot per possible reading, O(n + r) time and O(r) memory for r = 501.
| Approach | Time | Extra memory | What it removes |
|---|---|---|---|
| Count each reading against every other | O(n²) | O(1) | Nothing |
| Sort, then the longest run of equal values | O(n log n) | The sort's: up to O(n) | The repeated counting, by putting equal values together |
| A hash map of counts | O(n) on average | O(d), d distinct readings | The repeated counting, by one lookup per reading |
| A counting array of 501 slots | O(n + r) | O(r), r = 501 | The repeated counting, with no hashing |
The listing runs the hash map and the counting array on the ten readings.
from collections import Counter
readings = [42, 57, 42, 61, 57, 42, 38, 61, 57, 42]
counts = Counter(readings)
reading, times = counts.most_common(1)[0]
print(f"hash map: {reading} occurs {times} times; {len(counts)} counts stored")
slots = [0] * 501
for value in readings:
slots[value] += 1
most = max(range(501), key=slots.__getitem__)
print(f"counting array: {most} occurs {slots[most]} times; {len(slots)} counts stored")
print("all counts:", ", ".join(f"{v} x{c}" for v, c in counts.most_common()))hash map: 42 occurs 4 times; 4 counts stored
counting array: 42 occurs 4 times; 501 counts stored
all counts: 42 x4, 57 x3, 61 x2, 38 x1Both find 42, four times. The map stores 4 counts and the array 501, so on ten readings the map is smaller; on a year of readings taken every minute, about 525,000 of them, the array's 501 slots are far less than a map that could hold up to 501 keys plus its hashing overhead, and the array never hashes. When memory is the limit, sorting the readings in place where the language allows it, or keeping the nested count, are the options; when the range of values is small and known, the counting array is usually the best of both.
- Complexity Analysis
- Performance
← → move through sections and cards