ChristopherBiscardi / advent-of-code

236 stars 47 forks source link

Day 06 Mathematically deduce the count instead of iterating entire range #13

Closed dmaahs2017 closed 11 months ago

dmaahs2017 commented 11 months ago

I know it wasn't necessary for the performance of the problem, but an optimization here is to mathematically solve the max speed needed once you find the min speed needed

Benchmarks

Before the optimization

day_06_bench  fastest       │ slowest       │ median        │ mean          │ samples │ iters
├─ part1      374.6 ns      │ 15.12 µs      │ 416.6 ns      │ 583.8 ns      │ 100     │ 100
╰─ part2      15.35 ms      │ 16.65 ms      │ 16.07 ms      │ 16.03 ms      │ 100     │ 100

With the optimization we see a nominal improvement in part 1, but a vast improvement in part 2 where the iterations become quite long and we see an improvement of ~13 ms in all the statistics

├─ part1      374.6 ns      │ 12.33 µs      │ 415.6 ns      │ 521.7 ns      │ 100     │ 100
╰─ part2      1.664 ms      │ 3.084 ms      │ 2.99 ms       │ 2.967 ms      │ 100     │ 100
ChristopherBiscardi commented 11 months ago

nice! I'm going to merge this and then keep both copies side-by-side to show the speedup in the benchmarks.

thanks!