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

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

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

خوارزمية O(n²) تعمل على 100 عنصر تجري 10,000 عملية. هذا فوري على أي جهاز. شغّل نفس الخوارزمية على 100,000 عنصر وستصل إلى 10 مليار عملية — دقائق أو ساعات بدلاً من أجزاء من الثانية. القفزة من n إلى n² لا تبدو خطيرة حتى يصبح n كبيراً، وهذا بالضبط السبب في أنها تمر عبر code review والاختبار المحلي.

مثال كلاسيكي: التحقق من المضاعفات باستخدام حلقة متداخلة.

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 وعلوم الكمبيوتر في Korra Studio.