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

تكتب دالة، وتشغلها على بيانات الاختبار الخاصة بك، وتعمل بشكل جيد. ثم تضرب بيانات الإنتاج — 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)) أو بشكل أفضل، كومة (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.