Top 100 IPs

Quick Start

Just wanna see the code? Open lib.rs for the aforementioned function implementations and top_tracker.rs for the data structure supporting the whole thing.

If you are here for a little more fun, you can checkout the tests and benchmarks. They are as portable as Rust, but we recommend using a 64-bit machine and at least 2 gigabytes of available memory before attempting to run them. Installing rust is left as an exercise to the reader. Then, run the tests with cargo test, or the benchmarks with cargo bench`.

Analysis

First, I concretized and codified the performance critera of request_handled and top100 in the ip-counter tests. Then, I created benchmarks to estimate what kind of algorithmic complexity met the required performance characteristics. With request_handled requiring sub-logarithmic time (to the total number of IPs) and top_100 requiring sub-linear time (to the total number of IPs), one implemention was obvious.

The implementation stores all the IPs in a HashMap and maintains a "de-normalized" vector of the top IPs. Since counts only ever increment, a single round of bubble sort is sufficent to keep it sorted.