Python for AI/Data Structures আরও গভীরে/Lesson 14

Sorting ও Searching

sorted() আর key দিয়ে যেকোনো নিয়মে সাজানো, lambda-র প্রথম পরিচয়, min/max with key, আর binary search কেন এত দ্রুত।

সময়: 22 মিনিট
Exercise: 1
Challenge: 1
Quiz: 3 প্রশ্ন

সহজ ভাষায়

Sorting মানে নির্দিষ্ট নিয়মে সাজানো — ছোট থেকে বড়, বর্ণানুক্রমে, দাম অনুযায়ী। Searching মানে কোনো কিছু খুঁজে বের করা।

শুনতে সহজ, কিন্তু আসল প্রশ্ন হলো: কোন নিয়মে সাজাবো? আর বিশাল data-তে কত দ্রুত খুঁজবো?

কেন দরকার?

Leaderboard, top-10 product, সবচেয়ে বেশি বিক্রি — সবই sorting।
ML-এ: model-এর prediction-গুলো probability অনুযায়ী সাজিয়ে top-k উত্তর বের করা। Search engine আর recommendation system ঠিক এটাই করে।
RAG system-এ (Generative AI module) প্রশ্নের সাথে সবচেয়ে মিলে যাওয়া document খোঁজা — similarity score অনুযায়ী sort।

sorted() আর .sort()

main.py

marks = [72, 85, 90, 64]

print(sorted(marks))
print(sorted(marks, reverse=True))
print(marks)

marks.sort()
print(marks)

মনে আছে? sorted() নতুন list দেয়, .sort() মূল list-টাই বদলায়।

key: নিজের নিয়মে সাজানো

key হলো একটা function যেটা প্রতিটা item থেকে তুলনার মান বের করে দেয়:

main.py

words = ["banana", "Apple", "fig", "cherry"]

print(sorted(words))
print(sorted(words, key=str.lower))
print(sorted(words, key=len))

key=len হলে Python আসলে তুলনা করে:
"banana" -> 6    "Apple" -> 5    "fig" -> 3    "cherry" -> 6
তারপর এই সংখ্যাগুলো অনুযায়ী মূল শব্দগুলো সাজায়।

lambda: এক লাইনের ছোট function

key-তে প্রায়ই এমন function লাগে যেটা একবারই ব্যবহার হবে। পুরো def না লিখে lambda দিয়ে লেখা যায়:

main.py

def get_price(product):
    return product["price"]

products = [
    {"name": "Laptop", "price": 85000},
    {"name": "Mouse", "price": 450},
    {"name": "Monitor", "price": 18000},
]

print([p["name"] for p in sorted(products, key=get_price)])
print([p["name"] for p in sorted(products, key=lambda p: p["price"])])

lambda p: p["price"] মানে "p নাও, p["price"] return করো" — get_price-এর ছোট রূপ। Lambda নিয়ে বিস্তারিত পরের module-এ।

একাধিক নিয়মে সাজানো

key থেকে tuple return করলে প্রথমে প্রথম মান, সমান হলে দ্বিতীয় মান অনুযায়ী সাজায়:

main.py

students = [("Rafi", "CSE", 3.4), ("Mim", "EEE", 3.9), ("Tanvir", "CSE", 3.7)]

by_dept_then_cgpa = sorted(students, key=lambda s: (s[1], -s[2]))
for s in by_dept_then_cgpa:
    print(s)

-s[2] দিয়ে CGPA উল্টো (বড় থেকে ছোট) করেছি, department কিন্তু A→Z-ই আছে।

min / max with key

পুরোটা sort না করে শুধু সবচেয়ে বড়/ছোট চাইলে:

main.py

products = [("Laptop", 85000), ("Mouse", 450), ("Monitor", 18000)]

print(max(products, key=lambda p: p[1]))
print(min(products, key=lambda p: p[1]))

Searching

সাধারণ খোঁজা — একে একে দেখা (linear search):

main.py

cities = ["Dhaka", "Khulna", "Sylhet", "Rajshahi"]

print("Sylhet" in cities)
print(cities.index("Sylhet"))

ছোট list-এ এটাই যথেষ্ট। কিন্তু ১০ কোটি item-এ? প্রতিবার ১০ কোটি তুলনা।

Visual intuition: Binary Search

List যদি sorted থাকে, তাহলে অনেক চালাক উপায় আছে। অভিধানে শব্দ খোঁজার মতো — মাঝখানে খোলো, তারপর সামনে বা পেছনের অর্ধেকে যাও:

খুঁজছি 42:   [3, 8, 15, 23, 42, 57, 91]
ধাপ ১:  মাঝে 23  -> 42 বড়, ডান অর্ধেকে যাও   [42, 57, 91]
ধাপ ২:  মাঝে 57  -> 42 ছোট, বাম অর্ধেকে যাও   [42]
ধাপ ৩:  মাঝে 42  -> পেয়েছি!

প্রতি ধাপে অর্ধেক বাদ যায়। ১০ লাখ item → ~২০ ধাপ। ১০০ কোটি item → ~৩০ ধাপ!

Item সংখ্যা	Linear search (worst)	Binary search (worst)
১,০০০	১,০০০	১০
১০ লাখ	১০ লাখ	২০
১০০ কোটি	১০০ কোটি	৩০

Python-এ এটা বানানোই আছে bisect module-এ:

main.py

import bisect

scores = [3, 8, 15, 23, 42, 57, 91]
i = bisect.bisect_left(scores, 42)
print(i, scores[i] == 42)

Exercise

Top 3 student

+20 XP

students হলো (নাম, marks) tuple-এর list। marks অনুযায়ী বড় থেকে ছোট সাজিয়ে প্রথম তিনজনের নাম top_three list-এ রাখো।

solution.py

students = [("Rafi", 78), ("Mim", 92), ("Tanvir", 85), ("Nusrat", 88), ("Karim", 70)]

top_three = []

print(top_three)

Quiz

Q1sorted(["banana", "Apple", "cherry"])-এর ফলাফল কী?
['Apple', 'banana', 'cherry']['banana', 'cherry', 'Apple']['apple', 'banana', 'cherry']
Q2max(words, key=len) কী return করে?
সবচেয়ে বড় দৈর্ঘ্যের সংখ্যাটাসবচেয়ে লম্বা শব্দটাবর্ণানুক্রমে শেষের শব্দটা
Q3১০ লাখ item-এর sorted list-এ binary search সর্বোচ্চ প্রায় কতবার তুলনা করে?
প্রায় ২০ বারপ্রায় ১০০০ বারপ্রায় ৫ লাখ বার

0/3 answered

Challenge

Binary search নিজে লেখো

+50 XP

binary_search(items, target) function লেখো। items একটা sorted list। target পাওয়া গেলে তার index return করবে, না পেলে -1।

শর্ত: in, .index() বা একে একে সব item দেখা loop ব্যবহার করা যাবে না — প্রতি ধাপে খোঁজার জায়গা অর্ধেক করতে হবে।

solution.py

def binary_search(items, target):
    pass


print(binary_search([3, 8, 15, 23, 42, 57, 91], 42))
print(binary_search([3, 8, 15, 23, 42, 57, 91], 10))

বাস্তবে কোথায় ব্যবহার হয়?

একটা image classifier প্রতিটা class-এর জন্য probability দেয়। User-কে দেখাতে হবে top-3 prediction:

main.py

probs = {"cat": 0.62, "dog": 0.21, "fox": 0.09, "rabbit": 0.05, "bird": 0.03}

top3 = sorted(probs.items(), key=lambda kv: kv[1], reverse=True)[:3]
for label, p in top3:
    print(f"{label:<8}{p:.0%}")

ImageNet competition-এ model মাপা হতো "top-5 accuracy" দিয়ে — ঠিক উত্তর কি প্রথম ৫টার মধ্যে আছে? এটাই সেই হিসাব।

Interview প্রশ্ন

Beginner: sorted() আর list.sort()-এর পার্থক্য কী?
Intermediate: Python-এর sort কি stable? এর মানে কী, আর একাধিক নিয়মে sort করতে এটা কেন কাজে লাগে? (হ্যাঁ — সমান key-র item-গুলোর আগের ক্রম বজায় থাকে।)
Advanced: ১০০ কোটি item থেকে শুধু top-10 লাগলে পুরোটা sort করা কেন অপচয়? heapq.nlargest কীভাবে কাজ করে?

এরপর কী?

Data সাজালাম, খুঁজলাম — এখন সেটা সুন্দর করে দেখাতে হবে। Report, log, table — পরের lesson: String Formatting আরও গভীরে।