Ajuda-me a compreender este “pérolas programação” bitsort programa

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

  •  20-08-2019
  •  | 
  •  

Pergunta

Jon Bentley na coluna 1 das suas pérolas programação livro introduz uma técnica para classificar uma seqüência de zero não-inteiros positivos usando vetores bits.

Tomei a bitsort.c programa de href="http://www.cs.bell-labs.com/cm/cs/pearls/code.html" aqui e colou-a abaixo: 

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

Eu entendo o que as funções CLR, conjunto e de teste estão fazendo e explicá-los a seguir: (por favor me corrijam se eu estiver errado aqui)

.
  • clr limpa o bit om
  • set define o bit om
  • teste retorna o valor na om pouco

Agora, eu não entendo como as funções fazem o que fazem. Eu sou incapaz de descobrir todas as manipulações do bit acontecendo nesses três funções.

Por favor, ajuda.

Foi útil?

Solução

Os 3 primeiros constantes são inter-relacionados. BITSPERWORD é 32. Isso você deseja definir com base no seu compilador + arquitetura. DESLOCAMENTO é 5, porque 2 ^ 5 = 32. Por último, a máscara é 0x1F que é 11111 em binário (ou seja: o fundo 5 bits são todos conjunto). Equivalentemente, MASK = BITSPERWORD -. 1

O bitset é conceitualmente apenas uma matriz de bits. Esta aplicação efectivamente utiliza uma matriz de inteiros, e assume 32 bits por int. Assim, sempre que queremos definir, limpar ou teste (ler) um pouco precisamos descobrir duas coisas:

  • que int (da matriz) são em
  • que de bits que o int estamos falando

Porque estamos assumindo 32 bits por int, podemos simplesmente dividir por 32 (e truncado) para obter o índice da matriz que queremos. Dividindo por 32 (BITSPERWORD) é o mesmo que o deslocamento para a direita por 5 (SHIFT). Então é isso que o a [i >> SHIFT] bit é sobre. Você também pode escrever isso como um [i / BITSPERWORD] (e, na verdade, você provavelmente obter o mesmo ou muito semelhante código assumindo que o seu compilador tem um otimizador razoável).

Agora que sabemos qual elemento de uma queremos, precisamos descobrir qual bit. Realmente, queremos que o restante. Poderíamos fazer isso com BITSPERWORD i%, mas verifica-se que i & MASK é equivalente. Isso ocorre porque BITSPERWORD é uma potência de 2 (2 ^ 5 neste caso) e MASK é o fundo 5 bits tudo definido.

Outras dicas

Basicamente é um balde tipo otimizado:

  • reservar uma gama de comprimento de n bits BITS.
  • limpar a matriz de bits (primeiro no principal).
  • ler os itens um por um (todos eles devem ser distintas).
    • definir o bit i'ésima na matriz pouco se o número de leitura é i.
  • iterar a matriz de bits.
    • Se o bit é definido, em seguida, imprimir a posição.

ou em outras palavras para (n <10, e para classificar três números 4, 6, 2) 0

começar com uma matriz de 10 bits vazio (também conhecido como um número inteiro geralmente) 

0000000000

4 ler e definir o bit na matriz .. 

0000100000

Leia 6 e definir o bit na matriz 

0000101000

leia 2 e definir o bit na matriz 

0010101000

iterate a matriz e imprimir todas as posições em que os bits são definidos a um.

2, 4, 6

classificadas.

A partir do set ():
Um deslocamento para a direita de 5 é o mesmo que dividir por 32. Ele faz isso para descobrir qual int o bit está em.
MÁSCARA é 0x1f ou 31. AND com o endereço dá o índice de bit dentro do int. É o mesmo que o resto da divisão de endereço por 32.
Deslocando uma esquerda pelo índice de bit ( "1 << (i & MÁSCARA)") resulta em um número inteiro que tem apenas um pouco no dado conjunto posição.
conjuntos ORING a pouco.
O "sh int = i >> Shift;" linha é uma linha desperdiçado, porque não usar sh novamente abaixo dela, e simplesmente repetiu "i >> Shift"

clr () é basicamente o mesmo que definido, exceto em vez de ORing com 1 << (i & MASK) para definir o bit, que ANDS com o inverso para limpar o bit. test () ANDs com 1 << (i & MASK) para testar a pouco.

O bitsort também irá remover duplicatas da lista, porque ela só vai contar até 1 por inteiro. Uma espécie que usa inteiros em vez de bits para contar mais do que 1 de cada um é chamado de uma espécie radix.

A magia bit é usado como um esquema de endereçamento especial que funciona bem com tamanhos de linha que são potências de dois.

Se você tentar entender isso (nota: Eu prefiro usar bits por linha de bits por palavra, uma vez que estamos falando de um pouco de matriz aqui): 

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

O linear_address = y*BITSPERWORD + x declaração também significa que x = linear_address % BITSPERWORD e y = linear_address / BITSPERWORD.

Quando você otimizar isto em memória usando uma palavra de 32 bits por linha, você tem o fato de que um pouco na coluna x pode ser definido usando 

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

Agora, quando iterar sobre os bits, nós Have o endereço linear, mas necessidade de encontrar a palavra correspondente. 

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;

Assim, para definir o bit i'ésima, você pode fazer isso: 

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

Uma pegadinha extra é, que o operador módulo pode ser substituído por um E lógico, ea / operador pode ser substituída por uma mudança, também, se o segundo operando é uma potência de dois. 

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

Esta última análise, resume-se ao muito densa, ainda difícil de compreender-for-the-bitfucker agnóstico notação 

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

Mas eu não vejo o algoritmo trabalhando para, por exemplo, 40 bits por palavra.

Citando os trechos do artigo original Bentleys' em DDJ, isso é o que o código faz a um nível elevado: 

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

Algumas dúvidas: 1. Por que é uma necessidade para um de 32 bits? 2. Podemos fazer isso em Java, criando um HashMap com chaves 0.000.000-9.999.999 e os valores 0 ou 1, com base na presença / ausência do bit? Quais são as implicações para esse programa um?

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top