September 19, 2022

C++ Boolean vector

הרפתקאות הווקטור הבוליאני

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
std::vector<int> ints{ };
std::vector<bool> booleans{ };
// ----------------------------
std::cout << "Before the add \n";
std::cout << "Size of ints " << ints.capacity() << "\n";
std::cout << "Size of booleans " << booleans.capacity() << "\n";

ints.push_back(1);
booleans.push_back(true);

// ----------------------------

std::cout << "\nAfter push_back, Before the reserve \n";

std::cout << "Size of ints " << ints.capacity() << "\n";
std::cout << "Size of booleans " << booleans.capacity() << "\n";

// ----------------------------

ints.reserve(50);
booleans.reserve(50);

std::cout << "\nAfter the reserve \n";

std::cout << "Size of ints " << ints.capacity() << "\n";
std::cout << "Size of booleans " << booleans.capacity() << "\n";

מה לדעתכם יודפס?
במימוש ווקטור רגיל יודפס הבא:

1
2
3
4
5
6
7
8
9
10
11
Before the add
Size of ints 0
Size of booleans 0

After push_back, Before the reserve
Size of ints 1
Size of booleans 1
After the reserve

Size of ints 50
Size of booleans 50

אבל מה שיודפס הוא:

1
2
3
4
5
6
7
8
9
10
11
Before the add
Size of ints 0
Size of booleans 0

After push_back, Before the reserve
Size of ints 1
Size of booleans 32

After the reserve
Size of ints 50
Size of booleans 64

למה בעצם גודל הבוליאנים גדל ל-64?

כל התשובה טמונה באופטימיזציות.

מהו מערך בוליאנים ?

כל ערך מסומן בתור True או False.
בשפה בינארית - 0 או 1.

אולם גודל ההקצאה המינימאלי שלנו הוא - byte - 8 בייטים.
לכן הקצאות כאלו לא יהיו יעילות:

1
bool booleans[64];  // 64 bytes

נוכל לצמצם בקלות את המערך ל-8 בתים בלבד בעזרת long long.

1
long long booleans = 0;

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

שיטת הדגלים

1
2
3
4
5
6
7
8
long long booleans = 0;
auto thirdBit = 1 << 2;
booleans |= thirdBit;

if(booleans & thirdBit == thirdBit)
{
std::cout << "Third bit is turned on \n";
}

בעזרת shifting - נוכל לבצע פעולות על הביט שאנו רוצים.
במקרה הדוגמא - נשתמש בביט השלישי.
0 הוא ללא ביטים ו-1 הוא הביט הראשון הדלוק.

1
2
3
4
5
6
7
0 - 0
1 - 1
2 - 2
4 - 3
8 - 4
16 - 5
וכדו'...

כדי להדליק ביט ניתן להשתמש באופרטור “או” - |=.

כדי לבדוק אם ביט דלוק נשתמש באופרטור “וגם” - &=.

מימוש הווקטור

אם נצפה בקובץ ההאדר של vector נוכל לראות ש-vector<int> משתמש במימוש הגנרי:

אולם vector<bool> מכיל מימוש משלו בעזרת שיטת הספציפיקציה:

ניתן לממש מימוש ספציפי של יישות גנרית בעזרת ספציפיקציה:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<class TEntity>
int Calculate(TEntity one, TEntity two)
{
std::cout << "One\n";
return one + two;
}

template<>
int Calculate(std::string one, std::string two)
{
std::cout << "Two\n";
return one.size() + two.size();
}

auto a = Calculate(1,2);
auto b = Calculate("One"s,"Two"s);

מה יודפס?

מימוש פנימי בקומפיילר MSVC.

כאשר עוקבים אחרי פונקציית ה-insert ניתן לראות בעומק המימוש כיצד זה עובד:

ניתן לראות שאחרי חישוב ה-offset הם לוקחים את הביט הרלוונטי.

ניתן ללמוד מהקובץ vector.h הרבה, חלק מהערות בקוד שלהם:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// Optimize vector<bool> lexicographical comparisons.

// There are several endianness/ordering issues to consider here.
// * Machine endianness is irrelevant. (That affects how an unsigned int is stored
// as a sequence of bytes. While all of our supported architectures are little-endian,
// that's irrelevant as long as we avoid reinterpreting unsigned int as a sequence of bytes.)
// * Appending bits to vector<bool> eventually appends words to its underlying storage.
// For example, vb[10] is stored within vb._Myvec[0], while vb[100] is stored within vb._Myvec[3].
// This allows us to translate lexicographical comparisons from theoretical bits to physical words.
// * Unsigned integers are written and compared as big-endian (most significant bit first).
// For example, 0x10u > 0x07u.
// * However, vector<bool> packs bits into words as little-endian (least significant bit first).
// For example, vector<bool>{false, true, true, true} stores 0b0000'0000'0000'0000'0000'0000'0000'1110u.
// We could bit-reverse words before comparing, but we just need to find the least significant bit that differs.

ניתן לראות שבמימוש שלהם הם משתמשים ב-unsigned int אשר מכיל 32 בתים.
ולכן כל 32 איברים הוא ייקצה unsigned int נוסף ובכך אנחנו חוסכים הרבה מקום!


מה ניתן ללמוד מאופטימיזציות אלו:

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

זהו עוד מקרה פרטני ב-CPP שהופך את השפה ואת ספריית הסטנדרט לעוצמתיות.

תודה רבה על הקריאה!

על הפוסט

הפוסט נכתב על ידי Ilya, רישיון על ידי CC BY-NC-ND 4.0.

שתפו את הפוסט

Email Facebook Linkedin Print

קנו לי קפה

#Software#cpp