SPM Sains Komputer: Carian dalam 20,000 Rekod Inventori Koperasi

Carian dalam 20,000 Rekod Inventori Koperasi

Program inventori koperasi sekolah menyimpan 20,000 rekod barang dalam tatasusunan satu dimensi. Kod asal menggunakan carian linear seperti berikut: SET i = 0; SET jumpa = FALSE; WHILE jumpa = FALSE DO: jika inventori[i] = carian maka SET jumpa = TRUE; SET i = i + 1; ENDWHILE. Program berfungsi apabila kod barang yang dicari wujud, tetapi kadangkala terhenti dengan ralat 'index out of range' dan kadangkala tamat tanpa sebarang mesej apabila kod tidak wujud. Rekod disimpan mengikut urutan kemasukan barang, bukan mengikut kod. Setiap kali juruwang mengimbas kod barang, carian dijalankan dan purata carian mengambil masa 0.8 saat, menyebabkan barisan panjang semasa waktu rehat. Pihak koperasi mahu masa carian di bawah 0.05 saat untuk 5,000 imbasan sehari dan enggan menukar format fail data. Seorang pelajar mencadangkan carian binari, manakala seorang lagi mencadangkan penggunaan jadual hash.

1. Terangkan punca dua gejala dalam pseudokod asal dan tulis semula pseudokod yang betul, termasuk pengendalian kes 'tidak dijumpai'.

Read the worked answer

Punca gejala.

Tiada semakan had. Gelung hanya menguji jumpa = FALSE dan tidak pernah menyemak sama ada i masih dalam julat 0 hingga 19,999. Jika kod yang dicari tiada dalam tatasusunan, jumpa kekal FALSE, i terus bertambah hingga 20,000, dan rujukan inventori[20000] berada di luar sempadan tatasusunan. Itulah ralat 'index out of range'.
Tiada mesej apabila gagal. Sebahagian pelaksanaan lain mungkin menamatkan gelung melalui ralat yang ditangkap, atau tidak mencetak apa-apa selepas gelung. Pengguna melihat skrin kosong dan menganggap sistem tergantung, sedangkan carian sudah gagal.
Punca prestasi. Carian linear membandingkan secara purata 10,000 elemen untuk 20,000 rekod. Membandingkan rentetan teks 10,000 kali menjelaskan masa 0.8 saat.

Pseudokod yang dibetulkan.

SET i = 0
SET jumpa = FALSE
SET indeks = -1
WHILE i < 20000 AND jumpa = FALSE DO
    IF inventori[i] = carian THEN
        SET jumpa = TRUE
        SET indeks = i
    ELSE
        SET i = i + 1
    ENDIF
ENDWHILE
IF indeks = -1 THEN
    PAPAR 'Kod barang tidak dijumpai'
ELSE
    PAPAR inventori[indeks]
ENDIF

Nota penting: dalam versi ini i hanya ditambah dalam cabang ELSE supaya indeks elemen yang dijumpai tidak terlebih naik. Syarat i < 20000 mesti diuji dahulu (pintasan) supaya rujukan tatasusunan tidak berlaku apabila i sudah sama dengan 20,000.

2. Bandingkan carian binari dan jadual hash untuk keperluan 5,000 carian sehari ke atas 20,000 rekod, dengan mengambil kira kos menyusun data. Cadangkan pilihan yang paling sesuai.

Read the worked answer

Kiraan carian linear. 5,000 carian × purata 10,000 perbandingan = 50 juta perbandingan sehari. Itu punca masa carian 0.8 saat dan barisan di kaunter.

Carian binari. Selepas data disusun, setiap carian memerlukan paling banyak kira-kira log2(20,000) ≈ 15 perbandingan, jadi 5,000 × 15 = 75,000 perbandingan sehari, penurunan lebih 600 kali ganda. Masalahnya, data asal tidak tersusun mengikut kod barang. Kos menyusun sekali menggunakan isihan gabung ialah n log2 n ≈ 20,000 × 14.3 ≈ 286,000 perbandingan. Titik pulang modal ialah 286,000 ÷ 10,000 = kira-kira 29 carian sahaja. Oleh kerana koperasi melakukan 5,000 carian sehari, kos isihan dibayar balik dalam beberapa saat pertama operasi. Selepas itu, jika barang baharu ditambah, sisipkan pada kedudukan yang betul (kos kira-kira 20,000 pergerakan) dan bukan menyusun semula keseluruhan fail.

Jadual hash. Carian purata O(1), iaitu kira-kira 1–2 kuiri sehari, lebih pantas daripada binari. Namun ia memerlukan memori tambahan untuk tatasusunan hash (biasanya 1.3–2 kali saiz data), fungsi hash yang baik, dan pengendalian perlanggaran. Jika fungsi hash lemah atau semua kod jatuh ke baldi yang sama, prestasi merosot ke O(n) dan menjadi lebih buruk daripada linear. Ia juga tidak menyokong carian julat seperti 'semua barang antara kod A100 hingga A200'.

Cadangan. Pilih carian binari ke atas tatasusunan yang disusun mengikut kod barang, disusun sekali semasa permulaan program atau selepas kemasukan data harian. Ia memenuhi sasaran bawah 0.05 saat, menggunakan memori sedia ada, mengekalkan format fail yang sama, dan masih membenarkan carian julat. Jadual hash hanya wajar jika koperasi beralih kepada struktur data dalam memori berterusan dengan kadar kemas kini yang sangat tinggi.

3. Selain menukar algoritma, nyatakan dua perubahan pada cara data disimpan atau digunakan yang boleh mengurangkan masa carian, dan jelaskan risikonya.

Read the worked answer

Perubahan 1: simpan data dalam fail berindeks atau susunan tetap mengikut kod barang. Jika fail data disimpan mengikut susunan kod, isihan tidak perlu dijalankan setiap kali program dibuka; carian binari boleh digunakan serta-merta dan kos isihan hanya dibayar sekali. Risikonya ialah setiap penambahan barang baharu memerlukan penyisipan di tengah fail, yang boleh merosakkan fail jika proses terhenti separuh jalan. Kawalan: tulis ke fail sementara, kemudian ganti fail asal secara atomik, dan simpan salinan sandaran sebelum penyisipan.

Perubahan 2: cache hasil imbasan terkini atau gunakan kamus dalam memori. Semasa program berjalan, muatkan semua rekod ke dalam struktur kamus (dictionary) dengan kod barang sebagai kunci. Ini memberi carian satu langkah tanpa mengubah format fail cakera. Risikonya ialah penggunaan RAM: 20,000 rekod dengan medan teks mungkin mengambil beberapa megabait, dan kamus menggunakan lebih banyak memori daripada tatasusunan. Jika data dikemas kini oleh dua juruwang serentak, cache boleh menjadi lapuk dan memaparkan harga lama. Kawalan: muat semula cache selepas setiap kemas kini, atau gunakan satu proses pusat yang menguruskan data.

Perubahan 3: elakkan perbandingan teks yang tidak perlu. Bandingkan kod barang sebagai integer atau kod tetap 6 aksara, bukan rentetan panjang dengan huruf besar dan kecil bercampur. Risikonya ialah kehilangan maklumat jika kod sedia ada mengandungi huruf; kawalan ialah menormalkan kod semasa kemasukan dan menyimpan kod asal dalam medan berasingan untuk rujukan.