2

Supomos que, em dada implementação, as posições de um vetor podem conter valores de -2^16 a 2^16. É necessário "marcar" posições não utilizadas (por exemplo, colocar um * ). Porém, dado o range de valores, marcar as posições com -1, 0, 1 por exemplo, é inviável, bem como com símbolos (devido à equivalência ASCII onde, por exemplo, * equivale a 42 decimal, que está no range). Qual seria uma maneira eficiente de marcar as posições não utilizadas?

(A solução que pensei foi usar um valor fora do range, mas seria um valor relativamente alto, e não sei se é uma boa ideia)

Edit: A linguagem utilizada é C e o tipo de dado é int

3
  • Se seu vetor usa um dado de tamanho fixo (ex.: int de 4 bytes, double de 8 bytes, etc) então não faz diferença se o valor armazenado nele é alto ou baixo - o espaço ocupado será o mesmo, o tempo para comparar esse valor com a marcação é o mesmo, etc. Na minha opinião é a solução mais simples, somente se o range ocupar o tipo do dado inteiro e não sobrar valores inutilizados é que eu optaria por uma solução mais complexa (um array de bits, por exemplo). P.S. Poderia por favor editar a pergunta indicando a linguagem e tipo de dado utilizado?
    – mgibsonbr
    Commented 3/11/2015 às 4:26
  • Editado! Muito obrigado pelo esclarecimento.
    – Moni
    Commented 3/11/2015 às 11:39
  • Seria {-2^16 a 2^16} ou seria {-2^16 a 2^16-1}? Ou talvez {-2^15 a 2^15-1}? O motivo é que para caber em 16 bits usando notação de complemento de 2 (a notação binária utilizada nos computadores modernos), então o intervalo seria {-2^15 a 2^15-1}. Commented 3/11/2015 às 11:45

1 Resposta 1

2

Bem, há algumas soluções que vejo para isso: 1) Usar um valor fora do intervalo; 2) usar um vetor auxiliar para isso ou; 3) usar uma estrutura de dados mais complexa.

Também convém conhecer o padrão de projeto Null Object.

Abordagem 1

Se você está usando um array de inteiros (que permite valores de -2^31 até 2^31 - 1), mas os valores que te interessam são apenas uma faixa desses valores, então você pode usar um dos valores fora da faixa para representar um valor não preenchido. Normalmente os valores 0 ou -1 são usados para esta finalidade (ou caso o dado não seja numérico, pode ser usado NULL, uma string vazia, o endereço de um struct com os dados em branco, o endereço de uma função que não faz nada, ou algum outro tipo de dado que signifique vazio, não preenchido ou indefinido). No caso de inteiros, quando 0 ou -1 são válidos, algum outro número fora do intervalo pode ser utilizado.

Esta é a abordagem que mais economiza memória, e também é a abordagem mais comum.

Abordagem 2

Por outro lado, se você não pode ou não quer usar um valor fora da faixa, então talvez um vetor auxiliar te sirva. A forma mais simples é criar um vetor de int, short ou char do mesmo tamanho que o seu vetor original e preencher ele com 0 aonde o valor do seu array principal deve ser desconsiderado e considerado como não-preenchido e 1 em caso contrário.

Para economizar memória, usando-se uma implementação mais sofisticada, é possível trabalhar diretamente com bits, de forma a ter um vetor de char aonde cada posição do vetor auxiliar representa 8 posições do vetor original.

Abordagem 3

Por fim, a última abordagem consiste em fazer algo mais ou menos assim:

typedef struct {
    char usado;
    int valor;
} Elemento;

E então, ao invés de usar um array como int[], você usará Elemento[]. Esta abordagem consome um byte a mais para cada elemento que você quer usar (o que significa que 7 bits de memória são desperdiçados por elemento).

É possível evitar-se este desperdício de memória ao utilizar-se em cada Elemento, oito valores juntos com apenas um caractere para rastrear o que foi marcado, mas neste caso a abordagem 2 acaba sendo mais simples e eficiente na prática.

1
  • 1
    Acho que a abordagem 1 realmente é a mais indicada para o meu caso. Não tinha considerado a 3 também, achei interessante. Porém, a primeira ainda me parece a mais prática e menos custosa. Obrigada!
    – Moni
    Commented 3/11/2015 às 15:28

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .