Que me ayude a entender esta "Programación de perlas" bitsort programa

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

  •  20-08-2019
  •  | 
  •  

Pregunta

Jon Bentley en la Columna 1 de su libro de programación de perlas presenta una técnica para la ordenación de una secuencia de cero enteros positivos mediante vectores de bits.

Me he tomado el programa de bitsort.c de aquí y pegar a continuación:

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

Entiendo lo que las funciones clr, establecer y comprobar que están haciendo y que les explique a continuación:( por favor corríjanme si estoy equivocado ).

  • clr borra la i-ésima poco
  • conjunto de conjuntos de la i-ésima poco
  • prueba devuelve el valor en la i-ésima poco

Ahora, no entiendo cómo las funciones hacen lo que hacen.Soy incapaz de averiguar todos los de manipulación de bits sucediendo en esas tres funciones.

Por favor, ayudar.

¿Fue útil?

Solución

Los 3 primeros constantes son inter-relacionado. BITSPERWORD es 32. Este Lo que quiere establecer sobre la base de su compilador + arquitectura. SHIFT es 5, porque 2 ^ 5 = 32. Por último, máscara es 0x1F que es 11 111 en binario (es decir: el fondo 5 bits son todos set). De manera equivalente, MASK = BITSPERWORD -. 1

El bitset es conceptualmente tan sólo un conjunto de bits. Esta aplicación utiliza realmente una matriz de enteros, y supone 32 bits por int. Así que cada vez que queremos establecer, borrar o de prueba (leer) un poco tenemos que averiguar dos cosas:

  • que int (de la matriz) es en
  • ¿cuál de los bits de ese int estamos hablando

Debido a que estamos asumiendo 32 bits por int, sólo podemos dividir por 32 (y truncar) para obtener el índice de matriz que queremos. Dividiendo por 32 (BITSPERWORD) es el mismo que el cambio a la derecha por 5 (SHIFT). Así que eso es lo que el a [i >> SHIFT] poco se trata. También podría escribir esto como una [i / BITSPERWORD] (y de hecho, lo que probablemente obtiene el mismo o muy similar código suponiendo que su compilador tiene un optimizador razonable).

Ahora que sabemos qué elemento de la que queremos, tenemos que averiguar qué bit. En definitiva, queremos que el resto. Podríamos hacer esto con i% BITSPERWORD, pero resulta que I & máscara es equivalente. Esto se debe a BITSPERWORD es una potencia de 2 (2 ^ 5 en este caso) y la máscara es la parte inferior 5 bits todo listo.

Otros consejos

Básicamente es un cubo especie optimizado:

  • reservar una matriz de bits de longitud n    Bits.
  • borrar la matriz de bits (primero en el principal).
  • leer los artículos uno por uno (lo único que deben ser distintos).
    • establece el bit de orden i en la matriz de bits si el número de lectura es i.
  • iterar la matriz de bits.
    • Si el bit se establece a continuación, imprimir la posición.

O en otras palabras (por N <10 y para ordenar 3 números 4, 6, 2) 0

comenzar con una matriz de 10 bits vacío (también conocido como un número entero por lo general) 

0000000000

leer 4 y establecer el bit en la matriz .. 

0000100000

leer 6 y establecer el bit en la matriz 

0000101000

leer 2 y establecer el bit en la matriz 

0010101000

iterar la matriz e imprimir cada posición en la que los bits se ponen a uno.

2, 4, 6

ordenados.

A partir de set ():
Un desplazamiento a la derecha de 5 es el mismo que dividir por 32. Lo hace para encontrar qué int el bit está en.
MÁSCARA es 0x1f o 31. AND con la dirección da el índice de bit dentro del int. Es el mismo que el resto de la división por la dirección 32.
Desplazamiento de 1 dada por el índice de bit ( "1 << (i y máscara)") da como resultado un número entero que tiene sólo 1 bit en el conjunto de posición dada.
ORing establece el bit.
La línea "int i = sh >> SHIFT;" es una línea desperdiciado, porque no usan sh de nuevo por debajo de él, y en su lugar sólo repiten "i >> SHIFT"

CLR () es básicamente el mismo que el conjunto, pero en lugar de operación OR con 1 << (I & MÁSCARA) para establecer el bit, se AND con la inversa para borrar el bit. test () AND con 1 << (i y máscara) para probar el bit.

El bitsort también eliminará los duplicados de la lista, ya que sólo se hará válida hasta el 1 por entero. Un tipo que utiliza enteros en lugar de bits para contar más de 1 de cada una raíz se llama tipo.

El bit de magia se utiliza como un tipo especial de esquema de direccionamiento que funciona bien con la fila de los tamaños que son potencias de dos.

Si intenta entender esto (nota:Yo prefiero usar bits por cada fila de bits por palabra, ya que estamos hablando de un poco de la matriz de aquí):

// 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 declaración de linear_address = y*BITSPERWORD + x también significa que x = linear_address % BITSPERWORD y y = linear_address / BITSPERWORD.

Al optimizar esta en la memoria mediante 1 palabra de 32 bits por fila, usted consigue el hecho de que un bit en la columna x se puede establecer mediante

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

Ahora, cuando nos iterar a través de los bits, se han la dirección lineal, pero necesita encontrar la palabra correspondiente.

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;

De modo que para establecer la i-esima poco, puedes hacer esto:

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

Un extra de gotcha es, que el operador de módulo puede ser sustituida por una lógica, Y, y el operador / puede ser reemplazado por un cambio, también, si el segundo operando es una potencia de dos.

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

Esta última instancia se reduce a la muy densa, sin embargo, difícil de entender-para-el-bitfucker independiente de la notación

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

Pero no veo que el algoritmo de trabajo para, por ejemplo,40 bits por palabra.

Citando los extractos del artículo original Bentley en DDJ, esto es lo que hace el código en un nivel alto: 

/* 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 pocas dudas: 1. ¿Por qué es necesario un poco de 32? 2. ¿Podemos hacer esto en Java mediante la creación de un HashMap con claves 0000000-9999999    y los valores 0 o 1 basado en la presencia / ausencia del bit? ¿Cuáles son las implicaciones    para un programa de este tipo?

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top