ממואיזציה

שיעור 4 מתוך 15 בקורס תכנות דינמי 101 של Coddy.

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

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

אפשר להשתמש גם ב-list כדי לממש ממואיזציה.

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

אתגר

קל

כתבו פונקציית Python בשם fib שמחשבת את מספר פיבונאצ'י ה-n באמצעות ממואיזציה.

השתמשו במילון memo כדי לאחסן את מספרי פיבונאצ'י שכבר חושבו.
לפני חישוב מספר פיבונאצ'י ה-n, בדקו אם הוא כבר חושב ונשמר ב-memo.
אם כן, החזירו את התוצאה השמורה במטמון. אחרת, חשבו את מספר פיבונאצ'י ה-n באמצעות נוסחת הנסיגה fib(n) = fib(n-1) + fib(n-2), ושמרו את התוצאה במילון לשימוש עתידי.