Помогите мне разобраться в этой программе побитовой сортировки «Программирование жемчуга».
https://stackoverflow.com/questions/1050253
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Джон Бентли в первой колонке своей книги «Жемчужины программирования» представляет технику сортировки последовательности ненулевых положительных целых чисел с использованием битовых векторов.
Я взял программу 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-й бит
- тест возвращает значение в i-м бите
Я не понимаю, как функции делают то, что делают.Я не могу понять все манипуляции с битами, происходящие в этих трех функциях.
Пожалуйста помоги.
Решение
Первые три константы взаимосвязаны.БИТСПЕРВОРД — 32.Это вы хотите установить на основе вашего компилятора + архитектуры.SHIFT равен 5, потому что 2^5 = 32.Наконец, MASK — это 0x1F, что равно 11111 в двоичном формате (т. е.:нижние 5 бит установлены).Эквивалентно МАСКА = БИТСЛОВО - 1.
Битовый набор концептуально представляет собой просто массив битов.Эта реализация фактически использует массив целых чисел и предполагает 32 бита на целое число.Поэтому всякий раз, когда мы хотим установить, очистить или протестировать (прочитать) бит, нам нужно выяснить две вещи:
- в каком int (массиве) он находится
- о каком из битов этого целого числа мы говорим
Поскольку мы предполагаем, что на целое число приходится 32 бита, мы можем просто разделить на 32 (и усечь), чтобы получить нужный индекс массива.Деление на 32 (BITSPERWORD) аналогично сдвигу вправо на 5 (SHIFT).Вот в чем суть бита [i>>SHIFT].Вы также можете записать это как [i/BITSPERWORD] (и на самом деле вы, вероятно, получите тот же или очень похожий код, если у вашего компилятора есть разумный оптимизатор).
Теперь, когда мы знаем, какой элемент нам нужен, нам нужно выяснить, какой бит.На самом деле, нам нужен остаток.Мы могли бы сделать это с помощью i%BITSPERWORD, но оказывается, что i&MASK эквивалентен.Это связано с тем, что BITSPERWORD — это степень 2 (в данном случае 2^5), а MASK — это все 5 нижних битов.
Другие советы
По сути, это оптимизированная сортировка ведра:
- Зарезервируйте немного длины n битов.
- очистите битовый массив (сначала в основном).
- прочитайте элементы один за другим (все они должны быть разными).
- установите i-й бит в битовом массиве, если номер чтения равен i.
- перебрать битовый массив.
- если бит установлен, распечатайте позицию.
Или другими словами (для N < 10 и для сортировки 3 чисел 4, 6, 2) 0
начните с пустого 10-битного массива (обычно одного целого числа)
0000000000
прочитайте 4 и установите бит в массиве..
0000100000
прочитайте 6 и установите бит в массиве
0000101000
прочитайте 2 и установите бит в массиве
0010101000
перебрать массив и вывести каждую позицию, в которой биты установлены в единицу.
2, 4, 6
отсортировано.
Начиная с set():
Сдвиг вправо на 5 аналогичен делению на 32.Он делает это, чтобы определить, в каком int находится бит.
МАСКА — 0x1f или 31.Операция AND с адресом дает индекс бита внутри int.Это то же самое, что и остаток от деления адреса на 32.
Сдвиг на 1 влево по битовому индексу («1<<(i & MASK)») приводит к получению целого числа, которое имеет только 1 бит в заданном наборе позиций.
Операция OR устанавливает бит.
Строка "int sh = i >> shift;" это потерянная линия, потому что они больше не использовали SH под ней, и вместо этого просто повторили "I >> Shift"
clr() по сути аналогичен set, за исключением того, что вместо операции OR с 1<<(i & MASK) для установки бита используется операция AND с обратным оператором для очистки бита.test() AND с 1<<(i & MASK) для проверки бита.
Битовая сортировка также удалит дубликаты из списка, поскольку она будет учитывать только до 1 на целое число.Сортировка, в которой используются целые числа вместо битов для подсчета более 1 каждого из них, называется поразрядной сортировкой.
Битовая магия используется в качестве специальной схемы адресации, которая хорошо работает с размерами строк, равными степеням двойки.
Если вы попытаетесь понять это (примечание:Я предпочитаю использовать бит на строку, а не бит на слово, поскольку здесь мы говорим о битовой матрице):
// 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.
Когда вы оптимизируете это в памяти, используя одно слово по 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 бит на слово.
Цитируя выдержки из оригинальной статьи 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
Несколько сомнений:1.Зачем нужна 32-битная версия?2.Можем ли мы сделать это в Java, создав HashMap с ключами от 0000000 до 9999999 и значения 0 или 1 на основе присутствия/отсутствия бита?Каковы последствия для такой программы?
