To(Decimal)String
פעם, לפני מספיק זמן, שאלו אותי בראיון עבודה איך הייתי ממיר מספר חיובי שלם לטקסט, מבלי להעזר במתודות ToString הרגילות.
בקיצור: "קליין! מַמֵּש ToString של int חיובי! יש לך 2 דקות, זוז!!"
פתרתי, אלא מה. אומרים לי, אני עושה.
בפוסט הזה אני אראה את הפתרונות לשאלה הזו, ובכל פעם אני אסביר איך שאלה יחסית פשוטה יכולה לפתוח בפנינו עולמות שלמים. הפתרונות השונים שאני אציג ימחישו (אני מקווה) את ההבדל שבין משימה כללית לבין משימה נקודתית, ואיך אפשר לנצל את היתרונות של המשימה הנקודתית ולהפוך אותם ליתרון בביצועים. בכל שלב נצלול עמוק יותר בנבכי הקוד (ראו הוזהרתם!) ונראה מה ניתן לשפר ואיפה, והאם בכלל יש שיפור בביצועים.
אז בואו נראה איך אפשר להפוך קוד "כללי" לקוד תלוי משימה ספציפית.
ToDecimalString – גירסה ראשונה
בואו ניזכר רגע בדרישות: נתון int שהוא חיובי, ועלינו להמיר אותו ל string מבלי להיעזר במתודת ToString שמגיעה באופן מובנה עם הפריימוורק.
כדי לפתור את זה, נצטרך להשתמש בחלוקה ב 10 עם שארית. הנה גירסת הקוד לפתרון הראשון:
public class V1
{
public static string ToDecimalString(int value)
{
if (value == 0)
return "0";
var list = new List<char>(1);
while (value != 0)
{
var digitAsInt = value%10;
var digitAsChar = (char) ('0' + digitAsInt);
list.Add(digitAsChar);
value /= 10;
}
list.Reverse();
return new string(list.ToArray());
}
}
אוקיי, עכשיו בואו נבדוק מה הולך כאן: מכיוון שאנחנו לא יודעים מראש מה אורכו של המספר, אנחנו משתמשים ב List של תוים, שמאפשר לנו בכל פעם מחדש להוסיף char למערך פנימי משלו. בכל איטרציה אנחנו בודקים מהי השארית של חלוקה ב 10 (זו פעולת המודולו), ואח"כ מחלקים את המספר ב 10 (חלוקת int ב int היא ללא שארית). ממשיכים כך עד שמה שנשאר מכל החלוקות האלו הוא אפס (0).
מכיוון שסדר הכנסת התוים לליסט הוא הפוך ממה שאנחנו צריכים, נצטרך לקרוא למתודה Reverse.
בסוף אנחנו משתמשים במתודה ToArray של הרשימה (שלצערנו יוצרת הקצאת זכרון חדשה), והמערך המוחזר נכנס בקונסטרקטור של string. זה למעשה הערך המוחזר.
טוב ויפה, הקוד עובד ותקין. אלא שמבחינת ביצועים, אפעס, הקוד לא משהו. למה?
- אנחנו משתמשים ב List של תוים, רק כי הוא מאפשר לנו דינאמיות ומגדיל באופן שקוף את המערך הפנימי שלו לפי הצורך.
- אנחנו הופכים את הסדר במקום לכתוב בצורה הרצויה כבר מהשלב הראשון.
קצת מספרים: ה ToString הסטנדרטי לוקח בממוצע 7 טיקים (Ticks) והמימוש שיש כאן עכשיו לוקח 12 (!) טיקים. זה הפרש של עשרות אחוזים, כך שיש לנו עוד עבודה לעשות.
חדורי מוטיבציה להקטין את הקצאות הזיכרון האלו, אנחנו ניגשים לקוד ומתכננים את הגירסה השניה.
ToDecimalString – גירסה שניה
הבעיה העיקרית שלנו בהקצאות הזכרון היא שאנחנו לא יודעים כמה ספרות ה int הזה צורך בייצוג העשרוני שלו.
כאן באה לעזרתנו האלגברה. זוכרים את פונקציית ה Log? זאת של המתמטיקה, לא של log4net! אה, כן, Log, ויש גם ln ויש איזה e שקיים שם. טוב, בלי שאני אסחף כאן, בדוט נט יש את הפונקציה Log10 מובנית בפריימוורק. התוצאה שלה היא מספר לא שלם (double), ואם נעגל את המספר שיצא כלפי מעלה, נקבל את מספר הספרות שהמספר הנתון יצטרך בייצוג העשרוני שלו.
כלומר, הביטוי הבא:
var digitCount = (int)Math.Ceiling(Math.Log10(value));
יתן לנו את מספר הספרות הנדרשות.
ועכשיו, לא נצטרך הקצאה דינמית של מבנה נתונים, כי אנחנו יודעים בדיוק כמה ספרות יש לנו! נוכל לכתוב קוד שיש בו פחות הקצאות ומכאן שגם אמור לעבוד מהר יותר. הנה הקוד:
public static string ToDecimalString(int value)
{
if (value == 0)
return "0";
var log10 = Math.Log10(value);
var digitCount = (int) Math.Ceiling(log10);
//fix if needed for the values of 10^n (10, 100, etc.)
if (digitCount == (int)log10)
++digitCount;
var chars = new char[digitCount];
for (var k = chars.Length - 1; k >= 0 ; --k)
{
var mod = value%10;
chars[k] = (char) ('0' + mod);
value /= 10;
}
return new string(chars);
}
[לצערי הביטוי "מינוס מינוס" מומר אוטומטית ב WordPress ל "–"]
שימו לב שכבר תוך כדי הלולאה, סדר הכתיבה למערך התוים הוא הפוך, כדי שלא נצטרך להפוך אותו אח"כ.
נריץ עוד קצת השוואות בין הפתרונות השונים. הפתרון הנוכחי באמת משפר את הביצועים, ואנחנו מגיעים ל 9 טיקים בממוצע. עוד לא הצלחנו לשפר את המימוש המובנה, אבל אנחנו בהחלט בכיוון. מה הלאה? בואו נראה.
ToDecimalString – גירסה שלישית
אני מסתכל על הקוד, והקוד מסתכל עלי.
אני שוב מסתכל על הקוד, ונראה לי שאני עולה על משהו.
הפונקציה הזו, Log10, עושה בשבילי עבודה מיותרת: היא מחזירה לי ערך שאומר לי "עשר בחזקת מה יתן לי את המספר". כלומר היא נותנת לי את ה"מה" הזה. ואני לא צריך את ה"מה" הזה, אני צריך רק לדעת כמה ספרות יש למספר הנתון. אז אולי נוותר על הפונקציה הזה, וננסה להבין כמה ספרות יש למספר הנתון בצורה אחרת.
נסתכל על רצף המספרים בין 0 למספר הגדול ביותר שניתן לכתוב כ int, הלא הוא ידידנו int.MaxValue. נחלק את הרצף הזה לטווחים:
0-9
10-99
100-999
וכו'.
למעשה, נוכל לבנות מערך עם הערכים הבאים: 1, 10, 100 וכו' (המערך יהיה ממויין). כדי לדעת כמה ספרות יש במספר הנתון, נחפש אותו במערך בחיפוש בינארי. יש בדוט נט פונקציה מובנית לחיפוש בינארי, שלא סתם אומרת "מצאתי" או "לא מצאתי". בגדול, אפשר לדעת מהו האינדקס של הערך הקרוב ביותר למה שאנחנו מחפשים, גם אם לא נמצא. אני לא נכנס כאן לפרטים של המתודה Array.BinarySearch, מי שרוצה שיבדוק ב MSDN. אבל הנה הקוד:
private static int[] powersOf10 = new int[]
{
1, 10, 100, 1000, 10000, 100000, 1000000,
10000000, 100000000, 1000000000
};
public static string ToDecimalString(int value)
{
if (value == 0)
return "0";
var index = Array.BinarySearch(powersOf10, value);
if (index < 0)
index = ~index; // not found, get closest index
else
++index;
var digitCount = index;
var chars = new char[digitCount];
for (var k = chars.Length - 1; k >= 0; --k)
{
var mod = value % 10;
chars[k] = (char) ('0' + mod);
value /= 10;
}
return new string(chars);
}
אבל בדיקות של ביצועים בפועל מראות שלמרות המאמצים שלנו, כנראה לא השגנו שיפור משמעותי בביצועים. למעשה נשארנו עם ממוצע של 9 טיקים. למה?
ובכן, BinarySearch מבצע לא מעט השוואות של "גדול מ-" ו"קטן מ-". כל השוואה מחסרת בין המספר הנתון לחזקה מסויימת של 10. החיסור הזה לוקח קצת זמן, מה לעשות..
אבל! אולי, במקום לחלק את הטווח לחזקות של 10, נתחכם עוד יותר.
ToDecimalString – גירסה רביעית
הרעיון כאן הוא לבצע פחות פעולות של השוואת "גדול מ", ולהגיע לכל היותר לפעולת השוואה אחת כדי לדעת כמה ספרות עשרוניות נדרשות כדי לייצג מספר נתון.
איך?
נוכל לדעת מהי הסיבית שהיא ה MSB, שזה קיצור של Most Significant Bit. זוהי הסיבית שמבטאת פחות או יותר את המשפט הבא:
אם נתון לנו מספר x, כמה ספרות נדרשות לייצוג בינארי של x?
למשל, אם x=123, אז הייצוג הבינארי שלו הוא 1111011, ונדרשנו ל 7 ספרות בינאריות. כלומר MSB של 123 זה 7.
באותו אופן, אם x = 9 אז ה MSB שלו הוא 4, כי 9 בייצוג בינארי הוא 1001.
ולמה אני כותב את כל זה? כי למצוא MSB של מספר זה תהליך יחסית מהיר.
אם נוכל למפות את המספרים לפי ה MSB שלהם למספר הספרות שנדרשות לייצג אותם בייצוג עשרוני, אז אנחנו בדרך הנכונה. למעשה, לפי ה MSB נוכל לדעת בצורה די מדוייקת כמה ספרות נדרשות לו בייצוג עשרוני, ונצטרך לכל היותר לבצע בדיקת "גדול מ" אחת ויחידה.
כלומר ה"סוד" של הגירסה הזו הוא מיפוי (מראש) של כל הסיביות לטווח העשרוני שלהם.
אני לא נכנס כאן לתיאור מלא של הקוד, תצטרכו לסמוך עלי שזה עובד:
public class V4
{
private static readonly int[] powersOf10 = new int[]
{
1, 10, 100, 1000, 10000, 100000, 1000000,
10000000, 100000000, 1000000000
};
private static readonly int[] powersOf2 = new int[]
{
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024,
2048, 4096, 8192, 16384, 32768, 65536, 131072,
262144, 524288, 1048576, 2097152, 4194304,
8388608, 16777216, 33554432, 67108864,
134217728, 268435456, 536870912, 1073741824
};
private static int[] decimalDigitsByMsb;
static V4()
{
decimalDigitsByMsb = new int[powersOf2.Length];
for (int k = 1; k < powersOf2.Length; k++)
{
decimalDigitsByMsb[k] = powersOf2[k - 1].ToString().Length;
}
}
public static string ToDecimalString(int value)
{
var mostSignificantBit = 0;
for (int k = powersOf2.Length - 1; k >= 0; k--)
{
var bit = (value & powersOf2[k]) != 0;
if (bit)
{
mostSignificantBit = k + 1;
break;
}
}
if (mostSignificantBit == 0)
return "0";
int index;
if (mostSignificantBit >= decimalDigitsByMsb.Length)
index = decimalDigitsByMsb[decimalDigitsByMsb.Length - 1];
else
index = decimalDigitsByMsb[mostSignificantBit];
if (value >= powersOf10[index])
index++;
var digitCount = index;
var chars = new char[digitCount];
for (var k = chars.Length - 1; k >= 0; --k)
{
var mod = value%10;
chars[k] = (char) ('0' + mod);
value /= 10;
}
return new string(chars);
}
}
והביצועים?
סוף-סוף, המדידות מראות באופן מובהק יתרון קל לגירסה הרביעית: הגענו לממוצע של 6 טיקים! שיפור של 14% בממוצע!
זה לא נגמר
יש עוד כמה שיפורים שאפשר להכניס לכל גירסה:
- תנאי הלולאה בלולאות for לא חייב להיות "גדול מ-", מספיק לראות אם "שונה מ-".
מכאן והלאה הקוד יקבל את השידרוג הזה. - במקום לחשב בכל פעם מחדש את הביטוי '0' + mod, נוכל להשתמש (שוב) בטבלת מיפוי.
כלומר נוכל לכתוב פונקציה סטאטית באופן הבא:
private static char[] digits = new[]
{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };
public static char ToChar(int digit)
{
return digits[digit];
}
אלא שזה יכול קצת לקלקל לנו אם נשאיר את הפונקציה הזו כמו שהיא. למה?
כי עצם הקריאה והביצוע של פונקציה נוספת על ה stack יוצר overhead די רציני. בשפות קרובות יותר למעבד, כמו C, אפשר להנחות את הקומפיילר שיכניס את הפונקציה כמו שהיא לתוך הקוד שקורא לה. זה נקרא inline. זה נותן יתרון בביצועים, לצד תחזוקתיות גבוהה. מצד שני, זה יכול להגדיל קצת את גודל ה executable כולו. בכל מקרה, ב C# אין לנו את הלוקסוס הזה (וטוב שכך. רק למה השאירו לנו את ה volatile?). אז נצטרך לעקוף את זה ע"י הטמעת הקוד של הפונקציה ב class באופן ישיר.
גם את השידרוג הזה נוסיף לגירסאות השונות של המימוש שלנו.
נו, ומה עוד?
ToDecimalString – גירסה חמישית
כן, תמיד יש עוד. והפעם – פעולת החילוק.
לא, לא נפלתי על הראש. הפריימוורק אמור לתת לנו פעולת חילוק כללית. והוא באמת עושה את זה.
ואנחנו צריכים למשימה שלנו רק חילוק ב 10.
אז אולי יש איזה אלגוריתם של חילוק שלמים ב 10 בלבד?
חיפוש קצר העלה את הקוד הבא (מתוך stackoverflow, והנה לינק למקור):
public static int div10(int n)
{
int q, r;
q = (n >> 1) + (n >> 2);
q = q + (q >> 4);
q = q + (q >> 8);
q = q + (q >> 16);
q = q >> 3;
r = n - q * 10;
return q + ((r + 6) >> 4);
}
בדקתי את הקוד הזה על כל מרחב ה int32 החיובי. עובד.
ועכשיו נכניס אותו פנימה, כ inline כמובן:
public static string ToDecimalString(int value)
{
// ...
// old code remains the same
// ...
var chars = new char[digitCount];
for (var k = chars.Length - 1; k != (-1); --k)
{
// inline the div10 operation
int q, r;
q = (value >> 1) + (value >> 2);
q = q + (q >> 4);
q = q + (q >> 8);
q = q + (q >> 16);
q = q >> 3;
r = value - q * 10;
var valueDiv10 = q + ((r + 6) >> 4);
var mod = value - (valueDiv10 * 10);
chars[k] = digits[mod];
value = valueDiv10;
}
return new string(chars);
}
והצלחנו להרוויח עוד קצת: קבלנו ממוצע של 5 טיקים! שיפור של 28% בממוצע!
התוצאות עד כה
הגענו בינתיים לחמש גירסאות שונות, והנה הגרף המתבקש:
העמודה משמאל – מייצגת את ה ToString הסטנדרטי. העמודות שמימינה מייצגות את המימושים שמוצגים כאן.
יש עוד! כנסו כנסו!
תמיד יש עוד. אבל כאן בחרתי להפסיק. הנה כמה רעיונות נוספים לשיפור:
- הקוד כאן בונה את הטקסט המתקבל ספרה אחרי ספרה, מה שגורם גם להעתקות זכרון של תו אחד בכל פעם. כלומר הזכרון משוכפל בכל איטרציה בגודל של תו אחד. אפשר, למשל, לבצע העתקת זכרון של יותר מתו אחד בכל פעם. נניח בזוגות של תוים. או ברביעיות של תוים. סביר להניח שזה ישפר במשהו את הביצועים, כי אז תתבצע העתקה של מספר תוים בבת אחת. סביר להניח שזה גם יסבך קצת את הקוד. וגם יגדיל את צריכת הזכרון הסטאטי.
- ברמת המתמטיקה, אפשר לעשות קצת אנליזה נומרית, ולמצוא פולינום "קל" יותר מהמימוש של Log10, שיהיה קירוב מספיק טוב לדרישות שלנו מ Log10, אבל יהיה יותר קל לביצוע.
- אפשר להקצות מראש מערך באורך 10 תוים, שזה המקסימום שיכול להיות כאן (כי int.MaxValue זה 2147483647, וזה לוקח 10 ספרות. לא יכול להיות יותר מזה). וכך "ניצלנו" מכל העניין של לדעת מראש כמה ספרות יש למספר הנתון. מצד שני, נצטרך להפוך את הסדר של התוים במערך, כך שנוצרה לנו עוד קצת עבודה.
וכנראה אפשר עוד דברים, ואולי לשלב בין הפתרונות השונים כדי להגיע לפתרון אולטימטיבי. אפשר אפילו ללכת רחוק יותר ולנסות להריץ Profiler כמו dotTrace או ANTS. דווקא יכול להיות מעניין.
רגע, מה לגבי שלמים שליליים?
כן, כל הזמן הזה התייחסתי רק לשלמים חיוביים (או אפס, בחלק מהפתרונות). מרגע שידוע כמה ספרות עשרוניות נדרשות לייצוג העשרוני של המספר, זאת בכלל לא בעיה להתאים את הקוד גם למספרים שלמים שליליים. הקוד המצורף מכיל את הגירסה האחרונה עם התוספת הנ"ל.
סיכום
בפוסט הזה הראיתי איך משימה יחסית פשוטה יכולה להיות מורכבת ככל שרוצים להפיק ממנה ביצועים טובים יותר. הראיתי איך פעולות יחסית כלליות יכולות להיות ספציפיות למשימה ואיך אפשר להפוך את זה ליתרון בביצועים. בנוסף הראיתי איך הידיעה של "איך הדברים עובדים מתחת למנוע" יכולה להיות מומרת לביצועים. הדוגמה כאן היתה ToString שמגיע מובנה בפריימוורק, שמזכיר קצת את פונקציית itoa משפת C. רוב השימושים שהיו לי אי פעם ב ToString של int היו פשוט להציג את המספר בייצוג העשרוני שלו. הפריימוורק מציע הרבה יותר מזה: אפשר להשתמש ב Formatter אחר, נניח כזה שגם מציג מפריד אלפים. המעבר מקוד כללי לקוד ספציפי, שיציג את ה int בצורה הפשוטה ביותר, הוא מה שמאפשר להגיע לביצועים טובים יותר במימושים השונים שהצעתי כאן.
המעבר מהכללי לספציפי מביא אותי למסקנה הבאה: אפשר לבצע אופטימיזציות ברמת הקוד. חשוב רק לדעת לא לבצע אותן מוקדם מדי (Premature Optimization) וגם לדעת לא לעבור את הגבול בין קוד קריא ובר תחזוקה לקוד שעובד טיפה'לה יותר מהר. ברוב המקרים השיקולים יהיו לטובת תחזוקתיות גבוהה לעומת שיפורים של אחוזים בודדים בביצועים.
בנוסף, חשוב לי לציין, שחרגתי מגבולות הדוט נט. הקוד הספציפי של חלוקה ב 10 אמור להתקבל כהחלטה של ה JIT Compiler, וכדאי להתרחק ברמת הקוד מאופטימיזציות מהסוג הזה, אלא אם כן היא נותנת מענה ממש חשוב לצוואר בקבוק קיים. באותו אופן, לבצע inline זו גם החלטה קצת חורגת לגבולות הרגילים בדוט נט.
בקיצור, לא הייתי לוקח את הגירסה האחרונה איתי לפרודקשן. אבל כן נהניתי לכתוב אותה, לחקור ולהתעמק בה. המחקר כאן היה נחמד לכשעצמו, ולמדתי עוד קצת על אריתמטיקת שלמים, נברתי עוד קצת בויקיפדיה, שאלתי קצת בתפוז וב stackoverflow על הנושאים שעלו תוך כדי עבודה. פה ושם זה היה קצת כמו לחזור לאקדמיה :-). אם קראתם עד לכאן, כנראה שגם אתם נהניתם 🙂
קידוד נעים! כמובן, כל הקוד זמין להורדה מכאן.
אם יורשה לו להגיב