العودية العامة - ما مدى خطورة ذلك؟ [مكرر

Question

تكرار ممكن:
هل العودية أسرع من الحلقات؟

لقد تدربت لأول مرة على البرمجة بجدية في C ، منذ حوالي 15 عامًا. أراد صاحب العمل رمزًا محسّنًا للغاية للمهام الصعبة الحسابية. أتذكر أنني ننصح أكثر من مرة بإعادة كتابة التكرار كحلقات ، حتى باهظة الثمن من قابلية القراءة ، من أجل تجنب "العودية النفقات". كما فهمت ذلك ، كان العودية النفقات العامة هو الجهد الإضافي اللازم لدفع البيانات إلى مكدس ثم إيقافها لاحقًا.

الآن أنا رمز في C ، Python ، Perl ، وأحيانًا جافا ، وأتساءل أحيانًا عن التكرارات. هل ما زال هناك شيء يمكن اكتسابه عن طريق إعادة كتابتهم؟ ماذا لو كانت علامات الذيل؟ هل جعل المجمعون الحديثون كل هذه القضايا موضع نقاش؟ هل مثل هذه المخاوف غير ذات صلة باللغات المفسرة؟

Answer 1

يمكن أن تؤدي العودية إلى أن تكون النفقات العامة الكبيرة إذا كانت نواة الوظيفة العودية أقل تكلفة من الناحية الحسابية من رمز إدخال/مخرج الوظيفة وتكلفة المكالمة نفسها. أفضل طريقة لمعرفة ذلك هي ببساطة نسختين من الكود - واحد متكرر ، وواحد لا.

ومع ذلك ، إذا كانت فكرتك عن تجنب التكرار هي صنع بنية تشبه المكدس بنفسك ، فاحترس - قد لا تكون بالضرورة أسرع من النهج المتكرر الأكثر وضوحًا. مرة أخرى ، التنميط هو صديقك.

أخيرًا ، تذكر أن وقت المبرمج أغلى من وقت وحدة المعالجة المركزية. قبل أن تقوم بتحسين الكود الخاص بك ، من الجيد حقًا قياس ما إذا كانت هذه مشكلة حقًا.

Answer 2

كانت جادة. تحتوي معظم اللغات التي رمزها على تكلفة حقيقية لمكالمات الوظائف (يمكن للمترجمين لهم عمومًا القيام بكرات الذيل وكذلك في بعض الأحيان لا تكون مشكلة).

هذه التكلفة ، وحقيقة أن المكدس ليس موردًا غير محدود ، عادة ما يجعلني أميل إلى استخدام العودية فقط للحالات التي أعرف فيها وجود حد للعمق الذي يمكن أن يذهب إليه.

على سبيل المثال ، أعرف أن البحث عن الأشجار الثنائية المتوازنة لن يذهب سوى خمسين مستوى عميقًا لإدخالات كربون واحد. ومع ذلك ، لن أستخدم:

def sum1through (n):
    if n == 0 return 0
    return n + sum1through (n-1)

منذ القيام بذلك من أجل n من عشرين مليون لن يكون صحية لكمة.

Answer 3

لا تزال القضية موجودة. يأخذ Recursion الكثير من مساحة المكدس ، حيث في كل مرة تدعوها الطريقة نفسها ، يتم إنشاء مؤشر لها ومتغيراتها المحلية مرة أخرى. عدد مكالمات الوظائف التي تم إجراؤها أثناء العودية يجعل استخدام الذاكرة O (n) ؛ بالمقارنة مع O (1) من وظيفة غير مرغوب فيها مثل الحلقات.

Answer 4

لا أعتقد أن أي من اللغات التي ذكرتها تطلب أن ينفذ النظام الأساسي/المترجم الذيل استدعاء القضاء. يمكنك العثور على لغات ذلك فعل تتطلب هذا التحسين - معظم اللغات الوظيفية لها هذا المطلب.

على الرغم من أن الشيء الآخر الذي تحتاج إلى مراعاته هو أن أجهزة الكمبيوتر أصبحت أوامر من الأحجام بشكل أسرع مما كانت عليه قبل 15 عامًا ، لذلك أصبح نادرًا الآن قبل ذلك قبل أن تقلق بشأن التحسينات الصغيرة. قد يتطلب برنامج قبل 15 عامًا تحسينًا دقيقًا لليد في Assembler للحصول على أداء لائق قد يعمل بسرعة على جهاز كمبيوتر حديث ، حتى لو كان مكتوبًا بلغة أعلى من المستوى مثل Java. هذا لا يعني أن الأداء لم يعد مشكلة بعد الآن - ولكن يجب أن تركز على اختيار الخوارزمية الصحيحة وعلى الكتابة قابلة للقراءة الشفرة. قم فقط بإجراء عمليات تحسين صغيرة بعد قياس الأداء ويمكنك أن ترى أن الكود المعني هو عنق الزجاجة.

شيء واحد أنت فعل يجب أن تقلق على الرغم من أن تفيض المكدس. إذا كان هناك أي خطر حدوث ذلك ، فقد يكون من المفيد إعادة كتابة وظيفة متكررة بطريقة تكرارية بدلاً من ذلك.

Answer 5

يقول الناس الكثير من الأشياء السخيفة عن الأداء.

1. اذا أنت بحاجة إلى تكرار ، مثل القيام بالمشي في الأشجار ، ثم تحتاجه ، لذا استخدمه.

2. قبل القلق بشأن أداء اى شى, ، اكتشف ما إذا كان لديك مشكلة وأين هي.
   مشكلات الأداء تشبه الرجال ورجال الحيل - فهي متخصصة في المكان الذي تتوقعه ، لذلك إذا كنت قلقًا بشأن شيء محدد مثل العودية ، فأنت مضمون تقريبًا للقلق بشأن الشيء الخطأ.

في رأيي ، فإن أفضل طريقة للعثور على مشاكل الأداء هي عن طريق أخذ عينات المكدس في وقت الحائط, ، و فحص العينات لمعرفة ما يفعله البرنامج, ليس فقط من خلال الحصول على القياسات والتساؤل ماذا تعني.

ومع ذلك ، إذا وجدت 10 ٪ أو أكثر من الوقت في مكالمة متكررة ، ولم يحدث شيء آخر داخل الروتين العودية ، ويمكنك أن تساعده ، ثم سيساعده على الأرجح.