שאלה במימוש

[אנדרומארי]

שאלה במימוש

יש פונקציה

myTimer(func f, time t)​

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

timer(f,10) timer(g,11)​

אז הפונקציה g תתבצע תוך 11 שניות מרגע הקריאה אבל הפונקציה f לא תתבצע בכלל. המשימה היא לכתוב את הפונקציה

myTimer(func f, time t)​

שכן תהיה בעלת זכרון ולא "תזכור" רק את הקריאה האחרונה שנעשתה לה ותפעל באופן המצופה . העניין הוא שכתוב במפורש בחידה שאי אפשר להשתמש ב- thread-ים. היתה לי סקיצה מסויימת לפתרון החידה- אבל היא לא עובדת ללא thread-ים. חשבתי על להחזיק מבנה נתונים ממוין כמו map שה- key שלו יהיה timeOfExecution וה- value יהיה פוינטר לפונקציה שצריך להפעיל. העניין הוא שכל הנסיונות לעשות את זה ללא therad-ים עלו בתוהו שכן בכל פעם ממלאים את ה- map ומבצעים רק את המשימות שאמורות להתבצע כעת ואז רוצים לחזור מהפונקציה אבל הבעייה היאשאסור להחזיר את הפונקציה כי יתכן שיש ב- map עדיין משימות שזמנן להתבצע עוד לא הגיע ומצד שני אם נהפוך את הפונקציה להיות פונקציה רקורסיבית יתכן שהיא תתקע ולא תחזור עד שאחרונת המשימות לא תתבצע ובינתיים אי אפשר יהיה להשחיל עוד קריאות ל my_timer. לכן הסקתי שאי אפשר לממש את זה בלי thread-ים למרות ששואל השאלה התעקש שכן. מה דעתכם?

 

[freak2100]

זה אפשרי

אבל משהו אחד שאני לא בטוח לגביו - אם עושים את הקריאה:

timer(f,10) timer(g,11)​

אתה צריך שf תתבצע לאחר 10 שניות, וg שנייה לאחר מכן - או שאתה צריך שf תתבצע לאחר 10 שניות וg עוד 11 שניות לאחר מכן? בכל מקרה, תחשוב על זה שאתה צריך מבנה נתונים כלשהו שיכיל את הפונקציות שצריך להפעיל ואת הזמנים שלהן, וmyTimer צריך להוסיף קריאות למבנה הנתונים הזה. במקביל, אתה צריך פונקציה שתטפל בקריאה לפונקציות, ז"א תוציא מהמבנה את הפונקציות שצריך להפעיל ותפעיל אותן - ולפונקציה הזאת אתה קורא בעזרת timer.

 

[אנדרומארי]

הפיתרון שלך לא ברור.

ברור לך ש- myTimer לא יכולה רק להכניס לתוך המבנה נתונים , מכיוון שהיא צריכה במהותה להפעיל את הפונקציה שהיא תקבל כפרמטר אחד תוך זמן t אותו היא גם מקבלת כפרמטר. לכן myTimer חייבת לקרוא ל- timer , השאלה היא עם איזה זמן היא תקרא לו. בוא נניח שהמבנה נתונים שלנו הוא map שבתור key מחזיק timeOfExecution ובתור value מחזיק פוינטר לפונקציה אותה צריך לבצע וכמובן ה- map ממוין לפי ה- keys. לכן האיבר הראשון ב-map הוא הפונקציה הראשונה שצריכה להתבצע בזמן שמוחזק ב- value של האיבר. עכשיו, אתה דיברת על איזשהו functionDelegator שיעבור על ה- map לפי הסדר וכביכול יפעיל אותן. לכן הפתרון שאתה מציע נראה כמו

void funcDelegator() { map::iterator itr; *(itr->second)(); } myTimer(func f, time t) { adds the pair (f,t) as a record to map timer(f,t) }​

ועדיין לא הבנתי איך אפשר כמו שאתה מציע להפריד את הקריאה ל- timer מ- myTimer. הכוונה נוספת תתקבל ברצון.

 

[freak2100]

הרעיון הוא...

שmyTimer יקרא לtimer, אבל לא עם הפונקציה עצמה שהוא רוצה להפעיל ז"א, מה שmyTimer יבצע: * ידחוף למבנה הנתונים את (f,t) * אם timer לא רץ (צריך לשמור איזה boolean שיזכור את זה) - יקרא לtimer על t, אבל לא עם הפונקציה f אלא עם הפונקציה הנוספת שאני מציע לעשות מה שהפונקציה הנוספת צריכה לעשות: * להוציא את הפונקציה הראשונה שהוכנסה ולהפעיל אותה * אם מבנה הנתונים לא ריק - לשלוף את הזמן של הפונקציה הבאה ולקרוא לtimer, שוב פעם עם הזמן שצריך לחכות, ושבסוף הזמן שוב יקרא לפונקציה הנוספת הזאת

 

[אנדרומארי]

הפתרון שלך עדיין לא ברור לי:

"אם מבנה הנתונים לא ריק - לשלוף את הזמן של הפונקציה הבאה ולקרוא לtimer, שוב פעם עם הזמן שצריך לחכות, ושבסוף הזמן שוב יקרא לפונקציה הנוספת הזאת", אם בסוף הזמן שוב יקרא לפונקציה הזאת, אתה בעצם מדבר פה על לולאה אינסופית, מה שיתפוס את כל זמן ה- cpu ובמערכת שבה יש רק thread אחד , זה כמובן יתקע את כל הקריאות הבאות ל - mytimer.

 

[freak2100]

אבל...

timer עובד עם עוד thread לפי איך שתיארת אותו, ולכן זה לא יתקע את המערכת. אם הוא לא עובד בthread אחד, אז:

timer(g, 11); timer(f, 20);​

היה עובד, כי הקריאה הראשונה הייתה מחכה 11 שניות, מפעילה את g - ואז היית מגיע לקריאה השנייה. אבל אתה אומר שהקריאה השנייה דורסת את הראשונה, זה אומר שtimer כן בנוי על thread נוסף, פשוט במימוש של myTimer אסור לך לעשות עוד threadים...

 

[אנדרומארי]

לא הבנתי למה אם הקריאה השנייה

דורסת את הראשונה זה אומר שיש יותר מ- thread אחד?!? יש thread אחד שרץ מפעיל את timer עם (f,10)ומיד עובר לפקודה הבאה שזה timer(g,11( מבלי לחכות לשום דבר. הבעייה היא שהוא בטעות דורס את התכנים שהקריאה הראשונה השתמשה בהם עם התכנים החדשים במקום לשים את התכנים הנוכחיים במיקומים חדשים. אני לא מבין איך זה קשור ליותר מ- thread אחד.

 

[freak2100]

זה לא משנה

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

 

[אנדרומארי]

אתה צודק,

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

 

[freak2100]

כן, לא הייתי ברור

הייתי קצת לחוץ בזמן

 

[immortalus]

אני לא לחלוטין בטוח שהבנתי את המשימה...

אבל עלה לי רעיון כזה: קח דחוף לתוך timer את MyTimer לפרק זמן של שניה 1. אם MyTimer מופעלת עם פונק' נוספת היא תדחוף אותה למבנה הנתונים ששומר את המשימות לביצוע. אם היא נקראת בלי פונק' נוספת (משמע מתוך timer) היא תפעיל את הפונק' הבאה לביצוע, תקדם משתנה ששומר כמה פעמים הפונק' כבר נקראה ותזמן שוב את timer עם עצמה בזמן של שניה ואז תחזור. בין הקריאות ל-myTimer יש לך מרווח פעולה. כשאתה דוחף פונק' חדשות לביצוע - אתה שומר את זמן ההפעלה שלהם + מספר הזימונים שכבר היו כדי לדעת באיזה מספר זימון צריך יהיה להפעיל את הפונק' הנוכחית. מקווה שזו הייתה הכוונה בשאלה..

 

[אנדרומארי]

לצערי גם הפתרון שלך לא מובן לי:

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

 

[immortalus]

הכוונה היא לזימון כזה:

timer(MyTimer(NULL,-1),1);​

או איך שהפקודה לא אמורה להקרא... כלומר לזמן את הפונק' timer עם הפונק' MyTimer שתופעל בעוד שניה. הרעיון הוא שהפונק' timer תפעיל כל שניה את הפונק' MyTimer בלי פונק' בפנים. הפונק' MyTimer כשהיא מזומנת בודקת האם קיבלה כתובת ממש של פונק' או זומנה ללא פונק' (NULL). אם MyTimer זומנה ללא פרמטרים אזי היא יודעת שהיא זומנה ע"י הפונק' timer, אחרת זומנה מהתוכנית הראשית. אם היא זומנה עם פונק' היא פשוט תדחוף את הפונק' החדשה למבנה הנתונים שלך (רשימה, תור, עץ, מה שבא לך) ותסיים. אם היא זומנה בלי פונק' (משמע מתוך timer), היא תמצא את הפונק' שאמורה\אמורות להיות מופעלות בזמן הנתון, תפעיל אותן, תקדם משתנה שסופר כמה שניות עברו, תפעיל שוב את timer עם עצמה, ותסיים. ככה עד אין-סוף.

 

[אנדרומארי]

הבנתי! פתרון ממש יפה ויצירתי, תודה!

 

[immortalus]

שמחתי לעזור, בבקשה ../images/Emo13.gif