Silabus Pelajaran 54 dari 148 · Kecepatan tanpa cache
Kecepatan tanpa cache

Hitung ulang sekali saja

Kenapa ini penting "Total X antara dua titik" adalah salah satu pertanyaan paling umum dalam kode pelaporan. Menjawab setiap pertanyaan dengan menjumlahkan rentang itu lambat; menyimpan total untuk setiap titik bisa terlalu besar. Ada jalan tengah di antara keduanya.

Toko

A menyimpan 60.000 hari penjualan di toko berbayar, diberikan kepadamu sebagai Tape. Keuangan mengirimkan satu paket berisi 50 pertanyaan sekaligus: "total penjualan dari hari a sampai hari b". Kamu berjalan di worker kecil dengan sedikit memori sisa.

Total berjalan (prefix sum): jumlah dari semua hal sebelum posisi tertentu. Total sebuah window adalah total berjalan di akhirnya dikurangi total berjalan di awalnya.

sales = [5, 1, 4, 2, 8]
# running totals before each position: 0, 5, 6, 10, 12, 20
# window (1, 4) = 12 - 5 = 7
Giliranku

Tulis range_totals(tape, queries). tape adalah Tape penjualan harian (bilangan bulat). queries adalah daftar pasangan (start, end) dengan 0 <= start <= end <= len(tape). Kembalikan daftar dengan total tape[start:end] untuk setiap kueri, sesuai urutan yang diberikan. Budgets: baca pita maksimal satu kali (60,100 bacaan untuk 60,000 hari dan 50 kueri), dan gunakan maksimal 100,000 byte memori kerja saat fungsi kamu berjalan (diukur dengan tracemalloc; total berjalan untuk setiap hari, atau bahkan daftar biasa dari 60,000 nilai, jauh di atas 100,000 byte). Semua pertanyaan datang bersamaan, sebelum kamu membaca data.

Ada masalah di pelajaran ini? Laporkan · Tanya tentang pelajaran ini

Latihan ini akan segera dibuka

Selesaikan pelajaran sebelumnya agar pelajaran ini terbuka. Seluruh kursus ini gratis, tidak butuh akun, dan kamu bisa baca pelajaran ini sekarang.