Repository navigation
Expand file tree
/
Copy pathcollections_modules.py
More file actions
208 lines (146 loc) · 5.55 KB
/
Copy pathcollections_modules.py
File metadata and controls
208 lines (146 loc) · 5.55 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
# '''
# collections module
# │
# ├── defaultdict(dict) → hash table + auto default
# ├── Counter(dict) → hash table + counting
# ├── OrderedDict(dict) → hash table + order tracking
# ├── deque → doubly-linked list
# └── namedtuple → immutable struct (like lightweight class)
# Python dict — the foundation
# All three (defaultdict, Counter, OrderedDict) are built ON TOP of dict. Python's dict internally uses a hash table.
# dict
# ├── defaultdict (dict + default factory)
# ├── Counter (dict + counting methods)
# └── OrderedDict (dict + insertion order tracking)
# d = {"name": "Deepak"}
# # Step 1: hash("name") → some integer like 2314567
# # Step 2: index = hash_value % table_size → position in array
# # Step 3: store ("name", "Deepak") at that position
# # Lookup: same process — hash key → find position → O(1)
# # That's why dict lookups are O(1) — it doesn't search through everything, it jumps directly to the position.
# defaultdict — what's different?
# Regular dict throws KeyError on missing key. defaultdict overrides one method — __missing__:
# '''
# # Regular dict internally:
# class dict:
# def __getitem__(self, key):
# if key not in self.data:
# raise KeyError(key) # crashes
# return self.data[key]
# # defaultdict internally:
# class defaultdict(dict):
# def __init__(self, factory):
# self.factory = factory # int, list, set, etc.
# def __missing__(self, key):
# value = self.factory() # creates default: int()=0, list()=[]
# self[key] = value # stores it
# return value # returns it
# counts = defaultdict(int)
# counts["apple"] += 1
# # Behind the scenes:
# # 1. "apple" not found
# # 2. __missing__ called
# # 3. int() creates 0
# # 4. counts["apple"] = 0
# # 5. counts["apple"] += 1 → now it's 1
# '''
# Counter — what's different?
# Counter is a dict where values are always counts. It adds special methods on top:
# '''
# # Counter internally:
# class Counter(dict):
# def __init__(self, iterable):
# for item in iterable:
# self[item] = self.get(item, 0) + 1
# def most_common(self, n):
# return sorted(self.items(), key=lambda x: x[1], reverse=True)[:n]
# def __missing__(self, key):
# return 0 # missing key returns 0, not KeyError
# c = Counter(["a", "a", "b"])
# # Internally: {"a": 2, "b": 1}
# c["z"] # returns 0, no error (like defaultdict(int))
# # Counter also supports math:
# c1 = Counter(["a", "a", "b"])
# c2 = Counter(["a", "b", "b"])
# c1 + c2 # Counter({"a": 3, "b": 3})
# c1 - c2 # Counter({"a": 1})
# '''
# deque — completely different structure
# deque is NOT based on dict. It's a doubly-linked list internally.
# List (array):
# [1, 2, 3, 4, 5]
# ↑ inserting here shifts everything → O(n)
# Deque (doubly-linked list):
# None ← [1] ⇄ [2] ⇄ [3] ⇄ [4] ⇄ [5] → None
# ↑ insert here → just update pointers → O(1)
# Operation list deque
# ─────────────────────────────────
# append right O(1) O(1)
# pop right O(1) O(1)
# append left O(n) ❌ O(1) ✅
# pop left O(n) ❌ O(1) ✅
# access by index O(1) ✅ O(n) ❌
# Use deque when: you need fast operations on both ends (BFS, sliding window, rate limiter)
# Use list when: you need random access by index
# '''
# # BFS uses deque — popleft every iteration
# from collections import deque
# queue = deque([start_node])
# while queue:
# node = queue.popleft() # O(1) — fast!
# queue.append(neighbor)
# # With list this would be:
# queue = [start_node]
# node = queue.pop(0) # O(n) — slow!
# Exercise
logs = [
{"endpoint": "/products", "status": 200},
{"endpoint": "/users", "status": 500},
{"endpoint": "/products", "status": 200},
{"endpoint": "/orders", "status": 404},
{"endpoint": "/products", "status": 500},
{"endpoint": "/users", "status": 200},
{"endpoint": "/orders", "status": 500},
]
# def main():
# from collections import Counter
# endpointList = []
# for element in logs:
# endpointList.append(element["endpoint"])
# freq = Counter(endpointList)
# print(f"Task 1 : {dict(freq)}")
# from itertools import groupby
# data_sorted = sorted(logs, key=lambda x : x['status'])
# grouped_logs = {}
# for key, records in groupby(data_sorted, key=lambda x: x['status']):
# grouped_logs[key] = list(records)
# print(f"Task 2 : {grouped_logs}")
# print(f"Task 3 : {list(freq)[0]}")
# def main():
# from collections import Counter, defaultdict
# freq = Counter([log["endpoint"] for log in logs])
# print(f"Task 1 : {dict(freq)}")
# grouped = defaultdict(list)
# for log in logs:
# grouped[log['status']].append(log)
# print(f"Task 2 : {dict(grouped)}")
# print(f"Task 3 : {freq.most_common(1)[0][0]}")
# Task 1: Count how many times each endpoint was called
# Task 2: Group logs by status code
# Task 3: Find the most called endpoint
# deque
def main():
from collections import deque
queue = deque()
queue.append(1)
queue.append(1)
queue.append(2)
print(queue)
queue.append(5)
print(queue)
queue.appendleft(1)
print(queue)
queue.extendleft(queue)
print(queue)
queue.popleft()
print(queue)