Aidez-moi à comprendre ce « perles de programmation » programme bitsort
https://stackoverflow.com/questions/1050253
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Bentley Jon à la colonne 1 de ses perles de programmation de livre présente une technique pour le tri d'une suite d'entiers positifs non nuls en utilisant des vecteurs de bits.
J'ai pris le bitsort.c programme de ici et collé ci-dessous:
/* 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;
}
Je comprends ce que les fonctions clr, set et test sont en train de faire et de les expliquer ci-dessous: (s'il vous plaît me corriger si je me trompe)
.- clr efface le bit ième
- set définit le bit ième
- test renvoie la valeur au ième bit
Maintenant, je ne comprends pas comment les fonctions font ce qu'ils font. Je suis incapable de comprendre toutes les manipulations de bits qui se passe dans ces trois fonctions.
S'il vous plaît aider.
La solution
Les 3 premières constantes sont liés entre eux. BITSPERWORD est 32. Ce que vous voudriez mettre en fonction de votre compilateur + architecture. SHIFT est 5, parce que 2 ^ 5 = 32. Enfin, MASK est 0x1F qui est 11111 en binaire (à savoir: les 5 bits inférieurs sont tous ensemble). De manière équivalente, MASQUE = BITSPERWORD - 1.
Le bitset est conceptuellement simplement un tableau de bits. Cette mise en œuvre utilise en fait un tableau de ints, et prend 32 bits par int. Donc, chaque fois que nous voulons mettre, ni aucun critère (lire) un peu nous avons besoin de comprendre deux choses:
- qui int (de la matrice) est-il
- qui des morceaux de cette int-nous parlons
Parce que nous supposons 32 bits par int, on peut diviser par 32 simplement (et tronquer) pour obtenir l'index du tableau que nous voulons. La division par 32 (BITSPERWORD) est le même que celui se déplaçant vers la droite par 5 (SHIFT). Donc, c'est ce que l'un peu [i >> SHIFT] est sur le point. Vous pouvez aussi écrire ceci comme [i / BITSPERWORD] (et en fait, vous auriez probablement obtenir le code identique ou très similaire en supposant que votre compilateur a un optimiseur raisonnable).
Maintenant que nous savons quel élément d'un que nous voulons, nous devons comprendre que peu. Vraiment, nous voulons que le reste. Nous pourrions le faire avec i% BITSPERWORD, mais il se trouve que je & MASK est équivalent. En effet, BITSPERWORD est une puissance de deux (2 ^ 5 dans ce cas) et le masque est le fond 5 des bits tous ensemble.
Autres conseils
est essentiellement un seau tri optimisé:
- réserver un tableau de bits de longueur n morceaux.
- effacer la matrice de bits (premier dans principal).
- lire les éléments un par un (ils doivent tous être distincts).
- définir le bit i'th dans le tableau de bits si le numéro de lecture i est.
- itérer le tableau de bits.
- si le bit est alors imprimer la position.
Ou en d'autres termes (N <10 et 3 pour trier les numéros 4, 6, 2) 0
commencer avec un réseau de 10 bits vides (aka un nombre entier généralement)
0000000000
lu 4 et régler le bit dans le réseau ..
0000100000
lire 6 et régler le bit dans le tableau
0000101000
lu 2 et régler le bit dans le tableau
0010101000
itérer la matrice et imprimer chaque position dans laquelle les bits sont mis à un.
2, 4, 6
trié.
A partir de set ():
Un décalage vers la droite 5 est le même que la division par 32. Il le fait pour trouver int le bit est.
MASQUE est 0x1f ou 31. ANDing l'adresse donne l'indice de bit dans l'int. Il est le même que le reste de la division par l'adresse 32.
Shifting 1 à gauche par l'indice de bit ( "1 << (i & MASK)") se traduit par un nombre entier qui a juste 1 bit dans le jeu de position donnée.
ORing définit le bit.
La ligne "int i = sh >> SHIFT;" est une ligne perdue, parce qu'ils n'utilisent sh à nouveau en dessous et au lieu simplement répéter « i >> SHIFT »
est essentiellement identique à celle réglée, sauf qu'au lieu de ORing avec 1 << (i & MASK) pour définir le bit, il ANDs à l'inverse pour effacer le bit. test () avec 1 << ANDs (i & MASK) pour tester le bit.
Le bitsort va également supprimer les doublons dans la liste, car il ne comptera jusqu'à 1 par entier. Une sorte qui utilise des nombres entiers au lieu de bits pour compter plus de 1 de chacun est appelé un tri de base.
La magie de bit est utilisé comme un système d'adressage spécial qui fonctionne bien avec la taille des lignes qui sont des puissances de deux.
Si vous essayez de comprendre cette (note: J'utilise plutôt bits par rangée de bits par mot, puisque nous parlons d'une matrice binaire ici):
// 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)
La déclaration signifie également que linear_address = y*BITSPERWORD + x et x = linear_address % BITSPERWORD y = linear_address / BITSPERWORD.
Lorsque vous optimiser ceci en mémoire à l'aide d'une parole de 32 bits par rangée, on obtient le fait qu'un bit à x de la colonne peut être réglée à l'aide
int bitrow = 0;
bitrow |= 1 << (x);
Maintenant, lorsque nous parcourons les bits, nous Vous l'adresse linéaire, mais il faut trouver le mot correspondant.
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;
Donc, pour définir le bit i'th, vous pouvez faire ceci:
bits[ i%BITSPERROW ] |= 1 << (linear_address / BITSPERROW );
Un gotcha supplémentaire est que l'opérateur modulo peut être remplacé par un ET logique, et le / opérateur peut être remplacé par un changement, aussi, si le second opérande est une puissance de deux.
a % BITSPERROW == a & ( BITSPERROW - 1 ) == a & MASK
a / BITSPERROW == a >> ( log2(BITSPERROW) ) == a & SHIFT
Cela revient finalement à la notation très dense, mais difficile à comprendre-pour-le-bitfucker-agnostique
a[ i >> SHIFT ] |= ( 1 << (i&MASK) );
Mais je ne vois pas l'algorithme de travail pour exemple 40 bits par mot.
Citant les extraits de l'article original de Bentleys dans DDJ, voici ce que fait le code à un niveau élevé:
/* 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
Quelques doutes: 1. Pourquoi est-il besoin d'un 32 bits? 2. Peut-on faire en Java en créant une table de hachage avec les clés 0000000-9999999 et les valeurs 0 ou 1 en fonction de la présence / l'absence du bit? Quelles sont les implications pour un tel programme?
