Python kursi6.4-dars: Ro'yxat va xotira
Python kursi · Malumot tuzilmalari

6.4-dars: Ro'yxat va xotira

31 daqiqa4/18-dars

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


1. Kirish va motivatsiya

Ro'yxat ichida nima bor? Nega u ba'zan kutilganidan ko'p joy egallaydi?

python
import sys

print(sys.getsizeof([]))                    # 56
print(sys.getsizeof([1]))                   # 64
print(sys.getsizeof([1, 2, 3]))             # 88
print(sys.getsizeof(list(range(1000))))     # 8056

Sonlar mantiqli ko'rinadi. Lekin:

python
r = []
for i in range(10):
    r.append(i)
    print(len(r), sys.getsizeof(r))
text
1  88     ← bo'sh ro'yxat 56 edi, 1 element qo'shildi → 88?!
2  88
3  88
4  88
5  120

Nega bir necha element qo'shilganda hajm o'zgarmaydi, keyin sakraydi?

Va eng muhimi:

python
r = [1, 2, 3]
print(sys.getsizeof(r))                     # 88

r = ["juda uzun satr" * 1000, "yana bir", "uchinchi"]
print(sys.getsizeof(r))                     # 88 ← YANA 88?!

Bu darsda:

  • Ro'yxat ichki tuzilishi (PyListObject)
  • Ortiqcha ajratish (over-allocation) va o'sish formulasi
  • sys.getsizeof nima o'lchaydi va nimani o'lchamaydi
  • Chuqur hajm hisoblash
  • list o'rniga: array, bytearray, deque, numpy
  • Xotira tejash usullari

2. Nazariya — chuqur tushuntirish

2.1. PyListObject — ichki tuzilish

CPython'da ro'yxat quyidagicha ifodalanadi:

c
typedef struct {
    PyObject_VAR_HEAD          // ob_refcnt, ob_type, ob_size
    PyObject **ob_item;        // elementlar massiviga KO'RSATKICH
    Py_ssize_t allocated;      // ajratilgan joy (>= ob_size)
} PyListObject;

Uch qism:

PyListObject (56 bayt):
┌────────────────────────────┐
│ ob_refcnt    8 bayt        │  havolalar soni
│ ob_type      8 bayt        │  turga ko'rsatkich (list)
│ ob_size      8 bayt        │  len() — ELEMENTLAR SONI
│ ob_item      8 bayt   ─────┼──┐  massivga ko'rsatkich
│ allocated    8 bayt        │  │  AJRATILGAN joy
│ (GC sarlavhasi 16 bayt)    │  │
└────────────────────────────┘  │
                                ▼
Ko'rsatkichlar massivi (allocated × 8 bayt):
┌────┬────┬────┬────┬─────┬─────┐
│ p0 │ p1 │ p2 │ p3 │ ... │ ... │
└─┬──┴─┬──┴─┬──┴─┬──┴─────┴─────┘
  │    │    │    │
  ▼    ▼    ▼    ▼
 obyektlar (xotiraning boshqa joyida)

Uchta muhim xulosa:

1. Ro'yxat obyektlarni emas, ularga KO'RSATKICHLARNI saqlaydi.

Shuning uchun ro'yxat hajmi elementlar hajmiga bog'liq emas:

python
sys.getsizeof([1, 2, 3])                    # 88
sys.getsizeof(["a" * 10000, "b", "c"])      # 88 ← bir xil!

2. ob_size (uzunlik) va allocated (ajratilgan) — turli narsalar.

python
len(r)          # ob_size
# allocated — Pythondan to'g'ridan-to'g'ri ko'rinmaydi,
# lekin getsizeof orqali hisoblash mumkin:
allocated = (sys.getsizeof(r) - 56) // 8

3. Har bir element +8 bayt (64-bitli tizimda).

hajm = 56 (sarlavha) + 8 × allocated

2.2. Ortiqcha ajratish (over-allocation)

append har safar xotira ajratsa, u O(n) bo'lardi. Buning o'rniga Python kerakdan ko'proq ajratadi.

CPython o'sish formulasi (Objects/listobject.c, list_resize):

c
new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;

O'zbekcha: yangi_hajm ≈ n + n/8 + 6, keyin 4 ga karrali qilib yaxlitlanadi.

Natijada o'sish ketma-ketligi:

0, 4, 8, 16, 24, 32, 40, 52, 64, 76, 92, 108, 128, 148, 172, 200, ...

Har safar taxminan 1.125 barobar o'sadi (boshqa tillarda odatda 1.5 yoki 2).

python
import sys

r = []
oldingi = sys.getsizeof(r)
for i in range(100):
    r.append(i)
    hozirgi = sys.getsizeof(r)
    if hozirgi != oldingi:
        allocated = (hozirgi - 56) // 8
        print(f"  len={len(r):>3}  hajm={hozirgi:>5}  allocated={allocated}")
        oldingi = hozirgi
text
  len=  1  hajm=   88  allocated=4
  len=  5  hajm=  120  allocated=8
  len=  9  hajm=  184  allocated=16
  len= 17  hajm=  248  allocated=24
  len= 25  hajm=  312  allocated=32
  len= 33  hajm=  376  allocated=40
  len= 41  hajm=  472  allocated=52
  ...

Nega bu append ni O(1) qiladi:

n ta element qo'shish uchun jami ko'chirishlar soni ~n ga proporsional (geometrik qator). Demak bitta append ga to'g'ri keladigan o'rtacha ish — O(1). Bu — amortizatsiyalangan murakkablik (6.1-dars).

Bitta append ba'zan sekin bo'ladi (massiv ko'chirilganda), lekin o'rtacha O(1).

Nega 1.125, 2 emas?

  • Kichik o'sish koeffitsienti — kamroq isrof qilingan xotira
  • CPython uchun xotira tejash muhimroq, chunki ro'yxatlar juda ko'p ishlatiladi
  • realloc ko'pincha joyida kengaytira oladi (ko'chirishsiz)

2.3. Oldindan ma'lum hajm — ortiqcha ajratish yo'q

Agar Python hajmni oldindan bilsa, aniq ajratadi:

python
import sys

sys.getsizeof(list(range(10)))          # 136 = 56 + 8×10  ← aniq
sys.getsizeof([0] * 10)                 # 136              ← aniq
sys.getsizeof([x for x in range(10)])   # 184              ← ortiqcha

r = []
for i in range(10):
    r.append(i)
sys.getsizeof(r)                        # 184              ← ortiqcha

Sabab: list(range(10)) va [0] * 10 — hajm oldindan ma'lum. Ro'yxat generatori va append — noma'lum, shuning uchun ortiqcha ajratiladi.

Amaliy xulosa: hajmi ma'lum bo'lsa, list(...) yoki * n — xotira tejamli.

2.4. Qisqarish

Ro'yxat kichrayganda ham xotira qaytariladi — lekin darhol emas:

python
r = list(range(1000))
print(sys.getsizeof(r))         # 8056

del r[100:]
print(len(r), sys.getsizeof(r)) # 100  968  ← qisqardi

r.clear()
print(sys.getsizeof(r))         # 56   ← to'liq bo'shadi

CPython allocated > newsize * 2 bo'lganda qisqartiradi.

pop() bilan bittalab kamaytirish darhol qisqartirmaydi — faqat chegara oshgandan keyin.

2.5. sys.getsizeof nima o'lchaydi

Faqat obyektning O'ZINI — ichidagi obyektlarni emas.

python
kichik = [1, 2, 3]
katta = [[0] * 1000, [0] * 1000, [0] * 1000]

sys.getsizeof(kichik)       # 88
sys.getsizeof(katta)        # 88  ← BIR XIL!

Ikkalasi ham 3 ta ko'rsatkich saqlaydi.

Chuqur hajm hisoblash:

python
import sys
from collections.abc import Mapping, Set, Sequence


def chuqur_hajm(obyekt, korilgan=None) -> int:
    """Obyekt va uning barcha ichki obyektlari hajmi."""
    if korilgan is None:
        korilgan = set()

    obyekt_id = id(obyekt)
    if obyekt_id in korilgan:       # tsikllardan himoya
        return 0
    korilgan.add(obyekt_id)

    hajm = sys.getsizeof(obyekt)

    if isinstance(obyekt, (str, bytes, bytearray)):
        return hajm                 # ichida obyekt yo'q

    if isinstance(obyekt, Mapping):
        hajm += sum(chuqur_hajm(k, korilgan) + chuqur_hajm(v, korilgan)
                    for k, v in obyekt.items())
    elif isinstance(obyekt, (Sequence, Set)):
        hajm += sum(chuqur_hajm(x, korilgan) for x in obyekt)

    return hajm

Muhim nozikliklar:

1. Bir xil obyekt ikki marta sanalmaydi:

python
r = [1, 1, 1, 1, 1]
chuqur_hajm(r)      # 1 obyekti FAQAT BIR MARTA sanaladi (korilgan to'plami)

Bu — to'g'ri xatti-harakat: xotirada haqiqatan bitta 1 obyekti bor.

2. Kichik sonlar va satrlar kesh qilingan (3.3, 4.11-darslar):

python
sys.getsizeof(1)        # 28 bayt
# Lekin -5..256 oralig'idagi sonlar interpretator ishga tushganda
# yaratilgan — ro'yxatga qo'shganda yangi xotira ishlatilmaydi

3. __slots__ bo'lmagan sinf obyektlari — __dict__ bilan:

python
class Nuqta:
    def __init__(self, x, y):
        self.x, self.y = x, y

n = Nuqta(1, 2)
sys.getsizeof(n)                # 48  ← faqat obyektning "sarlavhasi"

O'lchash tuzog'i: sys.getsizeof(n.__dict__) ni qo'shib hisoblash Python 3.11+ da noto'g'ri. Endi oddiy obyekt atributlarini lug'atsiz, o'zida saqlaydi va n.__dict__ ga birinchi murojaat qilinganda lug'at o'sha paytda yaratiladi — ya'ni o'lchov o'lchanayotgan narsani o'zgartiradi. Ishonchli usul — ko'p obyekt yaratib, tracemalloc bilan umumiy o'sishni o'lchash (4-misol va 8.19-dars).

tracemalloc moduli — haqiqiy xotira profillash uchun (29-qism).

2.6. list o'rniga: muqobil tuzilmalar

array.array — bir turdagi sonlar:

python
from array import array

r = list(range(1_000_000))
a = array("i", range(1_000_000))        # 'i' = 4-baytli int

sys.getsizeof(r)        # ~8_000_056  + har bir int uchun ~28 bayt
sys.getsizeof(a)        # ~4_000_064  ← xom baytlar

Farq: list ko'rsatkichlar + alohida obyektlar saqlaydi. array — xom baytlar.

Tur kodi C turi Bayt
'b' / 'B' signed/unsigned char 1
'h' / 'H' short 2
'i' / 'I' int 4
'l' / 'L' long 4/8
'q' / 'Q' long long 8
'f' float 4
'd' double 8

array cheklovlari: bir tur, chegaradan chiqsa OverflowError, indekslashda har safar yangi Python obyekti yaratiladi (shuning uchun o'qish list dan sekinroq).

bytes / bytearray — baytlar:

python
b = bytes(range(256))               # o'zgarmas
ba = bytearray(range(256))          # o'zgaruvchan
sys.getsizeof(ba)                   # ~313 (256 + sarlavha)

collections.deque — ikki tomonlama navbat:

python
from collections import deque

d = deque([1, 2, 3])
d.appendleft(0)         # O(1) ✅  (list.insert(0) — O(n))
d.popleft()             # O(1) ✅  (list.pop(0) — O(n))
d[500]                  # O(n) ⚠️  (list[500] — O(1))

deque — bog'langan bloklar ro'yxati. Chetlarda tez, o'rtada sekin.

Cheklangan deque:

python
oxirgi_5 = deque(maxlen=5)          # avtomatik eski elementni chiqaradi
for i in range(10):
    oxirgi_5.append(i)
print(list(oxirgi_5))               # [5, 6, 7, 8, 9]

numpy.ndarray — ilmiy hisoblashlar:

python
import numpy as np

a = np.arange(1_000_000, dtype=np.int32)
a.nbytes                            # 4_000_000

numpy — vektorlashtirilgan amallar, list dan 10-100x tezroq. 24-qismda.

Solishtirish jadvali:

Tuzilma 1M int xotira Indeks Boshiga qo'shish Bir tur
list ~8 MB + obyektlar O(1) O(n)
array('i') 4 MB O(1) O(n)
deque ~8 MB + obyektlar O(n) O(1)
numpy int32 4 MB O(1) O(n)
bytes 1 MB O(1) — 0-255

2.7. Generatorlar — xotira tejashning asosiy usuli

Ro'yxat hamma narsani xotirada saqlaydi. Generator — birma-bir ishlab chiqaradi.

python
# ❌ ~8 MB xotira
kvadratlar = [x ** 2 for x in range(1_000_000)]
jami = sum(kvadratlar)

# ✅ ~200 bayt
kvadratlar = (x ** 2 for x in range(1_000_000))
jami = sum(kvadratlar)
python
sys.getsizeof([x for x in range(1_000_000)])    # 8_448_728
sys.getsizeof((x for x in range(1_000_000)))    # 200

17-darsda generator ifodalarini batafsil ko'ramiz.

Generator bir marta ishlatiladi:

python
g = (x for x in range(3))
print(sum(g))           # 3
print(sum(g))           # 0 ← tugagan!

Qachon ro'yxat kerak:

  • Bir necha marta o'tish kerak
  • Indeks bo'yicha murojaat kerak
  • len() kerak
  • Saralash kerak

2.8. Xotira tejash usullari

1. Generatorlar (yuqorida).

2. __slots__ — sinf obyektlari uchun (8-qism):

python
class Nuqta:
    __slots__ = ("x", "y")          # __dict__ yo'q
    def __init__(self, x, y):
        self.x, self.y = x, y

1M ikki atributli obyektda ~38 MB tejash (Python 3.14 da har biri ~88 → ~48 bayt).

3. array yoki numpy — bir turdagi sonlar uchun.

4. Bo'laklab o'qish:

python
# ❌ Butun faylni xotiraga
qatorlar = open("katta.txt").readlines()

# ✅ Birma-bir
with open("katta.txt") as f:
    for qator in f:
        qayta_ishla(qator)

5. itertools — oraliq ro'yxatsiz:

python
from itertools import islice

# ❌ Butun ro'yxat, keyin kesim
birinchi_10 = list(katta_generator)[:10]

# ✅ Faqat 10 ta
birinchi_10 = list(islice(katta_generator, 10))

6. Keraksiz nusxalardan qochish:

python
# ❌ Uchta ro'yxat
a = [x for x in malumot]
b = [x * 2 for x in a]
c = [x + 1 for x in b]

# ✅ Bitta o'tish
c = [x * 2 + 1 for x in malumot]

7. del bilan bo'shatish:

python
katta_royxat = qayta_ishla()
natija = xulosa(katta_royxat)
del katta_royxat                # havolani o'chirish → GC bo'shatadi

3. Tez ma'lumotnoma

Hajm formulasi

python
sys.getsizeof(royxat) == 56 + 8 * allocated     # 64-bit

sys.getsizeof([])           56
sys.getsizeof([1])          88   (allocated=4)
sys.getsizeof([1,2,3])      88
list(range(10))            136   (aniq — hajm ma'lum)
[x for x in range(10)]     184   (ortiqcha)

O'sish formulasi

new_allocated = (n + n>>3 + 6) & ~3

0 → 4 → 8 → 16 → 24 → 32 → 40 → 52 → 64 → 76 → 92 → ...
~1.125x     → append amortizatsiyalangan O(1)

getsizeof faqat obyektni o'lchaydi

python
sys.getsizeof([[0]*1000]*3)     88 — ko'rsatkichlar
chuqur_hajm(...)                haqiqiy hajm (rekursiv)
tracemalloc                     professional profillash

Muqobillar

python
array('i', ...)     bir turdagi son — 2x tejash
bytearray(...)      0-255 baytlar — 8x tejash
deque(...)          chetlarda O(1), indeks O(n)
deque(maxlen=n)     cheklangan bufer
numpy.array         ilmiy hisob, vektorlashtirilgan
(x for x in ...)    generator — O(1) xotira

Tejash

python
Generator            butun ro'yxat o'rniga
__slots__            sinf obyektlari
islice()             list(...)[:n] o'rniga
Bitta o'tish         oraliq ro'yxatlar o'rniga
del                  katta obyektdan keyin

4. Batafsil misollar

Misol 1 — Xotira anatomiyasi

python
"""Ro'yxat xotirasi qanday taqsimlanadi."""

import sys

print("=== 1. Asosiy hajmlar ===")

NAMUNALAR = [
    ("[]",                      []),
    ("[1]",                     [1]),
    ("[1, 2]",                  [1, 2]),
    ("[1, 2, 3]",               [1, 2, 3]),
    ("[1, 2, 3, 4]",            [1, 2, 3, 4]),
    ("[1, 2, 3, 4, 5]",         [1, 2, 3, 4, 5]),
    ("list(range(10))",         list(range(10))),
    ("[0] * 10",                [0] * 10),
    ("[x for x in range(10)]",  [x for x in range(10)]),
]

print(f"  {'Ifoda':<26} {'len':>4} {'hajm':>7} {'ajratilgan':>11} {'zaxira':>8}")
print("  " + "─" * 62)

for nom, r in NAMUNALAR:
    hajm = sys.getsizeof(r)
    ajratilgan = (hajm - 56) // 8
    zaxira = ajratilgan - len(r)
    print(f"  {nom:<26} {len(r):>4} {hajm:>7} {ajratilgan:>11} {zaxira:>8}")

print("""
  ⭐ hajm = 56 (sarlavha) + 8 × ajratilgan

     list(range(10)) va [0]*10 — hajm OLDINDAN ma'lum → aniq ajratish
     [x for x in ...] va append — noma'lum → ORTIQCHA ajratish
""")


print("\n=== 2. Elementlar hajmiga bog'liq emas ===")

SINOVLAR = [
    ("[1, 2, 3]",                       [1, 2, 3]),
    ("['a', 'b', 'c']",                 ["a", "b", "c"]),
    ("['x'*10000, 'y', 'z']",           ["x" * 10000, "y", "z"]),
    ("[[0]*1000, [0]*1000, [0]*1000]",  [[0] * 1000] * 3),
    ("[None, None, None]",              [None, None, None]),
]

for nom, r in SINOVLAR:
    print(f"  {nom:<34} getsizeof = {sys.getsizeof(r)}")

print("""
  ⭐ Hammasi 88 bayt — ro'yxat KO'RSATKICHLARNI saqlaydi,
     obyektlarning o'zini emas.
""")


print("\n=== 3. O'sish ketma-ketligi ===")

r = []
oldingi_hajm = sys.getsizeof(r)
qadamlar = []

for i in range(2000):
    r.append(i)
    hajm = sys.getsizeof(r)
    if hajm != oldingi_hajm:
        qadamlar.append((len(r), hajm, (hajm - 56) // 8))
        oldingi_hajm = hajm

print(f"  {'len':>6} {'hajm':>9} {'ajratilgan':>11} {'nisbat':>9}  Grafik")
print("  " + "─" * 64)

oldingi_alloc = 0
for uzunlik, hajm, ajratilgan in qadamlar[:20]:
    nisbat = ajratilgan / oldingi_alloc if oldingi_alloc else 0
    chiziq = "█" * min(ajratilgan // 4, 30)
    nisbat_matn = f"{nisbat:.3f}x" if nisbat else "—"
    print(f"  {uzunlik:>6} {hajm:>9} {ajratilgan:>11} {nisbat_matn:>9}  {chiziq}")
    oldingi_alloc = ajratilgan

print(f"\n  ... jami {len(qadamlar)} ta qayta ajratish, 2000 ta append uchun")

ortacha = sum(
    q[2] / p[2] for p, q in zip(qadamlar, qadamlar[1:])
) / (len(qadamlar) - 1)
print(f"  O'rtacha o'sish koeffitsienti: {ortacha:.4f}x")

print("""
  ⭐ Formula: new_allocated = (n + n>>3 + 6) & ~3
     ≈ 1.125x — boshqa tillarda odatda 1.5x yoki 2x

     Kichik koeffitsient = kamroq isrof, lekin ko'proq qayta ajratish.
     CPython xotira tejashni tanlagan.
""")


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

r = list(range(1000))
print(f"  list(range(1000)):     len={len(r):>5}  hajm={sys.getsizeof(r):>7}")

del r[100:]
print(f"  del r[100:]:           len={len(r):>5}  hajm={sys.getsizeof(r):>7}")

del r[10:]
print(f"  del r[10:]:            len={len(r):>5}  hajm={sys.getsizeof(r):>7}")

r.clear()
print(f"  r.clear():             len={len(r):>5}  hajm={sys.getsizeof(r):>7}")

print("\n  pop() bilan bittalab kamaytirish:")
r2 = list(range(1000))
for n in [1000, 900, 500, 200, 100, 10, 0]:
    while len(r2) > n:
        r2.pop()
    print(f"    len={len(r2):>5}  hajm={sys.getsizeof(r2):>7}  "
          f"ajratilgan={(sys.getsizeof(r2) - 56) // 8}")


print("\n=== 5. Ko'rsatkich va obyekt ===")

r = [1, 2, 3]

print(f"  Ro'yxat obyekti:  {sys.getsizeof(r)} bayt")
print(f"  Har bir int:      {sys.getsizeof(1)} bayt")
print(f"  Jami (nazariy):   {sys.getsizeof(r) + 3 * sys.getsizeof(1)} bayt")

print(f"""
  ⚠️ Lekin -5..256 oralig'idagi sonlar oldindan yaratilgan (3.3-dars):
     id(1) hamma joyda bir xil = {id(1)}

     Demak [1, 2, 3] haqiqatda faqat {sys.getsizeof(r)} bayt qo'shimcha oladi.
""")

katta = [10 ** 20 + i for i in range(3)]
jami = sys.getsizeof(katta) + sum(sys.getsizeof(x) for x in katta)
print(f"  Katta sonlar bilan:")
print(f"    Ro'yxat:        {sys.getsizeof(katta)} bayt")
print(f"    Har bir son:    {sys.getsizeof(katta[0])} bayt")
print(f"    Jami:           {jami} bayt")

Natijaning muhim qismi:

text
=== 1. Asosiy hajmlar ===
  Ifoda                       len    hajm  ajratilgan   zaxira
  ──────────────────────────────────────────────────────────────
  []                            0      56           0        0
  [1]                           1      64           1        0
  [1, 2, 3]                     3      88           4        1
  list(range(10))              10     136          10        0
  [0] * 10                     10     136          10        0
  [x for x in range(10)]       10     184          16        6

=== 3. O'sish ketma-ketligi ===
     len      hajm  ajratilgan    nisbat  Grafik
  ────────────────────────────────────────────────────────────────
       1        88           4         —  █
       5       120           8     2.000x  ██
       9       184          16     2.000x  ████
      17       248          24     1.500x  ██████
      25       312          32     1.333x  ████████
      33       376          40     1.250x  ██████████
      41       472          52     1.300x  █████████████

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

Misol 2 — Chuqur hajm

python
"""getsizeof nima o'lchaydi va haqiqiy hajmni qanday topish."""

import sys
from collections.abc import Mapping, Set, Sequence


def chuqur_hajm(obyekt, korilgan=None) -> int:
    """Obyekt va uning barcha ichki obyektlari hajmi (bayt)."""
    if korilgan is None:
        korilgan = set()

    obyekt_id = id(obyekt)
    if obyekt_id in korilgan:
        return 0
    korilgan.add(obyekt_id)

    hajm = sys.getsizeof(obyekt)

    if isinstance(obyekt, (str, bytes, bytearray, range)):
        return hajm

    if isinstance(obyekt, Mapping):
        hajm += sum(chuqur_hajm(k, korilgan) + chuqur_hajm(v, korilgan)
                    for k, v in obyekt.items())
    elif isinstance(obyekt, (Sequence, Set, frozenset)):
        hajm += sum(chuqur_hajm(x, korilgan) for x in obyekt)
    elif hasattr(obyekt, "__dict__"):
        hajm += chuqur_hajm(vars(obyekt), korilgan)

    return hajm


def formatla(baytlar: int) -> str:
    for birlik in ["B", "KB", "MB", "GB"]:
        if abs(baytlar) < 1024:
            return f"{baytlar:.1f} {birlik}"
        baytlar /= 1024
    return f"{baytlar:.1f} TB"


print("=== 1. Sayoz vs chuqur ===")

NAMUNALAR = [
    ("[1, 2, 3]",                       [1, 2, 3]),
    ("[10**20, 10**20+1, 10**20+2]",    [10 ** 20, 10 ** 20 + 1, 10 ** 20 + 2]),
    ("['a', 'b', 'c']",                 ["a", "b", "c"]),
    ("['x'*10000]",                     ["x" * 10000]),
    ("[[0]*1000 for _ in range(3)]",    [[0] * 1000 for _ in range(3)]),
    ("[[0]*1000] * 3  (bir xil!)",      [[0] * 1000] * 3),
    ("{'a': [1,2,3], 'b': 'x'*100}",    {"a": [1, 2, 3], "b": "x" * 100}),
]

print(f"  {'Obyekt':<32} {'getsizeof':>12} {'chuqur_hajm':>14}")
print("  " + "─" * 60)

for nom, o in NAMUNALAR:
    print(f"  {nom:<32} {formatla(sys.getsizeof(o)):>12} "
          f"{formatla(chuqur_hajm(o)):>14}")

print("""
  ⭐ [[0]*1000 for _ in range(3)]  — 3 ta ALOHIDA ro'yxat
     [[0]*1000] * 3                — 1 ta ro'yxatga 3 ta havola

     chuqur_hajm ikkinchisini to'g'ri hisoblaydi (bir marta sanaydi).
""")


print("\n=== 2. Bir xil obyektlar ===")

SINOVLAR = [
    ("[1] * 1000",              [1] * 1000),
    ("list(range(1000))",       list(range(1000))),
    ("['abc'] * 1000",          ["abc"] * 1000),
    ("[object()] * 1000",       [object()] * 1000),
    ("[object() for _ in range(1000)]", [object() for _ in range(1000)]),
]

print(f"  {'Ifoda':<36} {'chuqur_hajm':>14}")
print("  " + "─" * 52)
for nom, o in SINOVLAR:
    print(f"  {nom:<36} {formatla(chuqur_hajm(o)):>14}")

print("""
  ⭐ [1] * 1000        — bitta 1 obyekti, 1000 ta havola
     list(range(1000)) — 0..255 kesh qilingan, 256..999 yangi
     [object()] * 1000 — bitta obyekt
     [object() for ...] — 1000 ta alohida obyekt
""")


print("\n=== 3. Sinf obyektlari va __slots__ ===")


class OddiyNuqta:
    def __init__(self, x, y):
        self.x = x
        self.y = y


class SlotsNuqta:
    __slots__ = ("x", "y")

    def __init__(self, x, y):
        self.x = x
        self.y = y


from dataclasses import dataclass


@dataclass
class DataNuqta:
    x: int
    y: int


@dataclass(slots=True)
class DataSlotsNuqta:
    x: int
    y: int


from typing import NamedTuple


class TupleNuqta(NamedTuple):
    x: int
    y: int


SINFLAR = [OddiyNuqta, SlotsNuqta, DataNuqta, DataSlotsNuqta, TupleNuqta]

import tracemalloc


def bir_obyekt(sinf, n: int = 20_000) -> int:
    """Bitta obyektning haqiqiy o'rtacha hajmi (bayt).

    ⚠️ sys.getsizeof(vars(obj)) ishlatmaymiz: 3.11+ da vars() lug'atni
       o'sha paytda yaratib, natijani oshirib yuboradi.
    """
    joy = [None] * n
    tracemalloc.start()
    asos = tracemalloc.get_traced_memory()[0]
    for i in range(n):
        joy[i] = sinf(1, 2)
    jami = tracemalloc.get_traced_memory()[0] - asos
    tracemalloc.stop()
    return round(jami / n)


print(f"  {'Sinf':<20} {'getsizeof':>10} {'haqiqiy':>10}")
print("  " + "─" * 44)

for sinf in SINFLAR:
    print(f"  {sinf.__name__:<20} {sys.getsizeof(sinf(1, 2)):>10} "
          f"{bir_obyekt(sinf):>10}")

N = 100_000
print(f"\n  {N:,} ta obyekt uchun (haqiqiy o'lchov asosida):")
for sinf in SINFLAR:
    print(f"    {sinf.__name__:<20} {formatla(bir_obyekt(sinf) * N):>12}")

print("\n  ⭐ __slots__ — 2-3x tejash (8-qismda batafsil)")


print("\n=== 4. list vs array vs bytearray ===")

from array import array

N = 500_000

TUZILMALAR = [
    ("list(range(N))",              lambda: list(range(N))),
    ("array('i', range(N))",        lambda: array("i", range(N))),
    ("array('h', range(30000))",    lambda: array("h", range(30000))),
    ("bytearray(range(256))*1000",  lambda: bytearray(range(256)) * 1000),
]

print(f"  {'Tuzilma':<30} {'elementlar':>12} {'getsizeof':>12}")
print("  " + "─" * 58)

for nom, yaratuvchi in TUZILMALAR:
    o = yaratuvchi()
    print(f"  {nom:<30} {len(o):>12,} {formatla(sys.getsizeof(o)):>12}")

r = list(range(N))
a = array("i", range(N))
print(f"""
  {N:,} ta int uchun:
    list:     {formatla(chuqur_hajm(r))}  (ko'rsatkichlar + obyektlar)
    array:    {formatla(sys.getsizeof(a))}  (xom baytlar)
    Farq:     {chuqur_hajm(r) / sys.getsizeof(a):.1f}x
""")


print("\n=== 5. Generator vs ro'yxat ===")

N = 1_000_000

royxat = [x ** 2 for x in range(N)]
generator = (x ** 2 for x in range(N))

print(f"  {N:,} ta kvadrat:")
print(f"    Ro'yxat:    {formatla(sys.getsizeof(royxat))}")
print(f"    Generator:  {formatla(sys.getsizeof(generator))}")
print(f"    Farq:       {sys.getsizeof(royxat) / sys.getsizeof(generator):,.0f}x")

print(f"""
  Natija bir xil:
    sum(ro'yxat)    = {sum(royxat):,}
    sum(generator)  = {sum(generator):,}

  ⚠️ Lekin generator BIR MARTA ishlatiladi:
    sum(generator) ikkinchi marta = {sum(generator)}
""")

del royxat

Natijaning muhim qismi:

text
=== 1. Sayoz vs chuqur ===
  Obyekt                              getsizeof    chuqur_hajm
  ────────────────────────────────────────────────────────────
  [1, 2, 3]                              88.0 B         172.0 B
  [10**20, 10**20+1, 10**20+2]           88.0 B        196.0 B
  ['x'*10000]                            64.0 B         9.9 KB
  [[0]*1000 for _ in range(3)]           88.0 B        23.7 KB
  [[0]*1000] * 3  (bir xil!)             80.0 B         8.0 KB

=== 3. Sinf obyektlari va __slots__ ===
  Sinf                  getsizeof    haqiqiy
  ────────────────────────────────────────────
  OddiyNuqta                   48         88
  SlotsNuqta                   48         48
  DataNuqta                    48         88
  DataSlotsNuqta               48         48
  TupleNuqta                   64         72

=== 5. Generator vs ro'yxat ===
  1,000,000 ta kvadrat:
    Ro'yxat:    8.1 MB
    Generator:  208.0 B
    Farq:       42,244x

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

Misol 3 — Muqobil tuzilmalar

python
"""list o'rniga qachon boshqa tuzilma kerak."""

import sys
import time
from array import array
from collections import deque

print("=== 1. deque vs list — chetlarda ===")

N = 50_000

# list.insert(0)
boshlandi = time.perf_counter()
r = []
for i in range(N):
    r.insert(0, i)
vaqt_list_insert = time.perf_counter() - boshlandi

# deque.appendleft
boshlandi = time.perf_counter()
d = deque()
for i in range(N):
    d.appendleft(i)
vaqt_deque_left = time.perf_counter() - boshlandi

# list.pop(0)
r2 = list(range(N))
boshlandi = time.perf_counter()
while r2:
    r2.pop(0)
vaqt_list_pop0 = time.perf_counter() - boshlandi

# deque.popleft
d2 = deque(range(N))
boshlandi = time.perf_counter()
while d2:
    d2.popleft()
vaqt_deque_popleft = time.perf_counter() - boshlandi

AMALLAR = [
    ("list.insert(0, x)",   vaqt_list_insert,       "O(n)"),
    ("deque.appendleft(x)", vaqt_deque_left,        "O(1)"),
    ("list.pop(0)",         vaqt_list_pop0,         "O(n)"),
    ("deque.popleft()",     vaqt_deque_popleft,     "O(1)"),
]

print(f"  {N:,} amal:\n")
print(f"  {'Amal':<24} {'Vaqt':>10} {'Murakkablik':>13}")
print("  " + "─" * 50)
for nom, vaqt, m in AMALLAR:
    print(f"  {nom:<24} {vaqt * 1000:>7.1f} ms {m:>13}")

print(f"""
  ⭐ Boshiga qo'shish: deque {vaqt_list_insert / vaqt_deque_left:.0f}x tezroq
     Boshidan olish:   deque {vaqt_list_pop0 / vaqt_deque_popleft:.0f}x tezroq
""")


print("\n=== 2. deque vs list — indeks bo'yicha ===")

M = 100_000
r = list(range(M))
d = deque(range(M))
TAKROR = 20_000

import random
random.seed(1)
indekslar = [random.randrange(M) for _ in range(TAKROR)]

boshlandi = time.perf_counter()
for i in indekslar:
    _ = r[i]
vaqt_list_idx = time.perf_counter() - boshlandi

boshlandi = time.perf_counter()
for i in indekslar:
    _ = d[i]
vaqt_deque_idx = time.perf_counter() - boshlandi

print(f"  {TAKROR:,} ta tasodifiy indeks ({M:,} elementli tuzilmada):\n")
print(f"    list[i]:    {vaqt_list_idx * 1000:>8.1f} ms   O(1)")
print(f"    deque[i]:   {vaqt_deque_idx * 1000:>8.1f} ms   O(n)")
print(f"    Farq:       {vaqt_deque_idx / vaqt_list_idx:>8.0f}x")

print("""
  ⚠️ deque — chetlarda tez, o'rtada SEKIN.
     Indeks bo'yicha ko'p murojaat kerak bo'lsa — list.
""")


print("\n=== 3. deque(maxlen) — aylanma bufer ===")

oxirgi_5 = deque(maxlen=5)

print("  Oxirgi 5 ta hodisani saqlash:\n")
for i in range(1, 11):
    oxirgi_5.append(f"hodisa-{i}")
    print(f"    {i:>2}-qo'shishdan keyin: {list(oxirgi_5)}")

print("""
  ⭐ maxlen — eski elementlar AVTOMATIK chiqariladi.
     Loglar, oxirgi N ta natija, harakatlanuvchi o'rtacha uchun ideal.
""")

# Harakatlanuvchi o'rtacha
print("  Harakatlanuvchi o'rtacha (oyna=3):\n")
oyna = deque(maxlen=3)
QIYMATLAR = [10, 12, 15, 11, 20, 25, 18, 14]

print(f"    {'Qiymat':>8} {'Oyna':<16} {'O`rtacha':>10}")
print("    " + "─" * 38)
for q in QIYMATLAR:
    oyna.append(q)
    ortacha = sum(oyna) / len(oyna)
    print(f"    {q:>8} {str(list(oyna)):<16} {ortacha:>10.2f}")


print("\n=== 4. array — xotira tejash ===")

N = 300_000

r = list(range(N))
turlar = [
    ("array('b')", "b", range(min(N, 127))),
    ("array('h')", "h", range(min(N, 32767))),
    ("array('i')", "i", range(N)),
    ("array('q')", "q", range(N)),
    ("array('d')", "d", range(N)),
]

print(f"  {N:,} element uchun:\n")
print(f"  {'Tuzilma':<16} {'elementlar':>12} {'hajm':>12} {'bayt/element':>14}")
print("  " + "─" * 58)

hajm_list = sys.getsizeof(r)
print(f"  {'list':<16} {len(r):>12,} {hajm_list:>12,} "
      f"{hajm_list / len(r):>14.1f}")

for nom, kod, qiymatlar in turlar:
    a = array(kod, qiymatlar)
    h = sys.getsizeof(a)
    print(f"  {nom:<16} {len(a):>12,} {h:>12,} {h / len(a):>14.1f}")

print("""
  ⚠️ list ustunligi: har bir int obyekti ALOHIDA xotira oladi
     (256 dan katta sonlar uchun ~28 bayt).
     array — xom baytlar, obyekt yaratilmaydi.
""")

print("  ⚠️ array chegara nazorati:")
a = array("b")          # -128..127
for q in [127, 128]:
    try:
        a.append(q)
        print(f"    array('b').append({q}) → ✅")
    except OverflowError as x:
        print(f"    array('b').append({q}) → ❌ OverflowError: {x}")


print("\n=== 5. Qaysi tuzilmani tanlash ===")

print("""
  ┌─────────────────────────┬──────────────────────────────────┐
  │ Vazifa                  │ Tuzilma                          │
  ├─────────────────────────┼──────────────────────────────────┤
  │ Umumiy ketma-ketlik     │ list                             │
  │ O'zgarmas ketma-ketlik  │ tuple                            │
  │ Navbat (FIFO)           │ deque                            │
  │ Stek (LIFO)             │ list (append/pop)                │
  │ Oxirgi N ta element     │ deque(maxlen=N)                  │
  │ Bir turdagi sonlar      │ array                            │
  │ Baytlar (0-255)         │ bytes / bytearray                │
  │ Matematik hisoblashlar  │ numpy.ndarray                    │
  │ Tez `in` tekshiruvi     │ set                              │
  │ Kalit → qiymat          │ dict                             │
  │ Bir marta o'tish        │ generator                        │
  │ Har doim saralangan     │ heapq / sortedcontainers         │
  └─────────────────────────┴──────────────────────────────────┘
""")

Natijaning muhim qismi:

text
=== 1. deque vs list — chetlarda ===
  50,000 amal:

  Amal                           Vaqt   Murakkablik
  ──────────────────────────────────────────────────
  list.insert(0, x)             412.3 ms          O(n)
  deque.appendleft(x)             3.4 ms          O(1)
  list.pop(0)                   398.1 ms          O(n)
  deque.popleft()                 3.1 ms          O(1)

  ⭐ Boshiga qo'shish: deque 121x tezroq

=== 2. deque vs list — indeks bo'yicha ===
    list[i]:         1.9 ms   O(1)
    deque[i]:      842.3 ms   O(n)
    Farq:            443x

=== 4. array — xotira tejash ===
  300,000 element uchun:

  Tuzilma            elementlar         hajm   bayt/element
  ──────────────────────────────────────────────────────────
  list                  300,000    2,400,056            8.0
  array('h')             32,767       68,468            2.1
  array('i')            300,000    1,216,880            4.1
  array('q')            300,000    2,433,680            8.1

Nima ko'rsatdi: 2.6-bo'lim.

Misol 4 — Amaliy: xotira profillovchi

python
"""Katta ma'lumot bilan ishlashda xotirani kuzatish."""

import sys
import time
import tracemalloc
from array import array
from collections import deque
from dataclasses import dataclass


def formatla(baytlar: float) -> str:
    for birlik in ["B", "KB", "MB", "GB"]:
        if abs(baytlar) < 1024:
            return f"{baytlar:.1f} {birlik}"
        baytlar /= 1024
    return f"{baytlar:.1f} TB"


class XotiraOlchagich:
    """with bloki ichidagi xotira sarfini o'lchaydi."""

    def __init__(self, nom: str):
        self.nom = nom
        self.tepa = 0
        self.vaqt = 0.0

    def __enter__(self):
        tracemalloc.start()
        self.boshlandi = time.perf_counter()
        return self

    def __exit__(self, *xato):
        self.vaqt = time.perf_counter() - self.boshlandi
        _, self.tepa = tracemalloc.get_traced_memory()
        tracemalloc.stop()
        return False

    def __str__(self):
        return f"{self.nom:<34} {formatla(self.tepa):>10}  {self.vaqt * 1000:>7.1f} ms"


N = 500_000

print("=== 1. Bir xil vazifa, turli yechim ===\n")
print(f"  Vazifa: 0..{N:,} oralig'idagi juft sonlar kvadratlari yig'indisi\n")
print(f"  {'Usul':<34} {'Xotira':>10}  {'Vaqt':>10}")
print("  " + "─" * 58)

# 1. Uch oraliq ro'yxat
with XotiraOlchagich("3 ta oraliq ro'yxat") as o1:
    sonlar = list(range(N))
    juftlar = [x for x in sonlar if x % 2 == 0]
    kvadratlar = [x ** 2 for x in juftlar]
    natija1 = sum(kvadratlar)
    del sonlar, juftlar, kvadratlar
print(f"  {o1}")

# 2. Bitta ro'yxat
with XotiraOlchagich("1 ta ro'yxat generatori") as o2:
    natija2 = sum([x ** 2 for x in range(N) if x % 2 == 0])
print(f"  {o2}")

# 3. Generator
with XotiraOlchagich("Generator ifodasi") as o3:
    natija3 = sum(x ** 2 for x in range(N) if x % 2 == 0)
print(f"  {o3}")

# 4. Sikl
with XotiraOlchagich("Oddiy sikl") as o4:
    natija4 = 0
    for x in range(N):
        if x % 2 == 0:
            natija4 += x ** 2
print(f"  {o4}")

assert natija1 == natija2 == natija3 == natija4
print(f"\n  Natija (hammasida bir xil): {natija1:,}")
print(f"""
  ⭐ Generator {o1.tepa / max(o3.tepa, 1):,.0f}x kam xotira ishlatdi.
     Vaqt esa deyarli bir xil.
""")


print("\n=== 2. Sinf obyektlari: 100k yozuv ===\n")


class Oddiy:
    def __init__(self, id_, nom, ball):
        self.id = id_
        self.nom = nom
        self.ball = ball


class Slotli:
    __slots__ = ("id", "nom", "ball")

    def __init__(self, id_, nom, ball):
        self.id = id_
        self.nom = nom
        self.ball = ball


@dataclass(slots=True)
class DataSlotli:
    id: int
    nom: str
    ball: int


M = 100_000
NOMLAR = ["Aziz", "Bobur", "Aziza", "Dilnoza", "Eldor"]

print(f"  {'Ifodalash':<34} {'Xotira':>10}  {'Vaqt':>10}")
print("  " + "─" * 58)

with XotiraOlchagich("Sinf (__dict__ bilan)") as s1:
    a = [Oddiy(i, NOMLAR[i % 5], i % 100) for i in range(M)]
print(f"  {s1}")
del a

with XotiraOlchagich("Sinf (__slots__)") as s2:
    a = [Slotli(i, NOMLAR[i % 5], i % 100) for i in range(M)]
print(f"  {s2}")
del a

with XotiraOlchagich("dataclass(slots=True)") as s3:
    a = [DataSlotli(i, NOMLAR[i % 5], i % 100) for i in range(M)]
print(f"  {s3}")
del a

with XotiraOlchagich("tuple") as s4:
    a = [(i, NOMLAR[i % 5], i % 100) for i in range(M)]
print(f"  {s4}")
del a

with XotiraOlchagich("dict") as s5:
    a = [{"id": i, "nom": NOMLAR[i % 5], "ball": i % 100} for i in range(M)]
print(f"  {s5}")
del a

with XotiraOlchagich("3 ta alohida ro'yxat (ustunli)") as s6:
    idlar = array("i", range(M))
    nomlar = [NOMLAR[i % 5] for i in range(M)]
    ballar = array("b", (i % 100 for i in range(M)))
print(f"  {s6}")
del idlar, nomlar, ballar

print(f"""
  ⭐ Ustunli saqlash (columnar) eng tejamli —
     bu nega ma'lumotlar bazalari va pandas shunday ishlaydi.
""")


print("\n=== 3. Oqim bilan ishlash ===\n")

print("  Vazifa: 1M qatorli 'fayl' dan eng katta 5 tasini topish\n")
print(f"  {'Usul':<34} {'Xotira':>10}  {'Vaqt':>10}")
print("  " + "─" * 58)


def soxta_fayl(n):
    """Fayl o'qishni taqlid qiladi (generator)."""
    for i in range(n):
        yield (i * 7919) % 1_000_003


K = 1_000_000

with XotiraOlchagich("Butun faylni ro'yxatga") as f1:
    qatorlar = list(soxta_fayl(K))
    qatorlar.sort(reverse=True)
    eng_kattalar1 = qatorlar[:5]
    del qatorlar
print(f"  {f1}")

import heapq

with XotiraOlchagich("heapq.nlargest (oqim)") as f2:
    eng_kattalar2 = heapq.nlargest(5, soxta_fayl(K))
print(f"  {f2}")

with XotiraOlchagich("deque(maxlen) — oxirgi 5") as f3:
    oxirgi = deque(soxta_fayl(K), maxlen=5)
print(f"  {f3}")

assert eng_kattalar1 == eng_kattalar2
print(f"""
  Natija: {eng_kattalar2}

  ⭐ heapq.nlargest {f1.tepa / max(f2.tepa, 1):,.0f}x kam xotira —
     u faqat 5 ta elementni ushlab turadi.
""")


print("\n=== 4. Xotira sizishi (leak) namunasi ===\n")

print("""  ⚠️ Keng tarqalgan sabab: keraksiz havolalarni saqlash""")

KESH = {}


def qayta_ishla_yomon(malumot):
    """❌ Butun kirishni keshda saqlaydi."""
    natija = sum(malumot)
    KESH[id(malumot)] = malumot         # ⚠️ havola qoladi!
    return natija


def qayta_ishla_yaxshi(malumot):
    """✅ Faqat natijani saqlaydi."""
    natija = sum(malumot)
    KESH[id(malumot)] = natija
    return natija


for nom, funksiya in [("❌ butun ro'yxat keshda", qayta_ishla_yomon),
                      ("✅ faqat natija keshda", qayta_ishla_yaxshi)]:
    KESH.clear()
    tracemalloc.start()
    for _ in range(20):
        funksiya(list(range(10_000)))
    _, tepa = tracemalloc.get_traced_memory()
    tracemalloc.stop()
    print(f"  {nom:<34} {formatla(tepa):>10}")

KESH.clear()

print("""
  ✅ Yechimlar:
     • Faqat kerakli natijani saqlang
     • weakref.WeakValueDictionary — obyekt o'chsa kesh ham tozalanadi
     • functools.lru_cache(maxsize=N) — cheklangan kesh
     • Katta obyektdan keyin `del`
""")

Natijaning muhim qismi:

text
=== 1. Bir xil vazifa, turli yechim ===

  Usul                                   Xotira        Vaqt
  ──────────────────────────────────────────────────────────
  3 ta oraliq ro'yxat                   30.6 MB   1479.3 ms
  1 ta ro'yxat generatori                9.6 MB   1341.9 ms
  Generator ifodasi                     480.0 B    752.2 ms
  Oddiy sikl                            104.0 B   1313.2 ms

  ⭐ Generator 56,142x kam xotira ishlatdi.

=== 2. Sinf obyektlari: 100k yozuv ===

  Ifodalash                              Xotira        Vaqt
  ──────────────────────────────────────────────────────────
  Sinf (__dict__ bilan)                 13.0 MB    751.1 ms
  Sinf (__slots__)                       9.1 MB    820.3 ms
  dataclass(slots=True)                  9.1 MB    927.3 ms
  tuple                                 10.7 MB    994.0 ms
  dict                                  21.4 MB   1397.0 ms
  3 ta alohida ro'yxat (ustunli)         1.3 MB     46.9 ms

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


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

Noto'g'ri fikr To'g'risi
"getsizeof haqiqiy hajmni beradi" Faqat obyektning o'zini — ichidagilarni emas
"Ro'yxat hajmi elementlarga bog'liq" Faqat soniga — ko'rsatkichlar saqlanadi
"len(r) = ajratilgan joy" allocated ≥ len(r) — ortiqcha ajratish
"append doim bir xil tezlikda" Ba'zan qayta ajratish bo'ladi. O'rtacha O(1)
"Python ro'yxatni 2x kattalashtiradi" ~1.125x (CPython formulasi)
"clear() xotirani bo'shatmaydi" Bo'shatadi — 56 baytga qaytadi
"array doim yaxshiroq" Faqat bir turdagi son uchun; o'qish sekinroq
"deque — tezroq list" Chetlarda tez, indeksda sekin
"Generator har doim yaxshiroq" Bir marta o'tish uchun; len/indeks yo'q

6. Keng tarqalgan xatolar va yechimlari

1. Katta ro'yxatni butunlay xotiraga yuklash

python
qatorlar = open("katta.txt").readlines()    # ❌ butun fayl

with open("katta.txt") as f:                # ✅ birma-bir
    for qator in f:
        ...

2. Oraliq ro'yxatlar

python
a = [x for x in m]                          # ❌ 3 ta ro'yxat
b = [x * 2 for x in a]
c = [x + 1 for x in b]

c = [x * 2 + 1 for x in m]                  # ✅ bitta

3. list(...)[:n]

python
birinchi = list(katta_generator)[:10]       # ❌ hammasi

from itertools import islice                # ✅ faqat 10
birinchi = list(islice(katta_generator, 10))

4. getsizeof ga ishonish

python
sys.getsizeof(ichma_ich)                    # ❌ noto'g'ri
chuqur_hajm(ichma_ich)                      # ✅
tracemalloc                                 # ✅ professional

5. Navbat uchun list

python
navbat = []                                 # ❌ pop(0) — O(n)
navbat.pop(0)

from collections import deque               # ✅
navbat = deque()
navbat.popleft()

6. Ko'p obyekt, __slots__ siz

python
class Nuqta:                                # ❌ har biri ~40 bayt ortiq (3.14)
    def __init__(self, x, y): ...

class Nuqta:                                # ✅
    __slots__ = ("x", "y")

7. Keshda katta obyektlarni ushlab qolish

python
KESH[kalit] = katta_royxat                  # ❌ hech qachon bo'shamaydi

from functools import lru_cache             # ✅ cheklangan
@lru_cache(maxsize=128)
def hisobla(x): ...

8. Millionlab sonlarni list da

python
sonlar = list(range(10_000_000))            # ❌ ~400 MB

from array import array                     # ✅ ~40 MB
sonlar = array("i", range(10_000_000))

7. Integratsiya — bu bilim qayerda kerak bo'ladi

  • 6.1-dars (o'tilgan): amortizatsiyalangan O(1) — bu yerda sababi
  • 6.17-dars: generator ifodalari — xotira tejash
  • 4.11-dars (o'tilgan): satr o'zgarmasligi va interning
  • 8-qism: __slots__, dataclass(slots=True)
  • 15-qism: collections — deque, Counter, array
  • 11, 29-qismlar: tracemalloc, profillash, GC
  • 24-qism: numpy — ilmiy hisoblashlar

8. Eng yaxshi amaliyotlar

  1. Xotira muammosi bo'lmasa — list ishlating. Optimallashtirish o'lchashdan boshlanadi, taxmindan emas.

  2. Bir marta o'tish uchun generator. Ro'yxat faqat qayta o'tish, indeks yoki len kerak bo'lganda.

  3. getsizeof — sayoz. Haqiqiy hajm uchun tracemalloc yoki rekursiv funksiya.

  4. Navbat — deque, stek — list. pop(0) va insert(0) O(n).

  5. Bir turdagi millionlab son — array yoki numpy. 2-8x tejash.

  6. Ko'p obyekt — __slots__. dataclass(slots=True) eng qulay.

  7. Hajmi ma'lum bo'lsa list(...) yoki * n. Ortiqcha ajratish bo'lmaydi.

  8. Katta obyektdan keyin del. Havola yo'qolsa GC bo'shatadi.


9. Amaliy topshiriq

Vazifa 1: Natijani bashorat qiling

python
import sys
1.  sys.getsizeof([])
2.  sys.getsizeof([1, 2, 3]) == sys.getsizeof(['a'*1000, 'b', 'c'])
3.  sys.getsizeof(list(range(10))) == sys.getsizeof([x for x in range(10)])
4.  len([0] * 10) == (sys.getsizeof([0] * 10) - 56) // 8
5.  r = list(range(100)); r.clear(); sys.getsizeof(r)
6.  sys.getsizeof((x for x in range(10**9)))
Javoblar
  1. 56 — bo'sh ro'yxat, ajratilgan joy yo'q
  2. True — ko'rsatkichlar saqlanadi
  3. False — list(range()) aniq, generator ortiqcha ajratadi
  4. True — hajm oldindan ma'lum, zaxira yo'q
  5. 56 — clear() xotirani to'liq bo'shatadi
  6. ~200 — generator elementlar sonidan mustaqil

Vazifa 2: chuqur_hajm ni kengaytiring

2-misoldagi funksiyani yaxshilang:

  1. set va frozenset ni to'g'ri hisoblasin
  2. Rekursiv tsikllarni (a.append(a)) qayta ishlasin
  3. __slots__ li sinflarni qo'llab-quvvatlasin
  4. Natijani daraxt ko'rinishida chiqarsin (qaysi qism qancha joy oladi)

Vazifa 3: O'sish formulasini tekshiring

Dastur yozing:

  1. append bilan 10 000 elementgacha o'sishni kuzating
  2. Har bir qayta ajratishda ajratilgan qiymatini yozib boring
  3. CPython formulasi bilan solishtiring: (n + n>>3 + 6) & ~3
  4. Farq bo'lsa — nima uchun?

Vazifa 4: Tuzilmalar solishtiruvchisi

list, tuple, array, deque, set, dict uchun:

  1. 1M element xotirasi
  2. append / qo'shish tezligi
  3. in tekshiruvi tezligi
  4. Indeks bo'yicha murojaat tezligi
  5. Iteratsiya tezligi
  6. Natijani jadval + █ grafik ko'rinishida

Vazifa 5: Xotira profillovchi

XotiraOlchagich sinfini kengaytiring:

  1. tracemalloc.take_snapshot() bilan eng ko'p joy egallagan 5 qatorni ko'rsatsin
  2. Bir necha o'lchovni solishtirish (solishtir(*olchovlar))
  3. Chegaradan oshsa ogohlantirish (chegara=100 * 1024 ** 2)
  4. Dekorator sifatida ham ishlasin: @xotira_olcha

Vazifa 6: Katta fayl bilan ishlash

1M qatorli CSV bilan ishlash uchun dastur:

  1. Xotiraga sig'maydigan faylni bo'laklab qayta ishlash
  2. Ustunli saqlash (array bilan)
  3. Eng katta 100 ta qiymatni heapq bilan
  4. deque(maxlen=1000) bilan oxirgi 1000 ta qator
  5. Har bir usul uchun xotira o'lchovi

Vazifa 7: O'ylash

Nega CPython ro'yxatni 1.125x o'stiradi, ko'pchilik boshqa tillar esa 2x?

Javob

Bu — vaqt va xotira o'rtasidagi tanlov.

Nima o'zgaradi:

Koeffitsient Qayta ajratishlar (1M element) O'rtacha isrof
2.0 ~20 ~50%
1.5 ~35 ~25%
1.125 ~120 ~6%

Katta koeffitsient — kam qayta ajratish, ko'p isrof. Kichik — aksincha.

Nega CPython kichigini tanladi:

1. Ro'yxatlar juda ko'p va odatda kichik.

Tipik Python dasturida minglab kichik ro'yxat bo'ladi (funksiya natijalari, vaqtinchalik to'plamlar). Har birida 50% isrof — jami katta yo'qotish. 6% esa sezilmaydi.

2. realloc ko'pincha ko'chirishsiz kengaytiradi.

Qayta ajratish har doim ham "yangi joy ajratish + ko'chirish" degani emas. realloc ko'pincha mavjud blokni joyida kengaytiradi (agar keyingi xotira bo'sh bo'lsa). Bu holda qayta ajratish deyarli tekin.

Kichik qadamlar — realloc ning joyida kengaytirish ehtimoli yuqoriroq.

3. Amortizatsiyalangan O(1) baribir saqlanadi.

Muhim narsa — o'sish geometrik bo'lishi (qo'shimcha emas). 1.125x ham geometrik. Konstanta kattaroq, lekin murakkablik sinfi bir xil.

1.125x:  jami ko'chirish ≈ 9n
2.0x:    jami ko'chirish ≈ 2n

9n va 2n — ikkalasi ham O(n).

4. +6 qo'shimchasi kichik ro'yxatlarni himoyalaydi.

Formula (n + n>>3 + 6). Kichik n da n>>3 deyarli 0, shuning uchun +6 hukmron: 0 → 4 → 8 → 16. Bu — samarali "kichik ro'yxatlar uchun katta qadam, kattalar uchun kichik foiz" strategiyasi.

Boshqa tillar nega 2x:

  • C++ std::vector — odatda 2x (libstdc++) yoki 1.5x (MSVC). Xotira arzon, ko'chirish qimmat deb hisoblanadi.
  • Java ArrayList — 1.5x.
  • Go slice — 2x kichik, 1.25x katta slice'lar uchun (CPython'ga o'xshash g'oya!).
  • Rust Vec — 2x.

Qiziq: Go ham katta massivlar uchun kichik koeffitsientga o'tadi — xuddi shu mulohaza bilan.

Xulosa: universal "to'g'ri" javob yo'q. CPython Python dasturlarining haqiqiy naqshlariga (ko'p kichik ro'yxat) moslashtirilgan. Bu — o'lchov asosidagi qaror, nazariy emas.

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


Xulosa

Bu darsda ro'yxatning xotiradagi ko'rinishini o'rgandik.

Eng muhim uch fikr:

  1. Ro'yxat — ko'rsatkichlar massivi. Hajm = 56 + 8 × ajratilgan. Elementlar hajmiga bog'liq emas — shuning uchun sys.getsizeof ichma-ich tuzilmalar uchun aldamchi.

  2. Ortiqcha ajratish append ni O(1) qiladi. CPython ~1.125x o'sadi (n + n>>3 + 6). Hajm oldindan ma'lum bo'lsa (list(range(n)), [0]*n) — aniq ajratiladi, isrof yo'q.

  3. list — universal, lekin yagona emas. Navbat uchun deque, bir turdagi sonlar uchun array/numpy, bir marta o'tish uchun generator, ko'p obyekt uchun __slots__.

Keyingi darsda tuple ni ko'ramiz: o'zgarmaslik, paketlash/ochish, list bilan farqi va nega u lug'at kaliti bo'la oladi.

Malumot tuzilmalari · 4-dars yakunlandi

6.4-dars: Ro'yxat va xotira

31 daqvaqt
0belgi
Keyingi dars: 6.5-dars: tuple — o'zgarmas ketma-ketlik
Telegram'da
Darsda xato koʻrdingizmi?

Izohlar · 0