ساعدني على فهم هذا "البرمجة اللؤلؤ" bitsort البرنامج

Question

جون بنتلي في العمود 1 من كتاب البرمجة اللؤلؤ يدخل تقنية الفرز تسلسل غير الصفر الاعداد الصحيحه الايجابية باستخدام بت ناقلات.

لقد اتخذت البرنامج bitsort.ج من هنا و لصقه أدناه:

/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */

/* bitsort.c -- bitmap sort from Column 1
 *   Sort distinct integers in the range [0..N-1]
 */

#include <stdio.h>

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000

int a[1 + N/BITSPERWORD];

void set(int i) 
{
    int sh = i>>SHIFT;
    a[i>>SHIFT] |=  (1<<(i & MASK)); 
}
void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int  test(int i){ return a[i>>SHIFT] &   (1<<(i & MASK)); }

int main()
{   int i;
for (i = 0; i < N; i++)
    clr(i);

    /*Replace above 2 lines with below 3 for word-parallel init
    int top = 1 + N/BITSPERWORD;
    for (i = 0; i < top; i++)
    a[i] = 0;
    */

while (scanf("%d", &i) != EOF)
    set(i);
for (i = 0; i < N; i++)
        if (test(i))
    printf("%d\n", i);
return 0;
}

أنا أفهم ما وظائف clr, مجموعة اختبار يفعلون وشرح لهم أدناه:( يرجى تصحيح لي إذا كنت مخطئا هنا ).

• clr مسح ith بت
• مجموعة مجموعات ith بت
• اختبار بإرجاع قيمة في ith بت

الآن, أنا لا أفهم كيف مهام يفعلون ما يفعلونه.أنا غير قادر على معرفة كل بت التلاعب يحدث في تلك الوظائف الثلاث.

الرجاء المساعدة.

Answer 1

أول 3 الثوابت هي مترابطة.BITSPERWORD 32.هذا كنت ترغب في تعيين على أساس مترجم+العمارة.التحول هو 5 ، لأن 2^5 = 32.وأخيرا قناع 0x1F وهو 11111 الثنائية (أي:أسفل 5 قطع في كل مجموعة).مكافئ, قناع = BITSPERWORD - 1.

Bitset هو من الناحية النظرية فقط مجموعة من البتات.هذا التطبيق يستخدم في الواقع مجموعة من رجات ، يفترض 32 بت لكل int.لذا عندما نريد أن مجموعة مسح أو اختبار (قراءة) قليلا نحن بحاجة إلى معرفة أمرين:

• والتي الباحث (المصفوفة) هو في
• أي أن الباحث بت نتحدث عنه

لأننا افتراض 32 بت لكل int, يمكننا أن القسمة 32 (و اقتطاع) للحصول على مؤشر مجموعة نريد.قسمة 32 (BITSPERWORD) هو نفس التحول إلى اليمين قبل 5 (التحول).وهذا ما a[i>>SHIFT] قليلا عن.يمكنك أيضا كتابة هذا[أنا/BITSPERWORD] (و في الواقع, كنت على الارجح الحصول على نفس أو مماثلة رمز افتراض مترجم معقول محسن).

الآن أن نعرف أي عنصر من نريد, نحن بحاجة إلى معرفة أي قليلا.حقا نريد الباقي.يمكننا أن نفعل هذا مع%BITSPERWORD ، ولكن اتضح أنني&قناع ما يعادلها.وهذا لأن BITSPERWORD هو قوة 2 (2^5 في هذه الحالة) و القناع أسفل 5 قطع في كل مجموعة.

Answer 2

في الأساس هو دلو النوع الأمثل:

• الاحتياطي قليلا مجموعة من طول n بت.
• الواضح بت array (الأولى في الرئيسية).
• قراءة العناصر واحدا تلو الآخر (يجب أن تكون كلها متميزة).
  • تعيين لا يستحق قليلا في صفيف بت إذا كان قراءة عدد هو أنا.
• تكرار بت مجموعة.
  • إذا تم تعيين بت ثم طباعة الموقف.

أو بعبارة أخرى (ن < 10 لفرز الأرقام 3 4, 6, 2) 0

تبدأ مع فارغة 10 بت array (الملقب عدد صحيح واحد عادة)

0000000000

قراءة 4 و تعيين بت في مجموعة..

0000100000

قراءة 6 و تعيين بت في مجموعة

0000101000

قراءة 2 و تعيين بت في مجموعة

0010101000

تكرار مجموعة وطباعة كل موقف في بت تعيين واحد.

2, 4, 6

فرز.

Answer 3

بدءا من مجموعة():
الحق في التحول من 5 هو نفس تقسيم 32.فإنه يفعل ذلك على الباحث بت في.
قناع 0x1f أو 31.واقف مع العنوان يعطي بت مؤشر داخل int.انها نفس باقي قسمة خطاب 32.
تحويل 1 خلفها بت مؤشر ("1<<(i & قناع)") النتائج في عدد صحيح التي لديها فقط 1 بت في وضع مجموعة.
ORing مجموعات بت.
خط "الباحث sh = أنا>>SHIFT;" هو إهدار الخط ، لأنها لم تستخدم sh مرة أخرى تحتها, و بدلا من مجرد تكرار "أنا>>SHIFT"

clr() هو أساسا نفس المجموعة ، باستثناء بدلا من ORing مع 1<<(i & قناع) إلى تعيين بت ، فإنه يستخدم المعامل مع عكسية واضحة قليلا.اختبار() يستخدم المعامل 1<<(i & قناع) إلى اختبار قليلا.

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

Answer 4

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

إذا كنت في محاولة فهم هذا (ملاحظة:أنا أفضل استخدام بت لكل صف من البتات لكل كلمة ، منذ نتحدث عنه قليلا-مصفوفة هنا):

// supposing an int of 1 bit would exist...
int1 bits[BITSPERROW * N]; // an array of N x BITSPERROW elements

// set bit at x,y:
int linear_address = y*BITSPERWORD + x;
bits + linear_address = 1; // or 0
// 0 1 2 3 4 5 6 7 8 9 10 11 ... 31
// . . . . . . . . . .  .  .       .  
// . . . . X . . . . .  .  .       .  -> x = 4, y = 1 => i = (1*32 + 4)

بيان linear_address = y*BITSPERWORD + x يعني أيضا أن x = linear_address % BITSPERWORD و y = linear_address / BITSPERWORD.

عندما كنت أمثل هذا في الذاكرة باستخدام كلمة 1 من 32 بت لكل صف ، يمكنك الحصول على حقيقة أن قليلا في العمود x يمكن تعيين باستخدام

int bitrow = 0;
bitrow |= 1 << (x);

نحن الآن عندما أعاد على البتات ، ونحن لديك عنوان خطية ، ولكن تحتاج إلى العثور على الكلمة المقابلة.

int column = linear_address % BITSPERROW;
int bit_mask =  1 << column; // meaning for the xth column, 
                             // you take 1 and shift that bit x times
int row    = linear_address / BITSPERROW;

لذلك لضبط لا يستحق قليلا, يمكنك القيام بذلك:

bits[ i%BITSPERROW ] |= 1 << (linear_address / BITSPERROW );

إضافية مسكتك هو أن المشغل نمطية يمكن استبداله منطقية ، / المشغل يمكن الاستعاضة عن التحول أيضا ، إذا كان المعامل الثاني هو الطاقة من اثنين.

a % BITSPERROW == a & ( BITSPERROW - 1 ) == a & MASK
a / BITSPERROW == a >> ( log2(BITSPERROW) ) == a & SHIFT

هذا يتلخص في نهاية المطاف كثيفة جدا ، ومع ذلك يصعب فهم-for-the-bitfucker-الملحد التدوين

a[ i >> SHIFT ] |= ( 1 << (i&MASK) );

ولكن أنا لا أرى خوارزمية العمل مثلا40 بت لكل كلمة.

Answer 5

نقلا عن مقتطفات من بنتلي' المقالة الأصلية في DDJ, وهذا ما لا على مستوى عال:

/* phase 1: initialize set to empty */

for (i = 0; i < n; i++)

    bit[i] = 0

/* phase 2: insert present elements */

for each i in the input file

    bit[i] = 1

/* phase 3: write sorted output */

for (i = 0; i < n; i++)

    if bit[i] == 1

        write i on the output file

Answer 6

بعض الشكوك :1.لماذا هو في حاجة إلى 32 bit ?2.يمكننا أن نفعل هذا في جافا عن طريق إنشاء HashMap مع المفاتيح من 0000000 إلى 9999999 والقيم 0 أو 1 على أساس وجود/غياب ؟ ما هي الآثار المترتبة لمثل هذا البرنامج ؟