take a memo

אחד הדברים הראשונים שלומדים בתכנות הוא כיצד להשתמש במשתנה עזר כדי להחליף בין שני מספרים:

 //swap a & b

temp = a

a=b

b=temp

די פשוט. משתנה העזר בעצם יצר הגדיל את המקום, מה שמאפשר לנו להזיז את המשתנים במרחב בקלות. בשלב הבא האתגר הוא לעשות את אותו דבר בלי משתנה עזר. מה שמאפשר את זה זו טכניקה שנקראת xor swap שבצורה פשוטה נראית בערך כך:

//xor swap a & b

a=a+b

b=a-b

a=a-b

הצלחנו לחסוך את משתנה העזר בעזרת 3 פעולות חישוב.

השעשוע הקטן הזה ממחיש מאזן שניתן לראות בהמון רמות במערכות תוכנה – זיכרון לעומת כח חישוב. לעיתים קרובות ניתן להשתמש באחד מהם כדי לחסוך באחר והשאלה היא מה 'זול' יותר בסיטואציה נתונה. הדבר הזה קיים גם ברמת המיקרו של האלגוריתמים (לכל אלגוריתם יש סיבוכיות זמן וסיבוכיות מקום), ועד לרמת הארכיטקטורה של המערכת כולה, למשל שימוש במטמון אפליקטיבי.

טכניקה ידועה של אופטימיזציה בתכנות פונקציונאלי נקראת memoization. זוהי בעצם יכולת לעשות שימוש חוזר בתוצאות של ריצה של פונקציה (בהינתן שהארגומנטים זהים). בואו נראה דוגמא בשפת groovy:

def greet = {arg ->

    println 'running'

    return "hello ${arg}"

}

println greet("Joe")

println greet("Matt")

println greet("Joe")

def mem = greet.memoize()

println mem("Joe")

println mem("Matt")

println mem("Joe")

כאשר משתמשים בגרסה שכוללת memorization, הפונקציה לא צריכה לרוץ שוב עבור ערך שהיא כבר רצה עליו בעבר. הפונקציה דורשת כעת קצת יותר מקום בזיכרון (כדי לאחסן את התוצאות הקראיות הקודמות) אבל חוסכת זמן מעבד עבור ערכים שחושבו בעבר.

היופי של העניין הוא שהאופטימיזציה מוטמעת כחלק מהשפה (מגירסה 1.8), ושקופה הן לקוד שמממש את הפונקציה והן לקוד שמשתמש בה. כמובן שניתן לשלוט על כמות התוצאות שיש לשמור וכו'.

Avoid side effects

תנאי מקדים לשימוש בטכניקה הזו הוא לשמור על העקרונות הפונקציונאליים, כלומר להשתמש בה רק בפונקציות שמחשבות פלט עבור הקלט הנתון, ולא בפונקציות שעצם הפעולה שלהן משפיע על המצב החיצוני. אם לדוגמא ניתקל במחלקה כזו

Class flight{

int availableSeats=100

def book = {seats ->

                def confirmed = false;

                if (availablePlaces-places  >=  0){

                                confirmed=true

                                availeablePlaces -= places

                }

Return confirmed

}

המטודה book משנה ערך שמוגדר מחוץ לטווח שלה ולכן ברור שהיא איננה מתאימה לאופטימיזציה כזו (מה יקרה אם יקראו לה 3 פעמים עם הארגומנט 50?).

Memoizing javascript

בשפה גמישה ודינאמית כמו JS ניתן 'להלביש' יכולות של memoization אף על פי שזה לא מבנה שהוא חלק מהשפה. הדוגמא הבאה ממחישה זאת (למרות שזה לא המימוש הכי יעיל):

Function.prototype.memoize = function(){

    var self = this, cache = {};

    return function( arg ){

      if(arg in cache) {

        console.log('Cache hit for '+arg);

        return cache[arg];

      } else {

        console.log('Cache miss for '+arg);

        return cache[arg] = self( arg );

      }

    }

  }

function fib( x ) {

    if(x < 2) return 1; else return fib(x-1) + fib(x-2);

}

var fibTest = memoize(fib);

console.log(fibTest(40)); //run slow

console.log(fibTest(40)); //cached, returns immediately

קריאה רקורסיבית לסידרת פיבונצ'י לוקחת זמן רב, אבל הקריאה השנייה מוחזרת מהמטמון באופן מיידי. וריאציות נוספות, בנצ'מרקים ועוד ניתן למצוא בין היתר כאן וכאן.

כתיבת תגובה

הזינו את פרטיכם בטופס, או לחצו על אחד מהאייקונים כדי להשתמש בחשבון קיים:

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s