אופטימיזציה של זיכרון
שיעור 12 מתוך 15 בקורס תכנות דינמי 101 של Coddy.
בתכנות דינמי, אנו משתמשים לעיתים קרובות בטבלה או במטריצה כדי לאחסן פתרונות לתת־בעיות. עם זאת, במקרים מסוימים הטבלה עלולה להיות גדולה מדי ולצרוך יותר מדי זיכרון. כאן נכנסת לתמונה אופטימיזציית זיכרון. טכניקות לאופטימיזציית זיכרון משמשות להפחתת כמות הזיכרון הנדרשת לפתרון בעיית תכנות דינמי.
טכניקה פופולרית אחת לאופטימיזציית זיכרון היא שימוש במערכים מתגלגלים, הידועים גם כמערכים מחליקים. במקום לאחסן את הטבלה כולה, בכל פעם מאוחסן רק חלק ממנה, והערכים הקודמים מושלכים עם חישובם של ערכים חדשים. כך אפשר להפחית באופן משמעותי את כמות הזיכרון הנדרשת לפתרון בעיה.
אתגר
קשהבאתגר הזה ניתן לך מערך של מספרים שלמים. המשימה שלך היא למצוא את האורך של תת־הסדרה העולה הארוכה ביותר (LIS) במערך. תת־סדרה עולה היא סדרה של מספרים במערך שבה כל מספר גדול מהמספר הקודם. LIS היא תת־הסדרה הארוכה ביותר מסוג זה. עליך לממש את הפתרון באמצעות טכניקות לאופטימיזציה של השימוש בזיכרון.
נסו בעצמכם
def lis_length(arr):
# כתבו כאן קודכל השיעורים ביחידה תכנות דינמי 101
תרגלו בעצמכם: קומפיילר Python אונליין