ما هي ميزة استخدام عودة الذيل هنا؟

Question

لقد قرأت مقالات تصف كيف يمكن تقليل تعقيد الفضاء لـ Quicksort باستخدام النسخة العودية الذيل لكنني غير قادر على فهم كيف يكون الأمر كذلك. فيما يلي الإصداران:

QUICKSORT(A, p, r)
       q = PARTITION(A, p, r)
       QUICKSORT(A, p, q-1)
       QUICKSORT(A, q+1, r)


TAIL-RECURSIVE-QUICKSORT(A, p, r)
   while p < r
      q = PARTITION(A, p, r)
      TAIL-RECURSIVE-QUICKSORT(A, p, q-1)
      p = q+1

(مصدر - http://mypathtothe4.blogspot.com/2013/02/lesson-2-variations-on-quicksort-tail.html)

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

رمز الزائفة أعلاه مأخوذ من المقالة - http://mypathtothe4.blogspot.com/2013/02/lesson-2-variations-on-quicksort-tail.htmlالتفسير المقدم في المقالة يربكني أكثر -

أقسام Quicksort أبرز فرعية معينة وتتخلف عن التكرار مرتين ؛ واحد على المباراة اليسرى وواحد على اليمين. كل من هذه المكالمات العودية سوف تتطلب تيارها الفردي الخاص بمساحة المكدس. يتم استخدام هذه المساحة لتخزين متغيرات الفهرسة للمصفوفة على مستوى ما من العودية. إذا قمنا بتصوير هذا الأمر من البداية إلى نهاية التنفيذ ، فيمكننا أن نرى أن مساحة المكدس تتضاعف في كل طبقة.

فكيف يصلح كل هذا؟

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

لا أرى كيف تتضاعف مساحة المكدس في كل طبقة من التنفيذ في حالة وجود Quicksort العادية.

ملاحظة:- لا يوجد ذكر لتحسين التحويل البرمجي في المقالة.

Answer 1

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

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

إليك صفحة Wiki إذا كنت ترغب في مزيد من المعلومات حول كيفية عمل "حفظ المساحة" وإعادة استخدام المكدس فعليًا ، إلى جانب أمثلة: نداء الذيل

تحرير: لم أشرح كيف ينطبق هذا على Quicksort ، أليس كذلك؟ حسنًا ، يتم طرح بعض المصطلحات في هذه المقالة التي تجعل كل شيء مربكًا (وبعضها خطأ واضح). تقوم الوظيفة الأولى المعطاة (Quicksort) بإجراء مكالمة متكررة على اليسار ، ومكالمة عودية على اليمين ، ثم تخرج. لاحظ أن المكالمة العودية على اليمين هي آخر شيء يحدث في الوظيفة. إذا كان المترجم يدعم التحسين العودية الذيل (موضح أعلاه) ، فإن المكالمات اليسرى فقط تنشئ إطارات مكدس جديدة ؛ كل المكالمات الصحيحة فقط أعد استخدام الإطار الحالي. هذا يمكن أن ينقذ بعض إطارات المكدس ، ولكن لا يزال من الممكن أن تعاني من الحالة التي يخلق فيها التقسيم سلسلة من المكالمات حيث لا يهم تحسين عوائق الذيل. بالإضافة إلى ذلك ، على الرغم من أن المكالمات اليمنى تستخدم نفس الإطار ، إلا أن المكالمات اليسرى تسمى داخل لا تزال المكالمات اليمنى تستخدم المكدس. في أسوأ الحالات ، يكون عمق المكدس N.

النسخة الثانية الموصوفة ليس ذيل العودية السريعة ، ولكن بالأحرى مدونة سريعة حيث يتم الفرز الأيسر فقط بشكل متكرر ، ويتم الفرز الأيمن باستخدام الحلقة. في الواقع ، لا يمكن أن يكون هذا التحسين السريع (كما هو موضح سابقًا من قبل مستخدم آخر) هو تحسين عودة الذيل ، لأن المكالمة العودية ليست آخر شيء يتم تنفيذه. كيف يعمل هذا؟ عند تنفيذها بشكل صحيح ، تكون المكالمة الأولى إلى QuickSort هي نفس المكالمة اليسرى في الخوارزمية الأصلية. ومع ذلك ، لا تسمى أي مكالمات متكررة في الجانب الأيمن. كيف يعمل هذا؟ حسنًا ، تعتني الحلقة بذلك: بدلاً من فرز "اليسار ثم يمينًا" ، تقوم بفرز اليسار بمكالمة ، ثم يقوم بفرز اليمين باستمرار فقط يسار اليمين. إنه لأمر مثير للسخرية حقًا ، لكنه في الأساس مجرد فرز الكثير من اليسار بحيث تصبح الحقوق عناصر واحدة ولا تحتاج إلى فرزها. هذا يزيل بشكل فعال العودية الصحيحة ، مما يجعل الوظيفة أقل عودية (عودية زائفة ، إذا صح التعبير). ومع ذلك ، فإن التنفيذ الحقيقي لا يختار فقط الجانب الأيسر في كل مرة ؛ يختار أصغر جانب. الفكرة لا تزال هي نفسها. إنها تقوم بشكل أساسي فقط بإجراء مكالمة متكررة على جانب واحد بدلاً من كليهما. سيضمن اختيار الجانب الأقصر أن عمق المكدس لا يمكن أن يكون أكبر من Log2 (n) ، وهو عمق شجرة ثنائية مناسبة. وذلك لأن الجانب الأقصر سيكون دائمًا نصف حجم قسم الصفيف الحالي. لا يضمن التنفيذ الذي قدمته المقالة ذلك ، لأنه يمكن أن يعاني من نفس سيناريو الحالات الأكثر سوءًا لـ "اليسار هو الشجرة بأكملها". يقدم هذا المقال في الواقع شرحًا جيدًا لذلك إذا كنت على استعداد للقيام بالمزيد من القراءة: اختيار فعال وفرز جزئي على أساس Quicksort

Answer 2

الميزة ، النقطة الكاملة لإصدار "عودية/تكرارية مختلطة" ، أي إصدار يعالج المدى الفرعي عن طريق التكرار وآخر من التكرار ، هو أنه عن طريق اختيار أي من النطاقين الفرعيين للمعالجة بشكل متكرر يمكنك ذلك ضمان أن عمق العودة لن يتجاوز أبدًا log2 N, بغض النظر عن مدى سوء اختيار المحور.

ل TAIL-RECURSIVE-QUICKSORT الرمز الكاذب المقدم في السؤال ، حيث يتم إجراء المعالجة العودية أولاً عن طريق مكالمة متكررة حرفية ، يجب إعطاء المكالمة العودية أقصر المدى الفرعي. سوف يتأكد ذلك في حد ذاته من أن عمق العودة سيقتصر log2 N. لذلك ، من أجل تحقيق ضمان عمق التكرار ، يجب على الرمز على الإطلاق مقارنة أطوال النطاق الفرعي قبل تحديد المدى الفرعي الذي يجب معالجته عن طريق الاتصال العودية.

قد يبدو التنفيذ المناسب لهذا النهج على النحو التالي (استعارة رمز الكاذب كنقطة انطلاق)

HALF-RECURSIVE-QUICKSORT(A, p, r)
   while p < r
      q = PARTITION(A, p, r)
      if (q - p < r - q)
        HALF-RECURSIVE-QUICKSORT(A, p, q-1)
        p = q+1
      else
        HALF-RECURSIVE-QUICKSORT(A, q+1, r)
        r = q-1

ال TAIL-RECURSIVE-QUICKSORT لا يقوم Pseudocode الذي قدمته بتوفير أي محاولات لمقارنة أطوال النطاقات الفرعية. في مثل هذه الحالة ، لا يوفر أي فائدة على الإطلاق. ولا ، إنها ليست حقًا "عودية ذيل". لا يمكن تخفيض Quicksort إلى خوارزمية خلفية.

إذا قمت بإجراء بحث على Google على مصطلحات "Qsort Loguy Higuy" ، فستجد بسهولة عديدة من الحالات من تطبيقات Quicksort الشهيرة الأخرى (C standard Library Style) استنادًا إلى نفس الفكرة المتمثلة . يستخدم هذا التنفيذ لمنصات 32 بت على مجموعة واضحة من العمق القصوى البالغ 32 ~ على وجه التحديد لأنه يمكن أن يضمن أن عمق التكرار لن يزداد أبدًا. (وبالمثل ، ستحتاج منصات 64 بت تحتاج فقط إلى عمق مكدس قدره ~ 64.)

ال QUICKSORT الإصدار الذي يجعل مكالمتين متكررين حرفيين أسوأ بكثير في هذا الصدد ، لأن الاختيار السيئ المتكرر للمحور يمكن أن يجعله للوصول إلى عمق العودية العالية للغاية ، حتى إلى حد ما N في أسوأ الحالات. مع مكالمتين متكررتين ، لا يمكنك ضمان أن يكون عمق العودة محدودًا log2 N. قد يتمكن برنامج التحويل البرمجي الذكي من استبدال المكالمة الزائدة إلى QUICKSORT مع التكرار ، أي انعطف QUICKSORT الدخول الى حسابك TAIL-RECURSIVE-QUICKSORT, ، ولكن لن يكون ذكيًا بما يكفي لإجراء مقارنة طول المدى دون المدى.

Answer 3

ميزة استخدام قرار الذيل: = بحيث يقوم المترجم بتحسين الكود وتحويله إلى رمز غير متكرر.

ميزة الكود غير المتكرر على الرمز المتكرر: = الكود غير المتكرر يتطلب ذاكرة أقل لتنفيذها من العودية. هذا بسبب إطارات مكدس الخمول التي تستهلكها عودة.

هنا يأتي الجزء المثير للاهتمام:- على الرغم من أن المترجمين يستطيع النظرية أداء هذا التحسين ، فهي في الواقع لا. حتى المترجمين الواسعين مثل Dot-Net و Java لا يقومون بهذا التحسين.

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

لطفا أنظر:

1. https://stackoverflow.com/q/340762/1043824
2. لماذا لا .NET/C# تحسين عودة استدعاء الذيل؟
3. https://stackoverflow.com/a/3682044/1043824

Answer 4

يبدو أن هناك بعض الالتباس المفردات هنا.

الإصدار الأول هو الذيل ، لأن البيان الأخير هو مكالمة عودية:

QUICKSORT(A, p, r)
  q = PARTITION(A, p, r)
  QUICKSORT(A, p, q-1)
  QUICKSORT(A, q+1, r)

إذا قمت بتطبيق التحسين لعملية إعادة ذيل ، وهو تحويل العودية إلى حلقة ، فستحصل على الحلقة الثانية ، التي لم تعد مستنقعات التيل:

TAIL-RECURSIVE-QUICKSORT(A, p, r)
  while p < r
    q = PARTITION(A, p, r)
    TAIL-RECURSIVE-QUICKSORT(A, p, q-1)
    p = q+1

فائدة هذا هو أنه عادةً ما تحتاج إلى ذاكرة مكدس أقل. لماذا هذا؟ لفهم ، تخيل أنك تريد فرز مجموعة مع 31 عنصرًا. في حالة من غير المرجح للغاية أن تكون جميع الأقسام مثالية ، أي أنها تقسم الصفيف في الوسط ، سيكون عمق التكرار هو 4. في الواقع ، فإن الانقسام الأول سيؤدي الثالث اثنين من 3 عناصر ، وبعد فرز كل شيء الرابع.

لكن الأقسام نادراً ما تكون هذه مثالية. نتيجة لذلك ، لا تصل كل العواقب على قدم المساواة. في مثالنا ، قد يكون لديك بعض المستويات بعمق ثلاثة مستويات فقط ، وبعضها 7 أو أكثر (أسوأ حالة هو 30). من خلال القضاء على نصف التكرارات ، لديك فرصة عادلة لأن يكون عمق العودية القصوى أقل.

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

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

Answer 5

لا أعرف بالضبط ما إذا كان هذا هو المكان الصحيح لطرح هذا الشك أو كان ينبغي عليّ نشر سؤال جديد ولكن لدي شك مشابه تمامًا.

void print(int n) {
  if (n < 0) return;
  cout << " " << n;
// The last executed statement is recursive call
  print(n-1);
  print(n-1);
}

هل هذا الذيل متكرر؟

Answer 6

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

مثال: نسختنا -> يطبع n إلى 1

void fun(int n){
if(n==0)
return;
printf("%d\n",n);
fun(n-1)
}

بعد التحسين->

void fun(int n){
start:
if(n==0)
return;
printf("%d\n",n);
n=n-1;
goto start;
}

مزايا هذا التحسين: 1. يستخدم عدد قليل جدًا من الإطارات المكدس للمكالمات المتناثرة. 3. لا يوجد خطأ تجزئة أكثر هو C/C ++ ومكدس الفائض في Java.