تجاوزات المكدس من العودية العميقة في جافا؟

Question

بعد بعض الخبرة في اللغات الوظيفية، بدأت في استخدام التكرار بشكل أكبر في Java - ولكن يبدو أن اللغة تحتوي على مجموعة مكالمات ضحلة نسبيًا تبلغ حوالي 1000.

هل هناك طريقة لجعل مكدس الاستدعاءات أكبر؟هل يمكنني إجراء وظائف تتطلب ملايين المكالمات العميقة، كما هو الحال في Erlang؟

ألاحظ هذا أكثر فأكثر عندما أقوم بحل مسائل مشروع أويلر.

شكرًا.

Answer 1

وأعتقد أنك يمكن أن تستخدم هذه المعايير

<اقتباس فقرة>   

و-SS Stacksize لزيادة مواطن   حجم كومة أو

     

و-oss Stacksize لزيادة جافا   حجم المكدس،

     

ووأصلي حجم مكدس الافتراضي هو 128K،   مع قيمة الحد الأدنى من 1000 بايت.   حجم جافا كومة الافتراضي هو 400K،   مع قيمة الحد الأدنى من 1000 بايت.

http://edocs.bea.com/wls/docs61/ أسئلة وأجوبة / java.html # 251197

وتحرير:

وبعد قراءة التعليق الأول (Chuck's)، فضلا عن إعادة قراءة السؤال وقراءة الإجابات أخرى، مثل فما استقاموا لكم فاستقيموا لتوضيح أنني تفسير مسألة على أنها مجرد "حجم الزيادة كومة". لم أحدد تنوي أن أقول أنه يمكن أن يكون أكوام لا حصر له، كما هو الحال في البرمجة الوظيفية (نموذج البرمجة التي الصلع إلا اليسير سطحه).

Answer 2

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

حبة حمراء في متناول اليد؟حسنًا، بهذه الطريقة من فضلك.

هناك طرق يمكنك من خلالها استبدال المكدس بالكومة.على سبيل المثال، بدلاً من إجراء استدعاء متكرر داخل دالة، اطلب منها إرجاع ملف بنية البيانات البطيئة الذي يجعل المكالمة عند تقييمها.يمكنك بعد ذلك فك "المكدس" باستخدام Java for-construct.سأوضح مع مثال.خذ بعين الاعتبار رمز هاسكل هذا:

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = (f x) : map f xs

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

public <B> Stream<B> map(final F<A, B> f, final Stream<A> as)
  {return as.isEmpty()
     ? nil()
     : cons(f.f(as.head()), new P1<Stream<A>>()
         {public Stream<A> _1()
           {return map(f, as.tail);}});}

لاحظ أن Stream<A> يتكون من قيمة النوع A وقيمة النوع P1 وهو يشبه thunk الذي يُرجع بقية الدفق عند استدعاء _1().على الرغم من أن الأمر يبدو بالتأكيد مثل التكرار، إلا أنه لا يتم إجراء الاستدعاء التكراري للتعيين، ولكنه يصبح جزءًا من بنية بيانات الدفق.

يمكن بعد ذلك فك هذا من خلال البناء العادي.

for (Stream<B> b = bs; b.isNotEmpty(); b = b.tail()._1())
  {System.out.println(b.head());}

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

import fj.*; import fj.data.Natural;
import static fj.data.Enumerator.naturalEnumerator;
import static fj.data.Natural.*; import static fj.pre.Ord.naturalOrd;
import fj.data.Stream; import fj.data.vector.V2;
import static fj.data.Stream.*; import static fj.pre.Show.*;

public class Primes
  {public static Stream<Natural> primes()
    {return cons(natural(2).some(), new P1<Stream<Natural>>()
       {public Stream<Natural> _1()
         {return forever(naturalEnumerator, natural(3).some(), 2)
                 .filter(new F<Natural, Boolean>()
                   {public Boolean f(final Natural n)
                      {return primeFactors(n).length() == 1;}});}});}

   public static Stream<Natural> primeFactors(final Natural n)
     {return factor(n, natural(2).some(), primes().tail());}

   public static Stream<Natural> factor(final Natural n, final Natural p,
                                        final P1<Stream<Natural>> ps)
     {for (Stream<Natural> ns = cons(p, ps); true; ns = ns.tail()._1())
          {final Natural h = ns.head();
           final P1<Stream<Natural>> t = ns.tail();
           if (naturalOrd.isGreaterThan(h.multiply(h), n))
              return single(n);
           else {final V2<Natural> dm = n.divmod(h);
                 if (naturalOrd.eq(dm._2(), ZERO))
                    return cons(h, new P1<Stream<Natural>>()
                      {public Stream<Natural> _1()
                        {return factor(dm._1(), h, t);}});}}}

   public static void main(final String[] a)
     {streamShow(naturalShow).println(primes().takeWhile
       (naturalOrd.isLessThan(natural(Long.valueOf(a[0])).some())));}}

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

وفيما يلي مثال على ذلك في جافا.نعتذر عن أنه من الغموض بعض الشيء أن ننظر إليه بدون import static شروط:

public static <A, B> Promise<B> foldRight(final Strategy<Unit> s,
                                          final F<A, F<B, B>> f,
                                          final B b,
                                          final List<A> as)
  {return as.isEmpty()
     ? promise(s, P.p(b))
     : liftM2(f).f
         (promise(s, P.p(as.head()))).f
         (join(s, new P1<Promise<B>>>()
            {public Promise<B> _1()
              {return foldRight(s, f, b, as.tail());}}));}

Strategy<Unit> s مدعوم بتجمع مؤشرات الترابط، و promise تقوم الدالة بتسليم thunk إلى تجمع مؤشرات الترابط، مما يؤدي إلى إرجاع a Promise, ، وهو ما يشبه إلى حد كبير java.util.concurrent.Future, ، فقط أفضل. انظر هنا. النقطة المهمة هي أن الطريقة المذكورة أعلاه يطوي بنية بيانات متكررة إلى اليمين في مكدس O(1)., ، والذي يتطلب عادةً إزالة نداء الذيل.وبذلك نكون قد أنجزنا أشكال التعبير الثقافي التقليدي بشكل فعال، مقابل بعض التعقيد.يمكنك استدعاء هذه الوظيفة على النحو التالي:

Strategy<Unit> s = Strategy.simpleThreadStrategy();
int x = foldRight(s, Integers.add, List.nil(), range(1, 10000)).claim();
System.out.println(x); // 49995000

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

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

public final <B> Trampoline<B> foldRightC(final F2<A, B, B> f, final B b)
  {return Trampoline.suspend(new P1<Trampoline<B>>()
    {public Trampoline<B> _1()
      {return isEmpty()
         ? Trampoline.pure(b)
         : tail().foldRightC(f, b).map(f.f(head()));}});}

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

Answer 3

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

والأساس، ويجب عدم استخدام العودية غير محدود في اللغة التي لا بناء لذلك. سيكون لديك لاستخدام التكرار بدلا من ذلك، وأنا خائف. ونعم، وهذا يمكن أن يكون الألم بسيطا في بعض الأحيان: (

Answer 4

إذا عليك أن تسأل، وربما كنت تفعل شيئا الخطأ.

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

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

Answer 5

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

ومع العودية ذيل إعادة استخدام إطار كومة من الدالة التي يتم recursing، لذلك لم يكن لديك نفس القيود على المكدس.

Answer 6

ويمكنك تعيين هذا على سطر الأوامر:

وجافا الدرجة -Xss8M

Answer 7

وكلوجر، الذي يمتد على VM جافا، أود كثيرا لتنفيذ الأمثل دعوة الذيل، ولكنها لا تستطيع بسبب قيود في بايت كود JVM (أنا لا أعرف التفاصيل). ونتيجة لذلك، يمكن أن يساعد نفسه فقط مع "تتكرر" شكل خاص، الذي ينفذ عدد قليل من السمات الأساسية التي تتوقعها من العودية ذيل المناسبة.

وعلى أي حال، وهذا يعني أن JVM حاليا <م> لا يمكن دعم الدعوة ذيل الأمثل. أود أن أقترح بشدة بعدم استخدام العودية بوصفها بناء حلقات العام على JVM. رأيي الشخصي هو أن جافا ليست لغة عالية المستوى بما فيه الكفاية.

Answer 8

public static <A, B> Promise<B> foldRight(final Strategy<Unit> s,
                                          final F<A, F<B, B>> f,
                                          final B b,
                                          final List<A> as)
{
    return as.isEmpty() ? promise(s, P.p(b))
    : liftM2(f).f(promise(s, P.p(as.head())))
      .f(join(s, new F<List<A>, P1<Promise<B>>>()
        {
             public Promise<B> f(List<A> l)
             {
                 return foldRight(s, f, b, l);
             }
         }.f(as.tail())));
}

Answer 9

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

Answer 10

في الكسوف إذا كنت تستخدم، اضبط -xss2m كوسيطات vm.

أو

-xss2m مباشرة على سطر الأوامر.

java -xss2m classname