Pomóż mi zrozumieć ten program" Perły programowania " bitsort
Jon Bentley w kolumnie 1 swojej książki "perły programowania" wprowadza technikę sortowania ciągu niezerowych dodatnich liczb całkowitych przy użyciu wektorów bitowych.
Wziąłem program bitsort.c z tutaj i wkleiłem go poniżej:
/* 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;
}
Rozumiem, co robią funkcje clr, set i test i wyjaśniam je poniżej: (proszę mnie poprawić, jeśli się mylę).
- clr czyści i-Ty bit
- set ustawia I-ty bit
- test zwraca wartość na i-tym bitie
6 answers
Pierwsze 3 stałe są ze sobą powiązane. BITSPERWORD jest 32. To chcesz ustawić na podstawie kompilatora+architektury. SHIFT to 5, Bo 2^5 = 32. Wreszcie, maska jest 0x1F, który jest 11111 w binarnym (tj.: dolne 5 bitów są ustawione). Równoważnie, Maska = BITSPERWORD - 1.
Zestaw bitów jest koncepcyjnie tylko tablicą bitów. Implementacja ta używa tablicy int i przyjmuje 32 bity na int. Więc kiedy chcemy ustawić, wyczyścić lub przetestować (przeczytać) trochę musimy dowiedzieć się dwie rzeczy:
- który int (tablicy) jest w
- o którym z bitów int mówimy
Ponieważ zakładamy 32 bity na int, możemy po prostu podzielić przez 32 (i obciąć), aby uzyskać indeks tablicy, który chcemy. Dzielenie przez 32 (BITSPERWORD) jest takie samo jak przesunięcie w prawo przez 5 (SHIFT). Więc o to chodzi w bitach a[i>>SHIFT]. Możesz również napisać to jako [i / BITSPERWORD] (a w rzeczywistości prawdopodobnie dostaniesz ten sam lub bardzo podobny kod, zakładając, że kompilator Ma rozsądny optymalizator).
Teraz, gdy wiemy, który element a chcemy, musimy dowiedzieć się, który bit. Naprawdę, chcemy resztę. Możemy to zrobić z i % BITSPERWORD, ale okazuje się, że i&MASK jest równoważne. Dzieje się tak dlatego, że BITSPERWORD jest mocą 2 (w tym przypadku 2^5), a maska to dolne 5 bitów.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-06-26 17:56:03
W zasadzie jest to sortowanie kubełkowe zoptymalizowane:
- zarezerwować tablicę bitów o długości n bity.
- Wyczyść tablicę bitów (najpierw Dla in main).
- odczytaj pozycje jeden po drugim(wszystkie muszą być odrębne).
- ustawia i ' ten bit w tablicy bitów, jeśli odczytaną liczbą jest i.
- iteracja tablicy bitów.
- jeśli bit jest ustawiony, wypisuje pozycję.
Lub innymi słowy (dla N
Zacznij od pustej 10-bitowej tablicy (zwykle jedna liczba całkowita)
0000000000
Odczytaj 4 i ustaw bit w tablicy..
0000100000
Odczytaj 6 i ustaw bit w tablicy
0000101000
Odczytaj 2 i ustaw bit w tablicy
0010101000
Iteracja tablicy i wypisanie każdej pozycji, w której bity są ustawione na jeden.
2, 4, 6
Sortowane.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-06-26 17:34:44
Zaczynając od set ():
Przesunięcie w prawo o 5 jest takie samo jak podzielenie przez 32. Robi to, aby znaleźć int bit jest w.
Maska to 0x1f lub 31. ANDing z adresem daje indeks bitowy W int. To samo, co reszta dzieląca adres przez 32.
Przesunięcie 1 w lewo o indeks bitów ("1
ORing ustawia bit.
Linia "int sh = i> > SHIFT;" jest zmarnowaną linią, ponieważ nie użyłem SH ponownie pod nim, a zamiast tego powtórzyłem "I > > SHIFT"
Clr() jest w zasadzie tym samym co set, z tym, że zamiast Oringu z 1
Bitsort usunie również duplikaty z listy, ponieważ będzie liczyć tylko do 1 na liczbę całkowitą. Sortowanie, które używa liczb całkowitych zamiast bitów do zliczania więcej niż 1 z każdego, nazywa się sortowaniem radix.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-06-26 17:41:01
Magia bitów jest używana jako specjalny schemat adresowania, który działa dobrze z rozmiarami wierszy, które są potęgami dwóch.
Jeśli spróbujesz to zrozumieć (Uwaga: używam raczej bitów na wiersz niż bitów na słowo, ponieważ mówimy tu o macierzy bitowej): {]}
// 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)
Twierdzenie linear_address = y*BITSPERWORD + x oznacza również, że x = linear_address % BITSPERWORD i y = linear_address / BITSPERWORD.
Gdy optymalizujesz to w pamięci używając 1 słowa 32 bitów na wiersz, otrzymujesz fakt, że bit w kolumnie x może być ustawiony za pomocą
int bitrow = 0;
bitrow |= 1 << (x);
Teraz, gdy my iterując nad bitami, mamy adres liniowy, ale musimy znaleźć odpowiednie słowo.
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;
Więc aby ustawić i ' ten bit, możesz to zrobić:
bits[ i%BITSPERROW ] |= 1 << (linear_address / BITSPERROW );
Dodatkowym argumentem jest to, że operator modulo może być zastąpiony przez operator logiczny oraz, a operator / może być również zastąpiony przez przesunięcie, jeśli drugi operand jest potęgą dwóch.
a % BITSPERROW == a & ( BITSPERROW - 1 ) == a & MASK
a / BITSPERROW == a >> ( log2(BITSPERROW) ) == a & SHIFT
a[ i >> SHIFT ] |= ( 1 << (i&MASK) );
Ale nie widzę algorytmu pracującego np. dla 40 bitów na słowo.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-06-26 18:35:46
Cytując fragmenty oryginalnego artykułu Bentleysa w DDJ, to właśnie robi kod na wysokim poziomie:
/* 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
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2014-07-08 19:37:15
Kilka wątpliwości : 1. Dlaczego potrzebny jest 32 bit ? 2. Czy możemy to zrobić w Javie tworząc Hashmapę z kluczami od 0000000 do 9999999 i wartości 0 LUB 1 na podstawie obecności / braku bitu ? Jakie są konsekwencje na taki program ?