A monitoring page shows the k fastest requests of the day. The day has tens of thousands of requests, and comparing two response times is the costly step in this system (each one is a lookup in a remote store), so the page must not compare much more than a few times per request.
Write fastest(timings, k). timings is a one-pass stream of Timing objects; each has an id, and two timings can be compared with <, <=, >, >=, == and !=, which compares their response times. The time itself cannot be read. Return a list of the k fastest Timing objects, fastest first; timings with equal times keep the order in which they arrived. If there are fewer than k timings, return all of them in that order.
Every comparison is counted. The tests call fastest_of(fastest, latencies, k), which makes timings with ids 0, 1, 2, ... from a list of times, passes them to your function and returns the ids you picked. It allows 4n + 20k(log2(k) + 2) comparisons for n requests and raises TooManyComparisons beyond that. day_of_requests(n, seed) generates a day of response times.
Examples
Input: fastest_of(fastest, [30, 12, 45, 12, 7, 90], 3)
Output: ([4, 1, 3], True)
Explanation: 7 ms (id 4), then the two 12 ms requests in arrival order.
Input: fastest_of(fastest, [5, 1], 4)
Output: ([1, 0], True)
Constraints
0 <= n <= 60000,1 <= k <= 200.- The budget counts comparisons, not time.
Goals
- Recognise when sorting everything does more work than the question needs
- Select the k smallest items of a stream with `heapq` in about n comparisons
- Keep ties in their original order, and measure work by counting comparisons