الدوال التكرارية ، وتدفقات المكدس ، ودمج الصادي

Question

لدي دالة تكرارية (في C #) أحتاج إلى الاتصال بها 800 مليون مرة ؛من الواضح أن هذا سيؤدي عادةً إلى تجاوز سعة المكدس بعد حوالي الاستدعاء رقم 900.لقد بدأت هذا في حلقات متعددة ، لكن النمط العودي أسهل بكثير وأكثر نظافة للمحافظة عليه.

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

هل لدى أي شخص خبرة في استخدام مُجمع y؟هل سأظل عالقًا في تجاوز سعة المكدس؟

خذ المثال البسيط للمضروب.عامل عاملي على معظم الأعداد الأكبر من مثل 5000 سيؤدي إلى تجاوز حجم المكدس.إذا استخدمت أداة دمج y بشكل صحيح في هذا السيناريو ، فهل ستعمل على إصلاح تجاوز سعة المكدس؟

لا يبدو أن التنفيذ تافهًا ، لذلك أريد أن أؤكده قبل أن أنفق جهود التطوير / الموارد في تنفيذ وتعلم أداة دمج y.

Answer 1

لا ، استخدام Y-combinator لن يساعد في وضعك.إذا كنت بحاجة إلى القيام بشيء 800 مليون مرة ، فيمكنك إما (أ) التكرار ، أو (ب) التكرار (أو أفترض (ج) كتابة 800 مليون مكالمة إلى وظيفتك).نظرًا لأن المدمج Y لا يتكرر ، يجب أن يتكرر.

الحلقة هي ما تبحث عنه ، إلا إذا كنت تستخدم بيئة وقت تشغيل توفر تكرارا ذيلًا مناسبًا (مثل المخطط).

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

Answer 2

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

Answer 3

يمكنك استخدام الترامبولين كما هو مستخدم في الامتداد التفاعلي ، لقد حاولت شرحه على مدونتي http://rohiton.net/2011/08/15/trampoline-and-reactive-extensions/

Answer 4

One solution is to convert your function(s) to use a loop and an explicit context data structure. The context represents what people generally think of as the call stack. You might find my answer to another question about converting to tail recursion useful. The relevant steps are 1 through 5; 6 and 7 are specific to that particular function, whereas yours sounds more complicated.

The "easy" alternative, though, is to add a depth counter to each of your functions; when it hits some limit (determined by experimentation), spawn a new thread to continue the recursion with a fresh stack. The old thread blocks waiting for the new thread to send it a result (or if you want to be fancy, a result or an exception to re-raise). The depth counter goes back to 0 for the new thread; when it hits the limit, create a third thread, and so on. If you cache threads to avoid paying the thread creation cost more often than necessary, hopefully you'll get acceptable performance without having to drastically restructure your program.