Saya memiliki serangkaian float, diurutkan dari yang terkecil hingga terbesar, dan harus dapat memilih float terdekat yang lebih besar dari atau kurang dari nilai input yang diteruskan. Nilai input ini tidak harus hadir sebagai nilai dalam array.
Pendekatan naif adalah melakukan pencarian linear sederhana melalui array. Itu mungkin terlihat seperti ini:
void FindClosestFloatsInArray( float input, std::vector<float> array,
float *min_out, float *max_out )
{
assert( input >= array[0] && input < array[ array.size()-1 ] );
for( int i = 1; i < array.size(); i++ )
{
if ( array[i] >= input )
{
*min = array[i-1];
*max = array[i];
}
}
}Tapi jelas saat array semakin besar, ini akan menjadi semakin lambat.
Adakah yang punya ide tentang algoritma yang memungkinkan saya menemukan data ini secara lebih optimal? Saya sudah beralih ke pencarian biner, yang agak memperbaiki masalah, tetapi masih jauh lebih lambat dari yang saya inginkan, dan karena saya tidak benar-benar mencari nilai spesifik yang ada dalam array, itu tidak akan pernah dapat mengakhiri dini.
Informasi lebih lanjut: Nilai floating point dalam array tidak harus didistribusikan secara merata (yaitu, array dapat terdiri dari nilai "1.f, 2.f, 3.f, 4.f, 100.f, 1200.f , 1203.f, 1400.f ".
Saya melakukan operasi ini ratusan ribu kali, tetapi saya dapat melakukan sejumlah pra-pemrosesan pada array float, jika itu akan meningkatkan waktu pencarian. Saya benar-benar dapat mengubah menggunakan sesuatu selain vektor untuk menyimpannya, jika itu akan membantu.
sumber
Jawaban:
Kode dalam pertanyaan (pencarian linear), seperti yang Anda tunjukkan dengan benar, akan menjadi lambat untuk array float besar. Secara teknis itu O (n) di mana n adalah jumlah nilai float di array Anda.
Secara umum, yang terbaik yang dapat Anda lakukan untuk menemukan nilai dalam array yang dipesan adalah pencarian pohon rekursif dari beberapa jenis (misalnya pencarian biner), dalam hal ini Anda dapat mencapai waktu pencarian O (log n) dalam jumlah elemen dalam array Anda. O (log n) jauh lebih baik daripada O (n) untuk nilai n yang besar.
Karenanya, pendekatan yang saya sarankan adalah pencarian biner sederhana dari array , yaitu:
Ini adalah algoritma O (log n) yang harusnya cukup cepat untuk hampir semua situasi. Secara intuitif, ini berfungsi dengan mengurangi separuh rentang yang akan dicari pada setiap langkah hingga Anda menemukan nilai yang benar.
Sangat sulit untuk mengalahkan pencarian biner sederhana, jadi jika Anda sudah menerapkan ini dengan benar maka Anda mungkin sudah cukup dekat dengan optimal. Namun, jika Anda mengetahui distribusi data dan / atau memiliki rentang nilai pencarian terbatas (x), masih ada beberapa trik lanjutan lainnya yang dapat Anda coba:
Namun, kecuali Anda berada dalam situasi yang sangat istimewa, saya mungkin akan merekomendasikan tetap dengan pencarian biner sederhana. Alasan:
sumber
Ini tampaknya cukup sederhana:
Lakukan pencarian biner untuk float yang ingin Anda ikat - O (log n) waktu.
Kemudian elemen di sebelah kiri adalah batas bawah, dan elemen di sebelah kanannya adalah batas atas.
sumber
Jawaban yang jelas adalah menyimpan float di pohon . Mendukung operasi 'sebelumnya' dan 'berikutnya' sepele di pohon. Jadi lakukan saja 'berikutnya' pada nilai Anda, dan kemudian lakukan 'sebelumnya' pada nilai yang Anda temukan di langkah pertama.
sumber
Makalah ini ("pencarian sublogaritmik tanpa perkalian") mungkin menarik; bahkan berisi beberapa kode sumber. Untuk keperluan perbandingan, Anda bisa memperlakukan bilangan float sebagai bilangan bulat dengan pola bit yang sama; ini adalah salah satu tujuan desain standar floating point IEEE.
sumber