| Task | #5 |
|---|---|
| Position | 27 |
| Score | 14,262 |
| Best Score | 13,143 |
| Points | 0.922 |
Problem Statement
You have a data stream of uint8 numbers in binary representation sending to STDIN.
Try to find the count of elements with the value equals 127 for the shortest time.
Numbers quantity is 250 000 000.
Input Generator
Random Bytes for testing, but u32 distcheck fails for 2048 bins. I think this is ok, in practice I’ve seen z-scores ~1 for the errors I’ve had.
[INFO] u32_dist_check_solution.hpp: p = 0.158429 (256 bins)
[INFO] u32_dist_check_solution.hpp: p = 0.485589 (512 bins)
[INFO] u32_dist_check_solution.hpp: p = 0.309325 (1024 bins)
[INFO] u32_dist_check_solution.hpp: p = 0.0206942 (2048 bins)
Solution Sketch
See Matt Stuchlik’s solution. I didn’t do anything different, mostly because there aren’t many points to be gained. Wanted to try to use my raw profiling tools to profile memory access patterns and conclusively find the best one, but never got around to doing it, because other problems had lower hanging fruit. I might do this sometime now.
Thoughts
Same family of problems as Blue from RGB and Blue from RGBA.