Posts Tagged ‘optimization’

memoizing recursive functions

16/03/2010

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

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

هذا هو الكود الخاص بالوظيفه 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 إستدعاء فقط :D و إذا إستدعينا memFib مرة أخرى ستنادى نفسها مرة واحدة فقط لأن الناتج موجود فى ال cache .

كتاب O’Reilly even faster web sites

15/09/2009

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

oreilly even faster web sites

انتهيت من فتره من قراءه كتاب O’Reilly Even Faster Web Sites ، الكتاب ليس إصدار ثانى لكتاب O’Reilly high performance web sites من تأليف نفس الكاتب Steve Souders و لكنه يبدأ من حيث انتهى high performance web sites حيث يحتوى على الكثير من الابحاث و التكنيكات الجديده فى مجال كفاءه ال front-end ، ساعد فى تأليف الكتاب مع Steve Souders الكثير من الاسماء المعروفه فى مجال ال front-end ، مثل Douglas Crockford مكتشف لغه تبادل البيانات JSON الذى كتب الفصل الاول يتحدث فيه عن كفائه تطبيقات الاجاكس ، و الفصل الثانى كتبه Dion Almaer و Ben Galbraith اصحاب مدونه Ajaxian و تحدثوا فيه عن الإستجابه responsiveness و ال threading ، و الفصل الثالث كتبه Steve Souders يتحدث فيه عن كيفيه تأجيل تحميل وظائف الجافاسكربت عند استخدامها و إستخدام المطلوب منها فقط عند بدايه الوثيقه ، و الفصل الرابع تناول فيه Steve Souders كيفيه تحميل ملفات الجافاسكربت بالتوازى parallel download حيث ان طبيعه تحميل ملفات الجافاسكربت انها تمنع اى مورد من التحميل معها block download حتى تنتهى و تأثير ذلك على ترتيب تنفيذ كود الجافاسكربت Execution order و ال user experience ، و الفصل الخامس يتناول فيه Steve كيفيه ربط الكود ال inline ليتم تنفيذه فقط بعد تحميل الملفات الذى يعتمد عليها من الشبكه بالتوازى بدون عمل blocking و مثال على ذلك من مكتبه DoJo و مكتبه YUI ، و الفصل السادس يتناول فيه Steve تأثيركود الجافاسكربت ال inline على رسم الصفحه rendering و على ظهور تأثيرات ال CSS و الترتيب المناسب لملفات الجافاسكربت و ال CSS ، و الفصل السابع يتناول كيفيه كتابه كود جافاسكربت أسرع فى التنفيذ يكتبه Nicholas Zackas كاتب Wrox: JavaScript for Web developers ، و الفصل الثامن يتناول كفاءه تطبيقات ال comet او ماتعرف بالاجاكس العكسى حيث يبدأ السيرفر الطلب و ليس ال client و يستخدم فى التطبيقات التفاعليه و الreal time كتبه Dylan Schiemann الذى يرأس SitePen و مؤسس Dojo ، و الفصل التاسع يتناول به Tony Gentilcore مهندس بجوجل كيفيه تحسين الكفاءه للمستخدمين الذين لا يستطيعون الحصول على مميزات ال gzipping ، و الفصل العاشر يتناول تأثير الصور على كفاءه التطبيق و كيفيه تحسينها و تقليل حجمها و إستخدام ال CSS sprites و إستخدام command line لمعالجه الصور على السيرفر ديناميكا للحصول على اعلى جود و أصغر حجم يكتبه Nichole Sullivan صاحبه فكره ال CSS الموجه بالكائنات و Stoyan Stefanov مؤلف كتاب Object oriented JavaScript و الاثنين يعملان بياهو ، و الفصل الحادى عشر يتناول كيفيه إستخدام اكثر من دومين للحصول على اكثر من إتصال HTTP بالتوازى يكتبه Steve ، و الفصل التانى عشر يتحدث فيه Steve عن Chunked encoding و كيفيه استخدام ال buffer لزياده كفاءه تطبيقات الويب التى تعتمد على حجم بيانات كبير ، و الفصل التالت عشر يتحدث عن تأثير إستخدام ال iframes كتبه Steve ، و الفصل الرابع عشر يتحدث عن تأثير ال CSS selectors على كفاءه و سرعه اظهار العناصر renderning فى التطبيق و سبل كتابه CSS selectors اسرع و افضل و ال selectors التى يجب عليك تجنبها ، و فى نهايه الكتاب مرجع صغير عن الادوات التى تستخدم فى قياس الكفاءه .

أنص بشده قراءه هذا الكتاب ، فهو غنى جدا بالمعلومات و سيجعلك متقدما اكثر فى مجال ال front-end و ، و ان لم تقرأ كتاب O’Reilly High performance web sites فأنا انصحك ايضا بقرائته بشده ، لأن الكتاب الجديد يعتمد عليه فى بعض المناطق و به ابحاث و بعد التكنيكات الرائعه لترقيه كفاءه تطبيقات الانترنت .


Follow

Get every new post delivered to your Inbox.