Python kursi/Standart kutubxona7/16-dars23 daqiqa

Mundarija (20)

15.7-dars: `collections`: `deque`, `OrderedDict`

15-QISM — STANDART KUTUBXONA · 7-dars

1. Kirish va motivatsiya

list — Python'ning eng universal konteyneri. Lekin u bitta amalda juda yomon: boshidan qo'shish va olish. list.pop(0) va list.insert(0, x) barcha elementlarni bir qadam siljitadi — O(n).

Real vaziyat. Bildirishnomalar xizmati navbatni oddiy ro'yxatda saqlardi:

python

navbat.append(xabar)      # oxiriga
xabar = navbat.pop(0)     # boshidan

Kuniga bir necha ming xabarda hammasi yaxshi edi. Aksiya kuni navbatda yarim million xabar to'plandi va har bir pop(0) yarim million elementni siljita boshladi. Ishchilar protsessorni 100% band qildi, navbat esa kamaymadi — o'sishda davom etdi. collections.deque ga o'tish bitta qatorni o'zgartirdi va navbat bir necha daqiqada bo'shadi.

OrderedDict esa boshqa hikoya: Python 3.7 dan beri oddiy dict ham kiritilish tartibini saqlaydi. Unda OrderedDict nega hali ham bor? Chunki u tartibni boshqarish imkonini beradi (move_to_end, popitem(last=False)) va tartibni tenglikka qo'shadi.

Bu darsda ikkala turni ichki tuzilishidan boshlab o'rganamiz: qachon tez, qachon sekin va qayerda aynan ular kerak.

Bu darsda:

deque — ikki tomonlama navbat: ichki tuzilishi va murakkabligi
maxlen — cheklangan tarix, sirpanuvchi oyna
rotate, extendleft, insert va cheklovlar
deque qayerda list dan sekin: indeks bo'yicha murojaat
OrderedDict va dict: tartib, tenglik, move_to_end
LRU kesh — OrderedDict va functools.lru_cache
Amaliy: navbat, sirpanuvchi o'rtacha va tezlik cheklovchi

2. Nazariya — chuqur tushuntirish

2.1. `deque` ichki tuzilishi

list — uzluksiz massiv: elementlarga havolalar bitta xotira blokida. Boshiga qo'shish uchun hammasi siljiydi.

deque — bloklar zanjiri: har biri 64 ta havolali bloklar ikki tomonlama bog'langan. Chetlarga qo'shish — faqat chekka blokka yozish.

Amal	`list`	`deque`
`append(x)` / `pop()` — oxiridan	`O(1)`	`O(1)`
`insert(0, x)` / `pop(0)` — boshidan	`O(n)`	`O(1)` (`appendleft` / `popleft`)
`x[i]` — o'rtadan	`O(1)`	`O(n)` — chetdan bloklar bo'ylab
`x[i:j]` — kesma		`TypeError`
`sort()`		(`sorted(d)` — `list` qaytaradi)
`in`	`O(n)`	`O(n)`

Qoida: ikkala chetdan ishlash — deque; o'rtadan indeks bilan ishlash — list.

2.2. Asosiy API

python

from collections import deque

d = deque([1, 2, 3])
d.append(4); d.appendleft(0)        # deque([0, 1, 2, 3, 4])
d.pop(); d.popleft()                # 4, 0
d.extend([7, 8]); d.extendleft([7, 8])   # ⚠️ extendleft tartibni teskari qiladi: [8, 7, ...]
d.rotate(2)                         # o'ngga 2 qadam
d.rotate(-1)                        # chapga

Metod	Izoh
`extendleft(it)`	Har elementni navbat bilan boshiga — teskari tartibda
`rotate(n)`	`n > 0` — o'ngga, `n < 0` — chapga
`insert(i, x)`, `remove(x)`, `del d[i]`	Bor, lekin `O(n)`
`pop()` bo'sh `deque` da	`IndexError: pop from an empty deque`
Iteratsiya paytida o'zgartirish	`RuntimeError: deque mutated during iteration`

2.3. `maxlen` — cheklangan navbat

python

tarix = deque(maxlen=3)
for x in range(5):
    tarix.append(x)                 # deque([2, 3, 4], maxlen=3)

Holat	Xulq
To'la, `append`	Boshidagi eng eski element jim tashlanadi
To'la, `appendleft`	Oxiridagi element tashlanadi
To'la, `insert`	`IndexError: deque already at its maximum size`
`maxlen=0`	Hech narsa saqlamaydi

Qo'llanishlar: oxirgi N ta jurnal qatori, "bekor qilish" tarixi, sirpanuvchi oyna, tail -n.

2.4. `deque` va iplar

append, appendleft, pop, popleft — atomar (GIL ostida bitta amal). Shuning uchun deque oddiy ishlab chiqaruvchi-iste'molchi uchun ip-xavfsiz.

Lekin "bo'sh bo'lsa kut" kerak bo'lsa — queue.Queue (14.3-dars): deque da kutish yo'q, faqat IndexError.

Kerak	Tanlov
Bir ipda navbat, BFS, tarix	`deque`
Iplar orasida bloklovchi navbat	`queue.Queue`
`asyncio` vazifalari orasida	`asyncio.Queue`
Jarayonlar orasida	`multiprocessing.Queue`

2.5. `OrderedDict` va `dict`

3.7 dan beri dict kiritilish tartibini kafolatlaydi. Farqlar:

Xususiyat	`dict`	`OrderedDict`
Kiritilish tartibi
Tenglik `==` tartibni hisobga oladi		(ikkalasi ham `OrderedDict` bo'lsa)
`move_to_end(k, last=True)`		`O(1)`
`popitem(last=False)` — eng eskisini	(`popitem` faqat oxirgisini)
`reversed()`	(3.8+)
Xotira	Kam	Ko'proq (qo'shimcha bog'langan ro'yxat)
Mavjud kalitni qayta yozish	Tartib o'zgarmaydi	Tartib o'zgarmaydi

python

OrderedDict(a=1, b=2) == OrderedDict(b=2, a=1)   # False
dict(a=1, b=2) == dict(b=2, a=1)                 # True
OrderedDict(a=1, b=2) == dict(b=2, a=1)          # True — biri dict bo'lsa, tartib e'tiborsiz

Mavjud kalitga qiymat berish uni oxiriga surmaydi — o'chirib qayta qo'shish yoki move_to_end kerak.

2.6. LRU kesh

LRU (Least Recently Used) — sig'im to'lganda eng uzoq ishlatilmagan yozuvni chiqarib tashlash. OrderedDict bunga ideal:

Amal	`OrderedDict` bilan
O'qish	`move_to_end(k)` — "yaqinda ishlatildi"
Yozish	`d[k] = v`; `move_to_end(k)`
Sig'im oshdi	`popitem(last=False)` — eng eskisi

Funksiya natijalarini keshlash uchun tayyor vosita — functools.lru_cache(maxsize=...) (15.10-dars).

3. Tez ma'lumotnoma

python

from collections import OrderedDict, deque

navbat = deque()
navbat.append(x); x = navbat.popleft()          # FIFO, O(1)
stek = deque(); stek.append(x); stek.pop()      # LIFO
oxirgi_10 = deque(maxlen=10)                    # cheklangan tarix
d.rotate(1)

kesh = OrderedDict()
kesh.move_to_end(k)                             # yaqinda ishlatildi
kesh.popitem(last=False)                        # eng eskisini chiqarish

Qoidalar

boshidan olish — deque.popleft, list.pop(0) emas
o'rtadan indeks — list; deque[i] O(n)
maxlen — eski elementlar jim tashlanadi
iplar orasida kutish kerak — queue.Queue
tartib tenglikka ta'sir qilsin yoki move_to_end kerak — OrderedDict
aks holda — oddiy dict

4. Batafsil misollar

Misol 1 — `deque` asoslari va murakkablik

python

"""Ikki tomonlama amallar; extendleft tartibi; rotate; maxlen xulqi; cheklovlar; list bilan tezlik solishtiruvi."""

import timeit
from collections import deque


def main() -> None:
    print("=== 1. Ikkala chetdan ===")
    d = deque([1, 2, 3])
    d.appendleft(0)
    d.append(4)
    print(f"  {d}")
    print(f"  popleft()={d.popleft()}, pop()={d.pop()} → {d}")
    d.extendleft([7, 8])
    print(f"  extendleft([7, 8]) → {d}  ⚠️ teskari tartib")

    print("\n=== 2. rotate ===")
    d = deque(range(6))
    d.rotate(2)
    print(f"  rotate(2):  {d}")
    d.rotate(-3)
    print(f"  rotate(-3): {d}")

    print("\n=== 3. ⭐ maxlen ===")
    tarix = deque(maxlen=3)
    for x in range(5):
        tarix.append(x)
    print(f"  0..4 append: {tarix}")
    tarix.appendleft(-1)
    print(f"  appendleft(-1): {tarix}  ← oxiridagi tashlandi")
    try:
        tarix.insert(0, 100)
    except IndexError as xato:
        print(f"  insert → IndexError: {xato}")

    print("\n=== 4. Cheklovlar ===")
    d = deque(range(5))
    print(f"  d[2]={d[2]}, d[-1]={d[-1]}, 3 in d: {3 in d}, index(3)={d.index(3)}")
    try:
        d[1:3]
    except TypeError as xato:
        print(f"  d[1:3] → TypeError: {xato}")
    print(f"  sorted(deque): {sorted(deque([3, 1, 2]))} → turi {type(sorted(deque([3, 1, 2]))).__name__}")
    try:
        deque().popleft()
    except IndexError as xato:
        print(f"  bo'sh popleft → IndexError: {xato}")
    try:
        d = deque([1, 2, 3])
        for x in d:
            d.append(x)
    except RuntimeError as xato:
        print(f"  iteratsiyada o'zgartirish → RuntimeError: {xato}")

    print("\n=== 5. ⭐ Tezlik: list va deque ===")
    n = 100_000
    list_bosh = min(timeit.repeat("l.insert(0, 1); l.pop(0)", setup=f"l = list(range({n}))", number=2000, repeat=3))
    deque_bosh = min(timeit.repeat("d.appendleft(1); d.popleft()",
                                   setup=f"from collections import deque; d = deque(range({n}))", number=2000, repeat=3))
    print(f"  boshidan qo'shish/olish ({n} element): deque kamida 100 barobar tez: {list_bosh / deque_bosh >= 100}")
    list_orta = min(timeit.repeat("l[50_000]", setup=f"l = list(range({n}))", number=100_000, repeat=3))
    deque_orta = min(timeit.repeat("d[50_000]", setup=f"from collections import deque; d = deque(range({n}))",
                                   number=100_000, repeat=3))
    print(f"  o'rtadagi element d[50_000]: list kamida 20 barobar tez: {deque_orta / list_orta >= 20}")
    list_oxir = min(timeit.repeat("l.append(1); l.pop()", setup=f"l = list(range({n}))", number=200_000, repeat=3))
    deque_oxir = min(timeit.repeat("d.append(1); d.pop()",
                                   setup=f"from collections import deque; d = deque(range({n}))", number=200_000, repeat=3))
    print(f"  oxiridan: farq 3 barobardan kam: {max(list_oxir, deque_oxir) / min(list_oxir, deque_oxir) < 3}")


if __name__ == "__main__":
    main()

Natijaning muhim qismi:

text

=== 1. Ikkala chetdan ===
  deque([0, 1, 2, 3, 4])
  popleft()=0, pop()=4 → deque([1, 2, 3])
  extendleft([7, 8]) → deque([8, 7, 1, 2, 3])  ⚠️ teskari tartib

=== 2. rotate ===
  rotate(2):  deque([4, 5, 0, 1, 2, 3])
  rotate(-3): deque([1, 2, 3, 4, 5, 0])

=== 3. ⭐ maxlen ===
  0..4 append: deque([2, 3, 4], maxlen=3)
  appendleft(-1): deque([-1, 2, 3], maxlen=3)  ← oxiridagi tashlandi
  insert → IndexError: deque already at its maximum size

=== 4. Cheklovlar ===
  d[2]=2, d[-1]=4, 3 in d: True, index(3)=3
  d[1:3] → TypeError: sequence index must be integer, not 'slice'
  sorted(deque): [1, 2, 3] → turi list
  bo'sh popleft → IndexError: pop from an empty deque
  iteratsiyada o'zgartirish → RuntimeError: deque mutated during iteration

=== 5. ⭐ Tezlik: list va deque ===
  boshidan qo'shish/olish (100000 element): deque kamida 100 barobar tez: True
  o'rtadagi element d[50_000]: list kamida 20 barobar tez: True
  oxiridan: farq 3 barobardan kam: True

Nima ko'rsatdi: 2.1, 2.2, 2.3-bo'limlar.

Misol 2 — `deque` bilan algoritmlar

python

"""BFS — eng qisqa yo'l; sirpanuvchi oyna maksimumi; bekor qilish tarixi; tail -n; palindrom tekshiruvi."""

from collections import deque

METRO = {
    "Chilonzor": ["Mirzo Ulug'bek"],
    "Mirzo Ulug'bek": ["Chilonzor", "Novza"],
    "Novza": ["Mirzo Ulug'bek", "Milliy bog'"],
    "Milliy bog'": ["Novza", "Paxtakor"],
    "Paxtakor": ["Milliy bog'", "Alisher Navoiy", "Mustaqillik maydoni"],
    "Alisher Navoiy": ["Paxtakor", "O'zbekiston"],
    "Mustaqillik maydoni": ["Paxtakor", "Amir Temur xiyoboni"],
    "Amir Temur xiyoboni": ["Mustaqillik maydoni", "Yunus Rajabiy"],
    "O'zbekiston": ["Alisher Navoiy"],
    "Yunus Rajabiy": ["Amir Temur xiyoboni"],
}


def eng_qisqa_yol(graf: dict[str, list[str]], boshi: str, oxiri: str) -> list[str] | None:
    navbat = deque([[boshi]])
    korilgan = {boshi}
    while navbat:
        yol = navbat.popleft()
        if yol[-1] == oxiri:
            return yol
        for qoshni in graf[yol[-1]]:
            if qoshni not in korilgan:
                korilgan.add(qoshni)
                navbat.append(yol + [qoshni])
    return None


def oyna_maksimumi(sonlar: list[int], k: int) -> list[int]:
    """Har k uzunlikdagi oynaning maksimumi — O(n): deque da kamayuvchi indekslar."""
    indekslar: deque[int] = deque()
    natija = []
    for i, x in enumerate(sonlar):
        while indekslar and sonlar[indekslar[-1]] <= x:
            indekslar.pop()
        indekslar.append(i)
        if indekslar[0] <= i - k:
            indekslar.popleft()
        if i >= k - 1:
            natija.append(sonlar[indekslar[0]])
    return natija


def main() -> None:
    print("=== 1. BFS: metro bo'yicha eng qisqa yo'l ===")
    yol = eng_qisqa_yol(METRO, "Chilonzor", "Yunus Rajabiy")
    assert yol is not None
    print(f"  {' → '.join(yol)}")
    print(f"  bekatlar soni: {len(yol) - 1}")

    print("\n=== 2. Sirpanuvchi oyna maksimumi ===")
    harorat = [21, 24, 19, 26, 28, 22, 20, 25, 27, 23]
    maks = oyna_maksimumi(harorat, 3)
    sodda = [max(harorat[i:i + 3]) for i in range(len(harorat) - 2)]
    print(f"  harorat:     {harorat}")
    print(f"  3 kunlik max: {maks}")
    print(f"  sodda usul bilan bir xil: {maks == sodda}")

    print("\n=== 3. Bekor qilish tarixi (oxirgi 3 amal) ===")
    matn = ""
    tarix: deque[str] = deque(maxlen=3)
    for qism in ("Salom", ", ", "dunyo", "!", " Python"):
        tarix.append(matn)
        matn += qism
    print(f"  matn: {matn!r}")
    for _ in range(4):
        if tarix:
            matn = tarix.pop()
            print(f"  bekor qilish → {matn!r}")
        else:
            print("  tarix tugadi — 3 dan ortiq bekor qilib bo'lmaydi")

    print("\n=== 4. tail -n 3 ===")
    jurnal = [f"qator {i}" for i in range(1, 10_001)]
    print(f"  {list(deque(jurnal, maxlen=3))}")

    print("\n=== 5. Palindrom — ikki chetdan ===")
    for soz in ("qazaq", "kiyik", "Python"):
        d = deque(soz.lower())
        while len(d) > 1 and d.popleft() == d.pop():
            pass
        print(f"  {soz}: {len(d) <= 1}")


if __name__ == "__main__":
    main()

Natijaning muhim qismi:

text

=== 1. BFS: metro bo'yicha eng qisqa yo'l ===
  Chilonzor → Mirzo Ulug'bek → Novza → Milliy bog' → Paxtakor → Mustaqillik maydoni → Amir Temur xiyoboni → Yunus Rajabiy
  bekatlar soni: 7

=== 2. Sirpanuvchi oyna maksimumi ===
  harorat:     [21, 24, 19, 26, 28, 22, 20, 25, 27, 23]
  3 kunlik max: [24, 26, 28, 28, 28, 25, 27, 27]
  sodda usul bilan bir xil: True

=== 3. Bekor qilish tarixi (oxirgi 3 amal) ===
  matn: 'Salom, dunyo! Python'
  bekor qilish → 'Salom, dunyo!'
  bekor qilish → 'Salom, dunyo'
  bekor qilish → 'Salom, '
  tarix tugadi — 3 dan ortiq bekor qilib bo'lmaydi

=== 4. tail -n 3 ===
  ['qator 9998', 'qator 9999', 'qator 10000']

=== 5. Palindrom — ikki chetdan ===
  qazaq: True
  kiyik: True
  Python: False

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

Misol 3 — `OrderedDict`

python

"""dict bilan farqlar: tenglik, move_to_end, popitem(last=False); qayta yozish tartibni o'zgartirmaydi; LRU kesh; lru_cache; xotira."""

import sys
from collections import OrderedDict
from functools import lru_cache


class LRUKesh(OrderedDict):
    def __init__(self, sigim: int) -> None:
        super().__init__()
        self.sigim = sigim

    def __getitem__(self, kalit):
        qiymat = super().__getitem__(kalit)
        self.move_to_end(kalit)
        return qiymat

    def __setitem__(self, kalit, qiymat) -> None:
        super().__setitem__(kalit, qiymat)
        self.move_to_end(kalit)
        if len(self) > self.sigim:
            eski, _ = self.popitem(last=False)
            print(f"    chiqarildi: {eski}")


def main() -> None:
    print("=== 1. Tenglik ===")
    print(f"  dict(a, b) == dict(b, a):               {dict(a=1, b=2) == dict(b=2, a=1)}")
    print(f"  OrderedDict(a, b) == OrderedDict(b, a): {OrderedDict(a=1, b=2) == OrderedDict(b=2, a=1)}")
    print(f"  OrderedDict(a, b) == dict(b, a):        {OrderedDict(a=1, b=2) == dict(b=2, a=1)}")

    print("\n=== 2. Tartibni boshqarish ===")
    od = OrderedDict(a=1, b=2, c=3)
    od.move_to_end("a")
    print(f"  move_to_end('a'):             {list(od)}")
    od.move_to_end("c", last=False)
    print(f"  move_to_end('c', last=False): {list(od)}")
    oxirgi = od.popitem()
    birinchi = od.popitem(last=False)
    print(f"  popitem() → {oxirgi}, popitem(last=False) → {birinchi}, qoldi: {list(od)}")

    print("\n=== 3. ⚠️ Qayta yozish tartibni o'zgartirmaydi ===")
    d = {"a": 1, "b": 2}
    d["a"] = 5
    print(f"  d['a'] = 5 → {list(d)}")
    del d["a"]
    d["a"] = 5
    print(f"  del va qayta qo'shish → {list(d)}")
    print(f"  reversed(dict): {list(reversed({'x': 1, 'y': 2, 'z': 3}))}")

    print("\n=== 4. LRU kesh (sig'im 2) ===")
    kesh = LRUKesh(2)
    kesh["Toshkent"] = "+5"
    kesh["Berlin"] = "+1"
    print(f"  o'qildi: Toshkent={kesh['Toshkent']}")
    kesh["Tokio"] = "+9"
    print(f"  qoldi: {list(kesh)}")

    print("\n=== 5. functools.lru_cache ===")

    @lru_cache(maxsize=2)
    def ikkilantir(x: int) -> int:
        return x * 2

    for x in (1, 2, 1, 3, 2):
        ikkilantir(x)
    print(f"  {ikkilantir.cache_info()}")
    print("  ⭐ tayyor LRU — 15.10-darsda batafsil")

    print("\n=== 6. Xotira ===")
    oddiy = {i: i for i in range(1000)}
    tartibli = OrderedDict(oddiy)
    print(f"  OrderedDict dict dan kattaroq: {sys.getsizeof(tartibli) > sys.getsizeof(oddiy)}")
    print("  ⭐ tartibni boshqarish kerak bo'lmasa — oddiy dict")


if __name__ == "__main__":
    main()

Natijaning muhim qismi:

text

=== 1. Tenglik ===
  dict(a, b) == dict(b, a):               True
  OrderedDict(a, b) == OrderedDict(b, a): False
  OrderedDict(a, b) == dict(b, a):        True

=== 2. Tartibni boshqarish ===
  move_to_end('a'):             ['b', 'c', 'a']
  move_to_end('c', last=False): ['c', 'b', 'a']
  popitem() → ('a', 1), popitem(last=False) → ('c', 3), qoldi: ['b']

=== 3. ⚠️ Qayta yozish tartibni o'zgartirmaydi ===
  d['a'] = 5 → ['a', 'b']
  del va qayta qo'shish → ['b', 'a']
  reversed(dict): ['z', 'y', 'x']

=== 4. LRU kesh (sig'im 2) ===
  o'qildi: Toshkent=+5
    chiqarildi: Berlin
  qoldi: ['Toshkent', 'Tokio']

=== 5. functools.lru_cache ===
  CacheInfo(hits=1, misses=4, maxsize=2, currsize=2)
  ⭐ tayyor LRU — 15.10-darsda batafsil

=== 6. Xotira ===
  OrderedDict dict dan kattaroq: True
  ⭐ tartibni boshqarish kerak bo'lmasa — oddiy dict

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

Misol 4 — Amaliy: xabarlar navbati, sirpanuvchi o'rtacha va tezlik cheklovchi

Kirishdagi vaziyatni hal qilamiz. Uch qism: navbatni list va deque bilan bo'shatish (o'lchov bilan), oxirgi N ta so'rov javob vaqtining sirpanuvchi o'rtachasi (maxlen) va "har mijozga 10 soniyada ko'pi bilan 3 so'rov" cheklovchisi — sirpanuvchi vaqt oynasi bilan. Vaqt hozir parametri orqali beriladi — natija takrorlanadi va testlanadi.

python

"""Navbatni bo'shatish: list.pop(0) va deque.popleft; maxlen bilan sirpanuvchi o'rtacha; vaqt oynasi bilan tezlik cheklovchi."""

import time
from collections import defaultdict, deque


def navbatni_bosh_qil(navbat) -> int:
    ishlandi = 0
    olish = navbat.popleft if isinstance(navbat, deque) else lambda: navbat.pop(0)
    while navbat:
        olish()
        ishlandi += 1
    return ishlandi


class SirpanuvchiOrtacha:
    def __init__(self, oyna: int) -> None:
        self.qiymatlar: deque[float] = deque(maxlen=oyna)
        self.yigindi = 0.0

    def qosh(self, x: float) -> float:
        if len(self.qiymatlar) == self.qiymatlar.maxlen:
            self.yigindi -= self.qiymatlar[0]           # tashlanadigan element
        self.qiymatlar.append(x)
        self.yigindi += x
        return self.yigindi / len(self.qiymatlar)


class TezlikCheklovchi:
    def __init__(self, soni: int, oyna_soniya: float) -> None:
        self.soni, self.oyna = soni, oyna_soniya
        self.sorovlar: defaultdict[str, deque[float]] = defaultdict(deque)

    def ruxsat(self, mijoz: str, hozir: float) -> bool:
        vaqtlar = self.sorovlar[mijoz]
        while vaqtlar and vaqtlar[0] <= hozir - self.oyna:
            vaqtlar.popleft()                            # oynadan chiqqanlar
        if len(vaqtlar) >= self.soni:
            return False
        vaqtlar.append(hozir)
        return True


def main() -> None:
    print("=== 1. 50 000 xabarli navbatni bo'shatish ===")
    n = 50_000
    bosh = time.perf_counter()
    navbatni_bosh_qil(list(range(n)))
    list_vaqti = time.perf_counter() - bosh
    bosh = time.perf_counter()
    ishlandi = navbatni_bosh_qil(deque(range(n)))
    deque_vaqti = time.perf_counter() - bosh
    print(f"  ishlandi: {ishlandi}")
    print(f"  deque kamida 50 barobar tez: {list_vaqti / deque_vaqti >= 50}")

    print("\n=== 2. Javob vaqti: 3 ta so'rovlik sirpanuvchi o'rtacha ===")
    ortacha = SirpanuvchiOrtacha(3)
    for ms in (120, 80, 100, 400, 90, 110):
        print(f"  {ms:>4} ms → o'rtacha {ortacha.qosh(ms):6.1f} ms  oyna={list(ortacha.qiymatlar)}")

    print("\n=== 3. Tezlik cheklovchi: 10 soniyada 3 so'rov ===")
    cheklovchi = TezlikCheklovchi(soni=3, oyna_soniya=10)
    sorovlar = [("aziz", 0.0), ("aziz", 1.0), ("bek", 1.5), ("aziz", 2.0), ("aziz", 3.0),
                ("aziz", 9.9), ("aziz", 10.0), ("aziz", 11.5), ("bek", 12.0), ("aziz", 12.0)]
    for mijoz, vaqt in sorovlar:
        natija = "✅" if cheklovchi.ruxsat(mijoz, vaqt) else "❌ rad"
        oynada = [f"{t:g}" for t in cheklovchi.sorovlar[mijoz]]
        print(f"  t={vaqt:>4}  {mijoz:5} {natija:6}  oynada: {oynada}")

    print("\n=== 4. Tekshiruvlar ===")
    tekshiruv = TezlikCheklovchi(soni=3, oyna_soniya=10)
    ruxsatlar = [t for t in range(0, 60) if tekshiruv.ruxsat("x", float(t))]
    oynalar_toza = all(sum(1 for r in ruxsatlar if s - 10 < r <= s) <= 3 for s in range(60))
    print(f"  60 soniyada har soniyadan so'rov: {len(ruxsatlar)} ta ruxsat")
    print(f"  hech bir 10 soniyalik oynada 3 tadan ortiq emas: {oynalar_toza}")
    print(f"  xotira chegaralangan (oynada ≤ 3): {len(tekshiruv.sorovlar['x']) <= 3}")


if __name__ == "__main__":
    main()

Natijaning muhim qismi:

text

=== 1. 50 000 xabarli navbatni bo'shatish ===
  ishlandi: 50000
  deque kamida 50 barobar tez: True

=== 2. Javob vaqti: 3 ta so'rovlik sirpanuvchi o'rtacha ===
   120 ms → o'rtacha  120.0 ms  oyna=[120]
    80 ms → o'rtacha  100.0 ms  oyna=[120, 80]
   100 ms → o'rtacha  100.0 ms  oyna=[120, 80, 100]
   400 ms → o'rtacha  193.3 ms  oyna=[80, 100, 400]
    90 ms → o'rtacha  196.7 ms  oyna=[100, 400, 90]
   110 ms → o'rtacha  200.0 ms  oyna=[400, 90, 110]

=== 3. Tezlik cheklovchi: 10 soniyada 3 so'rov ===
  t= 0.0  aziz  ✅       oynada: ['0']
  t= 1.0  aziz  ✅       oynada: ['0', '1']
  t= 1.5  bek   ✅       oynada: ['1.5']
  t= 2.0  aziz  ✅       oynada: ['0', '1', '2']
  t= 3.0  aziz  ❌ rad   oynada: ['0', '1', '2']
  t= 9.9  aziz  ❌ rad   oynada: ['0', '1', '2']
  t=10.0  aziz  ✅       oynada: ['1', '2', '10']
  t=11.5  aziz  ✅       oynada: ['2', '10', '11.5']
  t=12.0  bek   ✅       oynada: ['12']
  t=12.0  aziz  ✅       oynada: ['10', '11.5', '12']

=== 4. Tekshiruvlar ===
  60 soniyada har soniyadan so'rov: 18 ta ruxsat
  hech bir 10 soniyalik oynada 3 tadan ortiq emas: True
  xotira chegaralangan (oynada ≤ 3): True

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

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

Noto'g'ri fikr	To'g'risi
"`deque` — hamma jihatdan tezroq `list`"	Chetlarda tez, o'rtadan indeksda sekin
"`deque` kesmani qo'llaydi"	`TypeError`
"`extendleft([1, 2])` → `[1, 2, ...]`"	`[2, 1, ...]`
"`maxlen` to'lsa xato beradi"	Eski elementni jim tashlaydi (`insert` dan tashqari)
"`deque` — iplar uchun navbat"	Atomar amallar bor, lekin kutish yo'q — `queue.Queue`
"3.7 dan keyin `OrderedDict` kerak emas"	`move_to_end`, `popitem(last=False)`, tartibli tenglik
"Kalitga qayta qiymat berish uni oxiriga suradi"	Yo'q
"`OrderedDict == dict` tartibni tekshiradi"	Faqat ikkalasi `OrderedDict` bo'lsa

6. Keng tarqalgan xatolar va yechimlari

1. list ni FIFO navbat sifatida

python

xabar = navbat.pop(0)                 # ❌ O(n)
xabar = navbat.popleft()              # ✅ deque

2. deque da indeks bo'yicha tsikl

python

for i in range(len(d)): d[i]          # ❌ O(n²)
for x in d: ...                       # ✅

3. Kesma kutish

python

d[-3:]                                # ❌ TypeError
list(itertools.islice(d, len(d) - 3, None))   # ✅ yoki deque(d, maxlen=3)

4. extendleft tartibi

python

d.extendleft([1, 2, 3])               # ⚠️ [3, 2, 1, ...]
d.extendleft(reversed([1, 2, 3]))     # ✅ [1, 2, 3, ...]

5. Chegarasiz tarix

python

tarix = []                            # ❌ xotira cheksiz o'sadi
tarix = deque(maxlen=1000)            # ✅

6. Iplar orasida deque bilan kutish

python

while not navbat: time.sleep(0.01)    # ❌ band kutish
navbat = queue.Queue(); navbat.get()  # ✅

7. LRU da o'qishni belgilamaslik

python

qiymat = kesh[k]                      # ⚠️ oddiy OrderedDict — tartib o'zgarmadi
kesh.move_to_end(k)                   # ✅

8. Keraksiz OrderedDict

python

OrderedDict(json.loads(s))            # ⚠️ dict tartibni allaqachon saqlaydi
json.loads(s)                         # ✅

7. Integratsiya — bu bilim qayerda kerak bo'ladi

6-qism (o'tilgan): list va dict ichki tuzilishi
14.3-dars (o'tilgan): queue.Queue — iplar orasida navbat
15.6-dars (o'tilgan): Counter, defaultdict
15.8-dars: itertools.islice — deque dan kesma
15.10-dars: functools.lru_cache
20-qism: FastAPI — API tezlik cheklovchilari
31.10-dars: texnik intervyu — algoritmlar: BFS, sirpanuvchi oyna
23.10-dars: Redis va kesh — taqsimlangan tezlik cheklovchi

8. Eng yaxshi amaliyotlar

FIFO navbat — deque.
"Oxirgi N ta" — deque(maxlen=N).
O'rtadan indeks va kesma kerak — list.
Iplar orasida kutish — queue.Queue, deque emas.
Tartibni boshqarish kerak bo'lsa — OrderedDict, aks holda dict.
Funksiya keshlash — functools.lru_cache; o'z LRU ingiz — faqat maxsus talab bo'lsa.
Vaqtga bog'liq sinflarga hozir ni parametr sifatida bering.
Murakkablikni o'lchang — katta hajmda O(n) va O(1) farqi minglab barobar.

9. Amaliy topshiriq

Vazifa 1: Natijani bashorat qiling

python

from collections import OrderedDict, deque
1.  d = deque([1, 2, 3]); d.appendleft(0); print(list(d))
2.  d = deque([1, 2]); d.extendleft([3, 4]); print(list(d))
3.  d = deque(range(5)); d.rotate(1); print(list(d))
4.  d = deque(range(5), maxlen=2); print(list(d))
5.  d = deque([1, 2], maxlen=2); d.appendleft(0); print(list(d))
6.  print(deque([3, 1, 2])[1])
7.  print(type(sorted(deque([2, 1]))).__name__)
8.  print(bool(deque()))
9.  print(OrderedDict(a=1, b=2) == OrderedDict(b=2, a=1))
10. print(OrderedDict(a=1, b=2) == {"b": 2, "a": 1})
11. od = OrderedDict(a=1, b=2, c=3); od.move_to_end("a"); print(list(od))
12. d = {"x": 1, "y": 2}; d["x"] = 3; print(list(d))

Javoblar

[0, 1, 2, 3]
[4, 3, 1, 2]
[4, 0, 1, 2, 3]
[3, 4]
[0, 1] — oxiridagi 2 tashlandi
1
list
False
False
True
['b', 'c', 'a']
['x', 'y']

Vazifa 2: Xatolarni tuzating

python

1.  def ishla(navbat):                    # navbat — 1 mln elementli list
        while navbat:
            vazifa = navbat.pop(0)
            bajar(vazifa)

2.  def oxirgi_qatorlar(fayl, n):
        return fayl.readlines()[-n:]       # 10 GB fayl

3.  def kesh_ol(kesh, k):                 # kesh — OrderedDict, LRU
        return kesh[k]

4.  def tarix_qosh(tarix, amal):
        tarix.append(amal)
        if len(tarix) > 100:
            tarix.pop(0)

5.  d = deque(range(10))
    oxirgi_uchta = d[-3:]

Javoblar

python

1.  def ishla(navbat):
        navbat = deque(navbat)
        while navbat:
            bajar(navbat.popleft())

2.  def oxirgi_qatorlar(fayl, n):
        return list(deque(fayl, maxlen=n))   # fayl satrma-satr, xotira O(n)

3.  def kesh_ol(kesh, k):
        kesh.move_to_end(k)
        return kesh[k]

4.  tarix = deque(maxlen=100)
    def tarix_qosh(tarix, amal):
        tarix.append(amal)

5.  from itertools import islice
    d = deque(range(10))
    oxirgi_uchta = list(islice(d, len(d) - 3, None))

Vazifa 3: Ikki tomonlama navbatdan foydalanib

"0-1 BFS": qirralari 0 yoki 1 og'irlikdagi grafda eng qisqa masofa (appendleft — 0, append — 1)
Toshkent metrosi uchun: bekatlar orasi — 1, bir liniyada qolish — 0, liniya almashtirish — 1
Oddiy BFS va Dijkstra (heapq) natijalari bilan solishtiring

Vazifa 4: Sirpanuvchi statistika

SirpanuvchiStat(oyna) sinfini yozing:

qosh(x) — O(1) o'rtacha
maksimum() — Misol 2 dagi monoton deque usuli bilan O(1) amortizatsiya
minimum() — xuddi shunday
1 000 000 tasodifiy son bilan sodda usul (max(oyna)) bilan tezlikni solishtiring

Vazifa 5: LRU va TTL kesh

OrderedDict asosida LRUKesh(sigim, ttl_soniya) — muddati o'tgan yozuvlar o'qilganda o'chirilsin
hozir parametri orqali vaqt
Statistika: tushish (hit), o'tkazib yuborish (miss), chiqarilganlar
functools.lru_cache bilan bir xil ketma-ketlikda natijalarni solishtiring

Vazifa 6: Token paqiri va oyna — solishtirish

Misol 4 dagi "sirpanuvchi oyna" cheklovchisi
"Token paqiri" cheklovchisi (15.1, Vazifa 5 — xotirasiz, faqat son va vaqt)
"Qat'iy oyna" (har 10 soniyada hisoblagich nolga tushadi)
Oyna chegarasida bir vaqtda kelgan so'rovlarda qaysi biri ko'proq ruxsat beradi?
Xotira: har mijozga qancha joy kerak?

Vazifa 7: O'ylash

Python 3.7 da dict kiritilish tartibini saqlashi til spetsifikatsiyasiga kiritildi. Bundan oldin bu faqat CPython 3.6 ning implementatsiya xususiyati edi. Nega "tasodifiy" optimallashtirishni til kafolatiga aylantirish muhim qaror edi va bu OrderedDict, JSON, **kwargs va boshqa Python implementatsiyalari (PyPy, MicroPython) uchun qanday oqibatlarga olib keldi?

Javob

Qisqa javob: 3.6 da CPython dict ni xotirani tejash uchun ixcham tuzilishga o'tkazdi (Raymond Hettinger g'oyasi): kalitlar zich massivda kiritilish tartibida, xesh jadvali esa faqat indekslarni saqlaydi. Tartib — yon ta'sir edi. 3.7 da Gvido van Rossum buni til kafolati deb e'lon qildi, chunki dasturchilar allaqachon unga tayana boshlagan edi. Bu **kwargs, sinf atributlari, JSON va konfiguratsiyalarni tabiiyroq qildi, lekin barcha Python implementatsiyalari uchun majburiyat bo'ldi va OrderedDict ning rolini toraytirdi.

1. Ixcham dict ichki tuzilishi (11-qism bilan bog'liq)

Eski (3.5 gacha)	Ixcham (3.6+)
Bitta siyrak jadval: `(xesh, kalit, qiymat)` yozuvlari	Kichik indekslar jadvali + zich yozuvlar massivi
Bo'sh joylar ko'p (1/3 bo'sh)	Yozuvlar zich, indekslar 1 bayt ham bo'lishi mumkin
Tartib — xeshga bog'liq	Tartib — yozuvlar massivi tartibi
Xotira ko'p	20–25% kam

2. Nega kafolatga aylantirish muhim

Hyrum qonuni: "Yetarlicha foydalanuvchi bo'lsa, API ning har bir kuzatiladigan xulqiga kimdir tayanadi". Dasturchilar 3.6 da tartibga tayana boshladi
Kafolatsiz holat — kod CPython'da ishlab, boshqa implementatsiyada jim buziladi
Kafolat — hujjat, test va implementatsiyalar orasida moslik

3. Oqibatlar

Soha	Nima o'zgardi
`**kwargs`	Tartib saqlanadi (PEP 468, 3.6) — `f(a=1, b=2)` tartibi ma'lum
Sinf tanasi	Atributlar e'lon qilingan tartibda (`__init_subclass__`, `dataclass` maydonlari)
JSON	`json.dumps(dict)` kalitlar tartibini saqlaydi — takrorlanadigan chiqish
`OrderedDict`	Faqat `move_to_end`, `popitem(last=False)`, tartibli tenglik uchun kerak
`collections.Counter`, `defaultdict`	Tartib meros qilib olindi
Testlar	`dict` chop etilishi takrorlanadi

4. Boshqa implementatsiyalar

PyPy ixcham dict ni CPython'dan oldin (2015) joriy qilgan edi — tartib uning uchun tabiiy
MicroPython — resurslar cheklangan; tartibli dict uchun qo'shimcha xotira talab qilinishi mumkin, u ba'zi farqlarni hujjatlashtiradi
Har yangi implementatsiya (masalan, GraalPy) bu kafolatni bajarishi shart

5. Nega OrderedDict o'chirilmadi

Orqaga moslik
move_to_end va popitem(last=False) — O(1), oddiy dict da bunday amallar yo'q
Tenglik semantikasi boshqacha — o'zgartirish mavjud kodni buzardi
Qayta tartiblashga moslashtirilgan (ikki tomonlama bog'langan ro'yxat), dict esa o'qishga

6. Xulosa

Implementatsiya tafsiloti ommalashsa — u amalda API ga aylanadi
3.7 qarori mavjud amaliyotni rasmiylashtirdi va implementatsiyalar orasidagi farqni yo'qotdi
dict tartibi — endi til xususiyati; OrderedDict — tartibni boshqarish vositasi
Xuddi shunday: "tasodifan ishlayotgan" xulqqa tayanishdan oldin, u hujjatlashtirilganmi — tekshiring

Nimani mustahkamlaydi: 2.1–2.6-bo'limlar.

Xulosa

Bu darsda collections ning ikki turini — ikki tomonlama navbat va tartibli lug'atni o'rgandik.

Eng muhim uch fikr:

deque — chetlar uchun, list — o'rta uchun. deque bloklar zanjiri: appendleft/popleft — O(1), list.pop(0) esa O(n); misolda 100 000 elementda deque yuz barobardan ham ko'proq tez chiqdi. Lekin d[i] o'rtadan O(n), kesma va sort yo'q. BFS, navbatlar va ikki chetdan ishlash — deque; indeks va kesma — list.
maxlen — xotirasi chegaralangan tarix. To'lganda eng eski element jim tashlanadi: "oxirgi N ta jurnal qatori", bekor qilish tarixi, sirpanuvchi o'rtacha va vaqt oynasi bilan tezlik cheklovchi. deque amallari atomar, lekin kutish yo'q — iplar orasida queue.Queue.
OrderedDict — tartibni boshqarish uchun. 3.7 dan beri oddiy dict ham tartibni saqlaydi; OrderedDict esa move_to_end, popitem(last=False) va tartibni hisobga oluvchi tenglikni beradi. Uning klassik qo'llanishi — LRU kesh; funksiya natijalari uchun esa tayyor functools.lru_cache bor. Mavjud kalitga qayta qiymat berish tartibni o'zgartirmaydi.

Keyingi darsda itertools moduliga o'tamiz: cheksiz iteratorlar, islice, chain, groupby, accumulate va dangasa quvurlar.

Ulashish:Telegram'da

Izohlar (0)

Izoh yozish uchun kiring.

Hozircha izoh yo'q. Birinchi bo'ling!

15.7-dars: collections: deque, OrderedDict

1. Kirish va motivatsiya

2. Nazariya — chuqur tushuntirish

2.1. deque ichki tuzilishi

2.2. Asosiy API

2.3. maxlen — cheklangan navbat

2.4. deque va iplar

2.5. OrderedDict va dict

2.6. LRU kesh

3. Tez ma'lumotnoma

4. Batafsil misollar

Misol 1 — deque asoslari va murakkablik

Misol 2 — deque bilan algoritmlar

Misol 3 — OrderedDict

Misol 4 — Amaliy: xabarlar navbati, sirpanuvchi o'rtacha va tezlik cheklovchi

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

6. Keng tarqalgan xatolar va yechimlari

7. Integratsiya — bu bilim qayerda kerak bo'ladi

8. Eng yaxshi amaliyotlar

9. Amaliy topshiriq

Xulosa

Izohlar (0)

15.7-dars: `collections`: `deque`, `OrderedDict`

2.1. `deque` ichki tuzilishi

2.3. `maxlen` — cheklangan navbat

2.4. `deque` va iplar

2.5. `OrderedDict` va `dict`

Misol 1 — `deque` asoslari va murakkablik

Misol 2 — `deque` bilan algoritmlar

Misol 3 — `OrderedDict`