Помогите мне понять эту программу «Программирование жемчуга».

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

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

/* 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 очищает бит-ю
набор устанавливает бит-ю
тест возвращает значение в г-й бит

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

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

источник

2009-06-26 ardsrk

Я принимаю ответ Лоуренса, как это помогло мне понять, о механике этой программы в фундаментальный уровень. – ardsrk

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

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

какой Int (массива) он в
который битов, ИНТ в мы говорим около

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

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

источник

2009-06-26 17:56:03

Это на человеческом языке то, что я намеревался скажем :) +1 за понятность! – xtofl

@Laurence Gonsalves отличный анализ, +1 :) – Tracy

В основном это ведро рода оптимизировано:

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

Или, другими словами (для N < 10 и сортировать 3 номера 4, 6, 2) 0

старт с пустой 10 битовый массив (он же одно число обычно)

0000000000

чтения 4 и установить бит в массиве ..

0000100000

чтения 6 и установить бит в массиве

0000101000

читать 2 и установить бит в массиве

0010101000

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

2, 4, 6

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

источник

2009-06-26 17:34:44

damn :-) Объяснил неправильный вопрос. –

Не беспокойтесь. Я ценю ваше участие. – ardsrk

Как бы то ни было, это была та часть, которую я не совсем понял. Благодарю. – xtofl

Начиная с набором():
Правый сдвиг 5 такая же, как деление на 32. Это что, чтобы найти который Int бит в
Маску 0x1F или 31. с операция AND адреса дает. битовый индекс внутри int. Это то же самое, что и остаток деления адреса на 32.
Смещение 1, оставшееся от битового индекса («1 < < (i & MASK)») приводит к целому числу, которое имеет только 1 бит в заданной позиции.
ORing устанавливает бит.
Линия «int sh = i >> SHIFT;» это потерянная линия, потому что они не использовали sh снова под ней, а вместо этого просто повторяли «i >> SHIFT»

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

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

источник

2009-06-26 17:41:01 David

Iirc, сортировка radix отличается. – quinmars

quinmars, не могли бы вы уточнить – ardsrk

Он прав. Наверное, я описал сортировку, а не сортировку. – David

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

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

// 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 бит в строку, вы получите тот факт, что немного в колонке х может быть установлена с помощью

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

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

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

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

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

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

источник

2009-06-26 18:35:46 xtofl

-3

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

источник

2009-09-14 12:01:20

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

источник

2014-07-08 19:37:15 Viren

Помогите мне понять эту программу «Программирование жемчуга».

ответ

Смежные вопросы