ما هي أسرع طريقة (طرق) للتكرار عبر مجموعة كبيرة من البيانات على أساس كل بت

Question

أنا أقوم بتشغيل كتلة ذاكرة من البيانات الثنائية حسب البايت.

حاليا أفعل شيئا مثل هذا:

for (i = 0; i < data->Count; i++)
{   
    byte = &data->Data[i];
    ((*byte & Masks[0]) == Masks[0]) ? Stats.FreqOf1++; // syntax incorrect but you get the point.
    ((*byte & Masks[1]) == Masks[1]) ? Stats.FreqOf1++;
    ((*byte & Masks[2]) == Masks[2]) ? Stats.FreqOf1++;
    ((*byte & Masks[3]) == Masks[3]) ? Stats.FreqOf1++;
    ((*byte & Masks[4]) == Masks[4]) ? Stats.FreqOf1++;
    ((*byte & Masks[5]) == Masks[5]) ? Stats.FreqOf1++;
    ((*byte & Masks[6]) == Masks[6]) ? Stats.FreqOf1++;
    ((*byte & Masks[7]) == Masks[7]) ? Stats.FreqOf1++;
}

أين الأقنعة:

for (i = 0; i < 8; i++)
{
    Masks[i] = 1 << i;
}

(بطريقة ما لم أتمكن من القيام بذلك بالسرعة في حلقة أو في دالة مضمنة، لذلك قمت بكتابتها.)

هل لدى أي شخص أي اقتراحات حول كيفية تحسين هذه الحلقة الأولى؟أنا عديم الخبرة إلى حد ما في الوصول إلى البتات.

قد يبدو هذا أمرًا غبيًا للقيام به.لكنني بصدد تنفيذ خوارزمية الضغط.أريد فقط الحصول على جزء الوصول إلى الأسفل بشكل صحيح.

شكرًا!

ملاحظة:هذا موجود في برنامج التحويل البرمجي Visual Studio 2008.لذلك سيكون من الرائع أن يتم تطبيق الاقتراحات على هذا المترجم.

pps:لقد أدركت للتو أنني لست بحاجة إلى زيادة عددين.واحد سيكون كافيا.ثم احسب الفرق بين إجمالي البتات في النهاية.لكن هذا سيكون خاصًا بالعد فقط.ما أريد فعله بسرعة هو استخراج البتات.

يحرر:فكرة جدول البحث التي تم طرحها رائعة.لكني أدركت أنني طرحت السؤال بشكل خاطئ في العنوان.لأن ما أريد القيام به في النهاية ليس عد البتات، بل الوصول إلى كل بت في أسرع وقت ممكن.

تعديل آخر:هل من الممكن تقديم المؤشر بمقدار بت واحد فقط في البيانات؟

تعديل آخر:شكرا لكم على كل إجاباتكم حتى الآن.

ما أريد تنفيذه في الخطوات التالية هو برنامج تشفير حسابي ثنائي غير متطور لا يقوم بتحليل السياق.لذلك أنا مهتم فقط بالبتات الفردية في الوقت الحالي.في النهاية سوف يصبح BAC متكيفًا مع السياق ولكني سأترك ذلك لوقت لاحق.

يمكن أن تكون معالجة 4 بايت بدلاً من بايت واحد خيارًا.لكن تكرار الحلقة التي تزيد عن 32 بت يعد مكلفًا أيضًا، أليس كذلك؟

Answer 1

لم أفهم حقًا ما تحاول القيام به.ولكن إذا كنت ترغب فقط في الوصول إلى أجزاء الصورة النقطية، فيمكنك استخدام هذه الوظائف (التي لم يتم اختبارها!!!):

#include <stddef.h>

_Bool isbitset(unsigned char * bitmap, size_t idx)
{
    return bitmap[idx / 8] & (1 << (idx % 8)) ? 1 : 0;
}

void setbit(unsigned char * bitmap, size_t idx)
{
    bitmap[idx / 8] |= (1 << (idx % 8));
}

void unsetbit(unsigned char * bitmap, size_t idx)
{
    bitmap[idx / 8] &= ~(1 << (idx % 8));
}

void togglebit(unsigned char * bitmap, size_t idx)
{
    bitmap[idx / 8] ^= (1 << (idx % 8));
}

يحرر: حسنًا، أنا يفكر أفهم ما تريد القيام به:التكرار السريع على سلسلة من البتات.لذلك، لا نريد استخدام وظائف الوصول العشوائي من الأعلى، بل نريد قراءة كلمة كاملة من البيانات مرة واحدة.

يمكنك استخدام أي نوع عدد صحيح غير موقّع تريده، ولكن يجب عليك اختيار نوع من المرجح أن يتوافق مع حجم الكلمة في بنيتك.سأذهب مع uint_fast32_t من stdint.h:

uint_fast32_t * data = __data_source__;
for(; __condition__; ++data)
{
    uint_fast32_t mask = 1;
    uint_fast32_t current = *data;
    for(; mask; mask <<= 1)
    {
        if(current & mask)
        {
            // bit is set
        }
        else
        {
            // bit is not set
        }
    }
}

من الحلقة الداخلية، يمكنك ضبط القطعة باستخدام

*data |= mask;

قم بإلغاء ضبط الشيء مع

*data &= ~mask;

وتبديل الشيء مع

*data ^= mask;

تحذير: قد يتصرف الكود بشكل غير متوقع في البنى ذات النهاية الكبيرة!

Answer 2

وأسرع طريقة هي على الأرجح لبناء جدول بحث القيم بايت مقابل عدد البتات المنصوص عليها في هذا بايت. ان كان ما لا يقل عن الإجابة عندما قابلت في جوجل.

Answer 3

وانظر الرابط التالي لعشرات من الاشياء المتعلقة بت: بت Twiddling المأجورون

Answer 4

استخدم جدول خرائط كل قيمة البايت (256) إلى رقم 1 في ذلك. (و# 0 هو مجرد (8 - # 1 ل)). ثم تكرار عبر بايت وإجراء بحث واحد لكل بايت، بدلا من عمليات البحث ومقارنات متعددة. على سبيل المثال:

int onesCount = 0;
for (i = 0; i < data->Count; i++)
{   
    byte = &data->Data[i];
    onesCount += NumOnes[byte];
}
Stats.FreqOf1 += onesCount;
Stats.FreqOf0 += (data->Count * 8) - onesCount;

Answer 5

هل يمكن استخدام جدول بحث precomputed، أي بمعنى:

static int bitcount_lookup[256] = { ..... } ; /* or make it a global and compute the values in code */

...

for( ... ) 
   byte = ... 
   Stats.FreqOf1 += bitcount_lookup[byte];

Answer 6

وهنا هو طريقة كيف نحسب 1 بت عدد صحيح 32BIT و(على أساس طريقة Integer.bitCount(i) جاوة):

unsigned bitCount(unsigned i) {
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    i = (i + (i >> 4)) & 0x0f0f0f0f;
    i = i + (i >> 8);
    i = i + (i >> 16);
    return i & 0x3f;
}

وهكذا يمكنك أن يلقي البيانات الخاصة بك لكثافة العمليات والمضي قدما في 4 خطوات بايت.

Answer 7

إليك فكرة بسيطة قمت بإعدادها بقيمة 32 بت واحدة فقط، ولكن يمكنك أن ترى أنه لن يكون من الصعب تكييفها مع أي عدد من البتات....

int ones = 0;
int x = 0xdeadbeef;
for(int y = 0;y < 32;y++)
{
    if((x & 0x1) == 0x1) ones++;
    x = (x >> 1);
}

printf("%x contains %d ones and %d zeros.\n", x, ones, 32-ones);

ومع ذلك، لاحظ أنه يعدل القيمة في العملية.إذا كنت تفعل ذلك على البيانات التي تحتاج إلى الاحتفاظ بها، فأنت بحاجة إلى عمل نسخة منها أولاً.

من المحتمل أن يكون القيام بذلك في __asm ​​طريقة أفضل، وربما أسرع، ولكن من الصعب تحديد مدى قدرة المترجم على التحسين...

مع كل حل تفكر فيه، سيكون لكل حل عيوبه.جدول البحث أو ناقل الحركة الصغير (مثل جدولي)، كلاهما لهما عيوب.

لاري

Answer 8

ttobiass - ضع في اعتبارك أن وظائفك المضمنة مهمة في التطبيقات مثل التي تتحدث عنها، ولكن هناك أشياء تحتاج إلى وضعها في الاعتبار.أنت يستطيع احصل على الأداء من التعليمات البرمجية المضمنة، فقط تذكر بعض الأشياء.

• مضمنة في وضع التصحيح غير موجود.(ما لم تجبره)
• سيقوم المترجم بتضمين الوظائف كما يراها مناسبة.في كثير من الأحيان، إذا طلبت منه تضمين دالة، فقد لا يفعل ذلك على الإطلاق.حتى لو كنت تستخدم __forceinline.تحقق من MSDN لمزيد من المعلومات حول التضمين.
• يمكن تضمين وظائف معينة فقط.على سبيل المثال، لا يمكنك تضمين دالة متكررة.

ستحصل على أفضل أداء من خلال إعدادات مشروعك للغة C/C++ وكيفية إنشاء التعليمات البرمجية الخاصة بك.في هذه المرحلة، من المهم أن نفهم الكومة مقابل.عمليات المكدس، واصطلاحات الاتصال، ومحاذاة الذاكرة، وما إلى ذلك.

أعلم أن هذا لا يجيب على سؤالك بالضبط، لكنك ذكرت الأداء، وكيفية الحصول على أفضل أداء، وهذه الأشياء هي المفتاح.

Answer 9

لتنضم إلى عربة الرابط: عد بت

Answer 10

إذا هذه ليست حالة من التحسين سابق لأوانه، وكنت بحاجة حقا للضغط على كل الفيمتو ثانية الماضي، ثم ربما كنت أفضل حالا مع مجموعة ثابتة 256 العنصر الذي نشر مرة واحدة مع العد قليلا من كل قيمة بايت ، ثم

<اقتباس فقرة>   

وStats.FreqOf1 + = bitCountTable [بايت]

وعندما يتم الحلقة:

<اقتباس فقرة>   

وStats.FreqOf0 = ((data-> عدد * 8) - Stats.FreqOf1)

Answer 11

هناك فصل كامل عن التقنيات المختلفة لهذا في الكتاب كود جميل.يمكنك قراءتها (معظمها) على كتب جوجل ابتداء من هنا.

Answer 12

الطريقة الأسرع لاستخراج البتات هي استخدام:

bitmask= data->Data[i];

while (bitmask)
{
    bit_set_as_power_of_two= bitmask & -bitmask;
    bitmask&= bitmask - 1;
}

إذا كنت تريد فقط حساب مجموعة البتات، فسيكون جدول البحث LUT الموجود في ذاكرة التخزين المؤقت سريعًا، ولكن يمكنك أيضًا القيام بذلك في وقت ثابت باستخدام طريقة عد البتات المتداخلة في الرابط في هذه الإجابة.