cp/cp01/bench.cpp

// CP01 bench: your one-pass countPairsWithSum against the brute force, on growing inputs.
// Build and run with   .\run.ps1 -Bench   (after step 9 passes). Do not edit this file.
// Predict the timing table in your notebook BEFORE you run it (CP01, lab step 10).
#include <chrono>
#include <cstdio>
#include <random>
#include <vector>

#include "drills.h"

// Every pair checked: about n * n / 2 additions.
static long long bruteForcePairs(const std::vector<int>& v, int target) {
    long long count = 0;
    for (std::size_t i = 0; i < v.size(); ++i)
        for (std::size_t j = i + 1; j < v.size(); ++j)
            if (static_cast<long long>(v[i]) + v[j] == target) ++count;
    return count;
}

template <class F>
static double secondsFor(F work) {
    auto start = std::chrono::steady_clock::now();
    work();
    return std::chrono::duration<double>(std::chrono::steady_clock::now() - start).count();
}

int main() {
    std::mt19937 rng(2026);
    std::uniform_int_distribution<int> pick(-1000, 1000);
    std::printf("%8s  %14s  %14s  %10s  %s\n", "n", "brute (ms)", "one pass (ms)", "ratio", "answers agree");
    for (int n : {1000, 4000, 16000, 64000}) {
        std::vector<int> v(n);
        for (int& x : v) x = pick(rng);
        long long a = 0, b = 0;
        double tb = secondsFor([&] { a = bruteForcePairs(v, 7); });
        double tf = secondsFor([&] { b = countPairsWithSum(v, 7); });
        std::printf("%8d  %14.2f  %14.2f  %10.0f  %s\n", n, tb * 1e3, tf * 1e3, tb / (tf > 0 ? tf : 1e-9),
                    a == b ? "yes" : "NO");
    }
    return 0;
}