Agar siz men kabi PHP tarafdan kelgan bo’lsangiz, array’ni shuffle() funksiyasi bilan aralashtirib, uning effektivligi yoki qanday ishlashi haqida bosh qotirib o’tirmagan bo’lsangiz kerak. Ba’zi dasturlash tillarida tayyor aralashtirish funksiyalari yo’q, shu sababli funksiyani o’zimiz yozishimizga to’g’ri keladi.
Qanday qilib aralashtirish funksiyasini yozamiz?
Eng oson (va hayolingizga keladigan) yo’li:
- sikl ichida array’dan tasodifiy (random) elementni olish
- uni yangi array’ga qo’shish
- qo’shilgan elementni array’dan o’chirish
- shu tariqa birinchi array’da element qolmaguncha davom etish.
Ok, bu algoritm ishlaydi, ammo birqancha muammosi bor:
- Tasodifiy elementning indeksini tanlashda, indeksning array ichida qolgan-qolmaganiniga e’tibor bermayapti.
- Sikl ishlashi array’da element qolmaguncha davom etadi, lekin time complexity aniq O(n) ga teng bo’lmaydi. Umuman bu algoritmning time complexity’ni topishning imkoni ham yo’q, ya’ni funksiyaning qachon tugashini bilmaysiz. Katta array’larda, tasodifiy indeks tanlashda funksiya doimiy ishlab turadi. Misol uchun 10,000 elementli array’da 3 ta element qolgan bo’lsa, tasodifiy tanlashda element indeksini 0 va 10,000 sonlari orasidan olasiz. Tabiiyki 3 dona qolgan array elementini topish uchun juda ko’p indekslarni generatsiya qilishga majbur bo’lasiz.
- Ma’lumotlar copy array’ga yig’ilyapti. Ortiqcha o’zgaruvchi ishlatmasdan, berilgan arrayning o’zida aralashtirishning iloji yo’qmi?
Moral: yuqoridagi kod bilan tartiblamang.
To’g’ri, tasodifiy elementni tanlashni optimallashtirish mumkin:
Ancha yaxshi. Endi tasodifiy element array’ning faqat qolgan elementlari orasidan tanlanadi. Shuni ortiqcha copy array’siz ham qilish mumkinmi?
Mana shu – Fisher-Yates algoritmi deyiladi.
Array’ning boshi va ohiri ma’lum bo’lgani uchun biz for siklini ishlatib ham yozamiz, va albatta kodni qisqartiramiz:
Algoritm’da time complexity – O(n), space complexity O(1).