משחק החיים

[הצלוי]

משחק החיים

בוקר טוב יש לי שאלה ממטלה לקורס בג'אווה שאני צריך לעשות- משחק החיים. מי שלא מכיר, משחק החיים זה סימולציה כמודל חקר מחזור החיים של האורגניזם החי. הרעיון הוא שהמשחק משוחק על מטריצת ענק שאיבריה מהווים אתרי מחייה (קיום) אפשריים: בכל אתר ייתכן אחד משני מצבים: 1- "יש חיים" 2- "אין חיים" הייתי מראה דוגמא, אבל זה בעייתי פה.. תחשבו על מטריצה בוליאנית. עכשיו, בכל מחזור חיים, כל תא במטריצה משנה את המצב שלו לפי השכנים שלו: 1.לידה- בכל אתר בו "אין חיים" שיש לו בדיוק 3 שכנים חיים, תהיה לידה בדור הבא. אחרת התא נשאר "ללא חים"- ריק. 2.מוות- בכל אתר בו "יש חיים" שלו 0 או 1 שכנים חיים יתרחש מוות בדור הבא כתוצאה מבדידות. בכל אתר בו "יש חיים" ולו 4 שכנים חיים ומעלה, יתרחש מוות בדור הבא כתוצאה מ"פיצוץ אוכלוסין". 3.קיום- כל אתר בו "יש חיים" והינו בעל 2 או 3 שכנים, ימשיך להתקיים בדור הבא. שכנים כוללים גם באלכסון, דרך אגב. אוקיי, אז בכל מחזור חיים צריך לעדכן כל תא במטריצה- עם ריבוי תהליכים. אז כמובן שאני רוצה ליצור אובייקט לכל תא במטריצה(Cell), שמממש את Runnable, ובזמן הריצה שלו הוא יבדוק את השכנים שלו ויעדכן את עצמו אחרי שכולם בדקו את כולם (בעזרת סינכרון כמובן). הבעיה היא שלפי OOP, צריך כמובן שכל תא יהיה נפרד מהשכנים שלו, ולא תלוי בהם. גם לשלוח ייחוס של מטריצה בוליאנית שתכלול את מצבי כל התאים נראה לי מסורבל מדי.. ואני לא יכול לשלוח ייחוס של התהליך שמנהל הכל (ויש לו את המטריצה) כי המחלקה הזאת בעצם מורכבת מכל התאים שעדיין לא יצרתי... למישהו יש רעיון?

 

[DadleFish]

הממממ

קודם כל, לא ברור לי למה Cell צריך לממש את Runnable. בכל אופן, הפתרון הכי פשוט הוא סתם להחזיק מטריצה בוליאנית בתוך אובייקט המשחק, לעבור עליה בכל איטרציה ולחשב את מצבה החדש. אגב, שים לב שאתה לא מעדכן במטריצה ישירות; אתה צריך לבנות מטריצה חדשה שתייצג את המצב החדש. אם תעדכן ישירות תשפיע כמובן על התאים הבאים, וזה לא טוב. אם אתה בכוח צריך לממש את זה OOP-י, אז הייתי מממש ב-Cell פונקציות שמסתכלות על השכנים. כל Cell יידע מה המיקום שלו, ויבקש מהתהליך המרכזי לומר לו מי מימינו, מי משמאלו, וכו'. משהו כמו isNeighbourAlive שיקבל כפרמטר את המיקום של השכן, ייגש לתהליך המרכזי ויברר את מצב השכן.

 

[הצלוי]

אוקיי

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

 

[DadleFish]

לחילופין,

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

 

[Zack DA]

אין צורך !!!!!!!! ../images/Emo13.gif

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

 

[הצלוי]

כן, אני יודע

שבאיטרציות ובלי תהליכים המימוש היה הרבה יותר קל אבל השאלה היא מקורס שאני עושה באוניברסיטה של ג'אווה, בפרק של ריבוי תהליכים

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

מצד שני, עם כל הסינכרונים האלה, זה כבר יוצא כמעט כמו תוכנית סידרתית אחת. או שיש שיפור ביעילות?

 

[Zack DA]

יעיל יותר ?!?

לפתוח Thread לכל תא ? השתגעת ?

 

[הצלוי]

מבחינת זמן ריצה, למה לא?

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

 

[Zack DA]

לא, לא תאורטית ולא מעשית ../images/Emo70.gif

קודם כל אין לך n מעבדים. חוץ מזה, יצירת thread על כל תא מבטיחה שהתהליך הראשי שלך יצטרך ליצור n threads, שזה כבר o של n. חוץ מזה, יצירת אובייקט thread זו פעולה מאוד מאוד מאוד כבדה, וגם לא נכונה למקרה הזה. אם כבר, תקח את כמות המעבדים שיש לך, ותתן לכל אחד בנפרד לעדכן חלק מהמטריצה. וגם אז מדובר במשימה יותר מורכבת ממה שאתה חושב.

 

[Zack DA]

חוץ מזה,

כבר הסברתי לך, בכל מקרה אתה לא צריך מטריצה נוספת, אלא משתנה נוסף בכל אובייקט של תא במטריצה.

 

[DadleFish]

מה ההבדל בין זה לבין מטריצה נוספת?

 

[Zack DA]

מבחינת משאבים אין הבדל

לדעתי אין סיבה ליצור אחת נוספת. נסכים שזה כבר ויכוח שולי מאוד.

 

[DadleFish]

ממש לא.

"כל תא דואג לעצמו" זה ממילא (O(N, וזה שיש לך thread-ים זה לא אומר שדברים קורים במקביל. ה-CPU הבודד שלך עדיין מריץ אותם אחד אחרי השני. מה שכן, זה אומר שיש הרבה יותר thread-ים במערכת, זה אומר שמערכת הסינכרון של מערכת ההפעלה עובדת הרבה יותר קשה, זה אומר שעל כל החלפת thread המערכת שלך תעבוד קשה, וכו'. אין ספק שמימוש פשוט במטריצה פשוטה הוא הפתרון המהיר ביותר; אבל זה לא ממש משנה כי הקורס שלך דורש ריבוי תהליכים.

 

[הצלוי]

אני מבין מה אתה אומר

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

 

[DNile]

כמה מצבים:

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

 

[DadleFish]

thread-ים

נותנים לך לשלב בין כמה משימות במקביל בצורה פשוטה. אם יש לך משימה א' ומשימה ב', אתה יכול בעיקרון לשלב ביניהן בתוך thread אחד בלבד, אבל יהיה לך יותר קשה לעשות את זה. תכנותית יהיה הרבה יותר ברור ונוח לעשות את זה multithreaded. מצד שני, כמובן שצריך להיזהר מבעיות שנובעות מריבוי thread-ים.

 

[joeher]

threads ממש מועילים כש

אתה מתכנת פונקציות שממתינות לאירועים (Blocking) כמו פוקציות תקשורת למיניהן (שלחת משהו ואתה מחכה לתגובה) או התכנה מחכה לקבל משהו- מקש וכדומה (לא היית רוצה שהעכבר לא יזוז או שהשעון יתקע כאשר אתה מחכה לאירוע כלשהוא אחר)

 

[gmorphus]

לגבי המטריצה הזמנית

אתה יכול פשוט לשמות מערך של enum שכולל 4 מצבים: קיים, לא קיים, ימות, יחייה. ואז אתה סורק את המטרציה פעמיים. פעם ראשונה אתה מתייחס רק "לקיים"/"לא קיים", פעם שנייה את הופך "ימות" ל"לא קיים" ו"יחיה" ל"קיים". אפשר גם עשות 4 מצבים: קיים1, לא קיים1, קיים2, לא קיים2. ואז אתה שומר משתנה שאומר 1 או 2, וסורק את המטריצה פעם אחת ובסוף משנה את הערך של המשתנה. כלומר, כאשר הוא 1, אז אתה מתייחס רק ל"קיים1" ול"לא קיים1" והופך אותם לקיים2 בהתאם. ואז אתה חוסך סריקה נוספת של המטריצה.