Counter)¶

যে operation-গুলো সত্যিই ব্যবহার করবে — সবগুলো, cost আর gotcha সহ। Average cost ধরে নিচ্ছে Python-এর built-in hash (যেটা সাধারণ input-এর জন্য চমৎকার)।

এক নজরে cost table¶

Operation	Average	Worst	Comment
`d[k] = v` (insert/update)	O(1)	O(n)	Worst case শুধু adversarial collision বা resize-এর সময়
`d[k]` (lookup)	O(1)	O(n)	Key না থাকলে KeyError
`d.get(k, default)`	O(1)	O(n)	Miss হলেও exception নেই
`k in d` / `x in s`	O(1)	O(n)	List-এর বদলে set পছন্দ করার আসল কারণ
`del d[k]` / `s.discard(x)`	O(1)	O(n)	`s.remove(x)` miss-এ error দেয়; `discard` দেয় না
`d.pop(k, default)`	O(1)	O(n)	Lookup + delete + value ফেরত
`len(d)`	O(1)	O(1)	Size cache করা থাকে
`for k in d` (iterate)	O(n)	O(n)	Python 3.7+-এ insertion order
`d.setdefault(k, v)`	O(1)	O(n)	না থাকলে insert, তারপর current value ফেরত
`s1 & s2`, `s1 \\| s2`, `s1 - s2`	O(len)	—	Set algebra, set-এর size-এর সমানুপাতিক
`Counter(iterable)`	O(n)	—	এক pass-এ সব গোনা
`c.most_common(k)`	O(n log n)	—	Count দিয়ে sort করে (ছোট k-র জন্য ভেতরে heap দিয়ে O(n log k))

একটা সাধারণ list-এর সাথে তুলনা করো: x in my_list প্রতিবারই O(n)। Loop-এর ভেতরে সেটা হয়ে যায় O(n^2) — beginner code-এ সবচেয়ে common accidental slowdown।

dict operations¶

Insert আর update¶

d = {}
d["apple"] = 3        # insert
d["apple"] = 5        # update (same key, value overwritten)

Lookup: তিন রকম¶

d = {"apple": 5}

d["apple"]            # 5
d["pear"]             # KeyError!  use only when key MUST exist
d.get("pear")         # None       quiet miss
d.get("pear", 0)      # 0          miss with a default — perfect for counting

get দিয়ে বানানো counting idiom:

counts = {}
for x in [1, 2, 2, 3]:
    counts[x] = counts.get(x, 0) + 1
# {1: 1, 2: 2, 3: 1}

Delete¶

d = {"a": 1, "b": 2}
del d["a"]            # KeyError if absent
v = d.pop("b")        # removes AND returns 2
v = d.pop("z", None)  # safe pop with default → None

Iterate¶

d = {"a": 1, "b": 2}

for k in d:                 # keys
    ...
for v in d.values():        # values
    ...
for k, v in d.items():      # both — the one you want most often
    ...

setdefault — এক ধাপে insert-if-absent¶

groups = {}
groups.setdefault("fruit", []).append("apple")
groups.setdefault("fruit", []).append("pear")
# {'fruit': ['apple', 'pear']}

বারবার এটা করতে হলে defaultdict(list) একই কাজ আরো পরিষ্কারভাবে করে।

set operations¶

s = set()
s.add(3)              # insert
s.add(3)              # no-op (sets hold each value once)
3 in s                # True, O(1)
s.discard(99)         # no error even though absent
s.remove(3)           # KeyError if absent — prefer discard when unsure

a = {1, 2, 3}
b = {3, 4}
a & b                 # {3}        intersection
a | b                 # {1,2,3,4}  union
a - b                 # {1, 2}     difference
a ^ b                 # {1,2,4}    symmetric difference (in exactly one)

Order ঠিক রেখে de-duplicate করা (একটা classic):

def dedupe(items):
    seen = set()
    out = []
    for x in items:
        if x not in seen:
            seen.add(x)
            out.append(x)
    return out

dedupe([3, 1, 3, 2, 1])   # [3, 1, 2]

Counter operations¶

from collections import Counter

c = Counter("mississippi")
c["s"]                 # 4
c["z"]                 # 0   <- missing keys give 0, NOT KeyError. Huge convenience.
c.most_common(2)       # [('i', 4), ('s', 4)]

a = Counter("aab")     # {'a': 2, 'b': 1}
b = Counter("ab")      # {'a': 1, 'b': 1}
a - b                  # Counter({'a': 1})        subtraction drops zero/negative
a + b                  # Counter({'a': 3, 'b': 2})

a - b উত্তর দেয় "a-র এমন কী আছে যেটা b cover করতে পারে না?" — এক expression-এ একদম Ransom Note-এর প্রশ্নটাই।

20 সেকেন্ডে defaultdict¶

from collections import defaultdict

g = defaultdict(list)   # missing key → fresh []
g["x"].append(1)        # no 'if "x" not in g' dance
g["x"].append(2)        # {'x': [1, 2]}

cnt = defaultdict(int)  # missing key → 0
cnt["a"] += 1

সাবধান: শুধু g["typo"] পড়লেই key-টা default value সহ তৈরি হয়ে যায়। শুধু membership check করতে হলে "typo" in g ব্যবহার করো।

Pitfalls (দুইবার পড়ো)¶

1. Iterate করতে করতে mutate করা¶

d = {"a": 1, "b": 2}
for k in d:
    if d[k] == 1:
        del d[k]        # RuntimeError: dictionary changed size during iteration

Fix: একটা snapshot-এর উপর iterate করো।

for k in list(d):       # list(...) copies the keys first
    if d[k] == 1:
        del d[k]

2. Key হিসেবে unhashable type¶

d = {}
d[[1, 2]] = "x"         # TypeError: unhashable type: 'list'
d[(1, 2)] = "x"         # fine — tuples are immutable, hence hashable

নিয়ম: key-কে immutable হতে হবে। list → tuple, set → frozenset, dict → sorted item-দের tuple।

3. Key হিসেবে float¶

d = {0.3: "hit"}
d.get(0.1 + 0.2)        # None!  because 0.1 + 0.2 == 0.30000000000000004

Float-এ rounding error থাকে, তাই equality (এবং সেই সাথে hashing) চুপচাপ fail করে। Key হিসেবে ব্যবহার করো integer (scale বাড়িয়ে: dollar না, cent), Fraction, বা rounded string।

4. `is` বনাম `in` গুলিয়ে ফেলা¶

x in s membership টেস্ট করে (hashing ব্যবহার করে)। x is y identity টেস্ট করে (একই object কিনা)। Beginner-রা মাঝে মাঝে if x is in s লিখে ফেলে — সেটা syntax error; শুধু in-ই যথেষ্ট।

5. "Worst case হবেই না" ধরে নেওয়া¶

Competitive programming-এ adversary-রা এমন input বানাতে পারে যেটা পুরনো setup-এ Python-এর default string hash-এর নিচে collide করে। Built-in dict প্রতি run-এ string hashing randomize করে, তাই তুমি সুরক্ষিত; কিন্তু custom rolling hash-এর নিজস্ব randomization লাগে (দেখো patterns.md)।

Quick self-test¶

Loop-এর ভেতরে x in some_list কেন বিপজ্জনক? (প্রতিবার O(n) → মোট O(n^2)।)
Counter("aa")["b"] কী ফেরত দেয়? (0 — কোনো KeyError নেই।)
List কেন dict-এর key হতে পারে না? (Mutate করতে পারে, তাই তার hash মিথ্যা বলত।)
Iteration-এর সময় key delete করার নিরাপদ উপায় কী? (list(d)-এর উপর iterate করো।)

পরেরটা: patterns.md — এই operation-গুলোর উপর দাঁড়ানো named problem-solving pattern।