בעברית קוראים לזה תזכור (tizkur) ובהתחלה זה נראה כמו שגיאת כתיב של המילה memorization אבל זה זה לא. ומדובר במושג בעל חשיבות גדולה מאוד, בעיקר לתוכנה כמו פייתון שעקב האכילס שלה הוא מהירות הריצה של התוכניות. הדבר מוצא את ביטויו לעיתים קרובות כאשר מבקשים לבצע חישובים מורכבים או חישובים רקורסיביים, אשר חוזרים על עצמם פעמים רבות בתוך פונקציה אחת וגורמים לאיטיות בלתי נסבלת עד בלתי אפשרית של התוכנית. הרעיון התיאורטי הוא פשוט, אנו עורכים מילון של כל החישובים הארוכים שכבר ערכנו, ואם יש לנו במילון תוצאה של חישוב שכבר ערכנו, אנו לא מחשבים שוב ובכך חוסכים זמן ריצה ומשאבי זיכרון.
אם כך נראה איך זה עובד בפייתון בפועל - לשם כך ניקח פונקציה רקורסיבית (המופיעה גם במדריך שלנו) המחשבת את מספרי פיבונאצ'י (....1,1,2,3,5,8,13,21), הבעיה המתעוררת כאשר מריצים את מספר פיבונאצ'י מספר 35 בסדרה, המחשב נעשה כבד ובקושי זז, ונראה שהוא נתקף בעיות זכרון קשות. נראה את הפונקציה ולאחר מכן מה עושים כדי לשפר את המצב. n מייצג את מיקום מספר הפיבונאצ'י בסדרה, למשל כאשר n=6 אנו מתכוונים למספר השישי ברשימה כלומר 8 -
def fib(n): if n<3: return 1 else: return (fib(n-1)+fib(n-2))
למעלה אנו רואים פונקציה רקורסיבית המחזירה את הערך 1 לשני האיברים הראשונים בסדרה ולגבי האחרים מפעילה את אותה פונקציה באופן רקורסיבי פעמיים, (fib(n-1)+fib(n-2 כדי למצוא את המספר שלנו (ניתן לעיין במדריך בערך פונקציה רקורסיבית). בדרך הזאת יוצא לפונקציה שלנו fib לבצע שוב ושוב פעמים רבות את אותו החישוב שהיא כבר ביצעה, למשל היא תחזור המון פעמים על החישוב (fib(5 כאשר אנו מחפשים את (fib(30. כעת נראה איך אנו יכולים להכין מילון עם התוצאות שכבר חישבנו - כדי להתגבר על הבעיה-
fibonacci_mem={} def fib(n): if n in fibonacci_mem: return fibonacci_mem[n] if n<3: value=1 else: value=fib(n-1)+fib(n-2) fibonacci_mem[n]=value return value print(fib(950))
אנו רואים שיצרנו מילון בשם fibonacci_mem שהדבר הראשון שהפונקציה עושה היא לחפש האם יש בו את החישוב עבור מספר הפיבונאצ'י המבוקש, אם יש היא מחזירה אותו ואם אין היא מחשבת אותו כרגיל ולבסוף לפני שהיא מחזירה את הערך שחושב, היא מכניסה אותו למילון שלנו. זה הכל, כעת אנו יכולים לחשב מהו מספר הפיבונאצ'י מספר 950 באופן מיידי בלי לשאוב את הזכרון של המחשב שלנו ובלי להמתין לנצח. נזכיר שלפני כן נתקענו כבר במספר פיבונאצ'י מספר 35.
הדברים עד כדי כך חשובים שפיתחו ספריה שעושה את הדבר הזה באופן אוטומטי עבור הפונקציות שלנו (בלי שאנו מכינים מילון וכו') ונראה איך הדבר עובד, מדובר במתודה הקיימת בספריה functools והנקראת lru_cache על שום שהיא עוסקת בזכרון המטמון של המחשב. ונראה איך עושים את זה -
from functools import lru_cache
@lru_cache() def fib(n): if n<3: return 1 else: return (fib(n-1)+fib(n-2)) for i in range(1,1000): print(fib(i))
הדברים פשוטים מאוד, לאחר שיבאנו את המתודה lru_cache של הספריה functools אנו בונים פונקציית קישוט (דקורטור) מעל הפונקציה הרגילה שלנו השורה שמתחילה בסימן שטרודל. אפשר גם לרשום מה גודל הזכרון שאנו רוצים לשמור וזה יראה כך (lru_cache(maxsize=1000@ וכעת אנו יכולים לחשב את אלף מספרי הפיבונאצ'י הראשונים באופן מיידי.
המספרים ארוכים מאוד מאוד ולכן לא מציג אותם כאן. טוב אולי רק את מספר פיבונאצ'י 950 המתחיל ב- 444 וממשיך הרבה אחרי זה סה"כ 199 ספרות (כדי לחשב את אורך המספר הופכים אותו למחרוזת ומבקשים את האורך שלה באמצעות len שאינה פועלת על integers .
4447803282326157141063860798140565135175279561812695372311151183404978544074576084779694906092198758336762454048905401589449506607204278264939097537573413980490519471907060934663660744135522705225
תזכור=memoization
Commenti