Saat mencari elemen atau titik penyisipan dalam array yang diurutkan, pada dasarnya ada dua pendekatan: pencarian langsung (elemen demi elemen) atau pencarian biner. Dari kompleksitas waktu O(n) vs O(log(n)) kita tahu bahwa pencarian biner pada akhirnya lebih efisien, namun ini tidak secara otomatis menyiratkan bahwa pencarian biner akan selalu lebih cepat daripada "pencarian normal" .

Oleh karena itu pertanyaan saya adalah: Bisakah pencarian biner secara praktis kurang efisien daripada pencarian "normal" untuk n rendah? Jika ya, dapatkah kita memperkirakan titik di mana pencarian biner akan lebih efisien?

Terima kasih!

2
Raphael Tarita 11 Mei 2021, 16:57

1 menjawab

Jawaban Terbaik

Ya, penelusuran biner bisa dibilang kurang efisien dibandingkan penelusuran "normal" untuk n kecil. Namun, ini sangat sulit untuk memperkirakan titik di mana pencarian biner akan lebih efisien (jika mungkin) karena ini sangat tergantung pada masalah (misalnya tipe data, predikat pencarian), perangkat keras (mis. prosesor, RAM) dan bahkan status dinamis perangkat keras yang digunakan saat penelusuran dilakukan serta data aktual dalam larik yang diurutkan pada sistem modern.

Alasan pertama pencarian biner bisa kurang efisien adalah vektorisasi. Memang, prosesor modern dapat mendukung instruksi SIMD yang bekerja pada vektor yang cukup besar. Dengan demikian, pencarian linier dapat bekerja secara simultan pada banyak item per siklus pemrosesan. Prosesor modern bahkan sering kali dapat mengeksekusi beberapa instruksi SIMD secara paralel per siklus. Sementara pencarian linier sering kali dapat divektorkan secara sepele, itu bukan kasus pencarian biner yang hampir secara inheren berurutan. Perlu diingat bahwa vektorisasi tidak selalu mungkin atau selalu dilakukan secara otomatis oleh kompiler, terutama pada tipe data non-sepele (mis. struktur data komposit, tipe berbasis pointer) atau predikat pencarian non-sepele (Misalnya yang dengan kondisional atau tipuan memori).

Alasan kedua pencarian biner bisa kurang efisien adalah prediktabilitas cabang. Memang, prosesor modern mencoba memprediksi cabang sebelumnya untuk menghindari kemacetan pipa. Jika prediksi ini berhasil, maka cabang dapat diambil dengan sangat cepat, jika tidak, prosesor dapat terhenti selama beberapa siklus (hingga puluhan). Sebuah cabang dapat dengan mudah diprediksi jika selalu benar atau selalu salah. Cabang yang diambil secara acak tidak dapat diprediksi menyebabkan kios. Karena array diurutkan, cabang dalam pencarian linier mudah diprediksi (cabang selalu diambil atau tidak pernah diambil sampai elemen ditemukan), sementara ini jelas tidak berlaku untuk pencarian biner. Akibatnya, kecepatan pencarian bergantung pada item yang dicari, dan data di dalam array yang diurutkan.

Hal yang sama berlaku untuk cache yang hilang dan pengambilan memori: karena latensi RAM sangat besar dibandingkan dengan mengeksekusi instruksi aritmatika, prosesor modern mengandung unit pengambilan awal perangkat keras khusus yang mencoba memprediksi pengambilan memori berikutnya dan pengambilan data sebelumnya untuk menghindari kesalahan cache. Prefetcher baik untuk memprediksi akses memori linier/berdekatan tetapi sangat buruk untuk akses memori acak. Akses memori pencarian linier adalah sepele sedangkan salah satu pencarian biner tampaknya sebagian besar acak untuk banyak prosesor. Kehilangan cache yang terjadi selama pencarian biner pasti akan menyebabkan prosesor terhenti selama banyak siklus. Jika array yang diurutkan sudah dimuat dalam cache, pencarian biner di dalamnya bisa jauh lebih cepat.

Tapi ini tidak cukup: menggunakan instruksi SIMD lebar atau melakukan kesalahan cache dapat memengaruhi frekuensi inti komputasi dan juga kecepatan algoritme. Belum lagi ukuran tipe data juga sangat penting karena throughput memori terbatas dan akses memori bertahap lebih lambat daripada yang berdekatan. Kita juga harus mempertimbangkan kompleksitas tambahan dari pencarian biner dibandingkan dengan pencarian linier (yaitu, seringkali lebih banyak instruksi untuk dieksekusi). Saya kira saya melewatkan beberapa poin penting dalam daftar di atas.


Sebagai seorang programmer, Anda mungkin perlu menentukan ambang batas untuk memilih algoritma mana yang akan digunakan. Jika Anda benar-benar membutuhkannya, solusi terbaik adalah menemukannya secara otomatis menggunakan metode benchmark atau autotuning. Eksperimen praktis menunjukkan bahwa ambang batas berubah selama beberapa dekade terakhir untuk konteks tetap tertentu (tipe data, status cache, dll.), mendukung penelusuran linier (sehingga ambang umumnya meningkat seiring waktu).

Saran pribadi saya adalah untuk tidak menggunakan pencarian biner untuk nilai n lebih kecil dari 256 / data_type_size_in_bytes dengan tipe data sepele/asli pada prosesor arus utama. Saya pikir itu adalah ide yang baik untuk menggunakan pencarian biner ketika n lebih besar dari 1000, atau juga ketika tipe datanya tidak sepele serta ketika predikatnya mahal.

3
Jérôme Richard 11 Mei 2021, 22:05