יום ראשון, 10 ביולי 2011

כל המוסיף גורע מזמן הריצה

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

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



הלולאה הראשונה כופלת את כל האיברים שבמטריצות x ו-y, ולפיכך אמורה לרוץ יותר זמן מיתר הלולאות, אשר כופלות מטריצות הקצרות בשורה אחת או בעמודה אחת. אולם בפועל, הלולאה הראשונה רצה הכי פחות זמן מבין השלוש – רק 0.25 שניות על המחשב שלי, בעוד שהשניה רצה 1.75 שניות, והשלישית – 6.65 שניות.

מדוע הלולאה הראשונה היא המהירה ביותר ?

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

ומדוע הלולאה השניה רצה יותר מהר מהשלישית?

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

האם בעבודתכם עם MATLAB נתקלתם בתופעות דומות המנוגדות לאינטואיציה הראשונית, דוגמת זו שמתוארת למעלה?