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

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

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

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

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

1. התוכנה במחשב, לפני שהיא שומרת את כל נקודות הציון שהמשתמש הזין, ממיינת אותן לפי קו הרוחב (Latitude).

2. הארדואינו מחפש בקובץ קודם כל לפי קו הרוחב בלבד, בחיפוש בינארי. הדבר מתאפשר בזכות הפקודה Seek, ש"מקפיצה" אותנו לבייט ספציפי בקובץ כרצוננו, ובזכות העובדה שכל רשומה היא באותו גודל בדיוק. כדי לקפוץ לרשומה i (כשהראשונה בקובץ נחשבת 0=i), פשוט נכתוב

file.seek(I * 222);

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

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

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

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

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