Back in the day I honed my optimization chops while working on Project Euler problems.

I was dumb and young, and most of the things I tried were pointless, but I did stumble on a technique that I have kept using in the nearly 2 decades since.

Write the slow version first Link to heading

Project Euler problems have the stated intention that all of the prompts should be solvable in less than a minute of computation time with the right algorithm. I don’t know if that’s true for all of them, especially the latest ones, but I took that as a challenge to try to optimize my solutions to fit within that window, or often to just optimize the solution as much as possible.

Usually it was simplest to write a naive solution that would be horrifically slow, with computation time in hours, days, or years. But that slow solution was obviously correct. It was short enough to read and understand pretty easily so I could be confident that is was correct.

This was helped and guided by Project Euler problems usually providing a “checkpoint” solution, an example output from a portion of the problem. For example, a question might be “how many primes are below 1,000,000?” and they’d give the answer for primes below 1,000 so that you could check your algorithm on a smaller input.

What I would often do is write an “obviously correct” solution that solved the example, then do two things:

  1. Start the slow solution running on the full answer. Sometimes this was fast enough.
  2. Write a new version that was actually fast.

While writing the fast version I still had access to the slow version for unit testing and comparison, which was immensely useful for further work.

A recent example Link to heading

A few months ago I got nerd-sniped by a slight variation of this LeetCode problem: Find Median from Data Stream

For a stream of numbers, at each new input print out the XX%-tile number from the already seen inputs.

This problem has an obviously correct solution: you just take all the inputs seen, sort them at every step, and print out the XX percentile. It’s extremely slow, O(N * N log N), but is clearly correct. I placed that obviously correct solution into my unit tests.

fn calculate_percentile<T: Clone>(values: &[T], percentile: usize) -> T {
    let index = (values.len() * percentile) / 100;
    values[index].clone()
}

/// Test helper that inserts a sequence of values into a PercentileTracker and
/// verifies that the calculated percentile matches the expected value at each step.
///
/// # Parameters
/// * `values` - A slice of values to insert
/// * `percentile` - The percentile to track (0-100)
fn insert_and_verify<T>(values: &[T], percentile: usize)
where
    T: Clone + Ord + Debug + PartialEq,
{
    let mut tracker = PercentileTracker::new(percentile);
    let mut test_values = Vec::new();
    for value in values {
        tracker.insert(value.clone());
        test_values.push(value.clone());
        test_values.sort_unstable();
        let expected = calculate_percentile(&test_values, percentile);
        assert_eq!(
            tracker.get_percentile(),
            expected,
            "Failed at insertion {:?}",
            value
        );
    }
}

Performance Results Link to heading

The “classic” solution to this that interviewers look for is using Priority Queues, one for each “side”. These have operations on the order of O(log N), so inserting a full stream of inputs is O(N log N). They usually have poor memory locality characteristics though, so they end up being relatively slow for inputs that don’t fit into CPU cache.

I wrote a more general, O(N) solution for this problem using a bucketing strategy that I named PercentileTracker. You can view my code and more details in the repo https://github.com/arcuru/lib/tree/main/percentiletracker

PercentileTracker is relatively fast, and is able to process ~40 million inputs per second even at input sizes that don’t fit in CPU cache. Here is the estimated time taken to process 400 million 64-bit ints as input, while also outputting the 50th percentile entry at every step.

Performance benchmark showing processing time for 400M inputs

(Bench run using criterion on a Ryzen 9 7900)

With 64-bit input integers, this is an effective throughput of over 300 MB/s. For comparison, the naive approach of sorting the entire dataset at every step would take several hours for this same workload. I’m sure I could tweak the optimized version to get more performance out of it but I’m happy stopping here for now. The focus was on testing out the dynamic bucketing solution rather than micro-optimizations, and I certainly had fun doing that.

Benefits Link to heading

With an obviously correct solution you can write test cases extremely easily. It is not a replacement for unit testing edge cases, but it lets you find edge cases in your algorithm.

An obviously correct solution has several useful benefits while working on an optimized version:

  1. Reference solution for testing edge cases. Run your unit tests against both versions and confirm that they both have the behavior you want. The clarity of the simple solution makes it easy to ensure you have the correct algorithm and edge case behavior.
  2. Enables “fuzz testing” of a solution to find edge cases non-deterministically. Generate valid inputs randomly, feed them to both solutions, and look for differences.
  3. It can serve as documentation. A naive solution can help a future reader of the code understand the problem in more depth.

For example, my PercentileTracker code was unit tested against the obviously correct solution during development. It helped catch some off-by-one errors, and helped find some test cases that I hadn’t considered when writing the code. It also gave me confidence that my code worked at different input percentages and sizes without having to manually code and define edge cases.

It also lets me run more comprehensive tests against small values for pretty cheap:

#[test]
fn test_large_dataset() {
    // Use a seed to make the test deterministic
    let mut rng = ChaCha8Rng::seed_from_u64(42);
    let values = {
        let mut v = Vec::new();
        // Insert enough values to trigger bucket splitting
        for _ in 0..(MAX_BUCKET_SIZE * 4) {
            v.push(rng.random::<i64>());
        }
        v
    };
    // Test at multiple percentiles
    for percentile in [1, 10, 20, 30, 40, 50, 60, 70, 80, 90, 95, 99] {
        insert_and_verify(&values, percentile);
    }
}

Honestly, it just gives me peace of mind that the faster version works without issue. Trading a little extra compute time for safer development and more correctness is a choice I’ll make every time.

Conclusion Link to heading

Writing and using the naive solution is a powerful tool for writing optimized algorithms. Having access to a slow but provably correct solution allows for verification of much more complex code without all the headache of formal proofs.