Applying Algorithms to Engineering Data

Part I · Module 20 · Chapter 20.10 · Applying Algorithms to Engineering Data

1. The Data

enum class Kind { Read, Write };
struct Txn {
    std::uint32_t addr;
    Kind          kind;
    int           latency;   // cycles
    int           master;    // which initiator
    bool          error;
};

A plain aggregate — Chapter 9.8 §2's definition — with fixed-width types for the address because it models a hardware field, which is Chapter 3.4's argument. Twenty thousand of them in a std::vector<Txn>, which is Chapter 19.7 §1's default and correct here: the log is built once, traversed repeatedly, and never needs insertion in the middle.

The generator is a deterministic xorshift seeded with a constant, so every number in this chapter reproduces exactly on re-run. That matters more than it sounds: a chapter quoting measurements from random data cannot be checked, and Chapter 19.8 §10's discipline applies to correctness figures as much as to timings.

A. the log: 20000 transactions

2. Filter

std::vector<Txn> sel;
std::copy_if(log.begin(), log.end(), std::back_inserter(sel),
    [](const Txn& t){ return t.kind == Kind::Write && t.master == 2 && !t.error; });

selected 2467 of 20000 (12.3%)

One pass, one predicate, three conditions. The std::back_inserter is doing the work Chapter 20.7 §2 measured: sel starts empty, and without an insert iterator the algorithm would write into no storage at all.

const Txn& in the predicate matters at this size — by value would copy a 20-byte struct twenty thousand times. Chapter 20.6 §1 made the same point for comparators.

If the count were known in advance, sel.reserve(n) before the call would turn Chapter 19.3 §4's eleven allocations into one. Here it is not known, which is exactly when back_inserter's growth is the right trade.

3. Sort, With a Tie-Break

std::sort(sel.begin(), sel.end(), [](const Txn& a, const Txn& b){
    return std::tie(a.addr, a.latency) < std::tie(b.addr, b.latency);
});

first 5: (0x0064,98) (0x00B0,79) (0x00CC,21) (0x00CC,102) (0x00F8,25)
is_sorted = 1

Address 0x00CC appears twice, with latencies 21 and 102 in that order — the tie-break working. std::tie is Chapter 20.6 §6's safe multi-key form: lexicographic by construction, so it cannot be the non-transitive || mistake.

The is_sorted check with the same comparator is not decoration. §6 runs a set_difference, and Chapter 20.5 §6 measured what the sorted-range algorithms do when the precondition is not met — six of six lookups wrong, exit 0, no diagnostic. Asserting the postcondition where it is established is cheap insurance: one O(n) pass.

Note that plain std::sort is used rather than stable_sort, and that is a decision rather than a default. The comparator already orders every pair that could be equivalent — two transactions with the same address and the same latency are genuinely interchangeable for this report — so Chapter 20.6 §4's instability cannot affect the output. If the report needed arrival order preserved among identical rows, stable_sort would be the only correct call.

4. Summarise

long long total = std::accumulate(sel.begin(), sel.end(), 0LL,
    [](long long acc, const Txn& t){ return acc + t.latency; });
auto [mn, mx] = std::minmax_element(sel.begin(), sel.end(),
    [](const Txn& a, const Txn& b){ return a.latency < b.latency; });

count  2467
sum    156748   (0LL accumulator, not 0 -- see 20.7)
mean   63.54 cycles   stddev 34.80
min    4    max 123
median 64    p90 112    p99 122   (nth_element, O(n) each)
over 100 cycles: 477  (count_if)

Five things in that block, each a deliberate choice.

0LL, not 0. Chapter 20.7 §4 measured a bare 0 making a sum of 8.00 come out as 6, silently, with nothing from -Weverything. Here the elements are int so truncation is not the risk — overflow is: 2,467 latencies could in principle exceed INT_MAX at a larger scale, and the habit costs two characters. The comment in the source points at the chapter.

minmax_element, not two calls. One pass, roughly 1.5n comparisons against 2n — Chapter 20.5 §8.

nth_element for the percentiles, three times on copies:

auto nth = [&](double q){
    std::vector<int> tmp = lat;
    std::size_t k = (std::size_t)(q * (double)(tmp.size() - 1));
    std::nth_element(tmp.begin(), tmp.begin() + k, tmp.end());
    return tmp[k];
};

O(n) each rather than O(n log n) for a full sort — Chapter 20.6 §5 measured 6.7× on 200,000 elements. The copy is necessary because nth_element reorders its input, and three percentiles from one sort would also have worked; at 2,467 elements either is fine, and the version that does not mutate the caller's data is the one to prefer.

The standard deviation is a second accumulate with a captured mean:

double var = std::accumulate(lat.begin(), lat.end(), 0.0,
    [mean](double acc, int x){ double d = x - mean; return acc + d*d; }) / (double)n;

0.0 here, because the accumulator genuinely is floating point — and [mean] by value, which is correct per Chapter 20.8 §4 since the lambda is called during the accumulate and the value should not change under it.

The mean alone would have been misleading. Mean 63.54 with a standard deviation of 34.80 and a p99 of 122 describes a wide, nearly uniform distribution; the 477 transactions over 100 cycles are a real population, not outliers. A report quoting only the mean would hide that.

5. Group

std::map<int, std::pair<long, long long>> byMaster;   // master -> (count, total)
for (const Txn& t : log) { auto& e = byMaster[t.master]; e.first++; e.second += t.latency; }

master 0:   5075 txns, mean latency 64.19
master 1:   4995 txns, mean latency 64.65
master 2:   4916 txns, mean latency 63.78
master 3:   5014 txns, mean latency 63.47

This step is a range-based for, not an algorithm, and that is Chapter 20.4 §6's rule being applied honestly rather than ignored. A grouped accumulation updates a different accumulator per element, and no standard algorithm expresses that: for_each with a capturing lambda would be the same loop with more syntax, and there is no group_by in C++17.

Two details. operator[] on the map is being used deliberately to insert-on-first-sight, which is the one idiom Chapter 19.5 §3 identifies as what that operator is actually for — the counting pattern. And std::map rather than unordered_map because the output is a report and should come out in master order, which Chapter 19.5 §2 measured as free.

The result is also a small cross-check on §2: the four counts sum to 20,000, and master 2's 4,916 is consistent with §2 selecting 2,467 writes-without-error from it.

6. Compare Two Result Sets

This is the part of the frozen purpose that is least often done well, because "the two differ" is rarely a useful answer.

Set B is the same filter with one condition dropped — errors are kept:

std::copy_if(log.begin(), log.end(), std::back_inserter(other),
    [](const Txn& t){ return t.kind == Kind::Write && t.master == 2; });

set A (no errors) 2467   set B (errors kept) 2482
equal as sequences? 0
first divergence at index 237
  A: (0x1A64,WR,54,err=0)   B: (0x1A60,WR,85,err=1)
addresses in B but not A: 15  (set_difference, both pre-sorted)
B's extra rows are exactly the errored ones: 15

Four steps, escalating in usefulness.

std::equal answers whether, and returned 0. That is the least informative possible answer and is where most comparisons stop.

std::mismatch answers where: index 237, with both records printed. The B record has err=1, which immediately suggests the cause. Chapter 20.5 §9's point that mismatch is the better tool than equal is this, concretely — the four-iterator form also handles ranges of different lengths, which these are.

std::set_difference answers what, on keys:

std::vector<std::uint32_t> ka(sel.size()), kb(other.size());
std::transform(sel.begin(), sel.end(), ka.begin(), [](const Txn& t){ return t.addr; });
std::transform(other.begin(), other.end(), kb.begin(), [](const Txn& t){ return t.addr; });
std::sort(ka.begin(), ka.end()); std::sort(kb.begin(), kb.end());
std::vector<std::uint32_t> onlyB;
std::set_difference(kb.begin(), kb.end(), ka.begin(), ka.end(), std::back_inserter(onlyB));

Fifteen addresses. Note the two std::sort calls on the line immediately before — set_difference requires both inputs sorted, and Chapter 20.5 §7 is explicit that putting the sort where the reader can see it is the practice, not relying on the inputs happening to be ordered from an earlier step.

And then the cross-check, which is the step that makes the conclusion trustworthy:

std::count_if(other.begin(), other.end(), [](const Txn& t){ return t.error; })

Fifteen. The set_difference over sorted address keys and a direct count_if on the error flag are completely independent computations — different algorithms, different data, different precondition requirements — and they agree. That is what turns "B has fifteen extra rows" from an output into a result.

7. Partition When You Want Both Halves

auto cut = std::stable_partition(all.begin(), all.end(),
    [](const Txn& t){ return t.latency <= 60; });

fast (<=60): 9393     slow (>60): 10607   in ONE pass
stable_partition keeps each half in its original order

Two copy_if passes would produce the same two groups in two traversals and two containers. stable_partition does it in one pass over the existing container, returns the boundary, and — because it is the stable variant — leaves each half in its original arrival order, which matters if either half is going to be read as a sequence of events.

9,393 and 10,607 sum to 20,000, which is the kind of arithmetic worth printing because it catches a filter that silently dropped rows.

8. The Whole Pipeline

copy_if -> sort -> accumulate / minmax_element / nth_element -> count_if
equal / mismatch / set_difference for the comparison
Not one nested loop, and not one index variable.

Nine distinct algorithms, one deliberate range-based for for the grouping, and no index arithmetic anywhere. Each step is one line of intent with a lambda supplying the per-element decision, which is the composition the module's frozen blurb describes: iterators describe position, algorithms describe intent, lambdas supply the decision.

The thing worth noticing is that the pipeline reads in the order the work happens, and each stage's output is named. That is not a property of algorithms as such — it is a property of having a named operation per stage, and it is what makes the whole thing reviewable by someone who did not write it.

9. The Steps and Why Each

10. What to Actually Do

• Name each stage and let its output be a variable. The pipeline then reads in work order.
• Write 0LL or std::int64_t{0} for any integer total that could grow, and 0.0 for a floating one.
• Use std::tie for multi-key comparators, always.
• Sort immediately before a sorted-range algorithm, on the adjacent line, where a reviewer can see it.
• Assert the postcondition with is_sorted where the order is established.
• Take predicate and comparator parameters by const& for any struct.
• Use minmax_element and nth_element rather than sorting to get extremes or percentiles.
• Report a spread, not just a mean. 63.54 with a stddev of 34.80 is a different story from 63.54 alone.
• Use mismatch, not equal, whenever a difference will need investigating.
• Compute the answer that matters twice, by independent routes, and print both.
• Print the totals that have to balance.
• Write the loop when no algorithm expresses the operation — grouping is the honest example.

11. Mistakes Worth Making Once

accumulate(..., 0) on a total that overflows. Chapter 20.7 §4 measured both the float and integer forms failing silently.

set_difference on unsorted inputs. Garbage, no diagnostic, and the result looks like a list of addresses.

std::equal as the whole comparison. Returns 0 and tells you nothing about where or why.

copy_if into dst.begin() on an empty dst. Writes into nothing.

Predicate parameters by value on a 20-byte struct. Twenty thousand copies per pass.

A full sort to get a median. O(n log n) where nth_element is O(n) — measured 6.7×.

Reporting a mean without a spread. The p99 of 122 against a mean of 63.54 is the information.

Trusting one computation of an important number. The whole point of §6's last line.

Forcing the grouping into for_each with a capturing lambda. The same loop with more syntax.

12. Interview Relevance

The frozen curriculum marks this chapter High, and the questions are usually a design exercise rather than a recall test.

"Walk me through analysing a log like this." The answer that lands is a named pipeline — filter, sort, summarise, group, compare — with a reason for each choice, and with the traps called out: a wide accumulator, the sorted precondition, const& parameters.

"How would you get a p99?" nth_element, O(n), on a copy. Volunteering that a full sort is O(n log n) and that nth_element leaves both sides unsorted is the detail.

"How do you compare two result sets?" mismatch for where, set_difference for what, and then — the part that distinguishes the answer — a second independent computation to confirm the number.

"Why a std::map for the grouping and not unordered_map?" The output is a report and should be in key order, which the tree gives free.

"Why is the grouping a loop?" Because no standard algorithm expresses per-key accumulation, and for_each with a capturing lambda would be the same loop with more syntax. Being willing to say that is better than forcing everything into an algorithm.

"What would you check before trusting the output?" The totals that must balance, the is_sorted postcondition, and an independent recomputation of the headline number.

13. What You Should Be Able to Say Now

• How to build a filter-sort-summarise-compare pipeline from named algorithms with no index arithmetic.
• Why the accumulator is 0LL and the variance accumulator is 0.0.
• Why std::tie is the multi-key comparator and why is_sorted is asserted after the sort.
• That nth_element gives percentiles in O(n) and must work on a copy.
• That mismatch found the divergence at index 237 and printed both records, where equal returned only 0.
• That set_difference requires both inputs sorted and that the sorts belong on the adjacent lines.
• That two independent methods both returned 15, and why that agreement is the result rather than either number alone.
• That stable_partition split 20,000 records into 9,393 and 10,607 in one pass with order preserved.
• That the grouping is deliberately a loop.

14. Exercises

Exercise 1 — reproduce it. Build the pipeline and confirm every figure: 2,467 selected, sum 156,748, median 64, p99 122, divergence at index 237, and 15 from both methods.

Exercise 2 — break the precondition. Remove the two std::sort calls before set_difference and report what it returns. Then add assert(std::is_sorted(...)) and show it firing.

Exercise 3 — break the accumulator. Change 0LL to 0 and scale the log until the sum overflows. Report the wrong total and whether UBSan catches it.

Exercise 4 — a third route. Compute the number of extra rows in B a third independent way — neither set_difference nor count_if on the flag — and confirm it also gives 15.

Exercise 5 — the spread. Add p50, p90, p99 and p99.9 plus a histogram of ten buckets. State what the histogram shows that the five numbers do not.

Exercise 6 — group differently. Redo §5 with unordered_map and with a std::vector indexed by master. Compare the code, the output order and the allocation counts.

Exercise 7 — partition versus two filters. Implement §7 both ways and measure passes, allocations and whether order is preserved.

Exercise 8 — one more condition. Add "address in a given range" to the filter using lower_bound on the sorted set rather than a predicate, and explain which is better and when.

15. Summary

• A realistic log analysis built from nine named algorithms, one deliberate range-based for, and no index variables.
• Measured: copy_if selected 2,467 of 20,000 (12.3%) in one pass, with back_inserter because the destination was empty.
• Measured: sort with std::tie(addr, latency) produced (0x00CC,21) before (0x00CC,102) — the tie-break — and is_sorted confirmed it.
• Measured: sum 156,748 with a 0LL accumulator, mean 63.54, stddev 34.80, min 4, max 123, median 64, p90 112, p99 122 via nth_element, and 477 transactions over 100 cycles.
• Measured: four masters at 5,075 / 4,995 / 4,916 / 5,014, summing to 20,000 — grouped with a loop, because no algorithm expresses per-key accumulation.
• Measured comparison: equal = 0; mismatch found index 237 and printed A: (0x1A64,WR,54,err=0) against B: (0x1A60,WR,85,err=1).
• Measured: set_difference on sorted keys gave 15, and count_if on the error flag gave 15 — two independent routes agreeing, which is what makes the answer a result.
• Measured: stable_partition split the log into 9,393 and 10,607 in one pass, order preserved.
• Every trap this module measured was a decision in this pipeline: 0LL, the adjacent sorts, const& parameters, sort over stable_sort with a reason, and a loop where no algorithm fits.

That completes Module 20, and with it the composable half of the standard library. Module 19 supplied the storage; this module supplied the three pieces that operate on it — iterators describing position, algorithms describing intent, and lambdas supplying the per-element decision — and the recurring finding across all ten chapters was that the library's value is correctness rather than speed. Four separate silent wrong answers were measured here, and only one of them was detectable by any tool on the machine.

Module 21 is Modern C++ Type and Utility Tools, and the frozen blurb describes it as the tools that let a type say more about itself, grouped by the design problem each one removes. Several of them close gaps this module had to work around. constexpr moves computation to compile time, which is where Chapter 20.5's sorted precondition would ideally be checked. Structured bindings — already used here for minmax_element and mismatch — get their proper treatment. std::optional replaces the find-returning-end() convention with a type that cannot be dereferenced unchecked. And concepts, in Chapter 21.8, are the fix for the diagnostic Chapter 20.2 measured at four errors across a hundred and thirty-eight lines, none of them naming a line of your own code.