Aiutami a capire questo programma bitsort “perle di programmazione”

StackOverflow https://stackoverflow.com/questions/1050253

  •  20-08-2019
  •  | 
  •  

Domanda

Jon Bentley nella colonna 1 della sue perle di programmazione libro introduce una tecnica per l'ordinamento una sequenza di diverso da zero interi positivi che utilizzano vettori di bit.

Mi sono preso la bitsort.c programma dal href="http://www.cs.bell-labs.com/cm/cs/pearls/code.html" qui e incollato qui sotto: 

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

ho capito quali sono le funzioni CLR, impostare e testare stanno facendo e li spiego qui di seguito: (per favore correggetemi se sbaglio qui)

.
  • CLR cancella il bit-esimo
  • set imposta il bit-esimo
  • test restituisce il valore al bit-esimo

Ora, io non capisco come le funzioni fanno quello che fanno. Non sono in grado di capire tutte le manipolazioni po 'accadendo in queste tre funzioni.

Si prega di aiutare.

È stato utile?

Soluzione

I primi 3 costanti sono correlati tra loro. BITSPERWORD è 32. Questo che ci si vuole impostare in base al compilatore + architettura. SHIFT è 5, perché 2 ^ 5 = 32. Infine, MASK è 0x1F che è 11111 in binario (cioè: i 5 bit inferiori sono tutti impostati). Equivalentemente, MASK = BITSPERWORD -. 1

Il bitset è concettualmente solo un array di bit. Questa implementazione effettivamente utilizza un array di int, ed assume 32 bit per int. Così ogni volta che si vuole impostare, trasparente o di test (lettura) un po 'abbiamo bisogno di capire due cose:

  • che int (dell'array) è altrove
  • che di bit che di int stiamo parlando

Perché stiamo assumendo 32 bit per int, possiamo semplicemente dividere per 32 (e troncare) per ottenere l'indice di array che vogliamo. Dividendo per 32 (BITSPERWORD) è lo stesso spostamento verso destra di 5 (SHIFT). Ecco, questo è ciò che l'a [i >> SHIFT] bit è circa. Si potrebbe anche scrivere questo come a [i / BITSPERWORD] (e in effetti, si sarebbe probabilmente ottenere lo stesso o molto simile codice supponendo che il compilatore ha un ottimizzatore ragionevole).

Ora che sappiamo che un elemento di che vogliamo, abbiamo bisogno di capire quali bit. In realtà, noi vogliamo il resto. Potremmo farlo con i% BITSPERWORD, ma si scopre che i & maschera è equivalente. Questo perché BITSPERWORD è una potenza di 2 (2 ^ 5 in questo caso) e la maschera è i 5 bit inferiori a posto.

Altri suggerimenti

In sostanza è un secchio sorta ottimizzato:

  • prenotare una matrice di bit di lunghezza n    bit.
  • cancellare la matrice di bit (prima dal principale).
  • leggi gli articoli uno per uno (devono essere tutti distinti).
    • impostare il bit-esima dell'array bit se il numero lettura è i.
  • iterare la matrice di bit.
    • se il bit è impostato quindi stampare la posizione.

In altre parole (per N <10 e per ordinare 3 numeri 4, 6, 2) 0

iniziare con una matrice 10 bit vuoto (alias un intero solito) 

0000000000

leggi 4 e impostare il bit nella matrice .. 

0000100000

leggi 6 e impostare il bit della matrice 

0000101000

leggere 2 e impostare il bit della matrice 

0010101000

scorrere l'array e stampare ogni posizione in cui vengono impostati a uno dei bit.

2, 4, 6

ordinato.

A partire con set ():
Un diritto spostamento di 5 è lo stesso dividendo per 32. Non che per trovare quale int il bit è in.
MASK è 0x1f o 31. ANDing con l'indirizzo dà l'indice bit all'interno del int. E 'lo stesso come il resto della divisione del discorso di 32.
Shifting 1 rimasti dall'indice bit ( "1 << (i & MASK)") determina un numero intero che ha solo 1 bit nella data posizione impostata.
ORing imposta il bit.
La linea "int sh = i >> SHIFT;" è una linea sprecato, perché non usano sh di nuovo sotto di esso, e invece solo ripetuto "i >> SHIFT"

clr () è sostanzialmente la stessa come insieme, tranne che invece di ORing con 1 << (i & MASK) per impostare il bit, AND con l'inverso per cancellare il bit. test () AND con 1 << (I & MASK) per testare il bit.

Il bitsort anche rimuovere i duplicati dalla lista, perché sarà contare solo fino a 1 per intero. Un tipo che utilizza numeri interi invece di bit per contare più di 1 di ciascuno è chiamato un ordinamento digitale.

La magia bit viene utilizzato come uno speciale schema di indirizzamento che funziona bene con i formati di fila che sono potenze di due.

Se si prova a capire questo (nota: Io invece uso bit per riga di bit per parola, dal momento che stiamo parlando di un po 'a matrice qui): 

// 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 dichiarazione linear_address = y*BITSPERWORD + x significa anche che x = linear_address % BITSPERWORD e y = linear_address / BITSPERWORD.

Quando si ottimizza questo in memoria utilizzando 1 parola di 32 bit per riga, si ottiene il fatto che un po 'alla colonna x può essere impostato utilizzando 

int bitrow = 0;
bitrow |= 1 << (x);

Ora, quando si scorrere i bit, abbiamo sono l'indirizzo lineare, ma bisogno di trovare la parola corrispondente. 

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;

Quindi, per impostare il bit-esimo, si può fare questo: 

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

Un Gotcha supplementare è, che l'operatore modulo può essere sostituito da un AND logico, e il / operatore può essere sostituito da uno spostamento, anche se il secondo operando è una potenza di due. 

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

Questo in ultima analisi, riduce al molto denso, ma difficile da capire-per-il-bitfucker-agnostic notazione 

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

Ma non vedo l'algoritmo che lavora per esempio 40 bit per parola.

Citando i brani tratti da Articolo originale di Bentley in DDJ, questo è ciò che fa il codice a un livello elevato: 

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

A pochi dubbi: 1. Perché è la necessità di un po '32? 2. Possiamo fare questo in Java con la creazione di un HashMap con i tasti 0.000.000-9.999.999    e valori 0 o 1 in base alla presenza / assenza del bit? Quali sono le implicazioni    per un tale programma?

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top