Dictionary (yoki Symbol table)

Dictionary ma’lumot tuzilmasi haqida eshitmagan bo’lishingiz mumkin, lekin dasturlash jarayonida ko’p foydalanganingiz aniq. Dictionary’ga misol qilib Javascriptda object’lar, yoki PHP’da assotsiativ array’lar, Python’da Map’ni keltirish mumkin.

Dictionary (yoki Symbol table) – obyektlar guruhini o’zida jamlagan ma’lumot tuzilmasi. Unda o’zaro bog’langan kalit (key) va qiymat (value) guruhi saqlanadi. Dictionary’dan ma’lumotni key’ni ko’rsatgan holda olinadi.

Masalan:

const cars = {
  'Mercedes': 'S223',
  'BMW': 'X7',
  'Mazda': 'CX-30'
}

cars ichidan Mazda modelini chaqirish uchun

cars['Mazda'] // CX-30

Dictionary’ning effektivligini tushuntirish uchun intervyuda beriladigan oddiy savollardan birini ko’rib chiqamiz.

Masala: Matn ichidan berilgan so’zdagi harflar borligini tekshiring.

const stringA = "Hello"
const stringB = "Goodbye"

Odatiy yechim – ikki sikl ichida har bir so’zning harflarini solishtirib chiqish bo’ladi. Bu metodning nomini Brute Force deyiladi.

Hm… Yechim bor, lekin Brute Force samarali emas. Time complexity – O(N2). Ikki katta matnni solishtirishda esa, mos keladigan harflar vaqtliroq uchrashini umid qilib o’tirasiz. Aks holda dasturning ishlashi uzoq vaqt oladi.

Endi dictionary’dan foydalangan holda masalani ishlaymiz. Bunda stringA’ni dictionary’ga yig’amiz.

Brute Force bilan taqqoslaganda, dictionary’ yordamida ishlash qanday afzallik berdi?

  • Time complexity – O(N) ga tushdi.
  • Dictionary’da faqat unikal harflar yig’ildi.

Kod

Boshqa ma’lumotlar tuzilmasi kabi Dictionary uchun ham biz API yozishimiz mumkin edi, ammo Javascript bu safar o’zining tayyor funksiyalari bilan ishimizni yengillashtiradi.

Map – key/value birikmalarini o’zida saqlovchi tuzilma (dictionary ta’rifi Map uchun mos tushadi). Map’ning object’dan farqi – Map’ga ma’lumot saqlashda key’ni istalgan ko’rinishda bersa bo’ladi, hatto key uchun object bersa ham.

Uning metodlari:

Map’dan foydalanib endi yuqoridagi masalani boshqatdan yozamiz.

Ok, bitta qismi yoqmayapti:

dictionary.set(stringA[i], stringA[i]);

Qiymat berilishi ortiqchalik qilyapti. Unikal key’larning o’zini saqlashning imkoni bormi?

Bor, lekin u holatda dictionary bo’lmay qoladi. Biz Javascriptning Set klassidan foydalanamiz.

Set – faqat unikal qiymatlarni o’zida saqlovchi tuzilma.

Endi yuqoridagi masalani Set bo’yicha yozib, biroz optimallashtiramiz.

stringB’ni ham Set’ga yig’ishimiz mumkin, shunda iteratsiya qadamlari keskin kamayadi. Qisqargan kod:

Bo’ldi. Yana nimani qisqartirish mumkin?.. 😀