איך תוכנה מוצאת מה השתנה בין שני קבצים - אלגוריתם Diff¶
בפוסט על אחסון קומיטים בגיט הסברנו שגיט שומר תמונות מצב מלאות, לא רשימת שינויים. אז איך בכל זאת, כשכותבים git diff, מקבלים בדיוק את השורות שהשתנו, מסומנות באדום וירוק? התשובה היא שהשוואה בין שתי תמונות מצב מלאות, ומציאת ההבדל המדויק ביניהן, היא בעיה אלגוריתמית משלה, שנפתרת בכל פעם מחדש כשמבקשים diff.
הבעיה - מה בכלל אומר "ההבדל הקטן ביותר"¶
תארו לעצמכם שתי גרסאות של קובץ, כל אחת עם עשרים שורות. כמה שורות באמת השתנו ביניהן? יש הרבה דרכים אפשריות לתאר את המעבר מגרסה אחת לשנייה - אפשר לומר "מחקו את כל עשרים השורות והוסיפו עשרים חדשות", וזה נכון טכנית, אבל לא שימושי בכלל למי שמנסה להבין מה השתנה. מה שבאמת רוצים הוא את התיאור הכי קצר וממוקד - כמה שפחות שורות שנמחקו והוספו, כדי שהשינוי האמיתי יבלוט.
הכלי המתמטי - תת-רצף משותף ארוך ביותר¶
הבסיס האלגוריתמי לרוב כלי ה-diff הוא בעיה קלאסית במדעי המחשב שנקראת Longest Common Subsequence, תת-הרצף המשותף הארוך ביותר, בקיצור LCS. תת-רצף הוא לא בהכרח רצף רציף - זו קבוצת שורות שמופיעה בשני הקבצים, באותו סדר יחסי, גם אם יש ביניהן שורות אחרות שלא שייכות לתת-הרצף. מציאת התת-רצף המשותף הארוך ביותר בין שתי הגרסאות היא בעצם מציאת מקסימום התוכן ה"משותף" ביניהן.
ברגע שיש לנו את התת-רצף המשותף הארוך ביותר, ה-diff נגזר ממנו כמעט אוטומטית - כל שורה שלא נמצאת בתת-הרצף המשותף אבל קיימת בקובץ הישן, סומנה כנמחקה. כל שורה שלא נמצאת בתת-הרצף המשותף אבל קיימת בקובץ החדש, סומנה כנוספה. שורות שכן חלק מהתת-רצף המשותף פשוט לא מוצגות בכלל בdiff, כי הן זהות בשני הקבצים ולא באמת השתנו.
איך בפועל מוצאים את התת-רצף הזה¶
מציאת LCS נעשית בעזרת טכניקה שנקראת תכנון דינמי (dynamic programming) - במקום לנסות כל שילוב אפשרי של שורות, מה שהיה איטי באופן קיצוני, בונים טבלה שבה כל תא מייצג את אורך התת-רצף המשותף הארוך ביותר בין קידומת מסוימת של הקובץ הראשון לקידומת מסוימת של הקובץ השני. כל תא בטבלה נבנה מהתאים שכבר חושבו לפניו - אם השורה הנוכחית בשני הקבצים זהה, אורך התת-רצף גדל באחד ביחס לתא באלכסון, ואם לא, לוקחים את המקסימום מבין השורה שמעל והעמודה שמשמאל. אחרי שממלאים את כל הטבלה, אפשר "לעקוב אחורה" ממנה ולשחזר בדיוק אילו שורות שייכות לתת-הרצף המשותף.
למה זה לא תמיד "אינטואיטיבי" למרות שהוא מתמטית אופטימלי¶
לפעמים diff שמחזירים כלים אמיתיים נראה קצת מוזר - למשל, שינוי ששיפצתם באמצע פונקציה יכול להיראות כאילו כל הפונקציה נמחקה והוחלפה, במקום שינוי נקודתי בשורה אחת. זה קורה כי יש לפעמים כמה תת-רצפים משותפים באותו אורך מקסימלי, וכלי ה-diff חייב לבחור אחד מהם, לא בהכרח את זה שנראה הכי "טבעי" לעין אנושית. כלים מתקדמים יותר, כמו האלגוריתם של Myers שגיט משתמש בו, מוסיפים היוריסטיקות נוספות כדי להעדיף תוצאות שקריאות יותר לבני אדם, לא רק מתמטית מינימליות.
למה שווה להבין את זה¶
הבנת אלגוריתם diff מסבירה למה שינוי סדר של פונקציות בקובץ יוצר diff מבלבל גם אם התוכן בפנים לא השתנה בכלל, ולמה כלים כמו git blame ו-git log -p, שמסתמכים על diff מדויק, לפעמים "מפספסים" מעקב אחרי קוד שהוזז ולא רק שונה. זה בדיוק סוג הידע שמחבר בין שימוש יומיומי בכלי לבין הבנה של האלגוריתם שמאחוריו.
בקורס התכנות הבסיסי שלנו עוברים על תכנון דינמי ובעיות אלגוריתמיות קלאסיות כמו LCS, בדיוק כדי לבנות את החשיבה האלגוריתמית שחוזרת שוב ושוב מאחורי כלים שאתם משתמשים בהם כל יום.
קורס התכנות הבסיסי שלנו בונה חשיבה אלגוריתמית שלב אחר שלב.
יש לכם diff מוזר שאתם לא מבינים למה הוא יצא ככה? שאלו בדיסקורד.
לסיכום¶
diff לא "מנחש" מה השתנה בין שני קבצים - הוא פותר בעיה אלגוריתמית מדויקת של מציאת התת-רצף המשותף הארוך ביותר, בעזרת תכנון דינמי, ומכל שורה שלא נמצאת בתת-הרצף הזה נגזרות הוספות ומחיקות. זו בדיוק הסיבה ש-git diff, שנראה כמו פיצ'ר פשוט, בעצם מריץ אלגוריתם קלאסי במדעי המחשב בכל פעם שאתם משתמשים בו.