Jarum dalam tumpukan jerami di ilmu komputer

Cara lambat: periksa semuanya

Jika Anda tidak tahu apa-apa tentang letak jarum, satu-satunya pilihan adalah memeriksa setiap potong jerami sampai menemukannya. Di ilmu komputer ini disebut pencarian linear. Rata-rata Anda memeriksa separuh dari semuanya sebelum berhasil, dan dalam kasus terburuk semuanya. Selalu berhasil, tetapi waktunya bertambah sebanding dengan ukuran tumpukan.

Mengurutkan mengubah segalanya

Sekarang bayangkan jerami tertata berurutan, seperti kata dalam kamus. Metode yang lebih cerdas, pencarian biner, membuka di tengah, memutuskan di separuh mana jawabannya, dan membuang separuh lainnya. Ulangi, dan satu juta item bisa dicari dalam sekitar 20 langkah. Syaratnya, tumpukan harus berurutan lebih dulu, dan tumpukan jerami tidak pernah begitu.

Indeks: curang dengan bersiap lebih dulu

Database dan mesin pencari menghindari masalah ini dengan mengerjakan pekerjaan berat di muka. Mereka membuat indeks, seperti daftar di belakang buku yang memberi tahu di halaman berapa sebuah kata berada. Mencari jadi cepat karena waktunya sudah dihabiskan sebelumnya. Tidak ada indeks untuk tumpukan jerami sungguhan, dan itulah mengapa ungkapan ini ada.

Mengikuti sinyal

Detektor logam berbeda. Ia tidak memberi tahu di mana jarum berada, tetapi apakah Anda makin dekat. Bayangkan sebuah angka yang naik saat Anda mendekat. Anda lalu bisa memakai aturan sederhana: ambil satu langkah, lihat apakah sinyal menguat, dan lanjutkan ke arah yang memperbaikinya. Programmer menyebut salah satu versinya hill climbing (mendaki bukit), dan itu mendasari banyak optimasi praktis.

Di game, sinyal dihitung dari seberapa jauh Anda dari potongan logam terdekat dibandingkan dengan jangkauan detektor. Bunyi makin cepat saat angka itu mendekati 1, jadi telinga Anda yang melakukan pendakian bukit untuk Anda. Lebih lanjut di Cara kerja detektor logam.

Saat sinyal gagal

Hill climbing bisa tersangkut. Jika banyak logam rongsokan di dekat jarum, sinyal terkuat bisa menuntun Anda ke sebuah paku. Game menanganinya dengan memberi detektor level tinggi kemampuan membedakan jarum. Pencarian di dunia nyata menghadapi masalah yang sama dan memakai sensor yang lebih baik atau filter tambahan.

Tumpukan jerami sebagai data

Tumpukan jerami di game itu sendiri adalah struktur data: grid 88 kali 40 kali 88 sel, masing-masing menyimpan angka untuk kepadatan jerami. Menggali berarti mengubah angka, dan chunk berisi 16 sel menjaga pekerjaan tetap kecil. Cara kerjanya ada di Cara kerja tumpukan jerami.