Apakah ada studi atau teori di balik menggabungkan pencarian biner dan pencarian interpolasi?

Saya baru saja membaca. Dapatkah algoritma ini dianggap sebagai algoritma Pencarian Biner? dan ingat bahwa beberapa tahun yang lalu saya menulis pengindeks / mencari file log untuk menemukan entri log dalam file teks biasa dengan jendela tanggal / waktu.

Ketika melakukan ini, saya memutuskan untuk mencoba pencarian interpolasi (saya tidak tahu itu namanya, saya agak menemukan ide itu sendiri). Kemudian untuk beberapa alasan saya melanjutkan ide bolak langkah interpolasi dengan langkah-langkah biner split: Pada langkah 0 saya akan interpolasi untuk menentukan titik uji, kemudian langkah 1 saya akan mengambil titik tengah yang tepat dll.

Saya kemudian membandingkan sistem menggunakan pencarian interpolasi murni, pencarian biner murni dan upaya kombinasi saya. Pendekatan bergantian adalah pemenang yang jelas, baik dalam waktu dan jumlah tes yang diperlukan sebelum menemukan serangkaian waktu yang dipilih secara acak.

Terinspirasi oleh pertanyaan yang ditautkan, saya hanya membuat pencarian cepat untuk "pencarian interpolasi bergantian dan pencarian biner" dan tidak menemukan apa pun. Saya juga mencoba "pencarian interpolasi lindung nilai" seperti yang disarankan pada komentar saya pada salah satu jawaban.

Apakah saya menemukan sesuatu yang diketahui? Apakah ada pembenaran teoretis untuk itu lebih cepat untuk jenis data tertentu? File log biasanya besar untuk saat itu (mis. 1-2 GB teks dengan mungkin 10 juta baris untuk dicari), dan penyebaran tanggal / waktu di dalamnya rumit dengan aktivitas yang padat, waktu puncak umum dan waktu tenang. Tes benchmark saya diambil dari distribusi waktu target yang rata untuk ditemukan.

Apakah saya menemukan sesuatu yang diketahui?

Ada berbagai metode, berdasarkan campuran interpolasi-pencarian dan pencarian biner, dengan waktu akses rata-rata kasus (seragam distribusi) dan O ( l o g n ) waktu kasus terburuk (nilai-nilai tidak merata):$O(log\ log\ n)$$O(log\ n)$

• Pencarian introspektif adalah metode Anda (iterasi antara pencarian interpolasi dan pencarian biner). Saya belum detail lebih lanjut.

• Pencarian interpolasi-biner (IBS) oleh N. Santoro, JB Sidney (1985).

  Gagasan umum adalah bahwa pencarian interpolasi hanya berguna ketika array yang dicari lebih besar dari ambang yang diberikan. Ketika segmen pencarian yang dipertimbangkan lebih kecil dari ambang batas yang ditentukan pengguna, pencarian biner diterapkan tanpa syarat. Begitu pula sebaliknya, di atas ambang batas itu, langkah pencarian interpolasi diterapkan, diikuti akhirnya oleh langkah pencarian biner.

  Ini memiliki banyak poin umum dengan pendekatan Anda.

• Pencarian adaptif (AS) oleh Biagio Bonasera, Emilio Ferrara, Giacomo Fiumara, Francesco Pagano, Alessandro Provetti

  Menggunakan kata-kata penulis:

  [Interpolasi-pencarian biner] menemukan solusi serupa yang menggabungkan (tetapi tidak berbaur) bersama-sama interpolasi dan pencarian biner. Meskipun kompleksitas asimptotiknya sama, ada beberapa perbedaan yang nyata.

  [MEMOTONG]

  Oleh karena itu, dimungkinkan untuk menunjukkan bahwa untuk input apa pun AS tidak akan mengambil lebih banyak operasi elementer daripada IBS.

  Algoritme dapat menghabiskan hingga dua kali lipat operasi daripada pencarian interpolasi "sederhana" dengan hati-hati menemukan separuh terbaik dari segmen pencarian, yang pada gilirannya akan berarti bahwa iterasi yang lebih sedikit akan diperlukan untuk menyelesaikan (tetapi Anda memiliki overhead yang lebih besar) .

Menggabungkan dua algoritma untuk mendapatkan yang terbaik dari kedua dunia adalah teknik yang dikenal, meskipun biasanya dinyatakan sebagai menjalankannya dalam "paralel" dan mengembalikan jawaban segera setelah salah satu berakhir.

Meskipun secara teoritis lebih cepat, pencarian interpolasi memiliki dua kelemahan dibandingkan dengan pencarian biner:

• Ini memiliki kinerja kasus terburuk (linier) yang mengerikan

• Overhead komputasi titik tengah agak besar; iterasi pencarian biner adalah ratusan kali lebih cepat daripada iterasi pencarian interpolasi

Saya berharap bahwa pendekatan di mana Anda melakukan pencarian interpolasi sementara kisaran besar dan beralih ke pencarian biner ketika rentang menjadi kecil adalah yang paling efisien. Alangkah baiknya jika Anda bisa mencoba eksperimen ini.

$\log n$$\log \log n$$\log n$$\log \log n$

Saya pikir hasil Anda dapat dijelaskan oleh dua fenomena:

• Menggabungkan dengan pencarian biner memungkinkan Anda untuk menghindari perilaku terburuk

• Efek positif dari beralih ke pencarian biner pada dataset kecil