قراءة الكود لمعدلات النمو
مراجعة الكود للصحة مقابل مراجعة الكود للتعقيد
تلتقط مراجعة الكود للصحة أخطاء المنطق: شروط خاطئة، مؤشرات غير صحيحة بمقدار واحد، فحوصات null مفقودة. تلتقط مراجعة الكود الواعية بالتعقيد فئة مختلفة من العيوب: كود يعمل بشكل صحيح عند N = 100 لكنه ينمو بشكل كارثي عند N = 100000.
يرتبط هذا الدرس بتحقيق أعمق في دورة unhamming: الفصل المفقود: التعقيد الخوارزمي يغطي Big O في سياق العيوب الإنتاجية، و MOAD-0001: العيب الرسوبي يعين النمط عبر 60+ نظام برمجيات.
استكشافان للمراجعة
الحلقات المتداخلة تضاعف التعقيد. حلقتان متداخلتان على N عنصر تنتج O(N²). ثلاث تنتج O(N³). عند المراجعة: احسب عمق التداخل أولاً.
حاوية تسلسلية داخل حلقة ساخنة. أي فحص .contains() أو .includes() أو .find() أو in list داخل حلقة يكلف O(N) لكل فحص. على N تكرار: O(N²) الإجمالية. يظهر هذا النمط في كود الإنتاج عبر عشرات الأنظمة — مترجم GHC Haskell و Python pip و Apache Maven و Rust Cargo و TypeScript و Godot. نفس الخطأ، أنظمة أساسية مختلفة.
المراجعة: find_duplicates
راجع دالة Python التالية للتعقيد:
def find_duplicates(items):
seen = []
duplicates = []
for item in items:
if item in seen:
duplicates.append(item)
else:
seen.append(item)
return duplicatesMOAD-0001: العيب الرسوبي
نفس العيب، ستون نظام
يظهر النمط if x not in list: list.append(x) داخل حلقة — وقد ظهر — في كود الإنتاج عبر عشرات أنظمة البرمجيات:
- GHC (مترجم Haskell): محلل التبعيات، O(N²) عند N = 50000 حزمة، بناء مدته 17 دقيقة
- Python pip: دقة تضارب التبعيات
- Apache Maven: إزالة التكرار من المسار الفئوي
- Rust Cargo: توحيد الميزات
- مترجم TypeScript: دقة وحدة المعالجة
- محرك لعبة Godot / Redot: اجتياز مخطط العقدة
لم يرتكب أي من هذه الفرق خطأ. كتبوا كوداً صحيحاً عند N صغير. نما N. تصلب الكود. للنمط اسم: MOAD-0001، العيب الرسوبي. الرسوب: صحيح وغير ضار في الطبقات الرقيقة. بمرور الوقت، تتراكم الطبقات وتتصلب.
الإصلاح
في كل حالة: استبدل حاوية تسلسلية بحاوية hash. سطر واحد. لا تغيير سلوكي عند المدخلات الصحيحة. تسريع 100–1000× عند N الحقيقية.
يعمل الإصلاح لأن عمليتين تحتاج إلى البقاء سريعة:
1. فحص العضوية: هل تم رؤية هذا العنصر من قبل؟
2. الناتج المرتب: عودة العناصر بالترتيب الذي ظهرت فيه (مطلوب أحياناً، وأحياناً لا).
تعالج مجموعة (1) في O(1). إذا كانت (2) مهمة أيضاً، احتفظ بقائمة منفصلة للناتج المرتب ومجموعة لفحص العضوية. هيكلا بيانات، كل واحد يقوم بعمل واحد.
الرد على المراجع
طلب دمج يصلح MOAD-0001 في دالة اجتياز الرسم البياني الخاصة بمشروع. يعلق المراجع:
> "المجموعات لا تحافظ على ترتيب الإدراج — هذا يغير السلوك."
نمط التحليل في المقابلة
الصيغة المتوقعة
يظهر تحليل التعقيد الخوارزمي في مقابلات هندسة البرمجيات. الإجابة القوية تتبع نمطاً من أربعة أجزاء:
1. حالة التعقيد الحالي — O(?) للوقت، O(?) للمساحة.
2. اشرح لماذا — حدد البناء المحدد المسؤول (حلقة متداخلة، مسح خطي في حلقة، تفريع عودي).
3. اقترح تحسيناً — سمّ التغيير وهيكل البيانات أو الخوارزمية التي يقدمها.
4. حالة التعقيد الجديد — بعد الإصلاح، ما هو التعقيد الزمني والفضائي؟
مثال:
الكود: [دالة تفحص العضوية في قائمة داخل حلقة]
الحالي: O(N²) — `item in seen_list` هو O(N) لكل فحص × N تكرار
التحسين: استبدل seen_list بـ seen_set (مجموعة hash)
بعد: O(N) — فحص عضوية المجموعة هو O(1)تنقل هذه المهارة بما وراء المقابلات: مراجعة الكود الواعية بالتعقيد، تصميم العمارة، تصحيح الأداء، التدقيق الأمني. أي نظام يعالج مدخلات بأحجام متغيرة يستفيد من ذلك.
يرتبط هذا الدرس إلى الأمام بدورة unhamming، التي تطبق هذا النمط الدقيق على التحقيق في العيوب الإنتاجية عبر 60+ مشروع مفتوح المصدر.
المقابلة: تحليل has_common_element
طبّق صيغة المقابلة من أربعة أجزاء على هذه الدالة:
def has_common_element(list_a, list_b):
for item in list_a:
for other in list_b:
if item == other:
return True
return False