כאשר אנו כותבים קוד שעובר על מטריצה, כלומר מערך דו ממדי, היינו יכולים לחשוב שאין כל הבדל אם נעבור עמודה עמודה:
או שמא שורה שורה:
וכך גם למדנו בחישובי היעילות, ששתי האופציות זהות.
אבל למען האמת יש הבדל עצום בזמן הביצוע בין שתי אפשרויות אלו.
ראשית אוכיח, ואז בע"ה אסביר למה, לשם דוגמה נשתמש בפונקציה שמאפסת מערך, ראשית ננסה שורה שורה, ואז טור טור, ונשוה את הזמנים (אגב, לא אשתמש בפייתון אלא בJS כי זה לא טבעי לפייתון לעבור שלא בשורות שורות):
שורה שורה או עמודה עמודה, יש הבדל? נבדוק:
ניצור שתי פונקציות זהות, למעט סדר הפעולות כאמור:
(שימו לב להבדל בסדר האינדקסים, i וj)
ניצור פונקציה למדידת זמן ריצה ממוצע, לאחר 1000 ריצות:
נבנה מערך בן מיליון אברים:
ונריץ:
(הקוד נגיש כאן, אשמח לשמוע בתגובות כמה מהר רץ אצלכם...)
בממוצע, מעבר על מערך בן מליון אברים שורה אחר שורה, לקח אצלי במחשב כ5 אלפיות השניה. ואילו אותו מערך לעבור עמודה אחר עמודה לקח בערך פי שבע! כ36 אלפיות השניה.
מדוע יש הבדל כה גדול?
הסיבה היא שבעת הריצה, כאשר אנו מבקשים מידע כל שהוא - נניח ניגשים לתחילת שורה של מערך - אז ניתן להניח שאם אנו מתחילים לקרוא מידע מתוך קטע זכרון, אז ייתכן שנרצה גם את המשך אותו הקטע, ולכן יטען לזכרון מראש גם המשך השורה!, כ"הכנה לעתיד", ומידע זה נשמר ב"מטמון" שזה זכרון מהיר מאד וקרוב למעבד.
כעת, אם נמשיך לרוץ על אותה שורה, הביצוע יהיה יעיל ומהיר, כי כל המידע כבר נטען וממתין בסביבה... אבל אם נלך עמודה עמודה, הרי בכל פעם שנעבור לאיבר הבא, הרי שהאיבר שכעת נרצה נמצא בשורה הבאה, וכל פעם מחדש נזרוק לפח את כל מה שנטען למטמון - שזו השורה הקודמת - וניגש מחדש לזכרון כדי לטען מחדש "מאפס" עוד שורה...
לכן כדאי מאד לעבור תמיד על קטע זכרון רציפים ככל האפשר. ובמקרה זה, לעבור על המערך שורה אחר שורה...
בפוסט המשך בע"ה אתאר פתרון פשוט למקרים מסוימים שבה רצוננו דווקא כן לעבור עמודה אחר עמודה...
הערות:
- פוסט זה מתבסס על מה שלמדנו אצל ד"ר אליהו חלסצ'י.
- לא זכיתי להבין מיהו האחראי על טעינת הזכרון למטמון, האם המעבד, מערכת ההפעלה, או שמא ישנו כלי מיוחד לכך? אודה למי שיאיר את עיני.