בקשר לשאלה מספר 1 - אתה צודק, השמירה על היחס הזה לא מבטיחה שתוכל לנצל מחדש זיכרון, אבל היא מעלה במידה ניכרת את ההסתברות לכך - לצורך העניין מעלה אותה מ-0 להסתברות גדולה מ-0 כלשהי
בקשר ל-2:
אוקי, אני אנסה להסביר בפשטות, עד כמה שניתן:
תחשוב שיש לך מערך בגודל התחלתי s כלשהו (הגודל עצמו לא רלבנטי במיוחד לצורך הדיון).
לצורך העניין נקרא לפקטור הגדילה שלנו g והוא בעצם נושא הדיון.
אז ככה:
בהתחלה יש לך מערך בגודל s. כאשר הוא מתמלא אתה מקצה מערך פי g יותר גדול ממנו ומקבל בלוק זיכרון בגודל g*s.
כאשר בלוק זה מתמלא גם הוא, אתה מקצה מחדש מערך בגודל [tex] g \cdot (g \cdot s) = g^2s [/tex].
מה שאתה רוצה, הוא מצב בו תוכל להכניס בחזרה את הבלוק השלישי לתוך הזיכרון ששוחרר מה-2 הקודמים!
כדי שזה יקרה, צריכה להתקיים המשוואה הבאה: [tex] s + g \cdot s = g^2 \cdot s [/tex]
שים לב ש-s מצטמטם ומתקבלת משוואה פשוטה יותר:
[tex]1 + g = g^2 [/tex]
ומשוואה זו נותנת לנו תנאי על g - שזה בדיוק מה שרצינו.
פתרון של משוואה זו הוא פתרון של משוואה ריבועית רגילה: [tex]g^2 - g - 1 = 0 [/tex]
ונתון ע"י נוסחא של פתרון משוואה ריבועית: [tex] g_{1,2} = \frac{1 \pm \sqrt{1 - 4 \cdot 1 \cdot (-1)}}{2 \cdot 1} = \frac{1 \pm \sqrt{1 + 4}}{2} [/tex]
מכיוון שפקטור הגדילה שלנו לא יכול להיות שלילי, הרי שיכול להתקבל רק הפתרון עם הפלוס ונקבל:
[tex] g = \frac{1 + \sqrt{5}}{2 } [/tex] שזהו בדיוק יחס הזהב.
עבור כל g הגדול מיחס זה, גודל הבלוק המוקצא הבא יהיה תמיד גדול יותר מהזיכרון שהיה בשימוש עד כה. עבור כל g קטן יותר, גודל הבלוק המוצקא הבא יהיה קטן יותר מסכום הזיכרון שהיה בשימוש עד כה, ולכן יוכל בסופו של דבר להיות מותאם לשם.
אגב, שים לב שלמשוואה המקורית ניתן להגיע לאחר כל מספר של הקצאות:
[tex] g ^ n \cdot s + g^{n+1} \cdot s = g^{n+2} \cdot s [/tex]
ואת המשוואה ניתן לצמצם ב-[tex] g^n \cdot s[/tex] ולחזור תמיד למשוואה המקורית - כלומר היחס ממשיך להיות נכון אחרי כל מספר של הקצאות
ראשי
צ'אט
24-01-2010, 19:00
מצב כלאיים
