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

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

הנה דוגמה פשוטה. קריאה של מתחים אנלוגיים בארדואינו באמצעות הפקודה analogRead מחזירה לנו ערכים בני 10 ביט, כלומר בטווח 0-1023. לעתים קרובות הטווח הזה לא מתאים לנו, ואנחנו צריכים להמיר אותו לסולם אחר – נניח בין 0 ל-100. איך מבצעים את ההמרה? רוב חובבי הארדואינו יעשו משהו בסגנון הזה:

y = map(x, 0, 1024, 0, 101);

וזה פתרון סביר, יחסית (לא מבינים למה כתבתי 1024 ו-101 במקום 1023 ו-100? קיראו את הפוסט החשוב מאד הזה). כמה זמן לוקח לארדואינו לחשב את התוצאה? כתבתי תוכנית קטנה שמחשבת את y עבור כל הערכים מ-0 ועד 1023, מאה פעמים (סה"כ 102,400 קריאות לפונקציה map), וקיבלתי מדידה של כ-5400 אלפיות שניה. כמובן שהזמן הזה כולל גם את ניהול הלולאות ולא רק את map. נחלק ונקבל כ-53 מיליוניות השניה ברוטו לכל המרה.

ועכשיו לטיפה חשבון, בלי קשר לארדואינו. איזו נוסחה פשוטה יכולה להמיר לנו את המספר x מסולם של 0-1024 לסולם של 0-101?

y = x / 1024 * 101

שזה בדיוק אותו דבר כמו

y = x * 101 / 1024

נכפיל את שני האגפים ב-1024:

y * 1024 = x * 101

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

y = (x * 101) >> 10;

כתבתי פונקציה שעושה בדיוק את זה, ונתתי לארדואינו להמיר את הסולמות בעזרתה במקום עם הפונקציה map. קיבלתי 793 אלפיות שניה, או 7.7 מיליוניות שניה ברוטו לכל חישוב – פי 6.81 מהר יותר מאשר map.

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

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