הרפתקאות הווקטור הבוליאני
1 | std::vector<int> ints{ }; |
מה לדעתכם יודפס?
במימוש ווקטור רגיל יודפס הבא:
1 | Before the add |
אבל מה שיודפס הוא:
1 | Before the add |
למה בעצם גודל הבוליאנים גדל ל-64?
כל התשובה טמונה באופטימיזציות.
מהו מערך בוליאנים ?
כל ערך מסומן בתור True
או False
.
בשפה בינארית - 0 או 1.
אולם גודל ההקצאה המינימאלי שלנו הוא - byte
- 8 בייטים.
לכן הקצאות כאלו לא יהיו יעילות:
1 | bool booleans[64]; // 64 bytes |
נוכל לצמצם בקלות את המערך ל-8 בתים בלבד בעזרת long long
.
1 | long long booleans = 0; |
ואז בשיטת הדגלים נוכל לקחת כל ערך מביט בודד.
שיטת הדגלים
1 | long long booleans = 0; |
בעזרת shifting
- נוכל לבצע פעולות על הביט שאנו רוצים.
במקרה הדוגמא - נשתמש בביט השלישי.0
הוא ללא ביטים ו-1
הוא הביט הראשון הדלוק.
1 | 0 - 0 |
כדי להדליק ביט ניתן להשתמש באופרטור “או” - |=
.
כדי לבדוק אם ביט דלוק נשתמש באופרטור “וגם” - &=
.
מימוש הווקטור
אם נצפה בקובץ ההאדר של vector
נוכל לראות ש-vector<int>
משתמש במימוש הגנרי:
אולם vector<bool>
מכיל מימוש משלו בעזרת שיטת הספציפיקציה:
ניתן לממש מימוש ספציפי של יישות גנרית בעזרת ספציפיקציה:
1 | template<class TEntity> |
מה יודפס?
מימוש פנימי בקומפיילר MSVC.
כאשר עוקבים אחרי פונקציית ה-insert
ניתן לראות בעומק המימוש כיצד זה עובד:
ניתן לראות שאחרי חישוב ה-offset
הם לוקחים את הביט הרלוונטי.
ניתן ללמוד מהקובץ vector.h
הרבה, חלק מהערות בקוד שלהם:
1 |
|
ניתן לראות שבמימוש שלהם הם משתמשים ב-unsigned int
אשר מכיל 32 בתים.
ולכן כל 32 איברים הוא ייקצה unsigned int
נוסף ובכך אנחנו חוסכים הרבה מקום!
מה ניתן ללמוד מאופטימיזציות אלו:
- ניתן לחסוך בזיכרון כשיכולים.
- מימוש פרטני לאלגוריתמים גנריים מעניק יכולות חדשות מבלי לגרוע מהממשק.
- כדי לממש אופטימציות צריך לצלול למימוש הספציפי - לא תמיד ניתן לעשות את זה באופן גנרי.
- המימוש הגנרי של ווקטור לא אופטימלי לכל המקרים.
זהו עוד מקרה פרטני ב-CPP
שהופך את השפה ואת ספריית הסטנדרט לעוצמתיות.
תודה רבה על הקריאה!