Mengapa pencarian biner lebih cepat daripada pencarian ternary?

Pencarian array elemen menggunakan pencarian biner, dalam kasus terburuk iterasi karena, pada setiap langkah kita memotong setengah dari ruang pencarian kita. Jika, sebagai gantinya, kami menggunakan 'pencarian ternary', kami akan memotong dua pertiga dari ruang pencarian kami di setiap iterasi, jadi kasus terburuk harus mengambil iterasi ... $N$ $\log_2 N$ $\log_3 N < \log_2 N$

Tampaknya pencarian ternary lebih cepat, jadi mengapa kita menggunakan pencarian biner?

algorithms algorithm-analysis runtime-analysis search-algorithms binary-search The Mean Square
sumber

Tidak bisakah seseorang menggunakan alasan yang sama tentang pencarian Kuarter? Atau bahkan pencarian desimal ... atau apa pun yang lebih besar dari 2.

d'alar'cop

tolong baca tentang B + Trees

arunmoezhi

Pencarian linear sering kali lebih cepat daripada pencarian biner pada masalah kecil-menengah pada perangkat keras modern, karena itu cache-koheren dan hampir semua cabang diprediksi dengan benar.

Nama samaran

Juga 2 * log_3 (N) = log_3 (N ^ 2) jika berbicara dengan intuisi Anda.

PawelP

Mari kita letakkan ini ke dalam istilah intuitif. Jika menggunakan pencarian berbasis 3 lebih cepat karena memotong ruang pencarian lebih banyak pada setiap iterasi, maka bukankah menggunakan pencarian berbasis juta lebih cepat? Tetapi Anda dapat dengan mudah melihat bahwa rata-rata Anda harus melakukan 500.000 cek di dalam setiap iterasi untuk menentukan potongan 1 juta yang berisi target. Jelas, memotong ruang pencarian di setengah setiap iterasi dan tidak lebih, memberi Anda informasi terbanyak dalam satu langkah, andal.

ErikE

Jawaban:

Jika Anda menerapkan pencarian biner, Anda memiliki banyak perbandingan. Jika Anda menerapkan pencarian ternary, Anda memiliki banyak perbandingan, seperti pada setiap langkah, Anda perlu melakukan 2 perbandingan untuk memotong ruang pencarian menjadi tiga bagian. Sekarang jika Anda , Anda dapat mengamati bahwa: Karena kita tahu bahwa , kita benar-benar mendapatkan lebih banyak perbandingan dengan pencarian ternary.

\log_{2} (n) + O (1)

$\log_2(n)+O(1)$

2 \cdot \log_{3} (n) + O (1)

$2 \cdot \log_3(n) + O(1)$

2 \cdot \log_{3} (n) + O (1) = 2 \cdot \frac{\log (2)}{\log (3)} \log_{2} (n) + O (1)

$2 \cdot \log_3(n) + O(1) = 2 \cdot \frac{\log(2)}{\log(3)} \log_2(n)+ O(1)$

2 \cdot \frac{\log (2)}{\log (3)} > 1

$2 \cdot \frac{\log(2)}{\log(3)} > 1$

Ngomong-ngomong: pencarian dapat membuat banyak akal jika perbandingan cukup mahal dan dapat diparalelkan, karena itu, komputer paralel dapat diterapkan. $n$

Perhatikan bahwa argumen dapat digeneralisasikan ke pencarian cukup mudah. Anda hanya perlu menunjukkan bahwa fungsi benar-benar meningkat monoton untuk nilai integer . $n$ $f(k) = (k-1) \cdot \frac{\log(2)}{\log(k)}$ $k$

DCTLib
sumber

Dan LHS adalah linear & RHS adalah logaritmik sehingga tidak akan membantu untuk kuartener atau sesuatu yang lebih dari itu .... Penjelasan Bagus .... Terima kasih

The Mean Square

Hanya demi kelengkapan: perhatikan bahwa ukuran abstrak seperti jumlah perbandingan elemen mungkin atau mungkin tidak mendominasi runtime yang sebenarnya. Secara khusus, Anda mungkin harus mempertimbangkan berapa banyak cache yang Anda lewatkan pada array panjang dengan salah satu pencarian. (Di sini, mereka bertepatan. Saya hanya mencatat ini karena OP bertanya, "mengapa lebih cepat?", Dan menjawab bahwa dengan ukuran abstrak dapat menyesatkan untuk beberapa algoritma.)

Raphael

Dalam pencarian ternary, 1/3 dari waktu Anda hanya perlu 1 perbandingan (lakukan perbandingan lebih rendah: jika di sepertiga lebih rendah, Anda tidak perlu perbandingan kedua). Itu membuat ternary hanya sekitar 5% lebih lambat daripada 25% (di dunia ini kita hanya peduli dengan jumlah perbandingan). Saya tidak yakin bagaimana menggeneralisasikan ini ke n-ary, meskipun saya curiga ini tidak pernah menjadi lebih cepat daripada biner.

Aaron Dufour

@ AaronDufour: Karena seseorang dapat melakukan pencarian kuaterner dengan membandingkan item tengah terlebih dahulu dan kemudian mengabaikan hasil perbandingan lainnya, satu-satunya cara pencarian kuaterner bisa lebih cepat adalah jika tiga perbandingan dapat dilakukan secara paralel lebih murah daripada dua perbandingan dapat dilakukan secara berurutan.

supercat

@ AaronDufour Tapi Anda amortisasi atas elemen untuk mencari, dan tidak jelas bagi saya mengapa itu ok. Dalam kasus terburuk, kedua perbandingan dapat dilakukan pada setiap langkah.

Sasho Nikolov

DCTLib benar, tapi lupakan matematika sebentar.

Dengan logika Anda kemudian, n -ary harus menjadi yang tercepat. Tetapi jika Anda memikirkannya, n -ary sama persis dengan pencarian iterasi reguler (hanya mengulangi daftar 1 per 1, tetapi dalam urutan terbalik). Pertama Anda memilih item terakhir (atau berikutnya ke terakhir) dalam daftar dan membandingkan nilai itu dengan nilai perbandingan Anda. Kemudian Anda menghapus item itu dari daftar Anda, dan kemudian memilih item terakhir di daftar baru, yang merupakan nilai terakhir berikutnya dalam array. Setiap kali, Anda hanya akan menghilangkan 1 nilai pada satu waktu sampai Anda menemukan nilai Anda.

Sebagai gantinya, Anda harus memikirkannya seperti ini - bagaimana cara menghilangkan nilai terbanyak dari daftar setiap iterasi? Dalam pencarian biner, Anda selalu menghilangkan setengah daftar. Dalam pencarian ternary, ada kemungkinan (33.33% peluang, sebenarnya) bahwa Anda dapat menghilangkan 2/3 dari daftar, tetapi ada peluang yang lebih besar (66.66%) bahwa Anda hanya akan menghilangkan 1/3 dari daftar. untuk menghitung O (n), Anda perlu melihat skenario terburuk, yaitu 1/3, kurang dari 1/2. Saat Anda semakin dekat dan semakin dekat dengan n, semakin buruk.

Skenario terburuk tidak hanya akan ditingkatkan dengan pencarian biner, tetapi waktu rata - rata Anda juga akan ditingkatkan. Melihat nilai yang diharapkan (bagian mana dari daftar yang dapat kami hapus secara rata-rata), kami menggunakan rumus ini:

(P_lower) x (bagian yang bisa kita hapus jika lebih rendah) + (P_higher) x (bagian yang bisa kita hapus jika lebih tinggi) = E

Untuk pencarian biner, ini adalah .5x.5 + .5x.5 = .5 (kami selalu menghapus setengah daftar). Untuk pencarian ternary, nilai ini adalah .666x.333 + .333x.666 = 0.44, atau pada setiap langkah, kami kemungkinan hanya akan menghapus 44% dari daftar, menjadikannya kurang efisien daripada pencarian biner, rata-rata. Nilai ini memuncak pada 1/2 (setengah daftar), dan mengurangi semakin dekat Anda ke n (iterasi terbalik) dan 0 (iterasi reguler).

Ok, jadi saya berbohong..ada sedikit matematika yang terlibat, tapi saya harap itu membantu!

dberm22
sumber

Ini jawaban yang bagus.

The_Sympathizer

Ya analisis batas membantu memahami matematika sulit! pencarian berurutan n-ary memiliki biaya yang sama untuk pencarian linear O (n).

shuva

-2

Harap perhatikan argumen perbandingan log (N) vs 2 log (N) didasarkan pada interpretasi naif dari algoritma. Jika saya benar-benar duduk dan menulis ini di x86 assembly, hasilnya akan terbalik. Masalahnya adalah penggunaan bilangan bulat untuk kasus uji yang dikombinasikan dengan kompiler cerdas yang tidak cukup yang tidak dapat menghapus perbandingan yang berlebihan. Coba lagi dengan string dan fungsi perbandingan string yang sesuai, dan kode untuk memanggil fungsi perbandingan sekali per loop dan Anda akan menemukan pencarian ternary lebih cepat lagi.

Joshua
sumber

Tentu saja pencarian ternary akan lebih cepat jika Anda bisa melakukannya dengan hanya satu perbandingan per iterasi. Tapi, tidak masalah apakah string atau integer, Anda tidak bisa.

FrankW

Perbandingan tidak akan mubazir dan masalahnya tidak ada hubungannya dengan kompiler. Untuk membagi ruang pencarian menjadi tiga bagian, Anda perlu 2 perbandingan. Dalam pencarian biner, Anda hanya perlu membandingkan dengan elemen tengah dan Anda kemudian tahu di mana setengah dari ruang pencarian hasilnya terletak. Dengan pencarian ternary, Anda harus membandingkan dengan elemen 1/3 dari jalan melalui daftar DAN yang 2/3 dari jalan melalui daftar. Jenis data apa yang Anda bandingkan atau bahasa apa yang Anda gunakan tidak relevan. Memang, jika item dalam ke-3 ke-1, Anda bisa berhenti setelah 1 perbandingan.

reirab

Pada beberapa platform, pencarian ternary bisa lebih cepat karena memungkinkan CPU lebih banyak waktu untuk mengambil operan dari RAM sebelum membutuhkannya untuk perbandingan. Tapi itu tergantung sepenuhnya pada platform yang digunakan dan latensi dan cache.

jpa

Sungguh - definisi pencarian terner yang salah.

Joshua