6.4-dars: Ro'yxat va xotira
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?
import sys
print(sys.getsizeof([])) # 56
print(sys.getsizeof([1])) # 64
print(sys.getsizeof([1, 2, 3])) # 88
print(sys.getsizeof(list(range(1000)))) # 8056Sonlar mantiqli ko'rinadi. Lekin:
r = []
for i in range(10):
r.append(i)
print(len(r), sys.getsizeof(r))1 88 ← bo'sh ro'yxat 56 edi, 1 element qo'shildi → 88?!
2 88
3 88
4 88
5 120Nega bir necha element qo'shilganda hajm o'zgarmaydi, keyin sakraydi?
Va eng muhimi:
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.getsizeofnima o'lchaydi va nimani o'lchamaydi- Chuqur hajm hisoblash
listo'rniga:array,bytearray,deque,numpy- Xotira tejash usullari
2. Nazariya — chuqur tushuntirish
2.1. PyListObject — ichki tuzilish
CPython'da ro'yxat quyidagicha ifodalanadi:
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:
sys.getsizeof([1, 2, 3]) # 88
sys.getsizeof(["a" * 10000, "b", "c"]) # 88 ← bir xil!2. ob_size (uzunlik) va allocated (ajratilgan) — turli narsalar.
len(r) # ob_size
# allocated — Pythondan to'g'ridan-to'g'ri ko'rinmaydi,
# lekin getsizeof orqali hisoblash mumkin:
allocated = (sys.getsizeof(r) - 56) // 83. Har bir element +8 bayt (64-bitli tizimda).
hajm = 56 (sarlavha) + 8 × allocated2.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):
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).
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 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
reallocko'pincha joyida kengaytira oladi (ko'chirishsiz)
2.3. Oldindan ma'lum hajm — ortiqcha ajratish yo'q
Agar Python hajmni oldindan bilsa, aniq ajratadi:
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 ← ortiqchaSabab: 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:
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'shadiCPython 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.
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:
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 hajmMuhim nozikliklar:
1. Bir xil obyekt ikki marta sanalmaydi:
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):
sys.getsizeof(1) # 28 bayt
# Lekin -5..256 oralig'idagi sonlar interpretator ishga tushganda
# yaratilgan — ro'yxatga qo'shganda yangi xotira ishlatilmaydi3. __slots__ bo'lmagan sinf obyektlari — __dict__ bilan:
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:
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 baytlarFarq: 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:
b = bytes(range(256)) # o'zgarmas
ba = bytearray(range(256)) # o'zgaruvchan
sys.getsizeof(ba) # ~313 (256 + sarlavha)collections.deque — ikki tomonlama navbat:
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:
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:
import numpy as np
a = np.arange(1_000_000, dtype=np.int32)
a.nbytes # 4_000_000numpy — 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.
# ❌ ~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)sys.getsizeof([x for x in range(1_000_000)]) # 8_448_728
sys.getsizeof((x for x in range(1_000_000))) # 20017-darsda generator ifodalarini batafsil ko'ramiz.
Generator bir marta ishlatiladi:
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):
class Nuqta:
__slots__ = ("x", "y") # __dict__ yo'q
def __init__(self, x, y):
self.x, self.y = x, y1M 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:
# ❌ 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:
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:
# ❌ 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:
katta_royxat = qayta_ishla()
natija = xulosa(katta_royxat)
del katta_royxat # havolani o'chirish → GC bo'shatadi3. Tez ma'lumotnoma
Hajm formulasi
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
sys.getsizeof([[0]*1000]*3) 88 — ko'rsatkichlar
chuqur_hajm(...) haqiqiy hajm (rekursiv)
tracemalloc professional profillashMuqobillar
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) xotiraTejash
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 keyin4. Batafsil misollar
Misol 1 — Xotira anatomiyasi
"""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:
=== 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
"""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 royxatNatijaning muhim qismi:
=== 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,244xNima ko'rsatdi: 2.5, 2.6, 2.7, 2.8-bo'limlar.
Misol 3 — Muqobil tuzilmalar
"""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:
=== 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.1Nima ko'rsatdi: 2.6-bo'lim.
Misol 4 — Amaliy: xotira profillovchi
"""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:
=== 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 msNima 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
qatorlar = open("katta.txt").readlines() # ❌ butun fayl
with open("katta.txt") as f: # ✅ birma-bir
for qator in f:
...2. Oraliq ro'yxatlar
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] # ✅ bitta3. list(...)[:n]
birinchi = list(katta_generator)[:10] # ❌ hammasi
from itertools import islice # ✅ faqat 10
birinchi = list(islice(katta_generator, 10))4. getsizeof ga ishonish
sys.getsizeof(ichma_ich) # ❌ noto'g'ri
chuqur_hajm(ichma_ich) # ✅
tracemalloc # ✅ professional5. Navbat uchun list
navbat = [] # ❌ pop(0) — O(n)
navbat.pop(0)
from collections import deque # ✅
navbat = deque()
navbat.popleft()6. Ko'p obyekt, __slots__ siz
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
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
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
Xotira muammosi bo'lmasa —
listishlating. Optimallashtirish o'lchashdan boshlanadi, taxmindan emas.Bir marta o'tish uchun generator. Ro'yxat faqat qayta o'tish, indeks yoki
lenkerak bo'lganda.getsizeof— sayoz. Haqiqiy hajm uchuntracemallocyoki rekursiv funksiya.Navbat —
deque, stek —list.pop(0)vainsert(0)O(n).Bir turdagi millionlab son —
arrayyokinumpy. 2-8x tejash.Ko'p obyekt —
__slots__.dataclass(slots=True)eng qulay.Hajmi ma'lum bo'lsa
list(...)yoki* n. Ortiqcha ajratish bo'lmaydi.Katta obyektdan keyin
del. Havola yo'qolsa GC bo'shatadi.
9. Amaliy topshiriq
Vazifa 1: Natijani bashorat qiling
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
56— bo'sh ro'yxat, ajratilgan joy yo'qTrue— ko'rsatkichlar saqlanadiFalse—list(range())aniq, generator ortiqcha ajratadiTrue— hajm oldindan ma'lum, zaxira yo'q56—clear()xotirani to'liq bo'shatadi~200— generator elementlar sonidan mustaqil
Vazifa 2: chuqur_hajm ni kengaytiring
2-misoldagi funksiyani yaxshilang:
setvafrozensetni to'g'ri hisoblasin- Rekursiv tsikllarni (
a.append(a)) qayta ishlasin __slots__li sinflarni qo'llab-quvvatlasin- Natijani daraxt ko'rinishida chiqarsin (qaysi qism qancha joy oladi)
Vazifa 3: O'sish formulasini tekshiring
Dastur yozing:
appendbilan 10 000 elementgacha o'sishni kuzating- Har bir qayta ajratishda
ajratilganqiymatini yozib boring - CPython formulasi bilan solishtiring:
(n + n>>3 + 6) & ~3 - Farq bo'lsa — nima uchun?
Vazifa 4: Tuzilmalar solishtiruvchisi
list, tuple, array, deque, set, dict uchun:
- 1M element xotirasi
append/ qo'shish tezligiintekshiruvi tezligi- Indeks bo'yicha murojaat tezligi
- Iteratsiya tezligi
- Natijani jadval +
█grafik ko'rinishida
Vazifa 5: Xotira profillovchi
XotiraOlchagich sinfini kengaytiring:
tracemalloc.take_snapshot()bilan eng ko'p joy egallagan 5 qatorni ko'rsatsin- Bir necha o'lchovni solishtirish (
solishtir(*olchovlar)) - Chegaradan oshsa ogohlantirish (
chegara=100 * 1024 ** 2) - Dekorator sifatida ham ishlasin:
@xotira_olcha
Vazifa 6: Katta fayl bilan ishlash
1M qatorli CSV bilan ishlash uchun dastur:
- Xotiraga sig'maydigan faylni bo'laklab qayta ishlash
- Ustunli saqlash (
arraybilan) - Eng katta 100 ta qiymatni
heapqbilan deque(maxlen=1000)bilan oxirgi 1000 ta qator- 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 ≈ 2n9n 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:
Ro'yxat — ko'rsatkichlar massivi. Hajm =
56 + 8 × ajratilgan. Elementlar hajmiga bog'liq emas — shuning uchunsys.getsizeofichma-ich tuzilmalar uchun aldamchi.Ortiqcha ajratish
appendni 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.list— universal, lekin yagona emas. Navbat uchundeque, bir turdagi sonlar uchunarray/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.
Izohlar · 0
Izoh yozish uchun kiring.