صفيف بت في C ++

Question

عند العمل مع مشكلات مشروع Euler ، غالبًا ما أحتاج إلى مجموعة كبيرة (> 10 ** 7).

مقاربي العادية هو واحد من:

bool* sieve = new bool[N];

bool sieve[N];

عندما n = 1،000،000 يستخدم برنامجي 1 ميغابايت (8 * 1،000،000 بت).

هل هناك طريقة أكثر كفاءة لاستخدام صفائف بت المتجر من Bool في C ++؟

Answer 1

يستخدم std::bitset (لو N هو ثابت) وإلا استخدم std::vector<bool> كما ذكر آخرون (لكن لا تنسوا القراءة هذه المقالة الممتازة بواسطة Herb Sutter)

BitSet عبارة عن فئة حاوية خاصة مصممة لتخزين البتات (عناصر ذات قيمتين محتملين فقط: 0 أو 1 ، صواب أو خطأ ، ...).

الفصل يشبه إلى حد كبير صفيف منتظم ، لكن التحسين لتخصيص المساحة: يحتل كل عنصر بت واحد فقط (وهو أقل من ثمانية أضعاف من أصغر نوع عنصري في C ++: char).

تعديل:

يذكر Herb Sutter (في هذا المقال) ذلك

السبب في أن السبب std :: vector <Oool> غير متطابق هو أنه يسحب الحيل تحت الأغطية في محاولة للتحسين للمساحة: بدلاً من تخزين char الكامل أو int لكل منطق [1] (تناول ما لا يقل عن 8 أضعاف المساحة ، على المنصات ذات 8 بت chars) ، إنه يحزم المنازل ويخزنها كبطن فردي(من الداخل ، على سبيل المثال ، chars) في تمثيلها الداخلي.

Std :: Vector <Oool> القوات تحسين محدد لجميع المستخدمين عن طريق تكريسه في المعيار. إنها ليست فكرة جيدة؛ لدى المستخدمين المختلفين متطلبات مختلفة ، والآن يجب على جميع مستخدمي Vector دفع عقوبة الأداء حتى لو كانوا لا يريدون أو يحتاجون إلى توفير المساحة.

تحرير 2:

وإذا كنت قد استخدمت دفعة يمكنك استخدامها boost::dynamic_bitset(لو N معروف في وقت التشغيل)

Answer 2

للأفضل أو للأسوأ، std::vector<bool> سوف تستخدم البتات بدلاً من Bool ، لتوفير المساحة. لذلك فقط استخدم std::vector كما يجب أن تكون في المقام الأول.

لو N ثابت, ، يمكنك استخدام std::bitset.

Answer 3

لا يتم تخزين نوع "Bool" باستخدام 1 بت فقط. من تعليقك حول الحجم ، يبدو أنه يستخدم بايت كامل لكل وحدة منطقية.

AC مثل طريقة القيام بذلك ستكون:

uint8_t sieve[N/8]; //array of N/8 bytes

ثم منطقيًا أو بايت معًا للحصول على جميع أجزاءك:

sieve[0] = 0x01 | 0x02; //this would turn on the first two bits

في هذا المثال ، 0x01 و 0x02 هي أرقام سداسية عشرية تمثل بايت.

Answer 4

يمكن أن تبحث عن std::bitset و std::vector<bool>. غالبًا ما ينصح هذا الأخير ، لأنه على الرغم من vector بالاسم ، لا يتصرف حقًا مثل متجه لأي نوع آخر من الأشياء ، وفي الواقع لا يفي بمتطلبات الحاوية بشكل عام. ومع ذلك ، يمكن أن تكون مفيدة جدا.

OTOH ، لا شيء سوف (على الأقل بشكل يمكن الاعتماد عليه) تخزين 1 مليون قيم منطقية في أقل من مليون بت. إنه ببساطة لا يمكن القيام به مع أي يقين. إذا كانت مجموعات البت الخاصة بك تحتوي على درجة من التكرار ، فهناك العديد من مخططات الضغط التي قد تكون فعالة (على سبيل المثال ، LZ*، Huffman ، الحساب) ولكن دون معرفة محتويات ، من المستحيل القول أنها ستكون مؤكدة. ومع ذلك ، فإن أيًا من هذين سيقومون بتخزين كل منطق/بت في تخزين واحد فقط (بالإضافة إلى أ القليل في سماء المسامير - ولكن هذا عادة ما يكون ثابتًا ، وعند ترتيب بايت لعشرات البايت على الأكثر).

Answer 5

نعم ، يمكنك استخدام أ bitset.

Answer 6

قد تكون مهتمًا بتجربة Bitscan المكتبة كبديل. في الآونة الأخيرة ، تم اقتراح امتداد للتفاؤل ، وهو ما لست متأكدًا من أنه قد تمثله ، ولكن قد يكون كذلك.

Answer 7

محاولة Std :: bitset

Answer 8

يمكنك استخدام صفيف بايت وفهرس في ذلك. فِهرِس n سيكون في فهرس البايت n/8, ، قليل # n%8. (في حالة std :: bitset غير متوفر لسبب ما).

Answer 9

إذا كان N معروفًا في وقت الترجمة ، فاستخدم Std :: bitset, ، وإلا استخدم Boost :: Dynamic_Bitset.

Answer 10

لا يتم تخزين نوع "Bool" باستخدام 1 بت فقط. من تعليقك حول الحجم ، يبدو أنه يستخدم بايت كامل لكل وحدة منطقية.

AC مثل طريقة القيام بذلك ستكون:

uint8_t sieve[N/8]; //array of N/8 bytes

عنصر الصفيف هو:

result = sieve[index / 8] || (1 << (index % 8)); 

أو

result = sieve[index >> 3] || (1 << (index & 7));

تعيين 1 في Array:

sieve[index >> 3] |= 1 << (index & 7);