Maneira mais eficiente de armazenar milhares de números de telefone

Esta é uma pergunta da entrevista do Google:

Existem cerca de mil números de telefone a serem armazenados, cada um com 10 dígitos. Você pode presumir que os primeiros 5 dígitos de cada um sejam iguais em milhares de números. Você deve realizar as seguintes operações: a. Pesquise se um determinado número existe. b. Imprimir todos os números

Qual é a maneira mais eficiente de economizar espaço para fazer isso?

Eu respondi a tabela hash e depois a codificação huffman, mas meu entrevistador disse que eu não estava indo na direção certa. Por favor me ajude aqui.

Usar um sufixo pode ajudar?

Idealmente, o armazenamento de 1000 números leva 4 bytes por número, portanto, ao todo, seriam necessários 4000 bytes para armazenar 1000 números. Quantitativamente, desejo reduzir o armazenamento para menos de 4000 bytes, foi o que meu entrevistador me explicou.

Aqui está uma melhoria na resposta de aix . Considere o uso de três "camadas" para a estrutura de dados: a primeira é uma constante para os primeiros cinco dígitos (17 bits); então, de agora em diante, cada número de telefone tem apenas os cinco dígitos restantes. Vemos esses cinco dígitos restantes como inteiros binários de 17 bits e armazenamos k desses bits usando um método e 17 - k = m com um método diferente, determinando k no final para minimizar o espaço necessário.

Primeiro classificamos os números de telefone (todos reduzidos a 5 dígitos decimais). Em seguida, contamos quantos números de telefone existem para os quais o número binário que consiste nos primeiros m bits é todo 0, para quantos números de telefone os primeiros m bits são no máximo 0 ... 01, para quantos números de telefone os primeiros m os bits são no máximo 0 ... 10, etc., até a contagem dos números de telefone para os quais os primeiros m bits são 1 ... 11 - esta última contagem é 1000 (decimal). Existem 2 ^ m dessas contagens e cada contagem é no máximo 1000. Se omitirmos a última (porque sabemos que é 1000 de qualquer maneira), podemos armazenar todos esses números em um bloco contíguo de (2 ^ m - 1) * 10 bits. (10 bits são suficientes para armazenar um número menor que 1024).

Os últimos k bits de todos os números de telefone (reduzidos) são armazenados de forma contígua na memória; então se k for, digamos, 7, então os primeiros 7 bits deste bloco de memória (bits 0 a 6) correspondem aos últimos 7 bits do primeiro número de telefone (reduzido), os bits 7 a 13 correspondem aos últimos 7 bits do segundo número de telefone (reduzido), etc. Isso requer 1000 * k bits para um total de 17 + (2 ^ (17 - k ) - 1) * 10 + 1000 * k , que atinge seu mínimo 11287 para k = 10. Assim, podemos armazenar todos os números de telefone no teto ( 11287/8) = 1411 bytes.

Espaço adicional pode ser salvo observando que nenhum dos nossos números pode começar com, por exemplo, 1111111 (binário), porque o menor número que começa com isso é 130048 e temos apenas cinco dígitos decimais. Isso nos permite cortar algumas entradas do primeiro bloco de memória: em vez de 2 ^ m - 1 contagens, precisamos apenas ceil (99999/2 ^ k ). Isso significa que a fórmula se torna

17 + teto (99999/2 ^ k ) * 10 + 1000 * k

que surpreendentemente atinge seu mínimo de 10997 para k = 9 e k = 10, ou ceil (10997/8) = 1375 bytes.

Se quisermos saber se um determinado número de telefone está em nosso conjunto, primeiro verificamos se os primeiros cinco dígitos binários correspondem aos cinco dígitos que armazenamos. Em seguida, dividimos os cinco dígitos restantes em seus m = 7 bits superiores (que é, digamos, o número de m- bits M ) e seus k inferior = 10 bits (o número K ). Agora encontramos o número a [M-1] de números de telefone reduzidos para os quais os primeiros m dígitos são no máximo M - 1, e o número a [M] de números de telefone reduzidos para os quais os primeiros m dígitos são no máximo M , ambos do primeiro bloco de bits. Nós agora verificar entre o um[M-1] th e a [M] th seqüência de k bits no segundo bloco de memória para ver se encontramos K ; no pior caso, existem 1000 dessas sequências, portanto, se usarmos a pesquisa binária, podemos terminar em O (log 1000) operações.

Segue-se um pseudocódigo para imprimir todos os 1000 números, onde eu acesso a entrada K 'th k- bits do primeiro bloco de memória como a [K] e a entrada M ' th m- bits do segundo bloco de memória como b [M] (ambos exigiriam algumas operações de bits que são entediantes de gravar). Os primeiros cinco dígitos estão no número c .

i := 0;
for K from 0 to ceil(99999 / 2^k) do
  while i < a[K] do
    print(c * 10^5 + K * 2^k + b[i]);
    i := i + 1;
  end do;
end do;

Talvez algo dê errado com o caso limite para K = ceil (99999/2 ^ k ), mas isso é fácil de corrigir.

Finalmente, do ponto de vista da entropia, não é possível armazenar um subconjunto de 10 ^ 3 inteiros positivos todos menores que 10 ^ 5 em menos que ceil (log [2] (binomial (10 ^ 5, 10 ^ 3)) ) = 8073. Incluindo os 17 de que precisamos para os primeiros 5 dígitos, ainda há um intervalo de 10997 - 8090 = 2907 bits. É um desafio interessante ver se existem soluções melhores onde você ainda pode acessar os números de forma relativamente eficiente!

A seguir, trato os números como variáveis ​​inteiras (em oposição a strings):

1. Classifique os números.
2. Divida cada número nos primeiros cinco dígitos e nos últimos cinco dígitos.
3. Os primeiros cinco dígitos são iguais para todos os números, portanto, armazene-os apenas uma vez. Isso exigirá 17 bits de armazenamento.
4. Armazene os cinco dígitos finais de cada número individualmente. Isso exigirá 17 bits por número.

Para recapitular: os primeiros 17 bits são o prefixo comum, os 1000 grupos subsequentes de 17 bits são os últimos cinco dígitos de cada número armazenado em ordem crescente.

No total, estamos olhando para 2128 bytes para os 1000 números, ou 17,017 bits por número de telefone de 10 dígitos.

A pesquisa é O(log n)(pesquisa binária) e a enumeração completa é O(n).

http://en.wikipedia.org/wiki/Acyclic_deterministic_finite_automaton

Certa vez, tive uma entrevista em que eles perguntaram sobre estruturas de dados. Esqueci "Array".

Eu provavelmente consideraria usar alguma versão compactada de um Trie (possivelmente um DAWG como sugerido por @Misha).

Isso se aproveitaria automaticamente do fato de que todos eles têm um prefixo comum.

A pesquisa será realizada em tempo constante e a impressão será realizada em tempo linear.

Já ouvi falar desse problema antes (mas sem a suposição de que os primeiros 5 dígitos são iguais), e a maneira mais simples de fazer isso era Codificação de arroz :

1) Como a ordem não importa, podemos classificá-los e salvar apenas as diferenças entre valores consecutivos. Em nosso caso, as diferenças médias seriam 100.000 / 1000 = 100

2) Codifique as diferenças usando códigos de arroz (base 128 ou 64) ou mesmo códigos de Golomb (base 100).

EDIT: Uma estimativa para a codificação de arroz com base 128 (não porque daria melhores resultados, mas porque é mais fácil de calcular):

Salvaremos o primeiro valor como está (32 bits).
O restante dos 999 valores são diferenças (esperamos que sejam pequenos, 100 em média) conterão:

valor unário value / 128(número variável de bits + 1 bit como terminador)
valor binário para value % 128(7 bits)

Temos que estimar de alguma forma os limites (vamos chamá-lo VBL) para o número de bits variáveis:
limite inferior: considere que temos sorte, e nenhuma diferença é maior do que nossa base (128 neste caso). isso significaria fornecer 0 bits adicionais.
limite alto: como todas as diferenças menores que a base serão codificadas na parte binária do número, o número máximo que precisaríamos codificar em unário é 100000/128 = 781,25 (ainda menos, porque não esperamos que a maioria das diferenças seja zero )

Portanto, o resultado é 32 + 999 * (1 + 7) + variável (0..782) bits = 1003 + variável (0..98) bytes.

Este é um problema bem conhecido do Bentley's Programming Pearls.

Solução: retire os primeiros cinco dígitos dos números, pois eles são iguais para todos os números. Em seguida, use operações bit a bit para representar os 9999 valores possíveis restantes. Você só precisará de 2 ^ 17 bits para representar os números. Cada bit representa um número. Se o bit estiver definido, o número está na lista telefônica.

Para imprimir todos os números, basta imprimir todos os números onde o bit é definido concatenado com o prefixo. Para pesquisar um determinado número, faça a aritmética de bits necessária para verificar a representação bit a bit do número.

Você pode pesquisar um número em O (1) e a eficiência de espaço é máxima devido à representação de bits.

HTH Chris.

Armazenamento fixo de 1.073 bytes para 1.000 números:

O formato básico deste método de armazenamento é armazenar os primeiros 5 dígitos, uma contagem para cada grupo e o deslocamento para cada número em cada grupo.

Prefixo:
nosso prefixo de 5 dígitos ocupa os primeiros 17 bits .

Agrupamento: em
seguida, precisamos descobrir um agrupamento de bom tamanho para números. Vamos tentar ter cerca de 1 número por grupo. Como sabemos que existem cerca de 1000 números para armazenar, dividimos 99.999 em cerca de 1000 partes. Se escolhermos o tamanho do grupo como 100, haverá desperdício de bits, então vamos tentar um tamanho de grupo de 128, que pode ser representado com 7 bits. Isso nos dá 782 grupos para trabalhar.

Contagens: a
seguir, para cada um dos 782 grupos, precisamos armazenar a contagem de entradas em cada grupo. Uma contagem de 7 bits para cada grupo resultaria 7*782=5,474 bits, o que é muito ineficiente porque o número médio representado é cerca de 1 por causa de como escolhemos nossos grupos.

Assim, em vez disso, temos contagens de tamanhos variáveis ​​com 1's iniciais para cada número em um grupo seguido por 0. Portanto, se tivéssemos xnúmeros em um grupo, teríamos x 1'sseguido por a 0para representar a contagem. Por exemplo, se tivéssemos 5 números em um grupo, a contagem seria representada por 111110. Com esse método, se houver 1.000 números, terminaremos com 1000 1's e 782 0's para um total de 1000 + 782 = 1.782 bits para as contagens .

Offset: por
último, o formato de cada número será apenas o offset de 7 bits para cada grupo. Por exemplo, se 00000 e 00001 forem os únicos números no grupo 0-127, os bits desse grupo seriam 110 0000000 0000001. Supondo 1.000 números, haverá 7.000 bits para os deslocamentos .

Portanto, nossa contagem final assumindo 1.000 números é a seguinte:

17 (prefix) + 1,782 (counts) + 7,000 (offsets) = 8,799 bits = 1100 bytes

Agora, vamos verificar se nossa seleção do tamanho do grupo arredondando para 128 bits foi a melhor escolha para o tamanho do grupo. Escolhendo xcomo o número de bits para representar cada grupo, a fórmula para o tamanho é:

Size in bits = 17 (prefix) + 1,000 + 99,999/2^x + x * 1,000

Minimizar essa equação para valores inteiros de xdá x=6, o que resulta em 8.580 bits = 1.073 bytes . Assim, nosso armazenamento ideal é o seguinte:

• Tamanho do grupo: 2 ^ 6 = 64
• Número de grupos: 1.562

• Armazenamento total:

  1017 (prefix plus 1's) + 1563 (0's in count) + 6*1000 (offsets) = 8,580 bits = 1,073 bytes

Tomando isso como um problema puramente teórico e deixando de lado a implementação, a maneira mais eficiente é apenas indexar todos os conjuntos possíveis de 10.000 últimos dígitos em uma tabela de indexação gigantesca. Supondo que você tenha exatamente 1.000 números, você precisaria de um pouco mais de 8.000 bits para identificar com exclusividade o conjunto atual. Não há compressão maior possível, porque então você teria dois conjuntos que são identificados com o mesmo estado.

O problema com isso é que você teria que representar cada um dos 2 ^ 8000 conjuntos em seu programa como um lut, e nem mesmo o Google seria remotamente capaz disso.

A pesquisa seria O (1), imprimindo todos os números O (n). A inserção seria O (2 ^ 8000) que em teoria é O (1), mas na prática é inutilizável.

Numa entrevista, só responderia, se tivesse a certeza, que a empresa procura alguém que saiba pensar muito fora da caixa. Caso contrário, isso pode fazer você parecer um teórico sem preocupações com o mundo real.

EDIT : Ok, aqui está uma "implementação".

Passos para construir a implementação:

1. Pegue uma matriz constante de tamanho 100.000 * (1000 escolha 100.000) bits. Sim, estou ciente do fato de que esta matriz precisará de mais espaço do que átomos no universo em várias magnitudes.
2. Separe essa grande matriz em blocos de 100.000 cada.
3. Em cada bloco, armazene uma matriz de bits para uma combinação específica dos últimos cinco dígitos.

Este não é o programa, mas uma espécie de metaprograma, que construirá um LUT gigante que agora pode ser usado em um programa. O material constante do programa normalmente não é contado ao calcular a eficiência de espaço, portanto, não nos importamos com essa matriz, ao fazer nossos cálculos finais.

Aqui está como usar este LUT:

1. Quando alguém lhe dá 1000 números, você armazena os primeiros cinco dígitos separadamente.
2. Descubra quais pedaços de sua matriz correspondem a este conjunto.
3. Armazene o número do conjunto em um único número de 8074 bits (chame isso de c).

Isso significa que para o armazenamento, precisamos apenas de 8091 bits, que provamos ser a codificação ideal. Encontrar o pedaço correto, entretanto, leva O (100.000 * (100.000 escolha 1000)), que de acordo com as regras matemáticas é O (1), mas na prática sempre levará mais tempo do que o tempo do universo.

No entanto, a pesquisa é simples:

1. tira dos primeiros cinco dígitos (o número restante será chamado de n ').
2. teste se eles combinam
3. Calcule i = c * 100000 + n '
4. Verifique se o bit em i no LUT está definido como um

Imprimir todos os números também é simples (e leva O (100000) = O (1) na verdade, porque você sempre tem que verificar todos os bits do bloco atual, então calculei mal isso acima).

Eu não chamaria isso de "implementação", por causa do desprezo flagrante das limitações (tamanho do universo e tempo que este universo viveu ou esta terra existirá). No entanto, em teoria, esta é a solução ideal. Para problemas menores, isso realmente pode ser feito, e às vezes será feito. Por exemplo, redes de classificação são um exemplo para esta forma de codificação e podem ser usadas como uma etapa final em algoritmos de classificação recursiva, para obter um grande aumento de velocidade.

Isso é equivalente a armazenar mil inteiros não negativos, cada um com menos de 100.000. Podemos usar algo como codificação aritmética para fazer isso.

Por fim, os números serão armazenados em uma lista classificada. Observo que a diferença esperada entre os números adjacentes na lista é 100.000 / 1000 = 100, que pode ser representado em 7 bits. Haverá também muitos casos em que mais de 7 bits são necessários. Uma maneira simples de representar esses casos menos comuns é adotar o esquema utf-8 em que um byte representa um inteiro de 7 bits, a menos que o primeiro bit seja definido, caso em que o próximo byte é lido para produzir um inteiro de 14 bits, a menos seu primeiro bit é definido, caso em que o próximo byte é lido para representar um inteiro de 21 bits.

Portanto, pelo menos metade das diferenças entre inteiros consecutivos pode ser representada com um byte, e quase todo o resto requer dois bytes. Alguns números, separados por diferenças maiores que 16.384, exigirão três bytes, mas não pode haver mais de 61 deles. O armazenamento médio será então de cerca de 12 bits por número, ou um pouco menos, ou no máximo 1.500 bytes.

A desvantagem dessa abordagem é que verificar a existência de um número agora é O (n). No entanto, nenhum requisito de complexidade de tempo foi especificado.

Depois de escrever, percebi que ruslik já sugeriu o método de diferença acima, a única diferença é o esquema de codificação. O meu é provavelmente mais simples, mas menos eficiente.

Só para perguntar rapidamente qualquer motivo pelo qual não gostaríamos de mudar os números em uma base 36. Pode não economizar tanto espaço, mas com certeza economizaria tempo na busca, pois você estará olhando muito menos que 10 dígitos. Ou eu os dividiria em arquivos dependendo de cada grupo. então, eu nomearia um arquivo (111) -222.txt e, em seguida, armazenaria apenas os números que cabem nesse grupo e os tornaria pesquisáveis ​​em ordem numérica. Dessa forma, eu sempre poderei pesquisar para ver se o arquivo é encerrado. antes de fazer uma pesquisa maior. ou para ser correto, eu correria para pesquisas binárias um para o arquivo para ver se ele sai. e outra pesquisa óssea no conteúdo do arquivo

Por que não manter as coisas simples? Use uma variedade de estruturas.

Portanto, podemos salvar os primeiros 5 dígitos como uma constante, então esqueça-os por enquanto.

65535 é o máximo que pode ser armazenado em um número de 16 bits, e o número máximo que podemos ter é 99999, que se encaixa no número de 17 bits com um máximo de 131071.

Usar tipos de dados de 32 bits é um desperdício porque precisamos apenas de 1 bit dos 16 bits extras ... portanto, podemos definir uma estrutura que tem um booleano (ou caractere) e um número de 16 bits.

Assumindo C / C ++

typedef struct _number {

    uint16_t number;
    bool overflow;
}Number;

Esta estrutura ocupa apenas 3 bytes e precisamos de um array de 1000, portanto, 3000 bytes no total. Reduzimos o espaço total em 25%!

No que diz respeito a armazenar os números, podemos fazer matemática simples bit a bit

overflow = (number5digits & 0x10000) >> 4;
number = number5digits & 0x1111;

E o inverso

//Something like this should work
number5digits = number | (overflow << 4);

Para imprimir todos eles, podemos usar um loop simples sobre o array. A recuperação de um número específico ocorre em tempo constante, é claro, pois é um array.

for(int i=0;i<1000;i++) cout << const5digits << number5digits << endl;

Para pesquisar um número, gostaríamos de um array ordenado. Assim, quando os números forem salvos, classifique a matriz (eu escolheria pessoalmente uma classificação por mesclagem, O (nlogn)). Agora, para pesquisar, eu usaria uma abordagem de classificação de mesclagem. Divida o array e veja qual é o nosso número. Em seguida, chame a função apenas nesse array. Faça isso recursivamente até obter uma correspondência e retornar o índice, caso contrário, ele não existe e imprime um código de erro. Esta pesquisa seria bastante rápida, e o pior caso ainda é melhor do que O (nlogn), pois será absolutamente executado em menos tempo do que o merge sort (apenas recorrendo a 1 lado da divisão de cada vez, em vez de ambos os lados :)), que é O (nlogn).

Minha solução: melhor caso 7,025 bits / número, pior caso 14,193 bits / número, média aproximada de 8,551 bits / número. Codificado em fluxo, sem acesso aleatório.

Antes mesmo de ler a resposta de ruslik, pensei imediatamente em codificar a diferença entre cada número, pois será pequeno e deve ser relativamente consistente, mas a solução também deve ser capaz de acomodar o pior cenário. Temos um espaço de 100.000 números que contêm apenas 1.000 números. Em uma lista telefônica perfeitamente uniforme, cada número seria maior do que o número anterior em 100:

55555-12 3 45
55555-12 4 45
55555-12 5 45

Se fosse esse o caso, seria necessário armazenamento zero para codificar as diferenças entre os números, uma vez que é uma constante conhecida. Infelizmente, os números podem variar dos passos ideais de 100. Eu codificaria a diferença do incremento ideal de 100, de modo que se dois números adjacentes diferirem por 103, eu codificaria o número 3 e se dois números adjacentes diferirem por 92, I codificaria -8. Eu chamo o delta de um incremento ideal de 100 de “ variância ”.

A variação pode variar de -99 (ou seja, dois números consecutivos) a 99000 (toda a lista telefônica consiste em números 00000… 00999 e um número mais distante adicional 99999), que é uma faixa de 99100 valores possíveis.

Eu pretendem alocar um mínimo de armazenamento para codificar as diferenças mais comuns e expandir o armazenamento se eu encontrar diferenças maiores (como Protobuf ‘s varint). Usarei pedaços de sete bits, seis para armazenamento e um bit de sinalizador adicional no final para indicar que essa variação é armazenada com um pedaço adicional após o atual, até um máximo de três pedaços (o que fornecerá um máximo de 3 * 6 = 18 bits de armazenamento, que são 262144 valores possíveis, mais do que o número de variações possíveis (99100). Cada pedaço adicional que segue um sinalizador elevado tem bits de significância mais alta, então o primeiro pedaço sempre tem bits 0- 5, os segundos pedaços opcionais têm os bits 6-11 e o terceiro pedaço opcional tem os bits 12-17.

Um único bloco fornece seis bits de armazenamento que podem acomodar 64 valores. Eu gostaria de mapear as 64 menores variações para caber naquele único pedaço (ou seja, variações de -32 a +31), então usarei a codificação ProtoBuf ZigZag, até as variações de -99 a +98 (já que não há necessidade para uma variação negativa além de -99), ponto em que mudarei para a codificação regular, com deslocamento de 98:  

Variância | Valor Codificado
----------- + ----------------
    0 | 0
   -1 | 1
    1 | 2
   -2 | 3
    2 | 4
   -3 | 5
    3 | 6
   ... | ...
  -31 | 61
   31 | 62
  -32 | 63
----------- | --------------- 6 bits
   32 64
  -33 | 65
   33 66
   ... | ...
  -98 | 195
   98 196
  -99 | 197
----------- | --------------- Fim do ZigZag
   100 198
   101 199
   ... | ...
  3996 | 4094
  3997 | 4095
----------- | --------------- 12 bits
  3998 | 4096
  3999 | 4097
   ... | ...
 262045 | 262143
----------- | --------------- 18 bits

Alguns exemplos de como as variações seriam codificadas como bits, incluindo o sinalizador para indicar um fragmento adicional:

Variância | Bits codificados
----------- + ----------------
     0 | 000000 0
     5 | 001010 0
    -8 | 001111 0
   -32 | 111111 0
    32 000000 1 000001 0
   -99 | 000101 1 000011 0
   177 010011 1 000100 0
 14444 | 001110 1 100011 1 000011 0

Portanto, os três primeiros números de uma amostra de catálogo telefônico seriam codificados como um fluxo de bits da seguinte forma:

BIN 000101001011001000100110010000011001 000110 1 010110 1 00001 0
PH # 55555-12345 55555-12448 55555-12491
POS 1 2 3

Na melhor das hipóteses , a lista telefônica é distribuída de maneira um tanto uniforme e não há dois números de telefone com variação maior do que 32, então ele usaria 7 bits por número mais 32 bits para o número inicial para um total de 32 + 7 * 999 = 7025 bits .
Um cenário misto , em que a variação de 800 números de telefone se encaixa em um bloco (800 * 7 = 5600), 180 números se encaixam em dois blocos cada (180 * 2 * 7 = 2520) e 19 números se encaixam em três blocos cada (20 * 3 * 7 = 399), mais os 32 bits iniciais, totalizam 8.551 bits .
Na pior das hipóteses , 25 números cabem em três blocos (25 * 3 * 7 = 525 bits) e os 974 números restantes cabem em dois blocos (974 * 2 * 7 = 13636 bits), mais 32 bits para o primeiro número de um grande total de14193 bits .

   Quantidade de números codificados |
 1 pedaço | 2 pedaços | 3 pedaços | Bits totais
--------- + ---------- + ---------- + ------------
   999 | 0 | 0 | 7025
   800 | 180 19 8551
    0 | 974 | 25 14193

Posso ver quatro otimizações adicionais que podem ser realizadas para reduzir ainda mais o espaço necessário:

1. O terceiro pedaço não precisa dos sete bits completos, pode ter apenas cinco bits e sem um bit de sinalizador.
2. Pode haver uma passagem inicial dos números para calcular os melhores tamanhos para cada pedaço. Talvez para uma determinada lista telefônica, seria ótimo ter o primeiro bloco com 5 + 1 bits, o segundo 7 + 1 e o terceiro 5 + 1. Isso reduziria ainda mais o tamanho para um mínimo de 6 * 999 + 32 = 6026 bits, mais dois conjuntos de três bits para armazenar os tamanhos dos blocos 1 e 2 (o tamanho do bloco 3 é o restante dos 16 bits necessários) para um total de 6032 bits!
3. A mesma passagem inicial pode calcular um incremento esperado melhor do que o padrão 100. Talvez haja uma lista telefônica que começa em 55555-50000 e, portanto, tem metade do intervalo de números, então o incremento esperado deve ser 50. Ou talvez haja um catálogo não linear distribuição (desvio padrão talvez) e algum outro incremento ideal esperado pode ser usado. Isso reduziria a variação típica e poderia permitir que um primeiro pedaço ainda menor fosse usado.
4. Uma análise posterior pode ser feita na primeira passagem para permitir que a lista telefônica seja particionada, com cada partição tendo seu próprio incremento esperado e otimizações de tamanho de bloco. Isso permitiria um primeiro tamanho de bloco menor para certas partes altamente uniformes da lista telefônica (reduzindo o número de bits consumidos) e tamanhos de bloco maiores para partes não uniformes (reduzindo o número de bits desperdiçados em sinalizadores de continuação).

A verdadeira questão é armazenar números de telefone de cinco dígitos.

O truque é que você precisaria de 17 bits para armazenar o intervalo de números de 0 a 99.999. Mas armazenar 17 bits em limites de palavra convencionais de 8 bytes é um incômodo. É por isso que eles estão perguntando se você pode fazer em menos de 4k, não usando inteiros de 32 bits.

Pergunta: todas as combinações de números são possíveis?

Devido à natureza do sistema telefônico, pode haver menos de 65k combinações possíveis. Vou supor que sim porque estamos falando das últimas cinco posições no número de telefone, em oposição ao código de área ou prefixos de troca.

Pergunta: esta lista será estática ou precisará oferecer suporte a atualizações?

Se for estático , quando chegar a hora de preencher o banco de dados, conte o número de dígitos <50.000 e o número de dígitos> = 50.000. Aloque duas matrizes de uint16comprimento apropriado: uma para os inteiros abaixo de 50.000 e outra para o conjunto superior. Ao armazenar inteiros na matriz superior, subtraia 50.000 e ao ler inteiros dessa matriz, adicione 50.000. Agora você armazenou seus 1.000 inteiros em 2.000 palavras de 8 bytes.

A construção da lista telefônica exigirá duas passagens de entrada, mas as pesquisas devem acontecer na metade do tempo, em média, do que fariam com uma única matriz. Se o tempo de pesquisa fosse muito importante, você poderia usar mais arrays para intervalos menores, mas acho que com esses tamanhos seu limite de desempenho seria puxar os arrays da memória e 2k provavelmente serão armazenados no cache da CPU se não registrar espaço em qualquer coisa que você usaria. dias.

Se for dinâmico , aloque uma matriz de 1000 ou mais uint16e adicione os números em ordem classificada. Defina o primeiro byte como 50.001 e defina o segundo byte como um valor nulo apropriado, como NULL ou 65.000. Ao armazenar os números, armazene-os em ordem de classificação. Se um número estiver abaixo de 50.001, armazene-o antes do marcador 50.001. Se um número for 50.001 ou maior, armazene-o após o marcador 50.001, mas subtraia 50.000 do valor armazenado.

Sua matriz será semelhante a:

00001 = 00001
12345 = 12345
50001 = reserved
00001 = 50001
12345 = 62345
65000 = end-of-list

Portanto, quando você procura um número na lista telefônica, percorre o array e, se atingir o valor 50.001, começará a adicionar 50.000 aos valores do array.

Isso torna as inserções muito caras, mas as pesquisas são fáceis e você não vai gastar muito mais do que 2k em armazenamento.