Dasturchi, frilanser, gik va introvert
Awakening Bangkok – yorug’lik dekoratsiyalarini o’z ichiga olgan festival bo’lib, har yili o’tkazib kelinar ekan. Men faqat bu yilgi festivalni tasodifan (har doimgidek) bilib qoldim va o’tgan shanbada dekoratsiyalarni aylanib chiqdim.
Matn ichida so’z/ibora qidiruv (substring search) algoritmlari bilan tanishib chiqishni boshlaymiz. Qo’yiladigan masala juda oddiy. N uzunlikdagi matn ichidan M uzunlikdagi iborani (pattern) topish kerak bo’lsin. Bunda matn juda katta hajmda, pattern esa juda kichik – bir-ikki so’zdan iborat.
Ushbu maqolada biz ba’zi string amallarini R-way trie ma’lumot tuzilmasida ko’rib o’tamiz.
Ternary search tries (TST, uchlamchi qidiruv trie) R-way tries’dagi kamchilikka yechim o’laroq tavsiya etiladi. TSTda belgilar indeks ko’rinishida emas, node ichida saqlanadi (R-way tries’da belgilar indeks nomer sifatida saqlanardi). Shuningdek har bir node uch child’ga ega: kichikroq (chap), teng (o’rtada), kattaroq (o’ngda).
Ushbu mavzu string key’lar qidiruvi uchun mo’ljallangan ma’lumotlar tuzilmasi – tries (trays) haqida bo’ladi. Shu vaqtgacha ko’rib o’tgan ma’lumotlar tuzilmalaridan qidiruv uchun eng yaxshisi red-black tree – key’ni qidirish / qo’shish / o’chirish uchun O(log N) vaqtni kafolatlardi.
Bizga N belgiga ega matndan so’zni qidirib, barcha so’zlarni topish kerak bo’lsin. To’g’ri, so’zni topadigan tayyor sub-string funksiyalar allaqachon mavjud. Ammo texnik intervyu jarayonida qo’yiladigan masalada tayyor funksiyadan foydalanmaslik kerak bo’ladi. Bunda odatiy yechim – brute-force algoritmi yordamida matndagi barcha belgilar solishtirib chiqiladi. Ishlash vaqti – O(N2), tezkor yechim emas.
Dijkstra’ning 3-way partitioning quicksort algoritmi bilan tanishib chiqqan bo’lsangiz kerak. U quicksort’dagi bir xil key’lar uchragan holatida ishlash vaqti ortishini oldini oladi. Biz 3-way quicksort’ga qaytamiz, bu safar bo’luvchi element – pivot’ni key belgilaridan olamiz.
LSD Radix sort’da string key’larni o’ngdan chapga tartiblab borgan edik. Albatta, chapdan o’ngga ham tartiblab borishning ham imkoni bor. Buning uchun ro’yhatdagi key’larning bosh harfi (belgisi) bo’yicha tartiblaymiz (Key indexed counting).
Biz o’tgan maqolada ko’rib o’tganimiz – key indexed counting tartiblash boshqa algoritmlar uchun asos bo’lib xizmat qiladi. Shu jumladan, LSD (Least Significant Digit) radix sort algoritmi key indexed counting usulini bir xil uzunlikdagi tartiblanadigan string yoki integer qiymatlarning har bir belgisiga qo’llaydi.
Key indeksli sanoq (bundan keyin Key indexed counting, KIC) bizga unikal bo’lmagan key’ga ega ro’yhatlarni tartiblash uchun asqotishi bois, dastlab biz tartiblash algoritmlari haqida eslab olamiz.