Qidiruv algoritmlari va ularni amalga oshirish
Kod yoki dasturiy ta'minotni yozishda siz muqarrar ravishda berilgan ma'lumotlar to'plamida ma'lum bir qiymatni topishingiz kerak bo'lgan vaziyatga duch kelasiz. Ushbu qidiruvni amalga oshirishning bir necha xil usullari mavjud. Men chiziqli va ikkilik qidiruvlarni va chiziqli qidiruv samaradorligini oshirishning yana bir usulini muhokama qilaman. Optimallashtirishga kelsak, har bir usul har xil natijaga ega. Harakatlar orasidagi samaradorlik farqlarini solishtirganda, eng yomon vaziyatga murojaat qilish odatiy holdir, ya'ni agar element funktsiyaning oxirgi bajarilishida topilgan bo'lsa, unumdorlik qanday bo'lishini anglatadi. Chiziqli va ikkilik qidiruvlar uchun biz eng yomon, eng yaxshi va o'rtacha holatlar qanday bo'lishini ko'ramiz.
Chiziqli qidiruv
Chiziqli qidiruv siz topmoqchi bo'lgan elementni topmaguncha, ma'lumotlar to'plamidagi har bir elementni bo'laklab o'tadi. Tartiblangan roʻyxatdagi n indeksidagi x bandini topish uchun elementni topish uchun aynan n qadam kerak boʻladi. Bu O(n) deb ataladi. Kichik ro'yxat uchun bu yaxshi va hech qanday muammo tug'dirmaydi. Misol uchun, agar menda quyidagi ko'rinishdagi massiv bo'lsa: [1, 2, 3, 4, 5, 6, 7] va 5 raqamini topmoqchi bo'lsam, I raqamini topish uchun menga roppa-rosa 5 qadam kerak bo'ladi. qidiryapman. Keling, bu tartiblangan massiv bilan Javascriptda qanday ishlashini ko'rib chiqaylik.
let sortedArr = [ 2, 4, 5, 6, 8, 10, 16, 32 ]
function linearSearch(num){
sortedArr.forEach(function(item, index){
if(item === num){
console.log(`I found ${item} at index ${index}!`)
return
}
})
}
linearSearch(32)
Ishchi misol: https://repl.it/@r_nilon92/sortedLinearSearchExample
Shunday qilib, sortedArr ning har bir elementi uchun biz har bir indeksdagi element funktsiyamizga argument sifatida kiritgan raqamga (son) teng yoki yo'qligini tekshiramiz.
Qidiruvning bu usuli bu kabi kichik massiv uchun juda mos keladi. Biroq, ma'lumotlarning kattaroq ro'yxati uchun, aytaylik, 4,000,000,000 elementni o'z ichiga olgan holda, bu noqulaylik tug'diradi. Eng yomon holatda ishlash (masalan, siz izlayotgan raqam massivning oxirgi elementi yoki hatto mavjud emas!), siz izlayotgan raqamni topish uchun 4 000 000 000 qadam yoki O(n) kerak bo'ladi. . Eng yaxshi holatda, bu aynan bir qadam (agar siz izlayotgan element massivimizdagi birinchi element bo'lsa) yoki O(1) bo'ladi. Ushbu turdagi qidiruv uchun o'rtacha holat O(n). Ko'rib turganingizdek, bu kattaroq ma'lumotlar to'plamini o'z ichiga olgan holatlar uchun eng samarali usul emas. Va dasturchilar sifatida biz doimo ko'proq samaradorlikni qidiramiz.
Ikkilik qidiruv
Ikkilik qidiruv ham juda sodda va tushunarli, ammo uni amalga oshirish uchun chiziqli qidiruvga qaraganda biroz ko'proq mantiq talab etiladi. Ikkilik qidiruv, shuningdek, yarim intervalli qidiruv, logarifmik qidiruv va mening shaxsiy sevimli, ikkilik chop etish sifatida ham tanilgan, ma'lum bir ma'lumotlar to'plamidagi elementni qidirishning ancha samarali usulidir. Yagona kamchilik shundaki, siz ko'rib chiqayotgan ma'lumotlar saralanishi kerak.
Tartiblangan massivdagi elementni topish uchun avval ushbu massivning o'rta nuqtasiga qarashingiz kerak. Agar o'rta nuqta siz topmoqchi bo'lgan raqamdan kattaroq bo'lsa, siz qidiruvni pastki yarmi bilan cheklab, yuqori yarmini bekor qilasiz. Xuddi shunday, agar o'rta nuqta siz izlayotgan raqamdan kamroq bo'lsa, siz qidiruvingizni yuqori yarmi bilan cheklaysiz. Raqam yarmining faqat bittasida mavjud va shuning uchun kompyuter siz izlayotgan raqam tegishli bo'lmagan yarmini tashlab yuboradi. Bu jarayon raqam topilmaguncha takrorlanadi. Kompyuter fanida bu natija O(log N) deb ataladi. Chiziqli va binarda bajarilgan qadamlar orasidagi farqni ko'rish uchun siz qidirmoqchi bo'lgan massivdagi elementlar miqdorining jurnal qiymatini oling. Aytaylik, bizda 8 000 000 000 ta elementdan iborat massiv bor. Buni izlash juda ko'p! Keling, yarmini kesib olaylik. Endi bizda 2.000.000.000 ta element mavjud boʻlib, unda biz xohlagan raqam joylashganini bilamiz. Buyumimizni topish uchun qancha qadamlar ketishini koʻrish uchun log2 8.000.000.000 ning ikkilik logarifmik funksiyasini hisoblashimiz mumkin, bu bizga 32 ni beradi. 32 esa juda koʻp. Raqamni topish uchun qadamlar soni, bu bizning eng yomon holatda chiziqli qidiruvimizdagi 8 000 000 000 dan ancha qisqa. Eng yomon va o'rtacha stsenariylarda siz O(log n) vaqtida x bandini topasiz, eng yaxshi holat esa O(1).
let orderedList = [ 2, 3, 5, 7, 8, 10, 12, 15, 18, 19, 24, 87, 111 ];
function binarySearch(arr, num) {
let lowestNum = 0;
let highestNum = orderedList.length - 1;
let midPoint;
let checkMidpoint;
while(lowestNum <= highestNum) {
midPoint = Math.floor((lowestNum + highestNum) / 2),
// midPoint = arr.length/2
checkMidpoint = arr[midPoint];
if(checkMidpoint === num) {
console.log('I found the number you were looking for at index: ' + midPoint + '! The value is ' + checkMidpoint + "!");
return;
}
if(num < checkMidpoint) {
highestNum = midPoint - 1;
}
else {
lowestNum = midPoint + 1;
}
}
return `I couldn't find ${num} in the list.` ;
}
binarySearch(orderedList,10);
Ishchi misol: https://repl.it/@r_nilon92/Binary-Search-Example
Ikkilik qidiruv ushbu vaziyatda juda yaxshi ishlaydi. Ammo bu faqat ma'lumotlaringiz tartiblangan holatlarda ishlaydi. Ma'lumotlaringiz tartiblanmagan bo'lsa nima bo'ladi?
Chiziqli qidiruvlar yordamida ma'lumotlar to'plamini yanada samaraliroq o'zgartirish
Ko'pincha ma'lumotlarni qidirishda biz bir xil ma'lumotlarni qayta-qayta qidirishni xohlaymiz. Ko'pgina hollarda, bizning qidiruvlarimizning 80% bizning qidiruv maydonimizning 20 foizida joylashgan. Bu 19-asr iqtisodchisi va muhandisi Vilfredo Pareto nomi bilan atalgan Pareto printsipi deb ataladi. Pareto printsipi dastlab daromadlar tengsizligi va taqsimotiga nisbatan qo'llanilgan, ammo u kompyuter fanida optimallashtirish bo'yicha ham o'z o'rnini topdi. Misol uchun, Microsoft o'z dasturiy ta'minotidagi xatolarning 20% 80% ishdan chiqishiga sabab bo'lganini aniqladi.
Agar biz qidiruvlarimizning 80% shunday kichik hududda joylashganligi tamoyilini qabul qilsak, biz ushbu eng keng tarqalgan qidiruvlarni ma'lumotlar to'plamimizning old qismiga ko'chirishimiz mumkin va shu bilan ko'p hollarda qidiruvimizni boshqacha bo'lganidan ancha qisqaroq qilishimiz mumkin. Keling, bir misolni ko'rib chiqaylik.
let unsortedArr = [2, 5, 3, 7, 8, 10, 15, 18, 24, 111, 12, 19, 87];
function linearSearch(num) {
unsortedArr.forEach(function(itemValue, index, array){
if(itemValue === num) {
if(index > 0) {
organizeArr(index, array, index -1);
}
}
});
return unsortedArr;
}
function organizeArr(index, array, indexSwitch) {
var tempCurrentValue = array[index];
//tempCurrentValue stays the same
array[index] = array[indexSwitch];
array[indexSwitch] = tempCurrentValue;
}
console.log("Before Organization: " + unsortedArr);
var first = linearSearch(7);
var second = linearSearch(7);
var third = linearSearch(7);
var fourth = linearSearch(7);
console.log("After Organization: " + fourth);
/*
Before Organization: 2,5,3,7,8,10,15,18,24,111,12,19,87
After Organization: 7,2,5,3,8,10,15,18,24,111,12,19,87
*/
Ishchi misol: https://repl.it/@r_nilon92/LinearSearchWIthOrganization
Vaqt o'tishi bilan ma'lumotlarimizni eng keng tarqalgan qidiruvlarni aks ettirish uchun o'zgartirib, biz o'rtacha ishlashimizni odatdagidan yaxshiroq qilishimiz mumkin.
Xulosa
Xo'sh, qaysi biri yaxshiroq? Chiziqli yoki ikkilikmi? Umuman olganda, biz ishlayotgan ma'lumotlar tartiblanmagan bo'lsa, chiziqli qidiruv algoritmlaridan foydalanishni xohlaymiz. Biz eng ko'p qidiriladigan elementlarni massivning old tomoniga siljitadigan funktsiyani yaratish orqali ushbu jarayonni samaraliroq qilishimiz mumkin. Saralangan massivlar uchun, ayniqsa massiv katta hajmga ega bo'lsa, ikkilik qidiruv algoritmlari ma'qulroq va bajarilishi ancha qisqaroq.
