الخوارزميات التي تنتهي في الوقت المحدد: فحص التعقيد السريع

تكتب دالة وتشغلها على بيانات الاختبار فتعمل بشكل صحيح. ثم تصل إلى بيانات الإنتاج — 500,000 صف بدلاً من 500 — وينقطع الاتصال. يحدث هذا باستمرار، وهو تقريباً دائماً مشكلة تعقيد مختبئة خلف كود بدا معقولاً في الحجم الصغير.

لماذا خدعك جهاز الكمبيوتر الخاص بك

خوارزمية O(n²) تعمل على 100 عنصر تقوم بـ 10,000 عملية. هذا فوري على أي جهاز. شغّل نفس الخوارزمية على 100,000 عنصر وستصل إلى 10 مليارات عملية — دقائق أو ساعات بدلاً من الميلي ثانية. الانتقال من 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(1) في المتوسط، لذا تتسع الدالة بأكملها خطياً بدلاً من تربيعياً. على 10,000 عنصر هذا الفرق بين حوالي 100 مليون مقارنة و 10,000.

قس قبل أن تحسّن

لا تتخمّن. استخدم timeit للمقاييس الدقيقة:

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

للدوال الأكبر، استخدم الملف الشخصي مع cProfile:

python -m cProfile -s cumulative myscript.py

انظر إلى عمود cumtime. إذا استهلكت دالة واحدة 90% من وقت التشغيل، فهذا هو هدفك. تحسين الكود الذي ليس الاختناق يهدر وقتك ويضيف تعقيداً بدون فائدة.

الأنماط الشائعة التي تصبح بطيئة بصمت

فحوصات العضوية المتكررة في القوائم. if x in my_list هي O(n) للقائمة لكن O(1) في المتوسط للمجموعة أو قاموس. إذا كنت تفحص العضوية داخل حلقة، فإن فحص O(n) داخل حلقة O(n) يعطيك O(n²) الكلي. استبدل القائمة بمجموعة وستعود إلى O(n).

تسلسل النصوص في حلقة. في Python، result += chunk داخل حلقة على النصوص هي O(n²) في أسوأ الحالات لأن النصوص غير قابلة للتغيير وكل ربط ينسخ الكل. استخدم ''.join(chunks) بدلاً منها — فهي تبني النص مرة واحدة.

الفرز عندما لا تحتاج إليه. sorted() هي O(n log n). إذا كنت تستدعيها داخل حلقة فقط للعثور على الأقصى أو الأدنى في كل تكرار، استخدم max()/min() (O(n)) أو بشكل أفضل، heap (heapq) إذا كنت تحتاج الحد الأقصى أو الأدنى المتحرك بشكل متكرر. heapq.nlargest(k, data) هي O(n log k)، أرخص بكثير من فرز القائمة بأكملها عندما تكون k صغيرة.

الدوال العودية بدون memoization. Fibonacci العودية الساذجة هي O(2ⁿ) لأنها تحسب نفس المسائل الفرعية مراراً وتكراراً. أضف 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)

قراءة Big O من الكود الحقيقي بسرعة

عدّ الحلقات المتداخلة على نفس الإدخال — هذا عادةً ما يكون أسك الخاص بك. حلقة واحدة هي O(n). حلقة داخل حلقة هي O(n²) إلا إذا تقلص نطاق الحلقة الداخلية (كما في شكل bubble sort المحسّن، لا يزال O(n²) في أسوأ الحالات لكن مع مقارنات أقل). استدعاءات عودية تقسم المشكلة إلى النصف، مثل البحث الثنائي أو merge sort، تشير إلى O(log n) أو O(n log n). استدعاءات عودية تتفرع إلى استدعاءات متعددة في كل مستوى، مثل Fibonacci الساذجة، تشير إلى وقت أسي — إشارة قوية بأنك تحتاج memoization أو إعادة كتابة تكرارية.

عادة جيدة: قبل أن تكتب حلقات متداخلة أو عودية على بيانات تواجه المستخدمين، اسأل نفسك ما الذي يمكن أن تكون عليه n بشكل واقعي في الإنتاج، وليس في ملف الاختبار. إذا كانت n يمكن أن تصل إلى ستة أرقام، فإن حل O(n²) يحتاج نظرة ثانية قبل نشره.

لمزيد من المعلومات عن تحليل التعقيد وخوارزميات الفرز وأدوات الملف الشخصي، اطّلع على أقسام Python وComputer Science على Korra Studio.