בתשובה לטל כהן, 30/12/06 2:18
שמות בתעתיק לועזי 427000
עכשיו אני סקרנית - מה זה ערימת המגשים בקפיטריה? מה הדוגמא הזו מנסה להסביר? (ניסיתי למצוא משהו שמקביל לפעולה עם מגשים ועם מחסנית, לא הצלחתי לחשוב על כזו)
שמות בתעתיק לועזי 427008
fifo - first in first out. את המגשים מכניסים לערימה מלמעלה, וגם מוציאים אותם מלמעלה, אז את המגש שהכנסת אחרון תשלפי ראשון. ככה גם עם כדורים במחסנית של רובה, ועם מידע במחסנית.
שמות בתעתיק לועזי 427018
אתה רואה? טוב שחוזרים ומסבירים את המושג בספרים שאתה קורא. אתה עדיין מתבלבל.

FIFO - first in first out זה תור.

מחסנית זה LIFO - LAST IN FIRST OUT. הכדור האחרון שהוכנס למחסנית הוא הראשון שיוצא.
שמות בתעתיק לועזי 427021
אז הדוגמא של דורפל עם המגשים מקבילה לדוגמא עם כדורי המחסנית, שהם בעצם LIFO ולא FIFO?
שמות בתעתיק לועזי 427022
כן. יש מקומות בעולם (אולי גם בישראל?) שבהם מחזיקי המגשים הם עם קפיץ למטה, כך שתמיד המגש העליון יהיה באותו הגובה, וכדי להכניס מגש דוחפים אותו מלמעלה.
427025
אוקי, את הדוגמא הבנתי.
עכשיו נשאר רק להסביר לי מה היא אמורה להסביר (:
427034
אחד מהדברים הבסיסיים בתכנות הוא שימוש ב"מבני נתונים" - אוספים של מידע שמסודרים בצורה כזו שהגישה אל פרטי המידע שבהם תהיה נוחה ומהירה ככל האפשר. אחד ממבני הנתונים הבסיסיים ביותר הוא המחסנית המדוברת. הרעיון בה הוא שהגישה היא תמיד רק אל ה"ראש" שלה: אפשר לדחוף איבר חדש לראש המחסנית (ואז הוא יהיה "מעל" האיברים שכבר דחפנו קודם) או להוציא איבר מראש המחסנית (ואז האיבר שהוכנס ממש לפניו הופך להיות האיבר שבראש המחסנית).

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

(אפשר תמיד "לרמות" ולגשת גם לאיברים שבאמצע המחסנית - זה פשוט לוקח רב גדול יותר, ויש מבני נתונים יותר יעילים כדי לעשות זאת)
427036
כלומר (בתרגום לשפה שאני מבינה) כמו שאם אתה מסדר ארון בגדים אתה בד"כ תקח את החולצה שבראש הערימה כי אם תקח את החולצה שבאמצע זה יבלגן את המדף? ואז אתה משתמש בה, ומכבס, ואחרי הכביסה באופן טבעי שם אותה בראש ערימת החולצות מסוגה* ולכן בפעם הבאה שוב תלבש אותה כי הגישה קלה יותר?
ואם אתה רוצה את החולצה הספיציפית מאמצע הערימה (כי היא מתאימה נהדר עם הג'ינס החדשים) אז אתה צריך להתאמץ בשבילה, אבל עדיין יש לך גישה אליה, נכון?
ככה שבעצם יוצא שהפער בין החולצות שאתה משתמש בהן לבין החולצות שאתה פחות משתמש בהן רק הולך וגדל, לא?

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

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

אז בשביל מה צריך מחסנית? כי גם מתוך הפונקציה אפשר לקפוץ לפונקציה אחרת. נניח שאנחנו בפונקציה A וקפצנו ממנה לפונקציה B וקפצנו ממנה לפונקציה C - אז אחרי ש-C נגמרת קודם כל נחזור ל-B ורק אחר כך נחזור ל-A. זה בדיוק LIFO.
427049
הבנתי עד לכאן"צריך לדעת לחזור לכתובת ממנו נקראה הפונקציה".
את "לכן דוחפים את הכתובת למחסנית לפני הקפיצה, וכשמגיעים לסוף הפונקציה מוציאים אותה מהמחסנית, ואז יודעים לאן לחזור". כבר לא הבנתי. למה דוחפים ולמה מוציאים? (אם נמאס לך להסביר למפגרת זה בסדר. אבל אם ממש בא לך, אני אשמח אם תוכל להסביר את המשפט הזה עם בגדים*)

*אתה רואה טל? גם קוסמופוליטי וגם לא מילטנטי!
427055
''...אחרי חצי שעה, הסר את הסיר מהאש. עבור להכין את הרוטב.'' - הרוטב משותף לכמה מתכונים, והוא מפורט במקום אחר בספר. משאירים סימניה, עוברים לעמוד עם הרוטב, וכשמסיימים איתו, חוזרים לשורה שמיד אחרי ''עבור להכין את הרוטב.'' בעמוד של הרוטב, כמובן, יכלו לשלוח את הקורא לעמוד שמסביר איך לקצוץ בצל.
427057
כן, את זה הבנתי כבר בהסבר הראשון. אבל לא הבנתי למה צריך לדחוף את הכתובת למחסנית לפני הקפיצה, ואז להוציא אותה.

הכתובת היא הסימניה או הרוטב?
427059
הכתובת היא הסימניה. מה שחשוב הוא שנדע לאיזה מקום בספר לחזור.
427062
הסימניה מסמנת את הדף והשורה שממנה קפצת לדף של הרוטב. אחרי שאת מסיימת עם הרוטב, את חוזרת לסימניה. אם בדף של הרוטב הייתה עוד קפיצה, את צריכה עוד סימניה - את צריכה לחזור מקיצוץ הבצל לרוטב, ורק אחרי שתסיימי את הרוטב כולו לחזור לשורה שאחרי "הכן את הרוטב". כל פעם שאת קופצת, את מוסיפה לרשימת הדפים שאת צריכה לחזור אליהם כתובת/סימניה. כל פעם שאת מסיימת איפשהו, את חוזרת למקום האחרון שממנו קפצת. מחסנית.
427068
אז כל הסימניות יחד הן "מחסנית"? שזה מתורגם בשפת מחשבים ל"כל הכתובות ששולחות אל הפונקציה"?
אם כן, אז למה זה רלוונטי שמגדירים את זה כליפו או פיפו?
427072
הסימניות (הכתובות) נכנסות למחסנית / מסודרות במחסנית.
רלוונטיות: יש שלושה דפים בדוגמה שלנו - דף המתכון הראשי, דף הרוטב, ודף הבצל. בשורה חמש בדף הראשי היה כתוב "הכן את הרוטב", אז את רוצה להכין את הרוטב, ואחרי שאת מסיימת אותו, לעבור לשורה שש בדף הראשי. את משאירה סימניה, ואחריה את קופצת לדף של הרוטב. את עוברת על ההוראות שם אחת-אחת, עד שאת מגיעה לעשירית (שאיננה בהכרח האחרונה), שבה כתוב "קצוץ את הבצל". את משאירה סימניה חדשה, ועוברת לדף של הבצל. כשאת מסיימת עם הדף של הבצל, את צריכה לחזור לסימניה של הרוטב, לא זאת שבדף הראשי. אבל גם אסור לך להפטר מהאחת של הדף הראשי עדיין - עוד מעט תצטרכי אותה. אז לאיזו סימניה את חוזרת עכשיו? לאחרונה שיצרת. ואחריה? לזו שיצרת אחרונה באותו רגע (אולי יצרת מאז עוד, אולי לא).
427074
כאן הדוגמה של דורפל קצת "נתקעת", כי מחסניות באמת לא מהוות מחסנית. מצד שני, אולי אפשר להראות למה מחסנית כ"כ יעילה כאן.

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

עכשיו בואי נניח שאת צריכה הרבה יותר הסברים (בשביל לדעת איך קוצצים בצל צריך לדעת איך משייפים סכין, ובשביל זה צריך לדעת איך בודקים שסכין הוא חד, ובשביל זה צריך לדעת מה זה סכין, וכו') ויש לך מאה סימניות בספר. מכיוון שהן לא מסודרות באף דרך ברורה, כדי למצוא את הסימניה שמעניינת אותך צריך לעבור על כולן (עם קצת מזל תגלי את הסימניה הנכונה על ההתחלה - בלי מזל, היא תהיה האחרונה שתקראי). לכן מאוד נוח אם הסימניות יהיו מסודרות ב"ערימה" (כי בכל פעם מעניינת אותך רק סימניה אחת - האחרונה ששמת).
427078
אני חושב שההסבר שלי עדיין טוב, עם השינוי הבא - אמרנו שצריך לדעת מי הייתה הסימנית האחרונה, מי לפניה, וכו'. הפתרון, כמובן, הוא לא להשתמש בסימניות של ממש, אלא בפתקים שעליהם רושמים את מספר העמוד והשורה שאותן אמורות הסימניות לסמן, ולהניח את הפתקיות בערימה על השולחן, כשלוקחים ומוסיפים לערימה מלמעלה.
427058
דורפל הסביר יפה עם אוכל וסימניות, ואני מציע פרס למי שיצליח למצוא הסבר עם בגדים (לא הצלחתי).
427061
בסדר, גם עם אוכל אני מבינה* (:
תודה.

*למרות שאני יכולה לחשוב על הסבר אלטרנטיבי עם חצאיות ומכנסיים, אבל מעמדי כבחורה-השטחית גם ככה הולך ומתחזק - וחבל.
427066
דווקא מסקרן.
427073
חזרתי לדוגמא הבסיסית שלך, ואני מתרגמת אותה לשפת-פקאצות:
כשאתה מתעורר ורוצה לצאת מהבית, אתה עובד באופן סדרתי - פוקח עיניים, מקלל, יוצא מהמיטה, מצחצח שינים וניגש לארון הבגדים.
אתה לוקח את החולצה הראשונה בערימה, ואז צריך להחליט מה יתאים איתה, אז אתה משאיר את דלת הארון פתוחה (זו הסימניה) ופותח את הארון השני - שם אתה צריך להחליט אם חצאית תתאים (כמובן שלא - אתה לא סקוטי ולא כליל נאורי, לא סידרת רגליים ואין לך חשק לגרביונים ובכלל - קור שועלות בחוץ) או שעדיף לבחור מהערימה השמאלית במדף שם שוכנים זוגות המכנסיים. בחרת את הג'ינס הרלוונטי (זה תמיד ג'ינס בסוף) וחוזר אל מדף החולצות כדי לבחור ג'קט מתאים. משם אתה ממשיך להסתרק, להתאפר, לשתות משהו ולגלות שאתה שוב מאחר לשיעור.

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

לפי הדוגמא הזו אתה צריך מחסנית הפוכה - אם לבשת היום את הסוודר השחור ואתה מחזיר אותו לראש הערימה, אתה צריך להקפיד בפעם הבאה לקחת את הסוודר מתחתית הערימה. הרי לא יעלה על הדעת שתלבש יום אחרי יום את אותו הבגד, הלא כך?
427075
כרגע המצאת מבנה נתונים בסיסי נוסף: תור. זה ה-FIFO שהוזכר קודם (First in first out - הסוודר הראשון שהכנסת לערימה יהיה גם הראשון שתוציאי, וכל אלו שהוספת לערימה מאז יחכו בסבלנות לתורם).
427084
(משום מה, הם בחרו לתת דווקא את אחד השימושים היותר מסובכים של מחסנית, ועוד להסביר אותו במונחים טכנוקרטיים-משהו...)

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

כשמדובר בהפניה אחת זה די פשוט, ובאמת לא רלוונטי אם זה FIFO או LIFO או סתם כתבת לעצמך על היד לאן לחזור. הבעייה מתחילה כשבעמוד 11 מפנים אותך באותו האופן לעמוד נוסף, שמפנה בתורו לעמוד אחר, וככה הלאה... איך תדעי לאן לחזור עם כל כך הרבה הפניות...?
פשוט: בכל פעם שאת עוברת לעמוד אחר את כותבת על פתק את המקום שבו את נמצאת כרגע, ומניחה את הפתק מעל שאר הפתקים. שימי לב: כך בכל שלב, הפתק העליון תמיד יכיל את המיקום שאליו את צריכה לחזור אחרי שנגמרו ההוראות בעמוד שאת נמצאת בו. כשזה קורה, את שולפת את הפתק העליון, חוזרת לאן שצריך וזורקת אותו משם, כשהפתק הבא אחריו הוא זה שהכנסת בהפניה הקודמת. לכן משתמשים במחסנית, ולא ב"תור", כי בתור היתה לך גישה בכל פעם רק לפתק הראשון שהכנסת, במקום לאחרון.

(כל זה, כאמור, די מסובך לדעתי למי שלא תיכנת אף פעם...)
427064
נניח שאת מסמלץ מכונת אוגרים בעזרת הקולקציה האחרונה של פוקס...
427044
אם אתה רוצה את החולצה שבאמצע, אתה מסיר את החולצות שלפניה אחת-אחת, לפני שאתה בכלל מגלה שהיא באמת שם. אז אתה מוציא אותה, ומחזיר את החולצות האחרות בחזרה, בסדר המתאים.
הסתבכתם, חבר'ה 427088
תסלחי לחבריה כאן שהחליטו לבחור דוגמא טכנית לחלוטין לרעיון טבעי ולא-טכני ביסודו. הנה דוגמא פשוטה יותר (לא שלי במקור) להסבר רעיון המחסנית: סיפור בתוך סיפור בתוך סיפור. את קוראת ספר של נבוקוב, וגיבורת הספר - נאמר, עדה - קוראת את "אלף לילה ולילה", ושם, שחרזדה מספרת את "המלט" לסולטאן, ובתוך המלט יש הצגה.

ההצגה הפנימית מסתיימת. לאן חוזרים? לשחרזדה שמספרת סיפור לסולטאן? לעדה? לא, ל"המלט"; יש כאן מסגרות בתוך מסגרות, וכל פעם שיוצאים ממסגרת, לא "מדלגים" שכבות לאחור אלא מגיעים למסגרת הקודמת. המוח שלנו זוכר את סדר המסגרות, עד גבול מסוים; הזכרון הזה עובד בשיטת "נכנס אחרון יוצא ראשון" (LIFO), או במחשבית "מחסנית". במהלך הקריאה שתארתי לעיל, סדר המחסנית הוא: הספר של נבוקוב, אלף לילה ולילה, המלט, הצגה. אם ההצגה מסתיימת, והמלט מסתיים, הוצאנו שתי רשומות מהמחסנית; ואם כעת שחרזדה (שבראש המחסנית) תתחיל לספר את "מסעות סינבאד", אנו בעצם מוסיפים רשומה חדשה בקצה המחסנית. ההוספה היא תמיד בקצה, ממש כמו שההסרה היא תמיד מהקצה.

אגב, יש גבול למחסניות שהזכרון האנושי מסוגל לנהל באופן אינטואיטיבי; דוגמא אפשר למצוא בתגובה 37497.
הסתבכתם, חבר'ה 427090
אגב, ב''גדל, אשר, באך'' יש ''דיאלוג'' אחד בין הצב ואכילס שהוא המחשה נהדרת לרעיון הזה.
שמות בתעתיק לועזי 427026
אכן כן.
שמות בתעתיק לועזי 427114
נכון. LIFO זה גם כמו ברשימת פיטורים של מפעל הסתדרותי.
FIFO לעומתו הוא כמו המתקן הזה של גלילי נייר טואלט (או של קופסאות סיגריות בקיוסקים) שמכניסים מלמעלה ומוציאים מלמטה.
שמות בתעתיק לועזי 427032
התבלבלתי במינוח, לא ברעיון. אפשר לחזור עוד שמונים פעמים, ולא תצמח מזה שום תועלת. (ותודה-סליחה על התיקון. איזו פאדיחה...)
שמות בתעתיק לועזי 427065
זה היה בצחוק. ברור לי שאתה יודע על מה אתה מדבר.
שמות בתעתיק לועזי 427121
ה-LIFO הזה זה גם שיטת פיטורי-הקיצוצים בימינו...
LIFO, כמוב... כמתוקן 427033
אופס

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים