சரியான நேரத்தில் முடிவடையும் அல்காரிதம்கள்: ஒரு சிக்கலுக்கான குட் செக்

நீங்கள் ஒரு ফங்க்ஷன் எழுதுகிறீர்கள், உங்கள் টெஸ்ட் டேட்டாவில் இயக்குகிறீர்கள், அது சரியாக வேலை செய்கிறது. பிறகு அது production டேட்டாவுக்கு செல்கிறது — 500 க்குப் பதிலாக 500,000 வரிகள் — மற்றும் request timeout ஆகிறது. இது தொடர்ந்து நடக்கிறது, மேலும் இது கிட்டத்திட்ட எப்போதும் complexity சிக்கலாகவே இருக்கிறது, ஆனால் சிறிய அளவில் நியாயமாகத் தெரிந்த code க்குப் பின்னால் மறைந்துள்ளது.

உங்கள் laptop உங்களுக்கு ஏன் பொய் சொன்னது

ஒரு O(n²) அல்காரிதம் 100 பொருட்களில் இயங்கும் போது 10,000 operations செய்கிறது. அது எந்த machine -ல்ய் உடனடியாக உள்ளது. அதே அல்காரிதம்ை 100,000 பொருட்களில் இயக்குங்கள் மற்றும் நீங்கள் 10 பில்லியன் operations -ல் இருக்கிறீர்கள் — நிமிஷங்கள் அல்லது மணிநேரங்கள் மிலிசெக்கன்டுகளுக்குப் பதிலாக. n இலிருந்து n² -க்கான பாய்ப்பு n பெரிதாகும் வரை ஆபத்தாகத் தெரியாது, இதுவே code review மற்றும் local testing -க் মூலமாக அதை தவறவிட்ட பொதுவான காரணம்.

ஒரு classic உதாரணம்: nested loop -உடன் duplicates -க்கு சரிபார்ப்பு.

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²). அதை set -ஆக மாற்றவும்:

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

இப்போது இது O(n). Set lookups சராசரி O(1), எனவே முழு function நேரியல் கிட்டாக மாপடை quadratically -க்குப் பதிலாக. 10,000 பொருட்களில் இது கிட்டத்திட்ட 100 மில்லியன் comparisons -க்கும் 10,000 -க்குமுள்ள வேறுபாடு.

optimize -ுவதுக்கு முன்பே அளவிடவும்

অনুமானம் செய்யாதீர்கள். Microbenchmarks -க்கு timeit பயன்படுத்தவும்:

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

பெரிய functions -க்கு, cProfile -ஆல் profile செய்யவும்:

python -m cProfile -s cumulative myscript.py

cumtime column -ஐ பார்க்கவும். ஒரு function 90% runtime -ை சாப்பிட்டால், அது உங்கள் இலக்கு. bottleneck இல்லாத code -ை optimize -ுவது உங்கள் நேரத்ை வீணாக்கி சிக்கலையை சேர்க்கிறது எந்தப் பலனுக்கும் இல்லாமல்.

பொதுவான patterns இவை조용히் slow ஆக மாறுகிறது

Repeated list membership checks. if x in my_list ஒரு list -க்கு O(n) ஆனால் set அல்லது dict -க்கு சராசரி O(1). நீங்கள் ஒரு loop உள்ளே membership -க்கு சரிபார்த்தால், O(n) loop உள்ளே அந்த O(n) check உங்களுக்கு O(n²) overall கொடுக்கிறது. list -ை set -ஆக மாற்றுங்கள் மற்றும் நீங்கள் O(n) -ுக்கு திரும்பி வருகிறீர்கள்.

String concatenation ஒரு loop -ல். Python -ல், result += chunk ஒரு loop உள்ளே strings மூலமாக O(n²) worst case -ல் ஆகிறது ஏனெனில் strings immutable ஆகிறது மற்றும் ஒவ்வொரு concatenation முழு thing -ஐ copy செய்கிறது. ''.join(chunks) பயன்படுத்தவும் — இது string -ஐ ஒரு முறை build செய்கிறது.

Sorting நீங்கள் தேவையில்லாத போது. sorted() O(n log n). நீங்கள் ஒவ்வொரு iteration க்கு max அல்லது min செய்ய loop உள்ளே அதை அழைத்தால், max()/min() பயன்படுத்தவும் (O(n)) அல்லது மிக நன்றாக, ஒரு heap (heapq) நீங்கள் கடக்கும் extreme மீண்டும் மீண்டும் தேவை என்றால். heapq.nlargest(k, data) O(n log k), k சிறிய போது முழு list -ை sorting விட மிக மலிவு.

Recursive functions memoization இல்லாத. Naive recursive Fibonacci O(2ⁿ) ஏனெனில் அது ஒரே subproblems மீண்டும் மீண்டும் recomputes. functools.lru_cache சேர்க்கவும் மற்றும் அது O(n) -ுக்கு drop ஆகிறது:

from functools import lru_cache

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

Real code மூலமாக வேகமாக Big O பாடம்

Same input மூலமாக nested loops count செய்யுங்கள் — அது வழக்கமாக உங்கள் exponent. ஒரு single loop O(n). ஒரு loop உள்ளே ஒரு loop O(n²) inner loop -ై range தவிர்க்கவில்லை என்றால் (bubble sort -ை optimized form உள்ளே போல, இன்னும் O(n²) worst case ஆனால் குறைவு comparisons). Recursive calls அது problem -ை பாதியாக பிரிக்கிறது, binary search அல்லது merge sort போல், O(log n) அல்லது O(n log n) -க்கு point. Recursive calls இவை ஒவ்வொரு level -ல் multiple calls -க்கு branch, naive Fibonacci போல், exponential time -க்கு point — ஒரு strong signal நீங்கள் memoization அல்லது ஒரு iterative rewrite தேவை.

ஒரு நல்ல habit: nested loops அல்லது recursion user-facing data மூலமாக எழுதுவதுக்கு முன்பே, n production -ல் realistially என்ன இருக்கலாம் என்பதை கேட்கவும், உங்கள் test file -ல் இல்லை. n ஆறு புள்ளிவிவரங்களை தாக்குதல் செய்யக்கூடியது என்றால், ஒரு O(n²) solution -ु அதை ship செய்வதுக்கு முன்பே ஒரு இரண்டாவது look தேவை.

Complexity analysis, sorting algorithms மற்றும் profiling tools -ல் மேல், Korra Studio -ல் Python மற்றும் Computer Science segments check செய்யவும்.