Recentemente, em um dos projetos surgiu um problema: existe um conjunto de conjuntos (Conjunto) que deve ser armazenado de forma eficiente na RAM. Porque existem muitos conjuntos, mas pouca memória. E temos que fazer algo a respeito.
Já que a linguagem em que tudo está escrito é C #, ou seja, as nuances. Ou seja, o HashSet padrão <int> gasta 16 bytes para armazenar um número, o fator phill também afeta. Existem implementações mais eficientes (eu escreverei sobre elas algum dia), mas por outro lado, você pode estupidamente armazenar em matrizes, 4 bytes por número (você precisa armazenar ints), o que é bastante eficiente. Mas pode ser reduzido ainda mais?
Devo dizer desde já que não tenho uma resposta sobre a melhor forma de o fazer, talvez não exista, porque são muitos os factores associados à distribuição de dados específicos. Mas há ideias que compartilharei: quais opções existem para economizar memória. Também recomendo que você pense por si mesmo antes de ler o post, ainda é um bom aquecimento para a mente. Para ser específico, formularei o problema da seguinte maneira:
Há um conjunto de ints únicos não negativos (32 bits). É necessário armazená-los de forma eficiente na RAM, desde as operações - criar um conjunto e obter todos os elementos. Não há necessidade de obter itens por índice, adicionar novos ou excluí-los.
O artigo conterá muitas letras e números e não uma única imagem (exceto para um gato embalado no KDPV).
, , .. , . . - , - , . - , - .
, — , .
, : , . 10
Portanto, temos dados básicos - uma matriz de ints, 4 bytes (32 bits) por número. Vamos nos basear neste indicador.
Para começar, expressarei uma ideia brilhante: para que um número ocupe menos de 32 bits na memória, você precisa armazená-lo usando menos bits. Boa ideia, hein? E as pessoas ganham fama e reconhecimento por isso. Então, pior eu sou.
Digressão lírica: há alguns anos, especialistas da Russian Railways descobriram que, se você fizer as rodas girarem e do mesmo tamanho, o trem vai mais rápido e mais silencioso.
Separando números por tamanho
Uma solução simples para começar: números de 0 a 255 podem ser armazenados usando 1 byte por número, até 65536 com dois, até 16777216 com três. Daí a primeira solução:
criamos 4 arrays, em um armazenamos números por 1 byte, no outro por 2, no terceiro por 3 e o que no quarto, proponho adivinhar por conta própria.
Aplauda, e já estamos salvando. Mas por que ficar onde você esteve? Vamos usar 32 matrizes! E armazene os números por 1, 2 ... bits. Tornou-se ainda mais econômico.
Por outro lado, o que é um array? Este é um ponteiro para um bloco de memória (8 bytes), comprimento, e para C # também há memória para o próprio objeto de array (20 bytes). No total, cada array custa 32 bytes (na verdade, em C #, um objeto leva pelo menos 24 bytes em incrementos de 8, dos quais 20 bytes são para o objeto e 4 são para o que resta ou é estúpido para o alinhamento). A seguir, cálculos para um sistema de 64 bits. Para 32 bits, os ponteiros são 2 vezes menos, o alinhamento também é 4, então quase tudo é 2 vezes mais econômico.
Para que serve esta passagem? Além disso, 32 arrays devoram 1 KB de memória apenas para eles. O que fazer sobre isso? E tudo é simples: vamos armazenar esses 32 arrays em um único array!
No primeiro elemento, armazenamos o comprimento de uma matriz de um bit, depois a própria matriz, depois o comprimento de dois bits, etc. Como resultado, há apenas 32 bytes de sobrecarga e armazenamento eficiente.
Um leitor curioso (sempre gostei dessa frase) pode notar um certo problema: para armazenar números de um bit, primeiro gastamos 2 bits para o comprimento (0, 1 ou 2) e depois 2 bits para os próprios números. Mas você só pode gastar 2 bits: o primeiro bit é se há um 0, o segundo é se há um 1.
Acabamos de criar um bitmap . Você não pode se preocupar muito e armazenar números de 0 a 255 com este método - há um número - 1, não - 0. E gastar 32 bytes nele (8 bits em um byte * 32 = 256). Naturalmente, a cada novo valor, a eficácia do cartão começa a diminuir. Essa. para armazenar todos os ints precisamos de 536870912 bytes ... É um pouco demais. Então, quando parar: em 256, em 16, em 65536 - depende dos dados. Que seja 256. Gosto desse número, é lindo.
Essa. armazenamos os primeiros 256 números com um bitmap, depois armazenamos o comprimento dos números de um determinado comprimento em bits e os próprios números.
Mas veja o que acontece: números de 0 a 511 requerem 9 bits para serem armazenados. Ao mesmo tempo, temos números de 0 a 255 - já os salvamos. Essa. no intervalo de 9 bits, não foi possível encontrar o número 12. Apenas 256 e mais. Então, por que armazená-los em 9 bits, se você pode armazenar um número de 0 a 255 e depois adicionar o que falta 256 em sua cabeça. Salvo mais um bit! Naturalmente, cada faixa seguinte também será 1 bit mais econômica. Nós somos ótimos!
O que mais você pode fazer? E você pode olhar os dados. Se eles forem muito densos (1,2,3,5,6), então você pode armazenar não os números em si, mas aqueles que não existem (4). Essa. em vez de armazenar 5 números condicionais, armazenaremos um. Uma regra simples: temos mais da metade - mantemos aqueles que não existem, caso contrário, vice-versa. Onde armazenar? E em comprimento! Veja: para armazenar números de 10 bits, precisamos de 11 bits (porque de 0 a 1024, inclusive). Mas, ao mesmo tempo, valores em 11 bits podem ser empurrados em 2048, e usamos apenas 1025. Portanto, vamos armazenar: comprimento positivo - armazenamos números. Negativo - armazenamos o que não é. Sugiro que o próprio leitor faça um cálculo detalhado como um exercício independente (porque não tenho certeza se tudo vai se encaixar, então vou fingir que é necessário).
Como resultado, obtivemos: uma matriz na qual os primeiros 16 bytes são uma máscara de bits para a presença de números de 0 a 255, então - o comprimento com uma indicação - armazenamos os números ou sua ausência, os próprios números, o comprimento do bit para o próximo, etc.
Depois de implementar isso, e mesmo sem erros, acho que você irá direto ao assunto, os programadores subsequentes que tentarem entender este código o seguirão. Então, vamos tentar mais algumas opções.
Nós pensamos em ordem
Veja. Temos uma matriz. O que ele tem, ao contrário de muitos? E ele tem: a ordem dos elementos. Esta é uma informação adicional e ainda não a usamos. O que você pode fazer em relação à isso?
E você pode armazenar não os próprios elementos, mas a diferença entre eles:
1,2,3,4,8 => 1,1,1,1,4
Ie. armazenamos o primeiro como está, o segundo - adicionamos o valor do primeiro ao segundo, etc. O que isso nos dá? E o fato de que, se classificarmos o array antecipadamente , nossos valores nele se tornarão menores em geral e poderão ser armazenados em menos bits.
Além disso, de acordo com a condição do problema, todos os elementos são diferentes, ou seja, ainda podemos subtrair um da diferença para salvar os bits:
1,2,3,4,8 => 1,1,1,1,4 => 1,0,0,0,3
Isso não é difícil, então por que não e não.
Mas agora o problema foi resolvido. Porque Agora, não podemos armazenar números independentemente, mas apenas na mesma ordem, então o método com uma matriz e comprimentos não é mais adequado. Você tem que pensar em outra coisa, porque todos os números devem ser armazenados em ordem.
Armazene o comprimento do número em bits antes do próprio número.
Não é uma opção ruim. O número varia de 1 a 32 bits, ou seja, para o comprimento, precisamos de 5 bits e, em seguida, o próprio número. Por conveniência, você pode eliminar casos extremos (bem, por que vamos economizar aí? Centavos!), Ou vice-versa, destaque-os separadamente - por exemplo, se o comprimento for 0, isso significa o número 0, se o comprimento for 1 - o número - 1, se o comprimento for 2, então os próximos 2 bit número 2,3,4,5 (já sabemos que podemos mudar para algo que não pode ser), etc.
Ou pode armazenar o comprimento de um número no próprio número?
Quantidade de comprimento variável
Não importa como sejamos os primeiros a fazer essa pergunta, há uma solução padrão. Usado para armazenar strings em UTF-8 e muitos outros lugares. O significado é simples.
Se o número for de 0 a 127 inclusive, nós o armazenamos em 1 byte (embora tenhamos usado apenas 7 bits). Se for mais, defina o 8º bit como 1 e use o próximo byte da mesma maneira (7 bits, faltando - caixa de seleção e próxima). Essa. números pequenos serão armazenados em um byte, um pouco mais - em dois e assim por diante até 5.
Você pode dizer - fuu ... nós apenas brincamos com os bits, e então os bytes foram, nada legal! Sim, não é legal, por outro lado trabalhar com bytes ainda é mais fácil do que com bits, economiza um pouco menos, mas a velocidade do trabalho é maior e o código é mais claro. Mas ... gastar um pouco por byte de alguma forma não é muito legal, talvez existam soluções melhores?
Usando valores como sinalizadores
Vamos pular todo o raciocínio e decidir imediatamente. Vamos armazená-lo da seguinte forma:
- números de 0 a 252 serão armazenados em um byte. Se mais, então:
- se o número for de 252 a 252 + 256 = 508 definimos o valor 252, e no próximo byte o número é 252 (sim, já sabemos como mudar os valores)
- se de 252 + 256 a 252 + 256 + 65536, defina 253 e use os próximos 2 bytes para armazenar o próprio número - uma diferença desnecessária
- se de 252 + 256 + 65536 a 252 + 256 + 65536 + 16777216, coloque 254 e 3 bytes
- caso contrário, 255 e 4 bytes.
Este é um bom caminho? Tudo é relativo. Em um byte podemos enviar valores de até 252, enquanto no VLQ apenas até 127, mas apenas 508 em 2 bytes, e já 16383 no VLQ. o método é bom se seus números forem densos o suficiente, e aqui vamos vencer. Mas a coisa boa sobre o método é que ele pode ser ajustado para diferentes intervalos. Por exemplo, se sabemos que a maioria dos números vai de 10.000 a 50.000, então podemos sempre armazená-los em dois bytes, mas se algum número grande sair, escreveremos 65535 e já usaremos 4. Na verdade, otimizamos o armazenamento da faixa necessária ao custo de armazenamento ineficiente desnecessário.
Conclusão
Examinamos as principais formas de economizar memória (na verdade, minha imaginação se esgotou, mas não vou admitir). Essas técnicas podem ser combinadas, usadas para outras tarefas e modificadas para se adequar à situação. Qual é a melhor técnica no final? Tudo depende dos seus dados. Pegue-os e experimente. Felizmente, não é necessário implementar tudo de uma vez. É fácil escrever um código que simplesmente avalie o comprimento. E após a avaliação, já implemente o que gostou.
Não se esqueça da velocidade de tudo isso: você está pronto para gastar muito tempo preparando ou obtendo dados. Vale a pena começar uma luta com bits, ou você não deveria ir abaixo de bytes. É o suficiente para otimizar situações frequentes, deixando raras com implementação ineficaz. É possível, dependendo dos dados, usar métodos de armazenamento diferentes (por exemplo, é estúpido armazenar até 8 bytes em uma matriz, uma vez que os custos colaterais irão devorar todo o ganho, e de 1 byte - geralmente armazenam em uma pseudomatriz de um elemento, ou seja, no número).
Além disso, algumas palavras sobre compressão: aqui não será muito eficaz. Algoritmos de compressão gostam muito de repetições, mas não há muitos deles aqui. Se você pegar um Zip condicional, que consiste em LZ77 + Huffman, é improvável que algo útil saia com o LZ77, mas Huffman pode tentar salvar bytes. Então Zip será meio inútil. Mas a velocidade vai cair muito, muito mesmo.
As situações em que sabemos que temos muitos conjuntos e podemos armazená-los todos juntos usando diferentes fatias ainda não foram consideradas. Aqui eu confesso - não tenho certeza se vai funcionar. Imediatamente, não pensei em opções. Mas percebi que seria difícil. No entanto, você pode ter opiniões diferentes.
Então compartilhe suas ideias nos comentários, talvez eu tenha perdido algum elefante óbvio que vai economizar ainda mais bytes e obter um resultado tal que as donas de casa do anúncio do detergente (que dá para uma gota) vão invejar a todos!