IlmHamroh
Python kursi/Malumot tuzilmalari7/18-dars34 daqiqa
Mundarija (22)

6.7-dars: set asoslari — noyob elementlar to'plami

6-QISM — MA'LUMOT TUZILMALARI · 7-dars

1. Kirish va motivatsiya

Ikki savol bilan boshlaymiz.

1. Ro'yxatdagi takrorlarni qanday olib tashlaysiz?

python
sozlar = ["olma", "anor", "olma", "behi", "anor", "olma"]

# ❌ Sekin va uzun
noyob = []
for s in sozlar:
    if s not in noyob:
        noyob.append(s)

# ✅ Bir qator
noyob = set(sozlar)

2. Element ro'yxatda bormi — tekshirish qancha vaqt oladi?

python
import time

katta_royxat = list(range(1_000_000))
katta_toplam = set(katta_royxat)

# Ro'yxatda: O(n) — hamma elementni tekshiradi
999_999 in katta_royxat         # ~15 ms

# To'plamda: O(1) — bitta hisoblash
999_999 in katta_toplam         # ~0.00005 ms

300 000 marta tezroq. Bu — dasturlashdagi eng katta "bir qator o'zgartirish" yutuqlaridan biri.

Lekin to'plamda tuzoqlar ham bor:

python
s = {}
print(type(s))          # dict! ← bo'sh to'plam emas

s = {1, 2, 3}
print(s[0])             # ❌ TypeError — indeks yo'q

s = {[1, 2]}            # ❌ TypeError: unhashable type

s = {3, 1, 2}
print(s)                # {1, 2, 3} ← saralangan? Yo'q, tasodif

Bu darsda:

  • To'plam yaratish va {} tuzog'i
  • Nega in O(1) — hash jadvali
  • Barcha metodlar va ularning murakkabligi
  • Tartibsizlik va uning oqibatlari
  • Element talablari: hashlanish
  • set vs list vs dict — qachon qaysi biri

2. Nazariya — chuqur tushuntirish

2.1. Yaratish va {} tuzog'i

python
s = {1, 2, 3}                   # ✅ to'plam
s = set([1, 2, 3])              # ✅ ro'yxatdan
s = set("abc")                  # ✅ {'a', 'b', 'c'}
s = set()                       # ✅ BO'SH to'plam
s = {x for x in range(3)}       # ✅ to'plam generatori (16-dars)

Bo'sh to'plam — faqat set():

python
s = {}
print(type(s))                  # <class 'dict'>  ← LUG'AT!

s = set()
print(type(s))                  # <class 'set'>   ✅

Sabab: {} sintaksisi lug'at uchun oldin band qilingan (Python 1.x), to'plam esa 2.4 da qo'shilgan. Orqaga moslik buzilmasligi uchun {} lug'at bo'lib qoldi.

Takrorlar avtomatik yo'qoladi:

python
{1, 2, 2, 3, 3, 3}              # {1, 2, 3}
set("mississippi")              # {'m', 'i', 's', 'p'}
len(set([1, 1, 1]))             # 1

set(satr) — belgilarga bo'ladi:

python
set("abc")                      # {'a', 'b', 'c'}
{"abc"}                         # {'abc'}  ← bitta element

Har qanday iterable'dan:

python
set([1, 2])                     # ro'yxat
set((1, 2))                     # tuple
set(range(3))                   # range
set({"a": 1, "b": 2})           # {'a', 'b'}  ← KALITLAR
set({"a": 1}.values())          # {1}

2.2. Nega in O(1) — hash jadvali

To'plam ichkarida hash jadvali (hash table) — lug'at bilan bir xil tuzilma, faqat qiymatlarsiz.

Qanday ishlaydi:

s.add("olma")

1. hash("olma")              →  8934572...  (katta son)
2. 8934572 % jadval_hajmi    →  5           (uyacha indeksi)
3. jadval[5] = "olma"

"olma" in s

1. hash("olma")              →  8934572     (BIR XIL)
2. 8934572 % jadval_hajmi    →  5
3. jadval[5] ni tekshirish   →  topildi ✅

Bitta hisoblash — elementlar soniga bog'liq emas. Shuning uchun O(1).

Sxematik:

Ro'yxat: [olma] [anor] [behi] [uzum] [nok] ...
         ↑ tekshirish: birma-bir, o'rtacha n/2 ta solishtirish

To'plam (hash jadvali):
  0: ─
  1: ─
  2: uzum
  3: ─
  4: nok
  5: olma        ← hash("olma") % 8 = 5  →  darhol shu yerga
  6: anor
  7: behi
         ↑ tekshirish: bitta hisoblash + bitta solishtirish

To'qnashuvlar (collisions):

Ikki element bir xil uyachaga tushsa:

python
hash("a") % 8 == hash("b") % 8      # mumkin

CPython ochiq adreslash (open addressing) ishlatadi — keyingi bo'sh uyachani qidiradi. Yuklanish 2/3 dan oshsa jadval kattalashadi.

Eng yomon holat — O(n):

Barcha element bir uyachaga tushsa. Amalda bu deyarli bo'lmaydi, chunki:

  • CPython hash funksiyalari yaxshi taqsimlaydi
  • Satrlar uchun hash randomizatsiyasi bor (PYTHONHASHSEED) — HashDoS hujumidan himoya

Amaliy natija:

Amal list set
x in s O(n) O(1)
add / append O(1) O(1)
remove O(n) O(1)
Indeks s[0] O(1) yo'q
Tartib

2.3. Element talablari — hashlanish

To'plam elementi hashlanadigan (hashable) bo'lishi kerak.

python
{1, 2, 3}                       # ✅ int
{"a", "b"}                      # ✅ str
{(1, 2), (3, 4)}                # ✅ tuple
{frozenset([1, 2])}             # ✅ frozenset
{None, True, 1.5}               # ✅

{[1, 2]}                        # ❌ TypeError: unhashable type: 'list'
{{1, 2}}                        # ❌ unhashable type: 'set'
{{"a": 1}}                      # ❌ unhashable type: 'dict'

Qoida: o'zgarmas obyektlar hashlanadi, o'zgaruvchanlar — yo'q.

Nega: hash element qiymatidan hisoblanadi. Element o'zgarsa hash ham o'zgaradi, va u jadvalda "yo'qolib qoladi":

python
# Agar ro'yxat hashlansa (tasavvur qiling):
r = [1, 2]
s = {r}                 # hash([1,2]) = 5 → jadval[5]
r.append(3)             # endi hash([1,2,3]) = 9
r in s                  # jadval[9] ga qaraydi → topilmaydi! ❌

Shuning uchun Python o'zgaruvchan obyektlarni hashlashni taqiqlaydi.

Ichma-ich tuzilmalar uchun frozenset yoki tuple:

python
{[1, 2], [3, 4]}                        # ❌
{(1, 2), (3, 4)}                        # ✅
{frozenset([1, 2]), frozenset([3, 4])}  # ✅ (9-dars)

1, 1.0, True — bir xil:

python
{1, 1.0, True}                  # {1}  ← hammasi teng va bir xil hash!
{0, 0.0, False}                 # {0}
{1, "1"}                        # {1, '1'}  ← turli

Sabab: 1 == 1.0 == True va hash(1) == hash(1.0) == hash(True).

Birinchi qo'shilgani qoladi:

python
print({1, True})                # {1}
print({True, 1})                # {True}

2.4. Asosiy metodlar

Qo'shish:

python
s = {1, 2}

s.add(3)                        # bitta element — O(1)
s.update([4, 5])                # ko'p element — O(k)
s.update([6], {7}, "89")        # ko'p iterable
s |= {10}                       # update bilan bir xil

add vs update:

python
s = {1, 2}
s.add([3, 4])                   # ❌ TypeError — ro'yxat hashlanmaydi
s.add((3, 4))                   # ✅ {1, 2, (3, 4)}  — bitta element
s.update([3, 4])                # ✅ {1, 2, 3, 4}    — ikki element
s.update("ab")                  # ✅ {1, 2, 'a', 'b'}  ← satr belgilarga!

Bu — list.append / list.extend bilan bir xil mantiq (6.2-dars).

Mavjud elementni qo'shish — xato emas:

python
s = {1, 2}
s.add(1)                        # ✅ hech narsa o'zgarmaydi
print(s)                        # {1, 2}

O'chirish:

python
s = {1, 2, 3}

s.remove(1)                     # ❌ KeyError agar yo'q bo'lsa
s.discard(99)                   # ✅ yo'q bo'lsa jim turadi
s.pop()                         # ⚠️ TASODIFIY element, bo'sh bo'lsa KeyError
s.clear()                       # hammasini

remove vs discard:

python
s = {1, 2}

s.remove(99)                    # ❌ KeyError: 99
s.discard(99)                   # ✅ hech narsa qilmaydi

set.pop() — ro'yxatdan farqli:

python
r = [1, 2, 3]
r.pop()                         # 3 — OXIRGISI (aniq)

s = {1, 2, 3}
s.pop()                         # ? — TASODIFIY (aniqlanmagan)

To'plamda "oxirgi" tushunchasi yo'q. Amalda hash jadvalidagi birinchi to'la uyacha qaytadi — bu ishga tushirishlar orasida o'zgarishi mumkin.

Nusxa:

python
s2 = s.copy()                   # sayoz nusxa
s2 = set(s)                     # bir xil

Barcha o'zgartiruvchi metodlar None qaytaradi (6.2-dars kelishuvi):

python
natija = s.add(4)               # None
natija = s.update([5])          # None
natija = s.discard(1)           # None

x = s.pop()                     # ✅ element qaytaradi

2.5. Tartibsizlik

To'plamda tartib yo'q — bu amalga oshirish tafsiloti emas, ta'rif.

python
s = {3, 1, 2}
print(s)                        # {1, 2, 3}  ← saralangandek ko'rinadi

Bu tasodif. Kichik butun sonlar uchun hash(n) == n, shuning uchun ular jadvalga tartib bilan tushadi. Boshqa turlar bilan:

python
print({"olma", "anor", "behi"})
# {'behi', 'olma', 'anor'}  ← tasodifiy ko'rinadi

Satrlar uchun tartib har ishga tushirishda o'zgaradi:

bash
$ python -c "print({'a','b','c','d'})"
{'d', 'b', 'a', 'c'}
$ python -c "print({'a','b','c','d'})"
{'a', 'c', 'd', 'b'}

Bu — hash randomizatsiyasi (PEP 456, Python 3.3+). Har jarayon boshlanganda tasodifiy urug' (seed) tanlanadi.

Nega: HashDoS hujumidan himoya. Hujumchi barchasi bir uyachaga tushadigan kalitlar yuborsa, dict/set O(n²) ga tushardi.

O'chirish (faqat testlar uchun):

bash
PYTHONHASHSEED=0 python skript.py

Amaliy oqibatlar:

python
# ❌ To'plam tartibiga tayanmang
birinchi = list(s)[0]           # har safar boshqa bo'lishi mumkin

# ❌ Testda to'plamni ro'yxat bilan solishtirmang
assert list(s) == ["a", "b"]    # nomustaqil

# ✅ To'plam bilan solishtiring
assert s == {"a", "b"}

# ✅ Tartib kerak bo'lsa — saralang
for x in sorted(s):
    ...

Tartibni saqlash kerak bo'lsa:

python
# Takrorlarni olib tashlash + tartib saqlash
noyob = list(dict.fromkeys(royxat))     # ✅ dict 3.7+ tartibni saqlaydi

# yoki
korilgan = set()
noyob = [x for x in royxat if not (x in korilgan or korilgan.add(x))]

Birinchi variant o'qilishi ancha oson.

2.6. Iteratsiya va o'zgartirish

python
s = {1, 2, 3}

for x in s:                     # ✅ tartib aniqlanmagan
    print(x)

len(s)                          # ✅
sum(s), min(s), max(s)          # ✅
sorted(s)                       # ✅ list qaytaradi
list(s), tuple(s)               # ✅

Iteratsiya paytida o'zgartirish — xato:

python
s = {1, 2, 3}
for x in s:
    if x == 2:
        s.remove(x)             # ❌ RuntimeError: Set changed size during iteration

Yechimlar:

python
# 1. Nusxa bo'yicha iteratsiya
for x in s.copy():
    if shart(x):
        s.remove(x)

# 2. Yangi to'plam (idiomatik)
s = {x for x in s if not shart(x)}

# 3. Farq amali
s -= {x for x in s if shart(x)}

To'plamda indeks yo'q:

python
s[0]                            # ❌ TypeError: 'set' object is not subscriptable
s[0:2]                          # ❌

Indeks kerak bo'lsa — list(s) yoki sorted(s).

2.7. Xotira va tezlik

python
import sys

sys.getsizeof(set())            # 216
sys.getsizeof({1})              # 216
sys.getsizeof({1, 2, 3, 4})     # 216
sys.getsizeof(set(range(5)))    # 728

sys.getsizeof([1, 2, 3, 4])     # 88
sys.getsizeof({1, 2, 3, 4})     # 216  ← 2.5x ko'p

To'plam ro'yxatdan ~2-4x ko'p xotira oladi — bo'sh uyachalar kerak (yuklanish 2/3 dan oshmasligi uchun).

Bu — savdo:

list:  kam xotira, sekin `in`     (O(n))
set:   ko'p xotira, tez `in`      (O(1))

Qachon foydali:

Element soni Tekshiruvlar soni Tavsiya
< 10 Har qanday list (farq sezilmaydi)
Har qanday 1 marta list (to'plam qurish O(n))
> 100 Ko'p marta set

Bir marta tekshirish uchun to'plam qurish — isrof:

python
# ❌ To'plam qurish O(n), keyin bitta O(1) tekshiruv
if x in set(katta_royxat):
    ...

# ✅ To'g'ridan-to'g'ri
if x in katta_royxat:
    ...

# ✅ Ko'p tekshiruv bo'lsa — to'plamni bir marta quring
tekshirish = set(katta_royxat)
for x in qidiruvlar:
    if x in tekshirish:
        ...

2.8. set vs list vs dict

list set dict
Tartib (3.7+)
Takrorlar Kalitlar noyob
Indeks Kalit bo'yicha
in O(n) O(1) O(1)
Qo'shish O(1) O(1) O(1)
O'chirish O(n) O(1) O(1)
Element talabi Har qanday Hashlanadigan Kalit hashlanadigan
Xotira (4 element) 88 B 216 B 184 B
Qiymat saqlaydi

Tanlash daraxti:

Kalit → qiymat kerakmi?
├── Ha → dict
└── Yo'q
    ├── Takrorlar kerakmi yoki tartib muhimmi?
    │   ├── Ha → list
    │   └── Yo'q
    │       ├── Tez `in` kerakmi? → set
    │       └── Yo'q → list (soddaroq)

Amaliy misollar:

python
# ✅ set — noyoblik va tez tekshiruv
korilgan_id = set()
ruxsat_etilgan_turlar = {"jpg", "png", "webp"}
tashrif_buyurilgan = {(0, 0), (1, 1)}

# ✅ list — tartib va takrorlar
tarix = ["sahifa1", "sahifa2", "sahifa1"]
ballar = [90, 85, 90]

# ✅ dict — moslik
narxlar = {"non": 5000, "sut": 12000}

3. Tez ma'lumotnoma

Yaratish

python
{1, 2, 3}           to'plam
set()               BO'SH to'plam  ⭐
{}                  ❌ LUG'AT!
set([1, 2])         iterable'dan
set("abc")          {'a','b','c'}
{"abc"}             {'abc'} — bitta element
{x for x in r}      generator

Metodlar

python
s.add(x)            bitta element        O(1)
s.update(it, ...)   ko'p element         O(k)
s.remove(x)         ❌ KeyError agar yo'q  O(1)
s.discard(x)        ✅ jim turadi         O(1)
s.pop()             ⚠️ TASODIFIY element  O(1)
s.clear()           hammasini
s.copy()            sayoz nusxa

x in s              ⭐ O(1)
len(s), min, max, sum, sorted(s)

Element talablari

python
{1, "a", (1,2), None, frozenset([1])}   ✅ hashlanadi
{[1,2]}, {{1,2}}, {{"a":1}}             ❌ unhashable

{1, 1.0, True}  →  {1}      ← teng va bir xil hash

Tartibsizlik

python
{3,1,2} → {1,2,3}       tasodif (hash(n)==n)
{'a','b'}               har ishga tushirishda BOSHQA
    → PYTHONHASHSEED randomizatsiyasi

sorted(s)               tartib kerak bo'lsa
list(dict.fromkeys(r))  takrorsiz + tartib saqlangan ⭐

Qachon set

> 100 element + ko'p marta `in`     → set ⭐
Bir marta tekshirish                → list
Tartib yoki takror kerak            → list
Xotira 2-4x ko'p                    → savdo

4. Batafsil misollar

Misol 1 — Yaratish va asosiy amallar

python
"""To'plam yaratishning barcha usullari va tuzoqlar."""

import sys

print("=== 1. ⚠️ {} tuzog'i ===")

NAMUNALAR = [
    ("{}",              {}),
    ("set()",           set()),
    ("{1}",             {1}),
    ("{1, 2, 3}",       {1, 2, 3}),
    ("set([1, 2])",     set([1, 2])),
    ("set('abc')",      set("abc")),
    ("{'abc'}",         {"abc"}),
    ("set(range(3))",   set(range(3))),
    ("set({'a': 1})",   set({"a": 1})),
    ("{x for x in '112'}", {x for x in "112"}),
]

print(f"  {'Ifoda':<24} {'Turi':<8} {'Qiymat'}")
print("  " + "─" * 52)
for nom, q in NAMUNALAR:
    print(f"  {nom:<24} {type(q).__name__:<8} {q}")

print("""
  ⚠️ {} → LUG'AT, to'plam emas!
     Sabab: {} lug'at uchun oldin band qilingan (Python 1.x),
     to'plam esa 2.4 da qo'shilgan.
""")


print("\n=== 2. Takrorlar avtomatik yo'qoladi ===")

SINOVLAR = [
    ("[1, 2, 2, 3, 3, 3]",      [1, 2, 2, 3, 3, 3]),
    ("'mississippi'",           "mississippi"),
    ("['a', 'A', 'a']",         ["a", "A", "a"]),
    ("[1, 1.0, True]",          [1, 1.0, True]),
    ("[0, 0.0, False]",         [0, 0.0, False]),
    ("[1, '1']",                [1, "1"]),
    ("[(1,2), (1,2), (2,1)]",   [(1, 2), (1, 2), (2, 1)]),
]

print(f"  {'Kirish':<26} {'len':>4} → {'To`plam':<24} {'len':>4}")
print("  " + "─" * 68)
for nom, malumot in SINOVLAR:
    s = set(malumot)
    print(f"  {nom:<26} {len(malumot):>4} → {str(s):<24} {len(s):>4}")

print("""
  ⚠️ 1, 1.0, True — TENG va bir xil hash → bitta element
     Qaysi biri qoladi? BIRINCHI qo'shilgani.
""")
print(f"    {{1, True}} = {{1, True}}")
print(f"    {{True, 1}} = {{True, 1}}")


print("\n=== 3. Element talablari ===")

SINOVLAR = [
    ("1",                   1),
    ("'abc'",               "abc"),
    ("(1, 2)",              (1, 2)),
    ("None",                None),
    ("1.5",                 1.5),
    ("frozenset([1, 2])",   frozenset([1, 2])),
    ("[1, 2]",              [1, 2]),
    ("{1, 2}",              {1, 2}),
    ("{'a': 1}",            {"a": 1}),
    ("(1, [2])",            (1, [2])),
    ("bytearray(b'ab')",    bytearray(b"ab")),
    ("b'ab'",               b"ab"),
]

print(f"  {'Element':<22} {'set ga qo`shish'}")
print("  " + "─" * 60)
for nom, q in SINOVLAR:
    try:
        s = {q}
        natija = f"✅ {s}"
    except TypeError as x:
        natija = f"❌ {x}"
    print(f"  {nom:<22} {natija}")

print("""
  ⭐ Qoida: o'zgarmas → hashlanadi → to'plamga qo'shiladi
""")


print("\n=== 4. Metodlar ===")

s = {1, 2, 3}
print(f"  Boshlang'ich: {s}\n")

AMALLAR = [
    ("s.add(4)",            lambda s: s.add(4)),
    ("s.add(1)",            lambda s: s.add(1)),
    ("s.update([5, 6])",    lambda s: s.update([5, 6])),
    ("s.update('ab')",      lambda s: s.update("ab")),
    ("s.update([7], {8})",  lambda s: s.update([7], {8})),
]

for kod, f in AMALLAR:
    nusxa = s.copy()
    natija = f(nusxa)
    print(f"  {kod:<22} → {sorted(nusxa, key=str)}  (qaytardi: {natija})")

print(f"\n  ⚠️ add vs update:")
n1 = {1, 2}
n1.add((3, 4))
print(f"    s.add((3, 4))       → {n1}    ← BITTA element")
n2 = {1, 2}
n2.update([3, 4])
print(f"    s.update([3, 4])    → {n2}      ← IKKI element")
n3 = {1, 2}
try:
    n3.add([3, 4])
except TypeError as x:
    print(f"    s.add([3, 4])       → ❌ {x}")


print("\n=== 5. O'chirish ===")

s = {1, 2, 3, 4, 5}
print(f"  Boshlang'ich: {s}\n")

nusxa = s.copy()
nusxa.remove(1)
print(f"  s.remove(1)     → {nusxa}")

try:
    nusxa.remove(99)
except KeyError as x:
    print(f"  s.remove(99)    → ❌ KeyError: {x}")

nusxa = s.copy()
nusxa.discard(2)
nusxa.discard(99)
print(f"  s.discard(2)    → {nusxa}")
print(f"  s.discard(99)   → ✅ xato yo'q")

nusxa = s.copy()
olingan = nusxa.pop()
print(f"\n  s.pop()         → {olingan} olindi, qoldi: {nusxa}")
print(f"                     ⚠️ TASODIFIY element!")

try:
    set().pop()
except KeyError as x:
    print(f"  set().pop()     → ❌ KeyError: {x}")

nusxa = s.copy()
nusxa.clear()
print(f"\n  s.clear()       → {nusxa}")


print("\n=== 6. ⚠️ Tartibsizlik ===")

SINOVLAR = [
    ("Kichik butun sonlar",         {5, 3, 1, 4, 2}),
    ("Katta butun sonlar",          {5000, 3000, 1000, 4000}),
    ("Satrlar",                     {"olma", "anor", "behi", "uzum"}),
    ("Aralash",                     {1, "a", 2.5, (3, 4), None}),
]

for nom, s in SINOVLAR:
    print(f"  {nom:<24} {s}")

print("""
  ⚠️ Kichik butun sonlar saralangandek ko'rinadi —
     bu TASODIF: hash(n) == n bo'lgani uchun.

  ⚠️ Satrlar tartibi HAR ISHGA TUSHIRISHDA boshqacha —
     hash randomizatsiyasi (PEP 456, HashDoS himoyasi).
""")

print("  Buni sinash uchun terminalda ikki marta ishga tushiring:")
print("    python -c \"print({'a','b','c','d'})\"")


print("\n=== 7. Xotira ===")

print(f"  {'n':>6} {'list':>9} {'set':>9} {'dict':>9} {'nisbat'}")
print("  " + "─" * 48)

for n in [0, 1, 4, 5, 10, 100, 1000, 10000]:
    r = list(range(n))
    s = set(range(n))
    d = dict.fromkeys(range(n))
    hr, hs, hd = sys.getsizeof(r), sys.getsizeof(s), sys.getsizeof(d)
    print(f"  {n:>6} {hr:>9,} {hs:>9,} {hd:>9,} {hs / max(hr, 1):>7.1f}x")

print("""
  To'plam ~2-4x ko'p xotira oladi — bo'sh uyachalar kerak.
  Bu — tezlik uchun to'lanadigan narx.
""")

Natijaning muhim qismi:

text
=== 1. ⚠️ {} tuzog'i ===
  Ifoda                    Turi     Qiymat
  ────────────────────────────────────────────────────
  {}                       dict     {}
  set()                    set      set()
  set('abc')               set      {'a', 'c', 'b'}
  {'abc'}                  set      {'abc'}
  set({'a': 1})            set      {'a'}

=== 2. Takrorlar avtomatik yo'qoladi ===
  Kirish                      len → To`plam                   len
  ────────────────────────────────────────────────────────────────────
  'mississippi'                11 → {'p', 'm', 's', 'i'}        4
  [1, 1.0, True]                3 → {1}                          1
  [0, 0.0, False]               3 → {0}                          1
  [1, '1']                      2 → {1, '1'}                     2

=== 7. Xotira ===
       n      list       set      dict   nisbat
  ────────────────────────────────────────────────
       4        88       216       224     2.5x
     100       856     8,408     4,688     9.8x
    1000     8,056    32,984    36,952     4.1x

Nima ko'rsatdi: 2.1, 2.3, 2.4, 2.5, 2.7-bo'limlar.

Misol 2 — Nega O(1)

python
"""Hash jadvali va tezlik namoyishi."""

import sys
import time
import random

print("=== 1. `in` tezligi: list vs set ===")

HAJMLAR = [100, 1_000, 10_000, 100_000, 1_000_000]
TEKSHIRUVLAR = 1_000

print(f"  {TEKSHIRUVLAR:,} ta tekshiruv:\n")
print(f"  {'n':>10} {'list':>12} {'set':>12} {'dict':>12} {'set tezligi':>13}")
print("  " + "─" * 64)

for n in HAJMLAR:
    r = list(range(n))
    s = set(r)
    d = dict.fromkeys(r)

    random.seed(1)
    qidiruvlar = [random.randrange(n * 2) for _ in range(TEKSHIRUVLAR)]

    boshlandi = time.perf_counter()
    for q in qidiruvlar:
        _ = q in r
    vaqt_list = time.perf_counter() - boshlandi

    boshlandi = time.perf_counter()
    for q in qidiruvlar:
        _ = q in s
    vaqt_set = time.perf_counter() - boshlandi

    boshlandi = time.perf_counter()
    for q in qidiruvlar:
        _ = q in d
    vaqt_dict = time.perf_counter() - boshlandi

    print(f"  {n:>10,} {vaqt_list * 1000:>10.2f}ms "
          f"{vaqt_set * 1000:>10.2f}ms {vaqt_dict * 1000:>10.2f}ms "
          f"{vaqt_list / vaqt_set:>11,.0f}x")

print("""
  ⭐ list: O(n) — n oshgan sari sekinlashadi
     set:  O(1) — n ga BOG'LIQ EMAS
""")


print("\n=== 2. Hash jadvali qanday ishlaydi ===")


def uyacha_korsat(elementlar, jadval_hajmi=8):
    """Soddalashtirilgan hash jadvali namoyishi."""
    uyachalar = [[] for _ in range(jadval_hajmi)]
    for x in elementlar:
        i = hash(x) % jadval_hajmi
        uyachalar[i].append(x)
    return uyachalar


MEVALAR = ["olma", "anor", "behi", "uzum", "nok"]

print(f"  Elementlar: {MEVALAR}\n")
print(f"  {'Element':<10} {'hash()':>22} {'% 8':>5}")
print("  " + "─" * 42)
for x in MEVALAR:
    h = hash(x)
    print(f"  {x:<10} {h:>22} {h % 8:>5}")

print(f"\n  Jadval (8 uyacha):")
for i, uyacha in enumerate(uyacha_korsat(MEVALAR)):
    belgi = ", ".join(uyacha) if uyacha else "─"
    ogoh = "  ⚠️ TO'QNASHUV" if len(uyacha) > 1 else ""
    print(f"    [{i}] {belgi}{ogoh}")

print("""
  ⭐ Qidirish: hash(x) % 8 → darhol kerakli uyacha.
     Elementlar sonidan qat'i nazar — bitta hisoblash.
""")


print("\n=== 3. To'qnashuvlar ===")


class YomonHash:
    """BARCHA obyekt bir xil hash — eng yomon holat."""

    def __init__(self, q):
        self.q = q

    def __hash__(self):
        return 42                   # ⚠️ hammasi bir xil!

    def __eq__(self, boshqa):
        return isinstance(boshqa, YomonHash) and self.q == boshqa.q


class YaxshiHash:
    def __init__(self, q):
        self.q = q

    def __hash__(self):
        return hash(self.q)

    def __eq__(self, boshqa):
        return isinstance(boshqa, YaxshiHash) and self.q == boshqa.q


N = 2_000

for sinf, nom in [(YaxshiHash, "Yaxshi hash"), (YomonHash, "Yomon hash (hammasi 42)")]:
    obyektlar = [sinf(i) for i in range(N)]

    boshlandi = time.perf_counter()
    s = set(obyektlar)
    qurish = time.perf_counter() - boshlandi

    qidiruvlar = obyektlar[::10]
    boshlandi = time.perf_counter()
    for o in qidiruvlar:
        _ = o in s
    qidirish = time.perf_counter() - boshlandi

    print(f"  {nom:<26} qurish: {qurish * 1000:>8.1f}ms  "
          f"qidirish: {qidirish * 1000:>8.1f}ms")

print("""
  ⚠️ Barcha element bir uyachaga tushsa — to'plam ro'yxatga aylanadi: O(n).

     Bu — HashDoS hujumining asosi. CPython buni
     hash randomizatsiyasi bilan oldini oladi.
""")


print("\n=== 4. Qachon to'plam foydali ===")

print("""  Savol: to'plam qurish O(n). Nechta tekshiruvdan keyin foyda beradi?\n""")

N = 100_000
r = list(range(N))
random.seed(2)

print(f"  Ro'yxat hajmi: {N:,}\n")
print(f"  {'Tekshiruvlar':>13} {'list':>12} {'set (qurish+)':>15} {'Foydalimi'}")
print("  " + "─" * 56)

for k in [1, 5, 10, 50, 100, 1000]:
    qidiruvlar = [random.randrange(N * 2) for _ in range(k)]

    boshlandi = time.perf_counter()
    for q in qidiruvlar:
        _ = q in r
    vaqt_list = time.perf_counter() - boshlandi

    boshlandi = time.perf_counter()
    s = set(r)
    for q in qidiruvlar:
        _ = q in s
    vaqt_set = time.perf_counter() - boshlandi

    foydali = "✅ ha" if vaqt_set < vaqt_list else "❌ yo'q"
    print(f"  {k:>13,} {vaqt_list * 1000:>10.2f}ms "
          f"{vaqt_set * 1000:>13.2f}ms  {foydali}")

print("""
  ⭐ Bir-ikki tekshiruv uchun to'plam qurish — ISROF.
     Ko'p tekshiruv bo'lsa — katta yutuq.
""")


print("\n=== 5. Takrorlarni olib tashlash ===")

N = 200_000
random.seed(3)
MALUMOT = [random.randrange(N // 2) for _ in range(N)]

USULLAR = []

# 1. Sikl + in (❌ O(n²))
boshlandi = time.perf_counter()
noyob = []
for x in MALUMOT[:3000]:            # 100x kam!
    if x not in noyob:
        noyob.append(x)
USULLAR.append(("sikl + `in` (O(n²))", (time.perf_counter() - boshlandi) * 66))

# 2. set (tartib yo'qoladi)
boshlandi = time.perf_counter()
noyob = list(set(MALUMOT))
USULLAR.append(("set(...)", time.perf_counter() - boshlandi))

# 3. dict.fromkeys (tartib saqlanadi) ⭐
boshlandi = time.perf_counter()
noyob = list(dict.fromkeys(MALUMOT))
USULLAR.append(("dict.fromkeys(...) ⭐", time.perf_counter() - boshlandi))

# 4. Ko'rilganlar to'plami
boshlandi = time.perf_counter()
korilgan = set()
noyob = []
for x in MALUMOT:
    if x not in korilgan:
        korilgan.add(x)
        noyob.append(x)
USULLAR.append(("korilgan to'plami", time.perf_counter() - boshlandi))

eng_tez = min(v for _, v in USULLAR)
print(f"  {N:,} elementdan takrorlarni olib tashlash:\n")
print(f"  {'Usul':<26} {'Vaqt':>10} {'Nisbat':>10} {'Tartib'}")
print("  " + "─" * 60)
for nom, vaqt in sorted(USULLAR, key=lambda x: x[1]):
    tartib = "❌" if "set(" in nom else "✅"
    taxmin = "~" if "O(n²)" in nom else " "
    print(f"  {nom:<26} {taxmin}{vaqt * 1000:>8.1f} ms "
          f"{vaqt / eng_tez:>9.1f}x  {tartib}")

print("""
  ⭐ Tartib kerak bo'lsa — dict.fromkeys()
     Tartib kerak bo'lmasa — set()
     Hech qachon — sikl + `in`
""")

Natijaning muhim qismi:

text
=== 1. `in` tezligi: list vs set ===
  1,000 ta tekshiruv:

           n         list          set         dict   set tezligi
  ────────────────────────────────────────────────────────────────
         100       0.42ms       0.05ms       0.05ms           9x
       1,000       3.81ms       0.05ms       0.05ms          76x
      10,000      38.24ms       0.05ms       0.05ms         765x
     100,000     382.10ms       0.05ms       0.05ms       7,642x
   1,000,000   15260.74ms       0.42ms       0.52ms      36,077x

=== 3. To'qnashuvlar ===
  Yaxshi hash                qurish:      1.2ms  qidirish:      0.1ms
  Yomon hash (hammasi 42)    qurish:   1842.3ms  qidirish:    184.2ms

=== 4. Qachon to'plam foydali ===
   Tekshiruvlar         list   set (qurish+)  Foydalimi
  ────────────────────────────────────────────────────────
              1       0.38ms          2.14ms  ❌ yo'q
             10       3.82ms          2.15ms  ✅ ha
          1,000     382.14ms          2.21ms  ✅ ha

Nima ko'rsatdi: 2.2, 2.7-bo'limlar.

Misol 3 — Tartibsizlik va tuzoqlar

python
"""To'plam bilan ishlashdagi keng tarqalgan xatolar."""

import random

print("=== 1. Tartibga tayanish ===")

s = {"olma", "anor", "behi", "uzum"}

print(f"  To'plam: {s}\n")
print("  ❌ Xavfli kod:")
print(f"    list(s)[0]     = {list(s)[0]!r}   ← har ishga tushirishda BOSHQA")
print(f"    s.pop()        = tasodifiy element")
print(f"    next(iter(s))  = {next(iter(s))!r}   ← ham tasodifiy")

print("\n  ✅ Xavfsiz:")
print(f"    sorted(s)[0]   = {sorted(s)[0]!r}   ← aniq")
print(f"    min(s)         = {min(s)!r}   ← aniq")
print(f"    sorted(s)      = {sorted(s)}")

print("""
  ⚠️ Testlarda:
     assert list(s) == ["a", "b"]     ❌ nomustaqil
     assert s == {"a", "b"}           ✅
     assert sorted(s) == ["a", "b"]   ✅
""")


print("\n=== 2. Kichik sonlar aldashi ===")

SINOVLAR = [
    ("Kichik sonlar 1-10",      set(range(1, 11))),
    ("Kichik sonlar aralash",   {7, 2, 9, 4, 1}),
    ("Katta sonlar",            {7000, 2000, 9000, 4000, 1000}),
    ("Manfiy sonlar",           {-3, -1, -2, 0, 1}),
    ("Float",                   {1.5, 0.5, 2.5}),
    ("Satrlar",                 {"e", "b", "a", "d", "c"}),
]

for nom, s in SINOVLAR:
    print(f"  {nom:<24} {s}")

print(f"\n  hash() qiymatlari:")
for x in [1, 5, 100, -1, -2, 1.5, 2.0]:
    print(f"    hash({x!r:>5}) = {hash(x)}")

print("""
  ⭐ Kichik musbat butun sonlar uchun hash(n) == n →
     ular jadvalga tartib bilan tushadi → saralangandek ko'rinadi.

  ⚠️ hash(-1) == -2 — CPython da -1 xato belgisi sifatida band.
""")


print("\n=== 3. Iteratsiya paytida o'zgartirish ===")

s = {1, 2, 3, 4, 5}
print(f"  To'plam: {s}\n")

print("  ❌ Xato:")
try:
    nusxa = s.copy()
    for x in nusxa:
        if x % 2 == 0:
            nusxa.remove(x)
except RuntimeError as x:
    print(f"    for x in s: s.remove(x)  → RuntimeError: {x}")

print("\n  ✅ Uch yechim:")

n1 = s.copy()
for x in n1.copy():
    if x % 2 == 0:
        n1.remove(x)
print(f"    1. for x in s.copy():        → {sorted(n1)}")

n2 = {x for x in s if x % 2 != 0}
print(f"    2. {{x for x in s if ...}}     → {sorted(n2)}")

n3 = s.copy()
n3 -= {x for x in n3 if x % 2 == 0}
print(f"    3. s -= {{x for x in s ...}}   → {sorted(n3)}")


print("\n=== 4. Indeks yo'q ===")

s = {10, 20, 30}
print(f"  To'plam: {s}\n")

AMALLAR = [
    ("s[0]",        lambda: s[0]),
    ("s[0:2]",      lambda: s[0:2]),
    ("s.index(10)", lambda: s.index(10)),
    ("s.sort()",    lambda: s.sort()),
    ("s + {40}",    lambda: s + {40}),
    ("s * 2",       lambda: s * 2),
]

for kod, f in AMALLAR:
    try:
        natija = f"✅ {f()}"
    except (TypeError, AttributeError) as x:
        natija = f"❌ {type(x).__name__}: {x}"
    print(f"  {kod:<14} {natija}")

print("\n  ✅ Muqobillar:")
print(f"    list(s)[0]        → {list(s)[0]}  (tasodifiy)")
print(f"    sorted(s)[0]      → {sorted(s)[0]}  (aniq)")
print(f"    s | {{40}}         → {s | {40}}")
print(f"    sorted(s)         → {sorted(s)}")


print("\n=== 5. add vs update ===")

MANBALAR = [
    ("[3, 4]",      [3, 4]),
    ("(3, 4)",      (3, 4)),
    ("'ab'",        "ab"),
    ("{3, 4}",      {3, 4}),
    ("range(2)",    range(2)),
    ("5",           5),
]

print(f"  {'Manba':<12} {'add(x)':<26} {'update(x)'}")
print("  " + "─" * 60)

for nom, manba in MANBALAR:
    a = {1, 2}
    try:
        a.add(manba)
        add_natija = str(sorted(a, key=str))
    except TypeError:
        add_natija = "❌ unhashable"

    b = {1, 2}
    try:
        b.update(manba)
        upd_natija = str(sorted(b, key=str))
    except TypeError:
        upd_natija = "❌ not iterable"

    print(f"  {nom:<12} {add_natija:<26} {upd_natija}")

print("""
  ⭐ add — BITTA element (hashlanishi kerak)
     update — HAR BIR element (iterable bo'lishi kerak)
""")


print("\n=== 6. remove vs discard vs pop ===")

print(f"  {'Amal':<20} {'Element bor':<22} {'Element yo`q'}")
print("  " + "─" * 62)

for kod in ["s.remove(x)", "s.discard(x)"]:
    natijalar = []
    for x in [1, 99]:
        s = {1, 2, 3}
        try:
            if "remove" in kod:
                s.remove(x)
            else:
                s.discard(x)
            natijalar.append(f"✅ {sorted(s)}")
        except KeyError:
            natijalar.append("❌ KeyError")
    print(f"  {kod:<20} {natijalar[0]:<22} {natijalar[1]}")

print(f"\n  s.pop() — tasodifiy element:")
for _ in range(3):
    s = {"olma", "anor", "behi", "uzum"}
    olingan = s.pop()
    print(f"    pop() → {olingan!r:<8} qoldi: {sorted(s)}")

print("""
  ⚠️ set.pop() — list.pop() dan FARQLI:
     list.pop()  → OXIRGISI (aniq)
     set.pop()   → tasodifiy (tartib yo'q)
""")


print("\n=== 7. 1 == 1.0 == True tuzog'i ===")

SINOVLAR = [
    "{1, 1.0, True}",
    "{0, 0.0, False}",
    "{1, True, 'True'}",
    "{1.0, 1, 2}",
    "{(1,), (1.0,)}",
    "{frozenset([1]), frozenset([1.0])}",
]

for kod in SINOVLAR:
    print(f"  {kod:<38} → {eval(kod)}")

print(f"\n  Sabab:")
for a, b in [(1, 1.0), (1, True), (0, False), (1.0, True)]:
    print(f"    {a!r:<6} == {b!r:<6}  {a == b:<6}  "
          f"hash teng: {hash(a) == hash(b)}")

print("""
  ⚠️ Bu — real muammo:
     ID lar {1, 2, 3} va bayroqlar {True, False} bir to'plamda
     bo'lsa, 1 va True birlashib ketadi.
""")

IDLAR = {1, 2, 3}
BAYROQLAR = {True, False}
print(f"    IDLAR | BAYROQLAR = {IDLAR | BAYROQLAR}")
print(f"    ⚠️ True yo'qoldi — u 1 bilan bir xil!")

Natijaning muhim qismi:

text
=== 4. Indeks yo'q ===
  To'plam: {10, 20, 30}

  s[0]           ❌ TypeError: 'set' object is not subscriptable
  s[0:2]         ❌ TypeError: 'set' object is not subscriptable
  s.index(10)    ❌ AttributeError: 'set' object has no attribute 'index'
  s.sort()       ❌ AttributeError: 'set' object has no attribute 'sort'
  s + {40}       ❌ TypeError: unsupported operand type(s) for +: 'set' and 'set'
  s * 2          ❌ TypeError: unsupported operand type(s) for *: 'set' and 'int'

=== 7. 1 == 1.0 == True tuzog'i ===
  {1, 1.0, True}                         → {1}
  {0, 0.0, False}                        → {0}
  {1, True, 'True'}                      → {'True', 1}
  {(1,), (1.0,)}                         → {(1,)}

    IDLAR | BAYROQLAR = {False, 1, 2, 3}
    ⚠️ True yo'qoldi — u 1 bilan bir xil!

Nima ko'rsatdi: 2.3, 2.4, 2.5, 2.6-bo'limlar.

Misol 4 — Amaliy: matn tahlili va deduplikatsiya

python
"""To'plamning haqiqiy vazifalarda qo'llanishi."""

import re
import time
import random
from collections import Counter

print("=== 1. Matn tahlili ===")

MATN = """
Python — kuchli va oddiy dasturlash tili. Python o'rganish oson,
lekin uning imkoniyatlari juda keng. Dasturlash tili sifatida
Python veb, ma'lumot tahlili va sun'iy intellektda ishlatiladi.
Oddiy sintaksis Python ni yangi boshlovchilar uchun ideal qiladi.
"""

TOXTASH_SOZLARI = {
    "va", "u", "bu", "uchun", "bilan", "lekin", "yoki",
    "ham", "ni", "ning", "da", "dan", "ga", "sifatida",
}


def sozlarga(matn: str) -> list[str]:
    return re.findall(r"[a-zA-Zʻʼ'Ѐ-ӿ]+", matn.lower())


sozlar = sozlarga(MATN)
noyob = set(sozlar)
mazmunli = noyob - TOXTASH_SOZLARI

print(f"  Jami so'zlar:        {len(sozlar)}")
print(f"  Noyob so'zlar:       {len(noyob)}")
print(f"  Takrorlanish:        {len(sozlar) / len(noyob):.2f}x")
print(f"  To'xtash so'zlari:   {len(noyob & TOXTASH_SOZLARI)}")
print(f"  Mazmunli so'zlar:    {len(mazmunli)}")

print(f"\n  Eng ko'p uchraganlar:")
for soz, soni in Counter(s for s in sozlar if s not in TOXTASH_SOZLARI).most_common(5):
    print(f"    {soz:<14} {'█' * soni} {soni}")

print(f"\n  Faqat bir marta uchraganlar ({len([s for s in noyob if sozlar.count(s) == 1])} ta):")
bir_martalik = sorted(s for s in mazmunli if sozlar.count(s) == 1)
print(f"    {', '.join(bir_martalik[:10])}...")


print("\n\n=== 2. Ruxsat tizimi ===")


class Foydalanuvchi:
    def __init__(self, ism: str, rollar: set[str]):
        self.ism = ism
        self.rollar = rollar


ROL_RUXSATLARI = {
    "mehmon":       {"oqish"},
    "foydalanuvchi": {"oqish", "izoh_yozish"},
    "muallif":      {"oqish", "izoh_yozish", "maqola_yozish", "maqola_tahrirlash"},
    "moderator":    {"oqish", "izoh_yozish", "izoh_ochirish", "foydalanuvchi_bloklash"},
    "admin":        {"oqish", "izoh_yozish", "maqola_yozish", "maqola_tahrirlash",
                     "izoh_ochirish", "foydalanuvchi_bloklash", "sozlamalar"},
}


def ruxsatlar(f: Foydalanuvchi) -> set[str]:
    """Barcha rollardan ruxsatlarni birlashtiradi."""
    natija = set()
    for rol in f.rollar:
        natija |= ROL_RUXSATLARI.get(rol, set())
    return natija


def ruxsat_bormi(f: Foydalanuvchi, kerakli: set[str]) -> bool:
    return kerakli <= ruxsatlar(f)          # qism to'plam


FOYDALANUVCHILAR = [
    Foydalanuvchi("Aziz", {"admin"}),
    Foydalanuvchi("Bobur", {"muallif", "moderator"}),
    Foydalanuvchi("Aziza", {"foydalanuvchi"}),
    Foydalanuvchi("Mehmon", {"mehmon"}),
]

TEKSHIRUVLAR = [
    ("Maqola yozish",       {"maqola_yozish"}),
    ("Izoh o'chirish",      {"izoh_ochirish"}),
    ("Sozlamalar",          {"sozlamalar"}),
    ("Yozish + o'chirish",  {"maqola_yozish", "izoh_ochirish"}),
]

sarlavha = f"  {'Foydalanuvchi':<14} {'Ruxsatlar':>10}"
for nom, _ in TEKSHIRUVLAR:
    sarlavha += f" {nom:>20}"
print(sarlavha)
print("  " + "─" * (26 + 21 * len(TEKSHIRUVLAR)))

for f in FOYDALANUVCHILAR:
    qator = f"  {f.ism:<14} {len(ruxsatlar(f)):>10}"
    for _, kerakli in TEKSHIRUVLAR:
        qator += f" {'✅' if ruxsat_bormi(f, kerakli) else '❌':>19}"
    print(qator)

print(f"\n  Bobur ruxsatlari (muallif + moderator):")
for r in sorted(ruxsatlar(FOYDALANUVCHILAR[1])):
    print(f"    • {r}")


print("\n\n=== 3. Deduplikatsiya — email ro'yxati ===")

XOM_EMAILLAR = [
    "Aziz@Mail.uz",
    "aziz@mail.uz",
    "  bobur@mail.uz  ",
    "BOBUR@MAIL.UZ",
    "aziza@mail.uz",
    "aziz@mail.uz",
    "noto'g'ri-email",
    "dilnoza@mail.uz",
    "aziza@Mail.UZ",
    "",
]


def normalla(email: str) -> str | None:
    email = email.strip().lower()
    if not re.fullmatch(r"[\w.+-]+@[\w-]+\.[\w.]+", email):
        return None
    return email


toza = set()
notogri = []
for e in XOM_EMAILLAR:
    n = normalla(e)
    if n is None:
        notogri.append(e)
    else:
        toza.add(n)

print(f"  Xom ro'yxat:     {len(XOM_EMAILLAR)}")
print(f"  Noto'g'ri:       {len(notogri)}  {notogri}")
print(f"  Noyob to'g'ri:   {len(toza)}\n")
for e in sorted(toza):
    print(f"    ✅ {e}")

print("""
  ⭐ Normalizatsiya + to'plam = deduplikatsiya.
     'Aziz@Mail.uz' va 'aziz@mail.uz' bitta odam.
""")


print("\n=== 4. Takrorlarni topish ===")

random.seed(5)
BUYURTMALAR = [f"BUY-{random.randrange(1000, 1100)}" for _ in range(50)]

korilgan = set()
takrorlar = set()
for b in BUYURTMALAR:
    if b in korilgan:
        takrorlar.add(b)
    korilgan.add(b)

print(f"  Jami buyurtmalar:  {len(BUYURTMALAR)}")
print(f"  Noyob raqamlar:    {len(korilgan)}")
print(f"  Takrorlangan:      {len(takrorlar)}")

if takrorlar:
    print(f"\n  Takrorlar (nechta marta):")
    hisob = Counter(BUYURTMALAR)
    for raqam in sorted(takrorlar)[:5]:
        print(f"    {raqam}  ×{hisob[raqam]}")

# Bir o'tishda
print(f"\n  Bir qatorda:")
print(f"    takrorlar = {{x for x in b if b.count(x) > 1}}   ⚠️ O(n²)")
print(f"    takrorlar = {{x for x, n in Counter(b).items() if n > 1}}  ✅ O(n)")


print("\n\n=== 5. Grafik: do'stlar tarmog'i ===")

DOSTLAR = {
    "Aziz":    {"Bobur", "Aziza", "Eldor"},
    "Bobur":   {"Aziz", "Dilnoza"},
    "Aziza":   {"Aziz", "Dilnoza", "Feruza"},
    "Dilnoza": {"Bobur", "Aziza"},
    "Eldor":   {"Aziz", "Feruza"},
    "Feruza":  {"Aziza", "Eldor"},
}


def umumiy_dostlar(a: str, b: str) -> set[str]:
    return DOSTLAR[a] & DOSTLAR[b]


def tavsiya(kim: str) -> set[str]:
    """Do'stlarning do'stlari, o'zi va mavjud do'stlarsiz."""
    natija = set()
    for dost in DOSTLAR[kim]:
        natija |= DOSTLAR[dost]
    return natija - DOSTLAR[kim] - {kim}


print(f"  Tarmoq:")
for kim in sorted(DOSTLAR):
    print(f"    {kim:<10} → {', '.join(sorted(DOSTLAR[kim]))}")

print(f"\n  Umumiy do'stlar:")
for a, b in [("Aziz", "Dilnoza"), ("Aziz", "Feruza"), ("Bobur", "Eldor")]:
    umumiy = umumiy_dostlar(a, b)
    print(f"    {a:<8} + {b:<8} → {sorted(umumiy) if umumiy else 'yo`q'}")

print(f"\n  Tanish bo'lishi mumkin:")
for kim in sorted(DOSTLAR):
    t = tavsiya(kim)
    print(f"    {kim:<10} → {', '.join(sorted(t)) if t else '—'}")

# Simmetriya tekshiruvi
print(f"\n  Tarmoq simmetrikmi:")
xatolar = set()
for a, dostlari in DOSTLAR.items():
    for b in dostlari:
        if a not in DOSTLAR.get(b, set()):
            xatolar.add((a, b))
print(f"    {'✅ ha' if not xatolar else f'❌ {xatolar}'}")


print("\n\n=== 6. Tezlik: real vazifa ===")

N = 500_000
random.seed(7)
BAZA = [f"user{i}" for i in range(N)]
QIDIRUVLAR = [f"user{random.randrange(N * 2)}" for _ in range(10_000)]

boshlandi = time.perf_counter()
topildi_list = sum(1 for q in QIDIRUVLAR if q in BAZA[:5000])
vaqt_list = (time.perf_counter() - boshlandi) * 100

baza_set = set(BAZA)
boshlandi = time.perf_counter()
topildi_set = sum(1 for q in QIDIRUVLAR if q in baza_set)
vaqt_set = time.perf_counter() - boshlandi

print(f"  {N:,} foydalanuvchi bazasi, {len(QIDIRUVLAR):,} ta qidiruv:\n")
print(f"    list bilan:  ~{vaqt_list * 1000:>9,.0f} ms")
print(f"    set bilan:    {vaqt_set * 1000:>9.1f} ms")
print(f"    Tezlik:       {vaqt_list / vaqt_set:>9,.0f}x")
print(f"\n    Topildi: {topildi_set:,} / {len(QIDIRUVLAR):,}")

Natijaning muhim qismi:

text
=== 2. Ruxsat tizimi ===
  Foydalanuvchi   Ruxsatlar        Maqola yozish       Izoh o'chirish
  ─────────────────────────────────────────────────────────────────────
  Aziz                    7                   ✅                   ✅
  Bobur                   6                   ✅                   ✅
  Aziza                   2                   ❌                   ❌
  Mehmon                  1                   ❌                   ❌

=== 5. Grafik: do'stlar tarmog'i ===
  Umumiy do'stlar:
    Aziz     + Dilnoza  → ['Aziza', 'Bobur']
    Aziz     + Feruza   → ['Aziza', 'Eldor']
    Bobur    + Eldor    → ['Aziz']

  Tanish bo'lishi mumkin:
    Aziz       → Dilnoza, Feruza
    Bobur      → Aziza, Eldor

Nima ko'rsatdi: 2.2, 2.4, 2.7-bo'limlar.

5. To'g'ri va noto'g'ri tushunishlar

Noto'g'ri fikr To'g'risi
"{} — bo'sh to'plam" Lug'at. set() kerak
"To'plam saralangan" Tartib yo'q. Kichik sonlar aldaydi
"To'plam tartibi barqaror" Satrlar uchun har ishga tushirishda boshqa
"set.pop() oxirgisini oladi" Tasodifiy element
"in ro'yxatda ham tez" O(n) vs O(1) — millionlab marta farq
"To'plam har doim yaxshiroq" 2-4x ko'p xotira; bir marta tekshiruvga isrof
"Har qanday obyekt qo'shiladi" Faqat hashlanadigan
"{1, True} — ikki element" Bitta: 1 == True
"s.add([1,2]) ishlaydi" unhashable. update yoki tuple

6. Keng tarqalgan xatolar va yechimlari

1. {} bilan bo'sh to'plam

python
s = {}                          # ❌ dict
s = set()                       # ✅

2. Tartibga tayanish

python
birinchi = list(s)[0]           # ❌ nomustaqil
birinchi = min(s)               # ✅
birinchi = sorted(s)[0]         # ✅

3. Iteratsiya paytida o'zgartirish

python
for x in s:
    s.remove(x)                 # ❌ RuntimeError

s = {x for x in s if not shart(x)}      # ✅

4. add o'rniga update

python
s.add([1, 2])                   # ❌ unhashable
s.update([1, 2])                # ✅ ikki element
s.add((1, 2))                   # ✅ bitta element

5. remove — KeyError

python
s.remove(x)                     # ❌ yo'q bo'lsa xato
s.discard(x)                    # ✅

6. Bir marta tekshirish uchun to'plam qurish

python
if x in set(katta_royxat):      # ❌ O(n) qurish
if x in katta_royxat:           # ✅

tekshirish = set(katta_royxat)  # ✅ ko'p tekshiruv bo'lsa
for q in qidiruvlar:
    if q in tekshirish: ...

7. Takrorlarni olib tashlashda tartibni yo'qotish

python
noyob = list(set(royxat))               # ❌ tartib yo'qoladi
noyob = list(dict.fromkeys(royxat))     # ✅ tartib saqlanadi

8. 1 va True aralashuvi

python
IDLAR | BAYROQLAR               # ⚠️ True va 1 birlashadi

# Turlarni aralashtirmang, yoki:
{(type(x).__name__, x) for x in aralash}

7. Integratsiya — bu bilim qayerda kerak bo'ladi

  • 6.8-dars: to'plam amallari — |, &, -, ^
  • 6.9-dars: frozenset — o'zgarmas to'plam
  • 6.10, 6.13-darslar: dict va hash — bir xil tuzilma
  • 6.16-dars: to'plam generatorlari {x for x in ...}
  • 6.5-dars (o'tilgan): tuple hashlanishi
  • 8-qism: __hash__ va __eq__ shartnomasi
  • 15-qism: collections.Counter — sanash bilan

8. Eng yaxshi amaliyotlar

  1. Bo'sh to'plam — set(). {} — lug'at.

  2. Ko'p marta in kerak bo'lsa — to'plamga aylantiring. Bir marta uchun isrof.

  3. Tartibga hech qachon tayanmang. Kerak bo'lsa sorted(s).

  4. Takrorsizlik + tartib = dict.fromkeys(). set() tartibni yo'qotadi.

  5. discard — xavfsiz o'chirish. remove KeyError beradi.

  6. Iteratsiya paytida o'zgartirmang. Yangi to'plam quring: {x for x in s if ...}.

  7. Turlarni aralashtirmang. 1, 1.0, True — bitta element.

  8. Testlarda to'plamni to'plam bilan solishtiring. assert s == {"a"}, list(s) emas.

9. Amaliy topshiriq

Vazifa 1: Natijani bashorat qiling

python
1.  print(type({}))
2.  print(type(set()))
3.  print({1, 2, 2, 3})
4.  print(set("hello"))
5.  print({"hello"})
6.  print({1, 1.0, True})
7.  print({0, False, ""})
8.  print(len({(1,2), (1,2), (2,1)}))
9.  s = {1,2}; print(s.add(3))
10. print(set([1,2]) == {2,1})
11. print(set({"a": 1, "b": 2}))
12. print({1,2} == [1,2])
Javoblar
  1. <class 'dict'>
  2. <class 'set'>
  3. {1, 2, 3}
  4. {'h', 'e', 'l', 'o'} — tartib turlicha
  5. {'hello'} — bitta element
  6. {1} — hammasi teng
  7. {0, ''} — 0 == False, lekin "" != 0
  8. 2
  9. None — add joyida o'zgartiradi
  10. True — tartib muhim emas
  11. {'a', 'b'} — kalitlar
  12. False — turlar farqli

Vazifa 2: Xatolarni tuzating

python
1.  s = {}
2.  birinchi = list(s)[0]
3.  for x in s: s.remove(x)
4.  s.add([1, 2])
5.  s.remove(x)          # x bo'lmasligi mumkin
6.  noyob = list(set(royxat))    # tartib kerak
7.  if x in set(katta_royxat):   # bir marta
8.  assert list(s) == ["a", "b"]
Javoblar
python
1.  s = set()
2.  birinchi = min(s)                        # yoki sorted(s)[0]
3.  s = {x for x in s if not shart(x)}
4.  s.update([1, 2])                         # yoki s.add((1, 2))
5.  s.discard(x)
6.  noyob = list(dict.fromkeys(royxat))
7.  if x in katta_royxat:
8.  assert s == {"a", "b"}

Vazifa 3: Deduplikatsiya vositasi

Funksiyalar yozing:

  1. noyob(it) — takrorsiz ro'yxat, tartib saqlangan
  2. noyob_kalit(it, key) — kalit funksiyasi bo'yicha
  3. takrorlar(it) — faqat takrorlangan elementlar
  4. birmartaliklar(it) — faqat bir marta uchraganlar
  5. guruhlab_takrorlar(it, key) — takrorlanuvchi guruhlar

Har biri O(n) bo'lsin.

Vazifa 4: Matn tahlilchisi

Sinf yozing:

  1. noyob_sozlar — to'plam
  2. bir_martaliklar — hapax legomena
  3. umumiy_sozlar(boshqa) — ikki matnda ham bor
  4. farqli_sozlar(boshqa) — faqat shu matnda
  5. oxshashlik(boshqa) — Jaccard indeksi
  6. To'xtash so'zlari filtri (o'zbekcha)
  7. Apostrof normalizatsiyasi (4.8-dars)

Vazifa 5: Ruxsat tizimi

Kengaytiring (3-misol):

  1. Rollar iyerarxiyasi (admin → moderator → foydalanuvchi)
  2. Alohida ruxsat berish/olib tashlash
  3. Vaqtinchalik ruxsatlar (muddat bilan)
  4. @ruxsat_kerak("maqola_yozish") dekoratori
  5. Ruxsatlar auditi — kim nimaga ega

Vazifa 6: Tezlik tadqiqoti

Dastur yozing:

  1. list, set, dict, sorted list + bisect uchun in tezligi
  2. Turli hajmlarda (10 → 1M) grafik
  3. To'plam qurish narxi qachon qoplanadi
  4. Xotira sarfi bilan solishtirish
  5. frozenset bilan farq bormi

Vazifa 7: O'ylash

Nega set xotirada list dan 2-4x ko'p joy oladi, garchi u kamroq ma'lumot saqlasa ham (tartib yo'q, takror yo'q)?

Javob

Sabab: hash jadvali ataylab bo'sh joy qoldiradi.

1. Yuklanish koeffitsienti (load factor).

Hash jadvali to'lib qolsa, to'qnashuvlar ko'payadi va qidirish O(1) dan O(n) ga siljiy boshlaydi.

Yuklanish 50%:  o'rtacha ~1.5 solishtirish
Yuklanish 66%:  o'rtacha ~2 solishtirish
Yuklanish 90%:  o'rtacha ~5.5 solishtirish
Yuklanish 99%:  o'rtacha ~50 solishtirish

CPython yuklanishni 3/5 (60%) dan past ushlab turadi. Ya'ni 100 element uchun ~167 uyacha kerak.

2. Har uyacha ko'proq joy oladi.

list uyachasi — 8 bayt (bitta ko'rsatkich).

set uyachasi (setentry) — 16 bayt:

c
typedef struct {
    PyObject *key;      // 8 bayt — element
    Py_hash_t hash;     // 8 bayt — KESH QILINGAN hash
} setentry;

Hash keshlanadi, chunki:

  • Jadval kattalashganda qayta hisoblash kerak emas
  • Solishtirishdan oldin hash'larni tekshirish arzonroq

3. Jadval hajmi — 2 ning darajasi.

hash % hajm o'rniga hash & (hajm - 1) ishlatish uchun (bitli AND — bo'lishdan ~10x tez). Shuning uchun jadval 8, 16, 32, 64, 128... o'sadi.

100 element → keyingi mos hajm 256 uyacha (yuklanish 39%).

Hisob:

1000 element:
  list:  56 + 8 × 1000              = 8,056 bayt
  set:   ~200 + 16 × 2048           = ~33,000 bayt   (4.1x)

4. Kichik to'plamlar uchun ichki massiv.

CPython set obyektida 8 ta uyacha ichkarida saqlanadi (smalltable). Shuning uchun bo'sh to'plam ham 216 bayt:

216 = obyekt sarlavhasi (~88) + 8 uyacha × 16 bayt

Bu — kichik to'plamlar uchun qo'shimcha ajratishni oldini oladi.

Savdo tahlili:

list set
Xotira (1000 int) 8 KB 33 KB
in (1000 element) ~3.8 ms/1000 ~0.05 ms/1000

76x tezlik uchun 4x xotira. Deyarli har doim foydali savdo.

Qachon foydali emas:

  • Juda katta ma'lumot + kam tekshiruv (xotira chegarasi)
  • Kichik to'plamlar (< 10 element — list da ham tez)
  • Faqat bir marta o'tish kerak (generator yetarli)

Muqobil: saralangan list + bisect — O(log n) qidirish, list xotirasi bilan. Lekin qo'shish O(n).

Xulosa: to'plam xotirani ataylab isrof qiladi — bu uning tezligining asosi, kamchiligi emas. Bu — informatikadagi klassik "vaqt vs xotira" savdosi, va bu holda vaqt deyarli har doim qimmatroq.

Nimani mustahkamlaydi: 2.2, 2.3, 2.5, 2.7-bo'limlar.

Xulosa

Bu darsda to'plamning asoslarini o'rgandik.

Eng muhim uch fikr:

  1. in — O(1). Bu to'plamning asosiy sababi. Hash jadvali element o'rnini bitta hisoblash bilan topadi, shuning uchun tekshirish elementlar soniga bog'liq emas. Millionlab elementli ro'yxatda bu 60 000x tezlik farqi.

  2. Tartib yo'q, takror yo'q, indeks yo'q. {3, 1, 2} saralangandek ko'rinishi — kichik sonlar uchun hash(n) == n bo'lgani sabab tasodif. Satrlar uchun tartib har ishga tushirishda o'zgaradi.

  3. Elementlar hashlanishi kerak. list, dict, set — hashlanmaydi. tuple, frozenset — hashlanadi. Va 1, 1.0, True bitta element bo'lib qoladi.

Keyingi darsda to'plam amallari ni ko'ramiz: birlashma, kesishma, ayirma va simmetrik ayirma — hamda ular qanday qilib murakkab filtrlashni bir qatorga sig'diradi.

Ulashish:Telegram'da

Izohlar (0)

Izoh yozish uchun kiring.

  • Hozircha izoh yo'q. Birinchi bo'ling!
6.7-dars: set asoslari — noyob elementlar to'plami — IlmHamroh