Latency Percentiles

A web server logs each request as a line 'METHOD PATH STATUS TIMEms', for example 'GET /api/users 200 87ms'. The endpoint is the method and path together ('GET /api/users'), and TIME is a whole number of milliseconds. Paths contain no spaces.

Write latency_report(lines) that returns a list with one tuple (endpoint, count, p50, p95, p99) per endpoint: how many requests it served and its 50th, 95th and 99th percentile times by the nearest-rank method. Sort the tuples by endpoint. Every request counts, whatever its status.

Nearest rank: sort the endpoint's N times from fastest to slowest and number them from 1. The Pth percentile is the time at position ceil(P * N / 100), that is P * N / 100 rounded up. With 20 times, the 95th percentile is the 19th and the 99th percentile is the 20th.

Examples

lines = [
    'GET /home 200 120ms', 'GET /home 200 80ms', 'POST /login 401 300ms',
    'GET /home 200 95ms', 'GET /home 500 2000ms', 'POST /login 200 250ms',
]
latency_report(lines)
# returns [('GET /home', 4, 95, 2000, 2000), ('POST /login', 2, 250, 300, 300)]

The times for GET /home in order are 80, 95, 120 and 2000. Its 50th percentile is at position ceil(50 * 4 / 100) = 2, which is 95, and its 95th percentile is at position ceil(3.8) = 4.

Constraints

• 0 <= len(lines) <= 200000
• Times from 0 to 100,000 ms.