java - جاوا - تراكب مكدس من العودية العميقة في جاوة؟



جاوة الوجهات (7)

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

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

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

شكر.

https://ffff65535.com


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

-s مكدسة لزيادة حجم المكدس الأصلي أو

-oss مكدس لزيادة حجم مكدس Java ،

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

http://edocs.bea.com/wls/docs61/faq/java.html#251197

تصحيح:

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


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

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


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

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

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

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

لاحظ أن هذه الوظيفة لا تقيم أبداً ذيل القائمة. لذا فإن الوظيفة لا تحتاج في الواقع إلى إجراء مكالمة متكررة. في Haskell ، تقوم بإرجاع thunk للذيل بالفعل ، وهو ما يسمى إذا كان مطلوبًا. يمكننا القيام بنفس الشيء في Java (يستخدم هذا الفئات من 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 (). بينما يبدو بالتأكيد مثل العودية ، لا يتم إجراء استدعاء متكررة للخريطة ، ولكن يصبح جزءا من datastructure دفق.

هذا يمكن بعد ذلك أن تكون فاسدة مع منتظم للبناء.

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

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

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.

فيما يلي مثال على ذلك في Java. نعتذر عن كونه معتمًا بعض الشيء دون النظر إلى البنود 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 إلى تجمع مؤشر الترابط ، بإرجاع Promise ، وهو يشبه إلى حد كبير java.util.concurrent.Future ، فقط بشكل أفضل. انظر هنا. النقطة هي أن الطريقة أعلاه تطوى datastructure يمينية اليمين إلى اليمين في مكدس O (1) ، والتي تتطلب عادةً إلغاء الاستدعاء الذيل. ﻟذا ﻓﻘد ﺣﺻﻟﻧﺎ ﺑﺷﮐل ﻓﻌﺎل ﻋﻟﯽ TCE ، ﻓﻲ ﻣﻘﺎﺑل ﺑﻌض اﻟﺗﻌﻘﯾد. يمكنك استدعاء هذه الوظيفة على النحو التالي:

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

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

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

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 .


في حالة الكسوف إذا كنت تستخدم ، set- xss2m كوسائط vm.

أو

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

java -xss2m classname

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

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


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

فئة جافا -Xss8M


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())));
}




overflow