memoizing recursive functions

السلام عليكم و رحمة الله تعالى و بركاته

فى الموضوع السابق ذكرت ان الوظيفة Fibonacci تنادى نفسها 21 الف و 890 مرة لتحسب رقم Fibonacci للرقم 20 ، و إذا ناديتها مرة أخرى لتحسب الرقم fibonacci للرقم 20 فإنها ستنادى نفسها 20 الف و 890 مرة أخرى و هذا بالطبع سيؤدى إلى تعطيل ال thread الرئيسى للتطبيق لفترة من الوقت و سيؤدى إلى user experience سىء للغاية ، الوظيفة fibonacci بطبيعة الحال هى وظيفة Idempotent بمعنى ان اعطيتها نفس المدخلات -العبارات-ستعطيك نفس النتائج فى كل مرة تنادى عليها ، يمكننا تخزين هذه النتيجة فى Cache و ربطها بالمدخل بحيث إذا ناديتها مرة أخرى بنفس المدخل ستحصل على النتيجة من ال Cache إذا كانت موجودة بدلا من ان تنادى نفسها 20,890 مرة لتحصل على النتيجة ، و بذلك يمكن تقليل عدد الاستدعائات من 20,890 إلى إستدعاء واحد فقط .

هذا هو الكود الخاص بالوظيفه fib اختصار ل fibonacci من الموضوع السابق :

function fib(n){
    if(n<2) return n;
    return fib(n-1) + fib(n-2);
};

و هذا هو الكود الخاص بالوظيفه memFib اختصارا ل memoized fibonacci بعد تطبيق ال memoization عليها ، الشرح يلى الكود :

//the memoized version of fibonacci
function memFib(n){
    if(!memFib.cache){
        memFib.cache = [0,1];
    }
    var result = memFib.cache[n];
    if(typeof result == "undefined"){
        result = memFib(n-1) + memFib(n-2);
        memFib.cache[n] = result;
    }
    return result;
};

السطر الثالث فى الكود السابق يقوم بفحص هل تم تعريف ال cache من قبل ك static property للوظيفة memFib ، إذا لم يكن تم تعريفه سيتم إعطاءه مصفوفة تحتوى على 0 و 1 و هى ال fibonacci number للرقم 0 و 1 ، اى ان ال key هو الرقم و ال value هو رقم fibonacci لهذ الرقم ، السطر السادس يتم إستخلاص رقم ال fibonacci للرقم n من ال cache ، إذا كان هناك رقم fibonacci سيتم إرجاعه من السطر 11 ، ان لم يكن هناك رقم fibonacci للرقم n سيتم حسابه فى السطر الثامن و سيتم تخزينه فى السطر التاسع فى ال cache لإستخدامه لاحقا ثم إرجاعه فى السطر 11.

و النتيجة لا توصف

الكود التالى يوضح كم مرة الوظيفة memFib و الوظيفة fib نادت نفسها لحساب ال fibonacci number لنفس الرقم بإستخدام الوظيفة howMany من الموضوع السابق :

howMany(fib, 10); // 176 calls
howMany(memFib, 10); // 18 calls
howMany(memFib, 10); // 1 call - result from [cache]

howMany(fib, 20); // 21,891 calls
howMany(memFib, 20); // 21 calls - [cache] used

howMany(fib, 15); // 1973 calls
howMany(memFib, 15); // 1 call - result from [cache]

howMany(fib, 9); // 109 calls
howMany(memFib, 9); // 1 call - result from [cache]

howMany(fib, 25); // 242785 calls
howMany(memFib, 25); // 11 calls [cache] used

هههههههههه تم تقليل 242,785 إستدعاء إلى 11 إستدعاء فقط و إذا إستدعينا memFib مرة أخرى ستنادى نفسها مرة واحدة فقط لأن الناتج موجود فى ال cache .

About these ads

الأوسمة: javascript, optimization, performance