9-dars: To'plam va lug'at

2-darajaKumush — usullar9–16 darslar

HayotdaMaktab

Yangi o’quvchi keldi va uni ro’yxatga qo’shish kerak. «Bu familiya bizda bormi?» degan savolga sinf rahbari jurnalni varaqlab javob beradi — har safar boshidan. Kompyuterda ham xuddi shu farq bor: varaqlash va bilish ikki boshqa narsa.

Bu darsdan keyin siz

• to’plam va lug’atdagi qidiruv nega deyarli bepul ekanini tushuntirasiz
• in operatorining ro’yxatdagi va to’plamdagi narxini ajratasiz
• O(n²) yechimni to’plam yordamida O(n) ga tushirasiz

Avval qo’lda

Avval qo‘lda

~5 daqiqa·guruh bilan·Qog'oz va sinf ro'yxati

Sinfda ikki kishining tug’ilgan kuni bir xil bo’lishi ehtimoli katta. Buni ikki usulda tekshiring.

Birinchi usul: har o’quvchi qolgan hamma bilan solishtiriladi. Nechta savol berildi? Ikkinchi usul: bitta qog’ozga 1 dan 366 gacha kataklar chizing va har o’quvchi o’z kunini belgilasin — band katakka ikkinchi belgi tushsa, javob topildi.

Nimani sezishingiz kerak

Birinchi usulda 25 kishilik sinf uchun 300 ta savol kerak, ikkinchisida 25 ta belgi. Ikkinchi usul oldindan joy tayyorlab qo’ydi — to’plam aynan shunday ishlaydi.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Nega to’plam tez

hashhash

Qiymatni sonli «manzil»ga aylantiruvchi hisob. To’plam har elementni shu manzil bo’yicha joylashtiradi, shuning uchun uni qidirmasdan topadi.

Ro’yxatda x in royxat yozganingizda Python boshidan oxirigacha yuradi. To’plamda esa x ning manzili darhol hisoblanadi va faqat o’sha joyga qaraladi — ro’yxat uzunligi javob vaqtiga ta’sir qilmaydi.

Hash ichkarida qanday ishlashi Computer Fundamentals 19-darsida ko’rsatilgan. Bu yerda bizga faqat natijasi kerak: qidirish narxi o’zgarmas.

◆Asosiy g'oya

To’plamga faqat o’zgarmaydigan narsalar joylanadi: son, satr, kortej. Ro’yxatni to’plamga qo’sha olmaysiz, chunki uning manzili keyin o’zgarib ketishi mumkin.

Sekin yechim

Masala: ikki sinf kutubxonadan kitob olgan. Ikkala ro’yxatda ham uchraydigan har xil kitoblar nechta?

sekin.pyNusxalash

1birinchi = [3, 8, 3, 12, 5]2ikkinchi = [12, 7, 3, 3]3topilgan = []4for x in birinchi:5  if x in ikkinchi and x not in topilgan:6      topilgan.append(x)7print(len(topilgan))

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1birinchi = [3, 8, 3, 12, 5]2ikkinchi = [12, 7, 3, 3]3topilgan = []4for x in birinchi:5  if x in ikkinchi and x not in topilgan:6      topilgan.append(x)7print(len(topilgan))

Sizning bashoratingizTekshirish

Javobni ko'rish

2

Umumiy kitoblar: 3 va 12. Beshinchi qatorda IKKITA ro'yxat qidiruvi bor — ikkalasi ham butun ro'yxat bo'ylab yuradi.

Nega sekin

Bitta in tekshiruvi ro’yxat uzunligiga proporsional. U tashqi sikl ichida turgani uchun narx ko’paytiriladi: n × m.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 100	n = 5 000	n = 200 000
Ro‘yxatda inn^2	10 000sig‘adi	10⁷sig‘adi	10¹⁰sig‘maydi
To‘plamda inn	100sig‘adi	5 000sig‘adi	200 000sig‘adi

Yashil — yechim o‘tadi. Sariq — chegarada, konstanta va til muhim bo‘lib qoladi. Qizil — bu yechim bilan bormaydi, boshqasini qidiring.

Ikkala ro’yxat ham 200000 gacha bo’lishi mumkin — bu 40 milliard taqqoslash. Kod bir qatorlik va chiroyli ko’rinadi, lekin ichida yashiringan sikl bor.

Tez yechim

Ikkala ro’yxatni to’plamga aylantiramiz va kesishmasini olamiz. Har element bir marta ko’riladi.

tez.pyNusxalash

1birinchi = [3, 8, 3, 12, 5]2ikkinchi = [12, 7, 3, 3]3print(len(set(birinchi) & set(ikkinchi)))

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1birinchi = [3, 8, 3, 12, 5]2ikkinchi = [12, 7, 3, 3]3print(len(set(birinchi) & set(ikkinchi)))

Sizning bashoratingizTekshirish

Javobni ko'rish

2

& — kesishma amali. To'plam takrorlarni o'zi olib tashlaydi, shuning uchun «har xil» sharti alohida ishlanmaydi.

Lug’at esa to’plamdan bir qadam narida: u nafaqat «bormi?», balki «nechta?» degan savolga ham javob beradi.

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1from collections import Counter2kitoblar = [3, 8, 3, 12, 5, 3]3hisob = Counter(kitoblar)4print(hisob[3], hisob[8], hisob[99])

Sizning bashoratingizTekshirish

Javobni ko'rish

3 1 0

Counter yo'q kalit uchun xato bermaydi, nol qaytaradi. Oddiy lug'atda bu KeyError bo'lardi.

Sinab ko’r

Vizualda ikki hisoblagich yonma-yon o’sadi. Ro’yxatniki har qadamda tezlashadi, to’plamniki esa bir tekis qoladi — butun darsning mazmuni shu farqda.

Ro'yxatda qidirish va to'plamda qidirish

Har qadamda ikki hisoblagich qanday o'sishini solishtiring.

Ro'yxatda in tekshiruvi butun ro'yxat bo'ylab yuradi, to'plamda esa hash bir amalda topadi.

Algoritmning har qadami quyidagi ro‘yxatda matn sifatida ham berilgan — vizual faqat shu qadamlarni chizadi, yangi ma’lumot qo‘shmaydi.

1. Beshta tug'ilgan kun. Savol: ikkitasi bir xilmi?
2. 14 yangi. Ro'yxatda qidirish 0 ta solishtirish oldi, to'plamda esa 1 ta.
3. 3 yangi. Ro'yxatda qidirish 1 ta solishtirish oldi, to'plamda esa 1 ta.
4. 27 yangi. Ro'yxatda qidirish 2 ta solishtirish oldi, to'plamda esa 1 ta.
5. 9 yangi. Ro'yxatda qidirish 3 ta solishtirish oldi, to'plamda esa 1 ta.
6. 3 avval uchragan — javob topildi. Ro'yxat 11 amal sarfladi, to'plam 5 ta.
7. Farq kichik ko'rinadi. Lekin ro'yxatning narxi elementlar soni bilan O'SADI, to'plamniki esa o'smaydi — u har doim bitta amal.

kunlar

140312729334

ro'yxatda

to'plamda

amal soni

ro'yxat0to'plam0

Beshta tug'ilgan kun. Savol: ikkitasi bir xilmi?

Amal0

OrqagaO‘ynatishOldinga1/7Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

9 / 40

MasalaRo'yxatda takrorlangan son bormi? n ≤ 200000.

Taklif qilingan yechim

1. 1Bo‘sh korilgan ro‘yxati ochamiz.
2. 2Har element uchun u korilgan ichida bor-yo‘qligini tekshiramiz.
3. 3Bor bo‘lsa — javob «ha», yo‘q bo‘lsa elementni korilgan ga qo‘shamiz.
4. 4Sikl tugasa — javob «yo‘q». Har element bir marta ko‘rilgani uchun yechim O(n).

Bu javobning 4-qismi noto'g'ri. Mantiq to'g'ri, lekin murakkablik bahosi noto'g'ri. korilgan — RO'YXAT, undagi in tekshiruvi butun ro'yxat bo'ylab yuradi. Demak yechim O(n) emas, O(n²). Bitta so'z o'zgartirilsa yetadi: korilgan = set().

Javobning qaysi qismi noto'g'ri? Bosib belgilang.

Javobni ko'rsatish

O’zingizni sinang

1x in royxat va x in toplam narxi qanday farq qiladi?

Javobni ko'rish

Ro’yxatda narx uzunlikka proporsional: eng yomon holatda hamma element ko’riladi. To’plamda esa narx o’zgarmas — element manzili hisoblanadi va faqat o’sha joyga qaraladi.

2Nega ro'yxatni to'plamga element sifatida qo'shib bo'lmaydi?

Javobni ko'rish

To’plam elementning manzilini hisoblab saqlaydi. Ro’yxat keyin o’zgarishi mumkin, ya’ni manzili ham o’zgaradi va element «yo’qolib» qoladi. Shuning uchun faqat o’zgarmas turlar ruxsat etilgan.

3Counter bilan oddiy lug'at orasidagi amaliy farq nima?

Javobni ko'rish

Yo’q kalit so’ralganda Counter nol qaytaradi, oddiy lug’at esa KeyError beradi. Shuning uchun sanash masalalarida Counter kod hajmini kamaytiradi.

4To'plamga o'tish har doim foyda beradimi?

Javobni ko'rish

Yo’q. To’plam tartibni saqlamaydi va indeks bilan murojaat qilishga ruxsat bermaydi. Element o’rni kerak bo’lsa, lug’at ishlatiladi: kalit — qiymat, qiymati — indeks.

52-darsdagi juftliklar masalasi bu dars bilan qanday bog'liq?

Javobni ko'rish

O’sha yerda korilgan lug’ati «kerakli sherik oldin uchraganmi?» savoliga bir amalda javob bergan edi. Nega bu ishlashi aynan shu darsda tushuntirildi.

Masalalar

Masalalar

3 ta

• Distinct NumbersCSES 1621oson

  Bitta qatorlik yechim. Saralab ham bo‘ladi — ikkala usulni ham yozing va vaqtini solishtiring.

• Sum of Two ValuesCSES 1640o'rta

  Har son uchun kerakli sherigini lug‘atdan qidiring. Indekslarni ham saqlang.

• PlaylistCSES 1141o'rta

  Oxirgi uchragan o‘rinni lug‘atda saqlang. Oyna chegarasi shu o‘rindan keyinga suriladi.

Lokal mashq: mashqlar/09-umumiy/ — masala matni, testlar va tekshir.py. Avval sekin.py ni o‘zingiz yozing, keyin tayyorini oching.

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

Sinfdoshlaringizning tug’ilgan oyini yig’ing va qaysi oyda eng ko’p tug’ilgan borligini qog’ozda sanang. Keyin xuddi shuni Counter bilan yozing va ikki javobni solishtiring.

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

09-umumiy masalasini yeching. sekin.py ni n = 200000 li test bilan yurgizishga urinib ko’ring va necha soniyada tugashini (yoki tugamasligini) yozib qo’ying.

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

Lug’atni o’zingiz yasang: 1000 katakli ro’yxat oling, kalitni shu son bo’yicha qoldiqqa aylantiring va bir katakka ikki kalit tushganda nima qilishni o’ylab toping. Keyin n = 100000 da o’z yechimingiz bilan set() ni vaqt bo’yicha solishtiring.

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.

Darsni tugatdim