Chương trình học Bài 136 trên tổng số 148 · Đánh bại Bóng ma của bạn
Đánh bại Bóng ma của bạn

Không sắp xếp: báo cáo độ trễ

Vì sao điều này quan trọng "Sắp xếp nó trước" biến nhiều bài toán thành bài dễ, nên nó trở thành tự động. Một số dữ liệu có hình dạng khiến sắp xếp là đường vòng.

Một dịch vụ ghi lại mỗi yêu cầu mất bao lâu, tính bằng mili giây nguyên. Các yêu cầu hết thời gian chờ ở 10 giây, nên mọi giá trị nằm giữa 0 và 10.000. Mỗi phút, một tác vụ biến khoảng 20.000 giá trị thành các con số trên bảng điều khiển trực: trung vị, phân vị thứ 90 và 99, và giá trị tệ nhất.

Phân vị theo hạng gần nhất (nearest-rank percentile): phân vị thứ p là giá trị nhỏ nhất sao cho ít nhất p% tất cả các giá trị bằng hoặc thấp hơn nó. Với 20 giá trị, phân vị thứ 90 là giá trị nhỏ thứ 18.

Dữ liệu

values = [120, 85, 3000, 95, 110, 90, 100, 105, 80, 130]
# latency_report(values) -> {"p50": 100, "p90": 130, "p99": 3000, "max": 3000}

Trong bài toán này sắp xếp bị cấm, bằng tay hay bằng thư viện. Hãy nhìn vào những gì bạn biết về các giá trị.

Đến lượt bạn

Viết latency_report(values). values là một list không rỗng các số nguyên từ 0 tới 10.000 (khoảng 20.000 số). Trả về {"p50", "p90", "p99", "max"}: các phân vị thứ 50, 90 và 99 theo hạng gần nhất (giá trị nhỏ nhất có ít nhất p% các giá trị bằng hoặc thấp hơn nó) và giá trị lớn nhất. Không thay đổi list. Quy tắc: không sắp xếp: không sorted(), .sort(), bisect.insort, và không nhập heapq hay statistics (chúng sắp xếp hộ bạn).

Bạn thấy vấn đề gì trong bài học này? Hãy báo cáo nó · Hỏi về bài học này

Bài tập này sẽ sớm mở.

Hoàn thành bài học trước đó để mở khóa bài này. Toàn bộ khóa học là miễn phí, không cần tài khoản, và bạn có thể đọc bài học này ngay bây giờ.