Chương trình học Bài 54 trên tổng số 148 · Tốc độ không cần bộ đệm
Tốc độ không cần bộ đệm

Tính trước một lần

Vì sao điều này quan trọng "Tổng của X giữa hai điểm" là một trong những câu hỏi phổ biến nhất trong mã báo cáo. Trả lời mỗi câu bằng cách cộng cả khoảng thì chậm; giữ một tổng cho mọi điểm thì có thể quá lớn. Có một con đường nằm giữa hai cách đó.

Một cửa hàng giữ doanh số 60.000 ngày trên một kho tính tiền theo lượng dùng, được đưa cho bạn dưới dạng một Tape. Bộ phận tài chính gửi một lô 50 câu hỏi cùng lúc: "tổng doanh số từ ngày a tới ngày b". Bạn chạy trên một máy làm việc nhỏ với rất ít bộ nhớ trống.

Tổng chạy (prefix sum): tổng của mọi thứ trước một vị trí. Tổng của một cửa sổ là tổng chạy ở điểm cuối của nó trừ tổng chạy ở điểm đầu của nó.

sales = [5, 1, 4, 2, 8]
# running totals before each position: 0, 5, 6, 10, 12, 20
# window (1, 4) = 12 - 5 = 7
Đến lượt bạn

Viết range_totals(tape, queries). tape là một Tape doanh số hằng ngày (số nguyên). queries là một list các cặp (start, end) với 0 <= start <= end <= len(tape). Trả về một list với tổng của tape[start:end] cho mỗi truy vấn, theo thứ tự đã cho. Ngân sách: đọc tape nhiều nhất một lần (60.100 lần đọc cho 60.000 ngày và 50 truy vấn), và dùng nhiều nhất 100.000 byte bộ nhớ làm việc trong lúc hàm của bạn chạy (đo bằng tracemalloc; một tổng chạy cho mọi ngày, hay thậm chí một list thường 60.000 giá trị, vượt xa 100.000 byte). Các câu hỏi đều tới cùng nhau, trước khi bạn đọc dữ liệu.

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ờ.