সময়মতো শেষ হওয়া অ্যালগরিদম: একটি কমপ্লেক্সিটি গাট চেক

আপনি একটি ফাংশন লেখেন, এটি আপনার টেস্ট ডেটায় চালান, এবং এটি ঠিক কাজ করে। তারপর এটি প্রোডাকশন ডেটায় চলে — ৫০০ এর পরিবর্তে ৫০০,০০০ সারি — এবং অনুরোধ টাইম আউট হয়। এটি ক্রমাগত ঘটে, এবং এটি প্রায় সবসময় একটি কমপ্লেক্সিটি সমস্যা যা ছোট স্কেলে যুক্তিসঙ্গত দেখাচ্ছে এমন কোডের পিছনে লুকানো আছে।

আপনার ল্যাপটপ কেন আপনাকে মিথ্যা বলেছে

এক্সটি ১০০ আইটেমে চলমান O(n²) অ্যালগরিদম ১০,০০০ অপারেশন করে। যেকোনো মেশিনে এটি তাৎক্ষণিক। ১০০,০০০ আইটেমে একই অ্যালগরিদম চালান এবং আপনি ১০ বিলিয়ন অপারেশনে আছেন — মিলিসেকেন্ডের পরিবর্তে মিনিট বা ঘন্টা। n থেকে n² এ জাম্প ততক্ষণ পর্যন্ত বিপজ্জনক অনুভব করে না যতক্ষণ না n বড় হয়, যা ঠিক কেন এটি কোড রিভিউ এবং লোকাল টেস্টিং এর মধ্য দিয়ে যায়।

ক্লাসিক উদাহরণ: নেস্টেড লুপ দিয়ে ডুপ্লিকেট চেক করা।

def has_duplicates(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

এটি O(n²)। এটিকে একটি সেটের সাথে স্ওয়াপ করুন:

def has_duplicates(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False

এখন এটি O(n)। সেট লুকআপগুলি গড়ে O(১), তাই সম্পূর্ণ ফাংশন লিনিয়ারলি স্কেল করে দ্বিঘাত পরিবর্তে। ১০,০০০ আইটেমে এটি প্রায় ১০০ মিলিয়ন তুলনার পরিবর্তে ১০,০০০ এর মধ্যে পার্থক্য।

অপ্টিমাইজ করার আগে পরিমাপ করুন

অনুমান করবেন না। মাইক্রোবেঞ্চমার্কের জন্য timeit ব্যবহার করুন:

import timeit
timeit.timeit(lambda: has_duplicates(list(range(5000))), number=10)

বড় ফাংশনের জন্য, cProfile দিয়ে প্রোফাইল করুন:

python -m cProfile -s cumulative myscript.py

cumtime কলাম দেখুন। যদি একটি ফাংশন ৯০% রানটাইম খায়, এটি আপনার লক্ষ্য। যে কোড বটলনেক নয় তা অপ্টিমাইজ করা আপনার সময় নষ্ট করে এবং কোন লাভের জন্য জটিলতা যোগ করে।

সাধারণ প্যাটার্ন যা চুপিসারে ধীর হয়ে যায়

পুনরাবৃত্ত লিস্ট মেম্বারশিপ চেক। if x in my_list একটি লিস্টের জন্য O(n) কিন্তু একটি সেট বা dict এর জন্য গড়ে O(१)। যদি আপনি একটি লুপের মধ্যে মেম্বারশিপ চেক করছেন, সেই O(n) চেক একটি O(n) লুপের মধ্যে আপনাকে সামগ্রিকভাবে O(n²) দেয়। লিস্টটিকে একটি সেটের সাথে স্ওয়াপ করুন এবং আপনি O(n) এ ফিরে যাবেন।

একটি লুপে স্ট্রিং কনক্যাটেনেশন। Python-এ, একটি স্ট্রিং লুপের উপর result += chunk সবচেয়ে খারাপ ক্ষেত্রে O(n²) কারণ স্ট্রিংগুলি অপরিবর্তনীয় এবং প্রতিটি কনক্যাটেনেশন সম্পূর্ণ জিনিসটি অনুলিপি করে। পরিবর্তে ''.join(chunks) ব্যবহার করুন — এটি স্ট্রিংটি একবার তৈরি করে।

বাছাই করা যখন আপনার প্রয়োজন নেই। sorted() হল O(n log n)। যদি আপনি প্রতিটি পুনরাবৃত্তি ম্যাক্স বা মিন খুঁজে পেতে একটি লুপের মধ্যে এটি কল করছেন, max()/min() (O(n)) ব্যবহার করুন বা আরও ভাল, একটি হিপ (heapq) যদি আপনার চলমান চরম প্রয়োজন হয়। heapq.nlargest(k, data) হল O(n log k), যখন k ছোট তখন সম্পূর্ণ লিস্টটি বাছাই করার চেয়ে অনেক সস্তা।

মেমোইজেশান ছাড়াই পুনরাবৃত্তিমূলক ফাংশন। নিষ্পাপ পুনরাবৃত্তিমূলক Fibonacci হল O(२ⁿ) কারণ এটি বারবার একই সাব-সমস্যা পুনর্গণনা করে। functools.lru_cache যোগ করুন এবং এটি O(n) এ ড্রপ করে:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

দ্রুত বাস্তব কোড অফ বিগ ও পড়া

এক্সপোনেন্ট অনুমান করতে একই ইনপুটের উপর নেস্টেড লুপ গণনা করুন। একটি একক লুপ হল O(n)। একটি লুপের মধ্যে একটি লুপ হল O(n²) যদি না অভ্যন্তরীণ লুপের পরিসীমা সঙ্কুচিত হয় (বাবল সর্টের অপ্টিমাইজড ফর্মের মতো, সর্বনিম্ন ক্ষেত্রে এখনও O(n²) কিন্তু কম তুলনা)। পুনরাবৃত্তিমূলক কল যা সমস্যাটি অর্ধেক ভাগ করে, যেমন বাইনারি সার্চ বা মার্জ সর্ট, O(log n) বা O(n log n) নির্দেশ করে। পুনরাবৃত্তিমূলক কল যা প্রতিটি স্তরে একাধিক কলে শাখা করে, যেমন নিষ্পাপ Fibonacci, সূচক সময় নির্দেশ করে — একটি শক্তিশালী সংকেত যে আপনার মেমোইজেশন বা একটি পুনরাবৃত্তিমূলক পুনর্লেখা প্রয়োজন।

এক ভাল অভ্যাস: আপনি ব্যবহারকারী-সম্মুখীন ডেটার উপর নেস্টেড লুপ বা পুনরাবৃত্তি লেখার আগে, প্রোডাকশনে n বাস্তবিকভাবে কি হতে পারে তা জিজ্ঞাসা করুন, আপনার টেস্ট ফাইলে নয়। যদি n ছয় পরিসংখ্যা হিট করতে পারে, একটি O(n२) সমাধান এটি শিপ করার আগে একটি দ্বিতীয় চেহারা প্রয়োজন।

কমপ্লেক্সিটি বিশ্লেষণ, সর্টিং অ্যালগরিদম এবং প্রোফাইলিং টুলস সম্পর্কে আরও জানার জন্য, Korra Studio-তে Python এবং Computer Science সেগমেন্ট দেখুন।