Помогите мне разобраться в этой программе битсорта "Programming pearls" - PullRequest
Новая
       62

Помогите мне разобраться в этой программе битсорта "Programming pearls"

11 голосов
/ 26 июня 2009

Джон Бентли в колонке 1 своей книги «Жемчужины программирования» представляет методику сортировки последовательности ненулевых натуральных чисел с использованием битовых векторов.

Я взял программу bitsort.c из здесь и вставил ее ниже: 

/* 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, set и test, и объясняю их ниже: (пожалуйста, исправьте меня, если я ошибаюсь).

  • clr очищает i-й бит
  • set устанавливает i-й бит
  • test возвращает значение в i-м бите

Теперь я не понимаю, как функции делают то, что они делают. Я не могу понять все битовые манипуляции, происходящие в этих трех функциях.

Пожалуйста, помогите.

Ответы [ 6 ]

23 голосов
/ 26 июня 2009

Первые 3 константы взаимосвязаны. BITSPERWORD - 32. Это вы хотите установить на основе вашей компиляции + архитектуры. SHIFT равен 5, потому что 2 ^ 5 = 32. Наконец, MASK равен 0x1F, что равно 11111 в двоичном формате (то есть: все нижние 5 битов установлены). Эквивалентно, MASK = BITSPERWORD - 1.

Битовый набор концептуально представляет собой просто массив битов. Эта реализация на самом деле использует массив целых и предполагает 32 бита на целое. Поэтому, когда мы хотим установить, очистить или протестировать (прочитать) немного, нам нужно выяснить две вещи:

  • который int (из массива) это в
  • о каких битах этого int мы говорим

Поскольку мы предполагаем 32 бита на целое, мы можем просто разделить на 32 (и усечь), чтобы получить нужный индекс массива. Деление на 32 (BITSPERWORD) аналогично сдвигу вправо на 5 (SHIFT). Так вот о чем говорит бит [i >> SHIFT]. Вы также можете написать это как [i / BITSPERWORD] (и на самом деле вы, вероятно, получите тот же или очень похожий код, если ваш компилятор имеет разумный оптимизатор).

Теперь, когда мы знаем, какой элемент мы хотим, нам нужно выяснить, какой бит. Действительно, мы хотим, чтобы остаток. Мы могли бы сделать это с помощью i% BITSPERWORD, но оказалось, что i & MASK эквивалентна. Это связано с тем, что BITSPERWORD имеет степень 2 (в данном случае 2 ^ 5), а MASK - это 5 нижних битов.

4 голосов
/ 26 июня 2009

По сути, оптимизирована сортировка сегментов:

  • зарезервировать битовый массив длины n биты.
  • очистить массив битов (сначала для основного).
  • читайте предметы по одному (все они должны быть разными).
    • установить i-й бит в массиве битов, если число чтения равно i.
  • итерация битового массива.
    • если бит установлен, вывести позицию.

Или другими словами (для N <10 и для сортировки 3 чисел 4, 6, 2) 0 </p>

начать с пустого 10-битного массива (обычно одно целое число) 

0000000000

прочитайте 4 и установите бит в массиве. 

0000100000

прочитайте 6 и установите бит в массиве 

0000101000

прочитайте 2 и установите бит в массиве 

0010101000

итерирует массив и печатает каждую позицию, в которой биты установлены в единицу.

2, 4, 6

отсортирован.

3 голосов
/ 26 июня 2009

Начиная с set ():
Сдвиг вправо на 5 - это то же самое, что деление на 32. Он делает это, чтобы определить, в каком числе находится бит.
MASK - 0x1f или 31. ANDing с адресом дает битовый индекс внутри int. Это то же самое, что и остаток от деления адреса на 32.
Сдвиг 1 влево на индекс бита («1 << (i & MASK)») приводит к целому числу, которое имеет только 1 бит в заданной позиции. <br> ORing устанавливает бит.
Строка "int sh = i >> SHIFT;" это пустая строка, потому что они не использовали sh снова под ней, а вместо этого просто повторили «i >> SHIFT»

clr () в основном совпадает с установленным, за исключением того, что вместо ORing с 1 << (i & MASK) для установки бита это AND с обратным для очистки бита. test () AND с 1 << (i & MASK) для проверки бита. </p>

Битовая сортировка также удалит дубликаты из списка, поскольку она будет считаться только до 1 на целое число. Сортировка, которая использует целые числа вместо битов для подсчета более 1 каждого, называется радикальной сортировкой.

2 голосов
/ 26 июня 2009

Битовая магия используется в качестве специальной схемы адресации, которая хорошо работает с размерами строк, равными двум.

Если вы попытаетесь понять это (примечание: я предпочитаю использовать биты на строку, а не биты на слово, поскольку здесь речь идет о битовой матрице): 

// 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;

Итак, чтобы установить i-й бит, вы можете сделать это: 

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

Еще один важный момент: оператор по модулю может быть заменен логическим И, а оператор / также может быть заменен смещением, если второй операнд имеет степень двойки. 

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

Это, в конечном счете, сводится к очень плотной, но трудной для понимания биткой лексике 

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

Но я не вижу, чтобы алгоритм работал, например, 40 бит на слово.

0 голосов
/ 08 июля 2014

Цитируя выдержки из оригинальной статьи Bentleys в 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
0 голосов
/ 14 сентября 2009

Несколько сомнений: 1. Зачем это нужно 32 бит? 2. Можем ли мы сделать это в Java, создав HashMap с ключами от 0000000 до 9999999 а значения 0 или 1 основаны на наличии / отсутствии бита? Каковы последствия для такой программы?

...