Mapa de bits, alguem se habilita?

Programação Java
#1

Bom pessoal, é o seguinte:

Tenho que arrumar uma forma rápida de armazenar e comparar “pedidos”.
Por exemplo, um “cliente” pode fazer de 1 a 15 pedidos, e para não usar boolean em cada item de pedido e sair testando depois, estava pensando utilizar mapa de bits.

A solução em que estou trabalhando é bem complicada para explicar, então vou usar um exemplo:

Imaginem o cenário hipotético:

Tenho 1 entregador, que faz entregas somente para os mesmos 5 clientes.
Cada cliente pode escolher de 1 a 15 itens.
Então o entregador tem que verificar o que cada cliente pediu e entregar.

Falando em código, eu não queria colocar por exemplo em cada objeto “Cliente” 15 flags, ou criar 15 arrays que representariam os 15 itens (ou qq coleção), pois iria consumir um certo processamento que não estou disposto a considerar no momento.

Li alguma coisa por alto sorbe mapa de bits, mas não achei nenhuma implentação ou qq coisa para me basear.

Valeu galera.

Ps.: O exemplo acima é hipotético. O que chamo de “cliente” é uma espécie de conexão com a minha aplicação que faz requisições em protocolo específicos.

#2

O mapa de bits não se aplica a esse caso. O mapa de bits é útil para representar vários flags. Vamos supor que para cada pedido, a pessoa pudesse:

  1. Embalar para presente
  2. Usar caixa reciclada;
  3. Solicitar entrega noturna;
  4. Solicitar entrega apenas nos finais de semana.

Note que o usuário pode escolher entre qualquer combinação desses itens.

Você poderia representar isso por 4 booleans. Entretanto, cada boolean ocupa um byte inteiro, pois esta é a menor unidade possível para o computador. Uma forma extremamente compacta seria agrupar esses 4 booleans num único byte, através de um mapa de bits.

Como cada campo binário tem 8 bits, definiremos então que o primeiro bit (da esquerda para direita) representa o item 1 daquela lista, o segundo bit o item 2, e assim por diante.

Então, um valor como 1010, representaria que nosso usuário não quer embalar nada para presente, quer usar caixa reciclada, solicita entrega noturna e não faz questão que entrega chegue nos finais de semana.

Vamos representar cada bit desses separadamente:
0001 - É o primeiro bit, o valor dessa constante é 1;
0010 - É o segundo bit, o valor dessa constante é 2;
0100 - É o segundo bit, o valor dessa constante é 4;
1000 - É o segundo bit, o valor dessa constante é 8;

Definimos isso na programação assim:

private static final int EMBALAR_PRESENTE = 1; private static final int CAIXA_RECICLADA = 2; private static final int ENTREGA_NOTURNA = 4; private static final int ENTREGA_FINAIS_SEMANA = 8;

Com esses valores é bem fácil montar um byte com combinações de valores. Basta associarmos valores com o operador OU bitwise:

int opcoes = EMBALAR_PRESENTE | ENTREGA_FINAIS_SEMANA; //Resulta no valor 1001

Também é fácil testar se nosso usuário definiu ou não alguma dessas opções. Para isso, basta usar o operador E bitwise, e verificar se o resultado é igual ao valor que estivermos testando:

if (opcoes & ENTREGA_FINAIS_SEMANA == ENTREGA_FINAIS_SEMANA) agendarParaSabado();

Você pode até mesmo testar conjuntos de opções de uma só vez. O teste fica assim:

int entregaEspecial = ENTREGA_NOTURNA | ENTREGA_FINAIS_SEMANA; if (opcoes & entregaEspecial == entregaEspecial) { fazerEntregaEspecial(); }

Há pouco ganho de processamento e, a menos que você tenha centenas de milhares de objetos (ou muito pouca memória), há pouco ganho de memória também. Essa opção é interessante para protocolos de rede ou sinalização de hardware, mas pouco interessante para qualquer sistema comercial normal hoje em dia.

#3

Pois é ViniGodoy,

Eu estava editando o post na hora que você escreveu a resposta.

A minha solução está ligada com solução de redes, envio e resposta de uma solicitação específica em um protocolo específico.
Cada conexão pode me pedir uma combinação de “itens”, e tenho que anotar os “pedidos” que cada conexão me fez, e a partir dai ficar respondendo incessantemente a cada um somente o que me foi pedido. Tenho um “depósito” que me chegam coisas novas o tempo todo.

#4

Nesse caso talvez valha a pena compactar vários bits em um byte. É só entender a teoria acima e fazer. :slight_smile:

#5

Beleza, vou quebrar a cabeça aqui.

Obrigadão meu camarada.

#6

Beleza, vou quebrar a cabeça aqui.

Obrigadão meu camarada.[/quote]

Só para adicionar alguma coisa no tópico…

Para mandar e receber pela rede, até concordo em enviar uns bytes compactando a informação (para até 15 itens, no mínimo 2 bytes aliás), mas para uma representação na classe e manipulação, eu talvez optasse por um vetor de booleans, ou um boolean representando cada item, ou até um mapa mesmo, com o item como chave e o boolean como valor.

#7