Generator expressions — memory efficiency: Visual walkthrough

1.2.36 · D2 · Coding › Introduction to Programming (Python) › Generator expressions — memory efficiency

Pehli line se pehle, teen simple words jo hum baar baar use karenge:

Hum parent ke headline result tak pahunchenge: $M_{list} = O (n) versus M_{gen} = O (1)$ aur samjhenge ki isme har symbol kya kar raha hai.

Step 1 — "Ek item store karna" kitna cost karta hai

KYA. Ek box jo jagah leta hai usse ek naam dete hain. Item number $i$ ki space ko symbol $s_{i}$ kehte hain (padho: "ess-sub-eye"). Chhota $i$ ek label hai, jaise jersey number — $s_{1}$ pehle item ki space hai, $s_{2}$ doosre ki, aur aise hi aage.

YEH SYMBOL KYUN. Humein "ek item kitna bada hai" ke baare mein baat karni hai yeh pretend kiye bina ki sab items same size ke hain. Kuch numbers chhote hain, kuch bade; $s_{i}$ se har item ko apna sach sacha size milta hai.

PICTURE. Ek box, desk par rakha hua, us space ke saath labelled jo woh kha raha hai.

Figure — Generator expressions — memory efficiency

Step 2 — List HAR ek box ko ek saath stack karti hai

KYA. [x*x for x in range(n)] jaisi ek list comprehension turant poori run ho jaati hai. Item 1 produce karta hai, rakhta hai. Item 2 produce karta hai, rakhta hai. … Item $n$ produce karta hai, rakhta hai. Kuch bhi nahi pheka jaata.

KYUN. List ka promise hai "tum koi bhi item, kisi bhi waqt, kisi bhi order mein dekh sakte ho" (jaise L[0] ya L[999]). Yeh promise nibhaane ke liye uske paas koi choice nahi sab boxes ek saath hold karne ke sivay.

PICTURE. Desk ko left-to-right bharte hue dekho; laal box wahi hai jo abhi ban raha hai, lekin uske peechhe kale boxes kabhi nahi jaate.

Step 3 — Boxes jodo: list ki memory ek sum hai

KYA. List ki total memory = list ke apne "header" ki ek chhoti fixed cost (uska wrapper, length counter, etc.), plus har ek box ki space jo woh hold karta hai.

SUM KYUN, AUR ABHI KYUN? Ek sum ( $\sum$ , "yeh sab jodo" ka sign) bilkul wahi tool hai "ek contribution per box, saare boxes par." Hum ise precisely isliye use karte hain kyunki Step 2 ne dikhaya ki har box ruk jaata hai — toh har box contribute karta hai.

PICTURE. Step 2 ki stack, ek brace ke saath jo saare boxes ko ek bade total mein ikattha kar raha hai.

Agar har box roughly same size $s$ ka ho, toh sum bas $n \times s$ hai. Woh $n$ key hai: items double karo, memory double ho jaati hai. Hum is growth ko $O (n)$ likhte hain — dekho Big-O space complexity: " $O (n)$ " ka matlab hai " $n$ ke proportion mein badhta hai."

Step 4 — Generator stack karne se mana kar deta hai. Banao, do, bhool jao.

KYA. Ek generator expression (x*x for x in range(n)) eager ka ulta karta hai. Jab tum agla value maango toh woh: ek box compute karta hai, tumhe deta hai, aur agle box banane se pehle use discard kar deta hai. Yeh Lazy evaluation hai — tab compute karo jab maango, sirf jitna maanga.

WOH YEH KAR SAKTA HAI KYUN. Generator list se weaker promise karta hai: "tumhein har item ek baar milega, order mein, aur phir woh chala jaata hai." Kyunki woh kabhi random access ka promise nahi karta, usse kabhi purane boxes rakhne ki zaroorat nahi. (Yahi exact reason hai ki ek exhausted generator ko dobara iterate karna kuch nahi deta — parent ka steel-man.)

PICTURE. Laal box akela box hai desk par. Left mein dashed ghost box pichla item hai — pehle hi bhool gaya. Koi growing stack nahi hai.

Step 5 — Generator ke boxes jodo: sum collapse ho jaata hai

KYA. Wohi accounting lagao jaise Step 3 mein. Memory = fixed cost + (space per stored box) × (ek waqt mein stored boxes ki sankhya). Lekin Step 4 ne dikhaya ki ek waqt mein stored sankhya hamesha 1 hai.

YAHI POORA TRICK HAI. Step 3 mein multiplier $n$ tha. Yahan multiplier $1$ hai — yeh $n$ ki parwah bilkul nahi karta. $n$ par dependency total se gayab ho jaati hai.

PICTURE. Do desks side by side: list ki growing staircase versus generator ka single flat box jo kabhi nahi badhta.

Step 6 — Edge cases (kahaan story toot ti hai?)

Har honest derivation ko apne corner cases survive karne chahiye. Yeh chaar hain jo matter karte hain.

Case A — Empty input, $n = 0$ . List: [] phir bhi header $C$ cost karta hai (ek empty list ek real, agar chhota, object hai). Generator: phir bhi $C_{gen}$ cost karta hai. Dono yahan $O (1)$ hain — koi box nahi, koi difference nahi. Gap tab hi khulta hai jab $n$ badhta hai.

Case B — Tumhein genuinely ek waqt mein sab items chahiye (jaise sort, reverse, len). Toh generator tumhein koi advantage nahi deta — kyunki sort karne ke liye sab kuch hold karna padta hai, toh tum list(gen) call karoge aur $O (n)$ pay karoge anyway. Jeet sirf tab milti hai jab tum items one-pass, order mein consume karo (sum, for, any, next).

Case C — Ise do baar consume karna. Ek full pass ke baad generator exhausted ho jaata hai — recipe range(n) ke end se aage nikal gayi. Doosra pass kuch nahi deta. Picture: printer ke pages khatam ho gaye. Fix: generator rebuild karo, ya list store karo agar tumhein sach mein repeats chahiye.

Case D — Tumne accidentally ise materialise kar diya. list(x for x in range(n)) ya sorted(gen) ya [*gen] sab silently poora stack rebuild karte hain — tum $O (n)$ par wapas aa gaye. Parentheses ne kuch nahi bachaya agar tumne turant use list mein daal diya.

Ek picture mein summary

Ek canvas par poori derivation: list ki memory ek rising staircase hai (har naye item se ek box add hota hai, toh total $\propto n$ , yaani $O (n)$ ), jabki generator ki memory ek flat red line hai jo bottom se chipki rehti hai (ek baar mein ek box, toh total constant, $O (1)$ ). Unke beech ka vertical gap hi woh memory hai jo tum bachate ho — aur yeh $n \to \infty$ ke saath bina kisi limit ke badhta rehta hai.

Recall Feynman retelling — plain words mein poora walkthrough

Ek box kuch space cost karta hai (Step 1). Ek list har box banati hai aur kisi ko bhi nahi phenkti, toh boxes ek staircase mein pile ho jaate hain — tum unke saare sizes ko sum karte ho aur total badhta jaata hai jinke saath kitne hain, $O (n)$ (Steps 2–3). Ek generator ek lazy printer hai: ek page print karta hai, deta hai, bhool jaata hai, phir agla print karta hai — toh kisi bhi waqt desk par exactly ek box hota hai plus ek tiny recipe jo kehti hai "aage kya hai." Jab tum wohi sum karte ho, "ek waqt mein kitne" bas $1$ hota hai, toh $n$ nikal jaata hai aur tumhare paas flat, constant cost reh jaati hai, $O (1)$ (Steps 4–5). Catches: ek empty list mein koi difference nahi, tum jeet nahi sakte agar tumhein sab kuch ek saath chahiye, generator ek pass ke baad khatam ho jaata hai, aur ise list() mein daalna poori staircase wapas le aata hai (Step 6). Woh akela missing $n$ hi poora magic hai.

Connections

Parent topic (Hinglish)
List comprehensions — Steps 2–3 ki eager staircase
Lazy evaluation — Step 4 ke peechhe "banao-phir-bhool-jao" principle
Iterators and the iterator protocol — jahan generator ki tiny recipe rehti hai
Generator functions and yield — same one-box idea use karne wala def/yield cousin
Big-O space complexity — summary figure ki $O (n)$ vs $O (1)$ language
Memory management in Python — boxes actually heap par kaise allocate hote hain

Visual walkthrough — Generator expressions — memory efficiency