Eu tenho um computador com 1 MB de RAM e nenhum outro armazenamento local. Preciso usá-lo para aceitar 1 milhão de números decimais de 8 dígitos em uma conexão TCP, classificá-los e enviar a lista classificada por outra conexão TCP.
A lista de números pode conter duplicatas, que não devo descartar. O código será colocado na ROM, portanto não preciso subtrair o tamanho do meu código dos 1 MB. Eu já tenho código para conduzir a porta Ethernet e manipular conexões TCP / IP e requer 2 KB para seus dados de estado, incluindo um buffer de 1 KB através do qual o código lerá e gravará dados. Existe uma solução para este problema?
Fontes de pergunta e resposta:
Respostas:
Existe um truque bastante sorrateiro não mencionado aqui até agora. Assumimos que você não tem uma maneira extra de armazenar dados, mas isso não é rigorosamente verdade.
Uma maneira de contornar o problema é fazer a seguinte coisa horrível, que não deve ser tentada por ninguém sob nenhuma circunstância: Use o tráfego de rede para armazenar dados. E não, eu não quero dizer NAS.
Você pode classificar os números com apenas alguns bytes de RAM da seguinte maneira:
COUNTER
eVALUE
.0
;I
, incrementeCOUNTER
e definaVALUE
comomax(VALUE, I)
;I
para o roteador. ApagueI
e repita.Uma vez
COUNTER
atingido1000000
, você tem todos os valores armazenados no fluxo incessante de solicitações de ICMP eVALUE
agora contém o número inteiro máximo. Escolha algunsthreshold T >> 1000000
. DefinaCOUNTER
como zero. Toda vez que você receber um pacote ICMP, aumenteCOUNTER
e envie o número inteiro contidoI
novamente em outra solicitação de eco, a menos queI=VALUE
, nesse caso, transmita-o para o destino dos números inteiros classificados. Uma vezCOUNTER=T
, diminuaVALUE
por1
, redefinaCOUNTER
para zero e repita. Uma vez queVALUE
chegar a zero você deve ter transmitido todos os inteiros em ordem da maior para a menor para o destino, e só ter usado cerca de 47 bits de RAM para as duas variáveis persistentes (e qualquer pequena quantidade que você precisa para os valores temporários).Sei que isso é horrível e sei que pode haver todo tipo de questões práticas, mas achei que isso poderia dar risada a alguns de vocês ou, pelo menos, horrorizá-los.
fonte
Aqui está um código C ++ que resolve o problema.
Prova de que as restrições de memória são atendidas:Editor: Não há provas dos requisitos máximos de memória oferecidos pelo autor nesta postagem ou em seus blogs. Como o número de bits necessários para codificar um valor depende dos valores codificados anteriormente, essa prova provavelmente não é trivial. O autor observa que o maior tamanho codificado que ele poderia encontrar empiricamente era
1011732
e escolheu o tamanho do buffer1013000
arbitrariamente.Juntas, essas duas matrizes ocupam 1045000 bytes de armazenamento. Isso deixa 1048576 - 1045000 - 2 × 1024 = 1528 bytes para as variáveis restantes e espaço na pilha.
Ele roda em cerca de 23 segundos no meu Xeon W3520. Você pode verificar se o programa funciona usando o seguinte script Python, assumindo o nome de um programa
sort1mb.exe
.Uma explicação detalhada do algoritmo pode ser encontrada na seguinte série de postagens:
fonte
(n+m)!/(n!m!)
), então você deve estar certo. Provavelmente, é minha estimativa que um delta de b bits leva b bits para armazenar - claramente deltas de 0 não levam 0 bits para armazenar.Consulte a primeira resposta correta ou a resposta posterior com codificação aritmética . Abaixo, você pode encontrar alguma solução divertida, mas não 100% à prova de balas.
Esta é uma tarefa bastante interessante e aqui está outra solução. Espero que alguém ache o resultado útil (ou pelo menos interessante).
Etapa 1: Estrutura de dados inicial, abordagem aproximada de compactação, resultados básicos
Vamos fazer algumas contas simples: temos 1M (1048576 bytes) de RAM disponível inicialmente para armazenar 10 ^ 6 números decimais de 8 dígitos. [0; 99999999]. Portanto, para armazenar um número, são necessários 27 bits (assumindo que números não assinados serão usados). Assim, para armazenar um fluxo bruto, serão necessários ~ 3,5M de RAM. Alguém já disse que isso não parece viável, mas eu diria que a tarefa pode ser resolvida se a entrada for "boa o suficiente". Basicamente, a idéia é compactar os dados de entrada com fator de compressão 0,29 ou superior e fazer a classificação de maneira adequada.
Vamos resolver o problema de compactação primeiro. Existem alguns testes relevantes já disponíveis:
http://www.theeggeadventure.com/wikimedia/index.php/Java_Data_Compression
Parece que o LZMA ( algoritmo de cadeia Lempel – Ziv – Markov ) é uma boa opção para continuar. Eu preparei um PoC simples, mas ainda há alguns detalhes a serem destacados:
Observe que o código anexado é um POC , não pode ser usado como solução final, apenas demonstra a idéia de usar vários buffers menores para armazenar números pré-classificados da melhor maneira possível (possivelmente compactados). O LZMA não é proposto como uma solução final. É usado como a maneira mais rápida possível de introduzir uma compactação neste PoC.
Veja o código PoC abaixo (observe apenas uma demonstração, para compilá-lo será necessário o LZMA-Java ):
Com números aleatórios, produz o seguinte:
Para uma sequência ascendente simples (um balde é usado), produz:
EDITAR
Conclusão:
Etapa 2: Compactação aprimorada, conclusão final
Como já foi mencionado na seção anterior, qualquer técnica de compressão adequada pode ser usada. Então, vamos nos livrar do LZMA em favor de uma abordagem mais simples e melhor (se possível). Existem muitas boas soluções, incluindo codificação aritmética , árvore Radix etc.
De qualquer forma, o esquema de codificação simples, mas útil, será mais ilustrativo do que outra biblioteca externa, fornecendo algum algoritmo bacana. A solução real é bastante direta: como existem depósitos com dados parcialmente classificados, deltas podem ser usados em vez de números.
O teste de entrada aleatória mostra resultados ligeiramente melhores:
Código de amostra
Observe que esta abordagem:
O código completo pode ser encontrado aqui , as implementações BinaryInput e BinaryOutput podem ser encontradas aqui
Conclusão final
Sem conclusão final :) Às vezes, é realmente uma boa ideia subir um nível acima e revisar a tarefa do ponto de vista de um nível meta .
Foi divertido passar algum tempo com essa tarefa. BTW, há muitas respostas interessantes abaixo. Obrigado por sua atenção e feliz codificação.
fonte
Uma solução é possível apenas devido à diferença entre 1 megabyte e 1 milhão de bytes. Existem cerca de 2 no poder 8093729.5 maneiras diferentes de escolher 1 milhão de números de 8 dígitos com duplicatas permitidas e solicitar sem importância, portanto, uma máquina com apenas 1 milhão de bytes de RAM não possui estados suficientes para representar todas as possibilidades. Mas 1M (menos 2k para TCP / IP) é 1022 * 1024 * 8 = 8372224 bits, portanto, uma solução é possível.
Parte 1, solução inicial
Essa abordagem precisa de um pouco mais de 1 milhão. Refino-a para caber na 1 milhão depois.
Armazenarei uma lista compacta e ordenada de números no intervalo de 0 a 99999999 como uma sequência de sublistas de números de 7 bits. A primeira sublista contém números de 0 a 127, a segunda sublista contém números de 128 a 255, etc. 100000000/128 é exatamente 781250, portanto 781250 tais sublistas serão necessários.
Cada sub-lista consiste em um cabeçalho de sub-lista de 2 bits seguido por um corpo de sub-lista. O corpo da sub-lista ocupa 7 bits por entrada da sub-lista. As sublistas são todas concatenadas juntas, e o formato permite dizer onde uma sub-lista termina e a seguinte começa. O armazenamento total necessário para uma lista totalmente preenchida é de 2 * 781250 + 7 * 1000000 = 8562500 bits, ou seja, 1,021 M-bytes.
Os 4 possíveis valores de cabeçalho da sub-lista são:
00 Sublist vazia, nada a seguir.
01 Singleton, existe apenas uma entrada na sublist e os próximos 7 bits a mantêm.
10 A sublist contém pelo menos 2 números distintos. As entradas são armazenadas em ordem não decrescente, exceto que a última entrada é menor ou igual à primeira. Isso permite que o final da sublist seja identificado. Por exemplo, os números 2,4,6 seriam armazenados como (4,6,2). Os números 2,2,3,4,4 seriam armazenados como (2,3,4,4,2).
11 A sublist contém 2 ou mais repetições de um único número. Os próximos 7 bits fornecem o número. Em seguida, vêm zero ou mais entradas de 7 bits com o valor 1, seguidas por uma entrada de 7 bits com o valor 0. O comprimento do corpo da sub-lista determina o número de repetições. Por exemplo, os números 12,12 seriam armazenados como (12,0), os números 12,12,12 seriam armazenados como (12,1,0), 12,12,12,12 seriam (12,1 1,0) e assim por diante.
Começo com uma lista vazia, leio vários números e os armazeno como números inteiros de 32 bits, classifico os novos números no local (usando heapsort, provavelmente) e os mesclamos em uma nova lista compacta. Repita até que não haja mais números para ler e, em seguida, caminhe na lista compacta mais uma vez para gerar a saída.
A linha abaixo representa a memória imediatamente antes do início da operação de mesclagem de lista. Os "O" s são a região que contém os números inteiros de 32 bits classificados. Os "X" s são a região que contém a lista compacta antiga. Os sinais "=" são a sala de expansão da lista compacta, 7 bits para cada número inteiro nos "O" s. Os "Z" s são outros custos indiretos.
A rotina de mesclagem começa a ler no "O" mais à esquerda e no "X" à esquerda e começa a escrever no "=" mais à esquerda. O ponteiro de gravação não captura o ponteiro de leitura da lista compacta até que todos os novos números inteiros sejam mesclados, porque os dois ponteiros avançam 2 bits para cada sublist e 7 bits para cada entrada na lista compacta antiga, e há espaço extra suficiente para o Entradas de 7 bits para os novos números.
Parte 2, colocando-a em 1 milhão
Para espremer a solução acima em 1M, preciso tornar o formato da lista compacta um pouco mais compacto. Vou me livrar de um dos tipos de sub-listas, para que existam apenas três valores possíveis diferentes do cabeçalho da sub-lista Então eu posso usar "00", "01" e "1" como os valores do cabeçalho da sublist e salvar alguns bits. Os tipos de sub-listas são:
Uma sublist vazia, nada a seguir.
B Singleton, existe apenas uma entrada na sublist e os próximos 7 bits a mantêm.
C A sublist contém pelo menos 2 números distintos. As entradas são armazenadas em ordem não decrescente, exceto que a última entrada é menor ou igual à primeira. Isso permite que o final da sublist seja identificado. Por exemplo, os números 2,4,6 seriam armazenados como (4,6,2). Os números 2,2,3,4,4 seriam armazenados como (2,3,4,4,2).
DA sub-lista consiste em 2 ou mais repetições de um único número.
Meus três valores de cabeçalho de sub-lista serão "A", "B" e "C", portanto, preciso de uma maneira de representar sublistas do tipo D.
Suponha que eu tenha o cabeçalho da sub-lista do tipo C seguido por 3 entradas, como "C [17] [101] [58]". Isso não pode fazer parte de uma sub-lista válida do tipo C, conforme descrito acima, pois a terceira entrada é menor que a segunda, mas maior que a primeira. Eu posso usar esse tipo de construção para representar uma sub-lista do tipo D. Em termos de bits, em qualquer lugar que eu tenha "C {00 ?????} {1 ??????} {01 ?????}" é uma sub-lista do tipo C impossível. Vou usar isso para representar uma sub-lista que consiste em 3 ou mais repetições de um único número. As duas primeiras palavras de 7 bits codificam o número (os bits "N" abaixo) e são seguidas por zero ou mais {0100001} palavras seguidas por uma palavra {0100000}.
Isso deixa apenas listas que contêm exatamente 2 repetições de um único número. Eu representarei aqueles com outro padrão impossível de sub-lista do tipo C: "C {0 ??????} {11 ?????} {10 ?????}". Há muito espaço para os 7 bits do número nas 2 primeiras palavras, mas esse padrão é maior que a sub-lista que ele representa, o que torna as coisas um pouco mais complexas. Os cinco pontos de interrogação no final podem ser considerados não parte do padrão, então eu tenho: "C {0NNNNNN} {11N ????} 10" como meu padrão, com o número a ser repetido armazenado no "N "s. São 2 bits a mais.
Vou precisar emprestar 2 bits e pagá-los dos 4 bits não utilizados nesse padrão. Ao ler, ao encontrar "C {0NNNNNN} {11N00AB} 10", imprima 2 instâncias do número nos "N" s, substitua o "10" no final pelos bits A e B e rebobine o ponteiro de leitura por 2 bits. Leituras destrutivas são aceitáveis para esse algoritmo, pois cada lista compacta é percorrida apenas uma vez.
Ao escrever uma sub-lista de 2 repetições de um único número, escreva "C {0NNNNNN} 11N00" e defina o contador de bits emprestados como 2. A cada gravação em que o contador de bits emprestados é diferente de zero, é decrementado para cada bit gravado e "10" é escrito quando o contador atinge zero. Portanto, os próximos 2 bits gravados serão inseridos nos slots A e B e, em seguida, o "10" será colocado no final.
Com três valores de cabeçalho de sub-lista representados por "00", "01" e "1", posso atribuir "1" ao tipo de sub-lista mais popular. Vou precisar de uma pequena tabela para mapear os valores do cabeçalho da sub-lista para os tipos de sub-lista e de um contador de ocorrências para cada tipo de sub-lista, para que eu saiba qual é o melhor mapeamento de cabeçalho da sub-lista.
A pior representação mínima possível de uma lista compacta totalmente preenchida ocorre quando todos os tipos de sub-listas são igualmente populares. Nesse caso, economizo 1 bit para cada 3 cabeçalhos de sub-listas; portanto, o tamanho da lista é 2 * 781250 + 7 * 1000000 - 781250/3 = 8302083,3 bits. Arredondar até um limite de palavras de 32 bits, 8302112 bits ou 1037764 bytes.
1M menos os 2k para o estado TCP / IP e os buffers são 1022 * 1024 = 1046528 bytes, deixando-me 8764 bytes para brincar.
Mas e o processo de alteração do mapeamento do cabeçalho da sublist? No mapa de memória abaixo, "Z" é sobrecarga aleatória, "=" é espaço livre, "X" é a lista compacta.
Comece a ler no "X" mais à esquerda e comece a escrever no "=" mais à esquerda e trabalhe à direita. Quando terminar, a lista compacta será um pouco menor e estará no final errado da memória:
Então, eu vou precisar desviar para a direita:
No processo de alteração do mapeamento de cabeçalho, até 1/3 dos cabeçalhos da sublist serão alterados de 1 para 2 bits. Na pior das hipóteses, todos estarão no topo da lista, portanto, precisarei de pelo menos 781250/3 bits de armazenamento gratuito antes de iniciar, o que me leva de volta aos requisitos de memória da versão anterior da lista compacta: (
Para contornar isso, dividirei as sublistas 781250 em 10 grupos de sub-listas de 78125 sublistas cada. Cada grupo possui seu próprio mapeamento de cabeçalho de sublist independente. Usando as letras A a J para os grupos:
Cada grupo de sub-listas diminui ou permanece o mesmo durante uma alteração no mapeamento do cabeçalho da sub-lista:
O pior caso de expansão temporária de um grupo de sub-listas durante uma alteração de mapeamento é 78125/3 = 26042 bits, abaixo de 4k. Se eu permitir 4k mais os 1037764 bytes para uma lista compacta totalmente preenchida, isso me deixa 8764 - 4096 = 4668 bytes para os "Z" s no mapa de memória.
Isso deve ser suficiente para as 10 tabelas de mapeamento de cabeçalho da sub-lista, as 30 contagens de ocorrência do cabeçalho da sub-lista e os outros poucos contadores, ponteiros e pequenos buffers que eu precisarei e o espaço que usei sem perceber, como espaço de pilha para endereços de retorno de chamada de função e variáveis locais.
Parte 3, quanto tempo levaria para ser executado?
Com uma lista compacta vazia, o cabeçalho da lista de 1 bit será usado para uma sublist vazia e o tamanho inicial da lista será 781250 bits. Na pior das hipóteses, a lista aumenta 8 bits para cada número adicionado; portanto, são necessários 32 + 8 = 40 bits de espaço livre para que cada um dos números de 32 bits seja colocado no topo do buffer da lista e, em seguida, classificado e mesclado. Na pior das hipóteses, alterar o mapeamento do cabeçalho da sublist resulta em um uso de espaço de 2 * 781250 + 7 * entradas - 781250/3 bits.
Com uma política de alterar o mapeamento de cabeçalho da sub-lista após cada quinto mesclado, quando houver pelo menos 800000 números na lista, uma execução de pior caso envolveria um total de cerca de 30 milhões de atividades compactas de leitura e gravação de lista.
Fonte:
http://nick.cleaton.net/ramsortsol.html
fonte
3 * 3 * 3 = 27 < 32
. Você os combinacombined_subheader = subheader1 + 3 * subheader2 + 9 * subheader3
.A resposta de Gilmanov está muito errada em suas suposições. Começa a especular com base em uma medida inútil de um milhão de números consecutivos . Isso significa que não há lacunas. Essas lacunas aleatórias, por menores que sejam, realmente a tornam uma péssima idéia.
Tente você mesmo. Obtenha 1 milhão de números inteiros aleatórios de 27 bits, classifique-os e comprima com 7-Zip , xz, qualquer que seja o LZMA que você deseja. O resultado é superior a 1,5 MB. A premissa no topo é a compactação de números seqüenciais. Até a codificação delta é superior a 1,1 MB . E não importa, isso está usando mais de 100 MB de RAM para compactação. Assim, mesmo os números inteiros compactados não se encaixam no problema e não importam o uso da RAM em tempo de execução .
Me entristece como as pessoas apenas votam em gráficos e racionalização bonitos.
Agora comprima ints.bin com LZMA ...
fonte
Eu acho que uma maneira de pensar sobre isso é do ponto de vista combinatório: quantas combinações possíveis de ordenação de números ordenados existem? Se atribuirmos à combinação 0,0,0, ...., 0 o código 0 e 0,0,0, ..., 1 o código 1, e 99999999, 99999999, ... 99999999, o código N, o que é N? Em outras palavras, qual é o tamanho do espaço de resultado?
Bem, uma maneira de pensar sobre isso é perceber que essa é uma desvantagem do problema de encontrar o número de caminhos monotônicos em uma grade N x M, em que N = 1.000.000 e M = 100.000.000. Em outras palavras, se você tiver uma grade com 1.000.000 de largura e 100.000.000 de altura, quantos caminhos mais curtos da parte inferior esquerda para a parte superior direita existem? É claro que os caminhos mais curtos exigem que você apenas se mova para a direita ou para cima (se você se movesse para baixo ou para a esquerda, estaria desfazendo o progresso realizado anteriormente). Para ver como isso é uma violação do nosso problema de classificação de números, observe o seguinte:
Você pode imaginar qualquer perna horizontal em nosso caminho como um número em nosso pedido, em que a localização Y da perna representa o valor.
Portanto, se o caminho simplesmente se move para a direita até o final, então pula para o topo, isso é equivalente à ordem de 0,0,0, ..., 0. se, em vez disso, começar pulando todo o caminho para o topo e depois se mover para a direita 1.000.000 vezes, isso é equivalente a 99999999,99999999, ..., 99999999. Um caminho em que ele se move uma vez, depois para cima uma vez e depois para a direita. , então, uma vez, etc. até o fim (então necessariamente salta todo o caminho até o topo), é equivalente a 0,1,2,3, ..., 999999.
Felizmente para nós, esse problema já foi resolvido, uma grade com esses caminhos (N + M) Escolha (M):
(1.000.000 + 100.000.000) Escolha (100.000.000) ~ = 2,27 * 10 ^ 2436455
N é igual a 2,27 * 10 ^ 2436455 e, portanto, o código 0 representa 0,0,0, ..., 0 e o código 2,27 * 10 ^ 2436455 e alguma alteração representa 99999999,99999999, ..., 99999999.
Para armazenar todos os números de 0 a 2,27 * 10 ^ 2436455, você precisa de lg2 (2,27 * 10 ^ 2436455) = 8,0937 * 10 ^ 6 bits.
1 megabyte = 8388608 bits> 8093700 bits
Parece que pelo menos temos espaço suficiente para armazenar o resultado! Agora, é claro que o bit interessante está fazendo a classificação à medida que os números entram. Não temos certeza da melhor abordagem para isso, temos 294908 bits restantes. Eu imagino que uma técnica interessante seria, em cada ponto, assumir que esse é o pedido inteiro, localizando o código para esse pedido e, em seguida, à medida que você recebe um novo número voltando e atualizando o código anterior. Onda de mão Onda de mão
fonte
Minhas sugestões aqui devem muito à solução de Dan
Primeiro, suponho que a solução deve lidar com todas as listas de entradas possíveis. Eu acho que as respostas populares não fazem essa suposição (que IMO é um grande erro).
Sabe-se que nenhuma forma de compactação sem perdas reduzirá o tamanho de todas as entradas.
Todas as respostas populares supõem que eles serão capazes de aplicar a compactação com eficácia suficiente para permitir espaço extra. De fato, um pedaço de espaço extra é grande o suficiente para reter parte da lista parcialmente concluída de forma não compactada e permitir que eles executem suas operações de classificação. Esta é apenas uma suposição ruim.
Para uma solução desse tipo, qualquer pessoa com conhecimento de como realiza sua compactação poderá projetar alguns dados de entrada que não compactam bem para esse esquema, e a "solução" provavelmente será interrompida devido à falta de espaço.
Em vez disso, adoto uma abordagem matemática. Nossas saídas possíveis são todas as listas de comprimento LEN consistindo de elementos no intervalo 0..MAX. Aqui, o LEN é 1.000.000 e nosso MAX é 100.000.000.
Para LEN e MAX arbitrários, a quantidade de bits necessária para codificar esse estado é:
Log2 (MAX Multichoose LEN)
Portanto, para nossos números, depois de concluir a recepção e a classificação, precisaremos de pelo menos Log2 (100.000.000 MC 1.000.000) bits para armazenar nosso resultado de uma maneira que possa distinguir exclusivamente todas as saídas possíveis.
Isso é ~ = 988kb . Então, na verdade, temos espaço suficiente para manter nosso resultado. Deste ponto de vista, é possível.
[Deletadas inúteis excluídas agora que existem melhores exemplos ...]
A melhor resposta está aqui .
Outra boa resposta está aqui e basicamente usa a classificação por inserção como a função para expandir a lista por um elemento (armazena em buffer alguns elementos e pré-classificações, para permitir a inserção de mais de um por vez, economizando um pouco de tempo). também usa uma boa codificação de estado compacta, baldes de sete bits deltas
fonte
Suponha que esta tarefa seja possível. Imediatamente antes da saída, haverá uma representação na memória dos milhões de números classificados. Quantas representações diferentes existem? Como pode haver números repetidos, não podemos usar nCr (escolha), mas há uma operação chamada multichoose que funciona em vários conjuntos .
Então, teoricamente, pode ser possível, se você conseguir uma representação sã (suficiente) da lista ordenada de números. Por exemplo, uma representação insana pode exigir uma tabela de pesquisa de 10 MB ou milhares de linhas de código.
No entanto, se "1M RAM" significa um milhão de bytes, então claramente não há espaço suficiente. O fato de que 5% a mais de memória torna teoricamente possível sugere para mim que a representação terá que ser MUITO eficiente e provavelmente não sã.
fonte
(Minha resposta original estava errada, desculpe pela matemática ruim, veja abaixo o intervalo.)
Que tal agora?
Os primeiros 27 bits armazenam o número mais baixo que você viu, depois a diferença para o próximo número, codificado da seguinte forma: 5 bits para armazenar o número de bits usados no armazenamento da diferença e, em seguida, a diferença. Use 00000 para indicar que você viu esse número novamente.
Isso funciona porque, à medida que mais números são inseridos, a diferença média entre os números diminui; portanto, você usa menos bits para armazenar a diferença à medida que adiciona mais números. Eu acredito que isso é chamado de lista delta.
O pior caso em que consigo pensar é em todos os números espaçados igualmente (por 100), por exemplo, supondo que 0 seja o primeiro número:
Reddit para o resgate!
Se tudo o que você precisava fazer fosse classificá-los, esse problema seria fácil. São necessários 122k (1 milhão de bits) para armazenar quais números você viu (0º bit se 0 foi visto, 2300º bit se 2300 foram vistos etc.)
Você lê os números, armazena-os no campo de bits e, em seguida, desloca os bits enquanto mantém uma contagem.
MAS, você tem que lembrar quantos você viu. Fui inspirado pela resposta da sublista acima para criar esse esquema:
Em vez de usar um bit, use 2 ou 27 bits:
Eu acho que isso funciona: se não houver duplicatas, você tem uma lista de 244k. Na pior das hipóteses, você vê cada número duas vezes (se você vê um número três vezes, reduz o resto da lista para você), isso significa que você viu 50.000 mais de uma vez e 950.000 itens 0 ou 1 vezes.
50.000 * 27 + 950.000 * 2 = 396,7k.
Você pode fazer melhorias adicionais se usar a seguinte codificação:
0 significa que você não viu o número 10 significa que você o viu uma vez 11 é como você continua a contar
O que resultará, em média, em 280,7k de armazenamento.
EDIT: minha matemática de domingo de manhã estava errada.
O pior caso é que vemos 500.000 números duas vezes, então a matemática se torna:
500.000 * 27 + 500.000 * 2 = 1,77M
A codificação alternativa resulta em um armazenamento médio de
500.000 * 27 + 500.000 = 1,70M
: (
fonte
Existe uma solução para esse problema em todas as entradas possíveis. Enganação.
fonte
Eu tentaria uma árvore Radix . Se você pudesse armazenar os dados em uma árvore, poderia fazer uma travessia em ordem para transmitir os dados.
Não sei se você poderia ajustar isso em 1 MB, mas acho que vale a pena tentar.
fonte
Que tipo de computador você está usando? Pode não ter outro armazenamento local "normal", mas possui RAM de vídeo, por exemplo? 1 megapixel x 32 bits por pixel (por exemplo) está bem próximo do tamanho de entrada de dados necessário.
(Em grande parte, pergunto em memória o antigo PC Acorn RISC , que poderia "emprestar" a VRAM para expandir a RAM do sistema disponível, se você escolher um modo de tela de baixa resolução ou baixa profundidade de cor!). Isso foi bastante útil em uma máquina com apenas alguns MB de RAM normal.
fonte
Uma representação em árvore de base seria próxima de lidar com esse problema, pois a árvore de base utiliza a "compressão de prefixo". Mas é difícil conceber uma representação em árvore de raiz que possa representar um único nó em um byte - dois é provavelmente o limite.
Mas, independentemente de como os dados são representados, uma vez classificados, eles podem ser armazenados na forma de prefixo compactado, onde os números 10, 11 e 12 seriam representados por, digamos 001b, 001b, 001b, indicando um incremento de 1 do número anterior. Talvez, então, 10101b represente um incremento de 5, 1101001b um incremento de 9, etc.
fonte
Existem 10 ^ 6 valores em um intervalo de 10 ^ 8, portanto, há um valor por cem pontos de código em média. Armazene a distância do enésimo ponto até o (N + 1) th. Os valores duplicados têm um pulo de 0. Isso significa que o pulo precisa de uma média de menos de 7 bits para armazenar, para que um milhão deles se encaixe nos nossos 8 milhões de bits de armazenamento.
Esses pulos precisam ser codificados em um fluxo de bits, digamos pela codificação de Huffman. A inserção é iterativa no fluxo de bits e reescrita após o novo valor. Saída iterando e gravando os valores implícitos. Por praticidade, ele provavelmente quer ser feito como, digamos, 10 ^ 4 listas que cobrem 10 ^ 4 pontos de código (e uma média de 100 valores) cada.
Uma boa árvore de Huffman para dados aleatórios pode ser construída a priori assumindo uma distribuição de Poisson (média = variância = 100) no comprimento dos saltos, mas estatísticas reais podem ser mantidas na entrada e usadas para gerar uma árvore ideal para lidar com elas. casos patológicos.
fonte
Outra maneira de trapacear: você poderia usar armazenamento não local (em rede) (sua pergunta não impede isso) e chamar um serviço em rede que poderia usar uma combinação direta baseada em disco (ou apenas RAM suficiente para classificar na memória, desde que você só precisa aceitar números de 1 milhão), sem precisar das soluções (reconhecidamente extremamente engenhosas) já fornecidas.
Isso pode ser trapaça, mas não está claro se você está procurando uma solução para um problema do mundo real ou um quebra-cabeça que convida à flexão das regras ... se for o caso, uma trapaça simples pode obter melhores resultados do que um complexo mas a solução "genuína" (que, como outros já apontaram, só pode funcionar com entradas compressíveis).
fonte
Penso que a solução é combinar técnicas de codificação de vídeo, nomeadamente a transformação discreta de cosseno. No vídeo digital, em vez de gravar a alteração do brilho ou da cor do vídeo como valores regulares, como 110 112 115 116, cada um é subtraído do último (semelhante à codificação da duração da execução). 110 112 115 116 passa a 110 2 3 1. Os valores, 2 3 1 requerem menos bits que os originais.
Então, digamos que criamos uma lista dos valores de entrada conforme eles chegam no soquete. Estamos armazenando em cada elemento, não o valor, mas o deslocamento do elemento anterior. Como ordenamos à medida que avançamos, as compensações só serão positivas. Mas o deslocamento pode ter 8 dígitos decimais de largura, o que cabe em 3 bytes. Cada elemento não pode ter 3 bytes, por isso precisamos compactá-los. Poderíamos usar o bit superior de cada byte como um "bit contínuo", indicando que o próximo byte faz parte do número e os 7 bits inferiores de cada byte precisam ser combinados. zero é válido para duplicatas.
À medida que a lista é preenchida, os números devem se aproximar, o que significa que, em média, apenas 1 byte é usado para determinar a distância até o próximo valor. 7 bits de valor e 1 bit de deslocamento, se for conveniente, mas pode haver um ponto ideal que requer menos de 8 bits para um valor "continue".
Enfim, eu fiz um experimento. Eu uso um gerador de números aleatórios e posso ajustar um milhão de números decimais de 8 dígitos classificados em cerca de 1279000 bytes. O espaço médio entre cada número é consistentemente 99 ...
fonte
Poderíamos jogar com a pilha de rede para enviar os números em ordem classificada antes de termos todos os números. Se você enviar 1 milhão de dados, o TCP / IP os dividirá em pacotes de 1500 bytes e os transmitirá para o destino. Cada pacote receberá um número de sequência.
Podemos fazer isso manualmente. Pouco antes de preenchermos nossa RAM, podemos classificar o que temos e enviar a lista para o nosso alvo, mas deixar buracos em nossa sequência em torno de cada número. Em seguida, processe o segundo 1/2 dos números da mesma maneira, usando esses orifícios na sequência.
A pilha de rede na extremidade remota reunirá o fluxo de dados resultante em ordem de sequência antes de entregá-lo ao aplicativo.
Está usando a rede para executar uma classificação de mesclagem. Este é um hack total, mas fui inspirado pelo outro hack de rede listado anteriormente.
fonte
Google 's (mau) abordagem, a partir de fios HN. Armazene contagens no estilo RLE.
O problema deles parece não cobrir duplicatas, mas digamos que eles usem "0: 1" para duplicatas.
Grande problema nº 1: inserções para números inteiros de 1 milhão levariam idades .
Grande problema nº 2: como todas as soluções simples de codificação delta, algumas distribuições não podem ser abordadas dessa maneira. Por exemplo, 1m números inteiros com distâncias de 0:99 (por exemplo, +99 cada). Agora pense o mesmo, mas com distância aleatória no intervalo de 0:99 . (Nota: 99999999/1000000 = 99,99)
A abordagem do Google é indigna (lenta) e incorreta. Mas em defesa deles, o problema deles poderia ter sido um pouco diferente.
fonte
Para representar a matriz classificada, basta armazenar o primeiro elemento e a diferença entre os elementos adjacentes. Dessa forma, estamos preocupados em codificar 10 ^ 6 elementos que podem somar no máximo 10 ^ 8. Vamos chamar essa D . Para codificar os elementos de D, pode-se usar um código de Huffman . O dicionário para o código Huffman pode ser criado em movimento e a matriz é atualizada sempre que um novo item é inserido na matriz classificada (classificação por inserção). Observe que quando o dicionário muda devido a um novo item, toda a matriz deve ser atualizada para corresponder à nova codificação.
O número médio de bits para codificar cada elemento de D é maximizado se tivermos um número igual de cada elemento único. Digamos que os elementos d1 , d2 , ..., dN em D apareçam F vezes. Nesse caso (no pior dos casos, temos 0 e 10 ^ 8 na sequência de entrada), temos
soma (1 <= i <= N ) F . di = 10 ^ 8
Onde
soma (1 <= i <= N ) F = 10 ^ 6, ou F = 10 ^ 6 / N e a frequência normalizada será p = F / 10 ^ = 1 / N
O número médio de bits será -log2 (1 / P ) = log2 ( N ). Nestas circunstâncias, devemos encontrar um caso que maximiza N . Isso acontece se tivermos números consecutivos para di a partir de 0, ou, di = i -1, portanto,
10 ^ 8 = soma (1 <= i <= N ) F . di = soma (1 <= i <= N ) (10 ^ 6 / N ) (i-1) = (10 ^ 6 / N ) N ( N -1) / 2
ie
N <= 201. E, neste caso, o número médio de bits é log2 (201) = 7,6511, o que significa que precisaremos de cerca de 1 byte por elemento de entrada para salvar a matriz classificada. Observe que isso não significa que D em geral não possa ter mais de 201 elementos. Apenas semeia que, se os elementos de D são distribuídos uniformemente, ele não pode ter mais de 201 valores únicos.
fonte
Eu exploraria o comportamento de retransmissão do TCP.
Isso pressupõe algum tipo de benefício de baldes ou passes múltiplos.
Provavelmente, classificando os lotes / baldes e mesclando-os. -> árvores de raiz
Use esta técnica para aceitar e classificar os primeiros 80% e depois ler os últimos 20%, verifique se os últimos 20% não contêm números que aterrissariam nos primeiros 20% dos números mais baixos. Em seguida, envie os 20% dos números mais baixos, remova da memória, aceite os 20% restantes dos novos números e faça a mesclagem. **
fonte
Aqui está uma solução generalizada para esse tipo de problema:
Procedimento geral
A abordagem adotada é a seguinte. O algoritmo opera em um único buffer de palavras de 32 bits. Ele executa o seguinte procedimento em um loop:
Começamos com um buffer preenchido com dados compactados da última iteração. O buffer fica assim
|compressed sorted|empty|
Calcule a quantidade máxima de números que podem ser armazenados nesse buffer, compactados e não compactados. Divida o buffer nessas duas seções, começando com o espaço para dados compactados e terminando com os dados não compactados. O buffer parece
|compressed sorted|empty|empty|
Preencha a seção não compactada com os números a serem classificados. O buffer parece
|compressed sorted|empty|uncompressed unsorted|
Classifique os novos números com uma classificação no local. O buffer parece
|compressed sorted|empty|uncompressed sorted|
Alinhe com o botão direito qualquer dado já compactado da iteração anterior na seção compactada. Neste ponto, o buffer é particionado
|empty|compressed sorted|uncompressed sorted|
Execute uma descompressão-recompressão de streaming na seção compactada, mesclando os dados classificados na seção não compactada. A seção compactada antiga é consumida à medida que a nova seção compactada cresce. O buffer parece
|compressed sorted|empty|
Este procedimento é realizado até que todos os números tenham sido classificados.
Compressão
Obviamente, esse algoritmo só funciona quando é possível calcular o tamanho final compactado do novo buffer de classificação antes de saber o que realmente será compactado. Além disso, o algoritmo de compactação precisa ser bom o suficiente para resolver o problema real.
A abordagem usada usa três etapas. Primeiro, o algoritmo sempre armazenará sequências classificadas; portanto, podemos armazenar apenas as diferenças entre entradas consecutivas. Cada diferença está no intervalo [0, 99999999].
Essas diferenças são então codificadas como um fluxo de bits unário. Um 1 nesse fluxo significa "Adicionar 1 ao acumulador, A 0 significa" Emitir o acumulador como uma entrada e redefinir ". Portanto, a diferença N será representada por N 1 e um 0.
A soma de todas as diferenças se aproximará do valor máximo suportado pelo algoritmo, e a contagem de todas as diferenças se aproximará da quantidade de valores inseridos no algoritmo. Isso significa que esperamos que o fluxo, no final, contenha o valor máximo 1 e conte 0. Isso nos permite calcular a probabilidade esperada de 0 e 1 no fluxo. Ou seja, a probabilidade de um 0 é
count/(count+maxval)
e a probabilidade de um 1 émaxval/(count+maxval)
.Usamos essas probabilidades para definir um modelo de codificação aritmética sobre esse fluxo de bits. Esse código aritmético codifica exatamente essas quantidades de 1 e 0 no espaço ideal. Podemos calcular o espaço usado por este modelo para qualquer bitstream intermediário como:
bits = encoded * log2(1 + amount / maxval) + maxval * log2(1 + maxval / amount)
. Para calcular o espaço total necessário para o algoritmo, definaencoded
igual à quantidade.Para não exigir uma quantidade ridícula de iterações, uma pequena sobrecarga pode ser adicionada ao buffer. Isso garantirá que o algoritmo opere pelo menos na quantidade de números que se encaixa nessa sobrecarga, já que, de longe, o maior custo de tempo do algoritmo é a compressão e descompressão da codificação aritmética a cada ciclo.
Além disso, é necessária alguma sobrecarga para armazenar dados da contabilidade e lidar com pequenas imprecisões na aproximação de ponto fixo do algoritmo de codificação aritmética, mas no total o algoritmo é capaz de caber em 1MiB de espaço, mesmo com um buffer extra que pode conter 8000 números, para um total de 1043916 bytes de espaço.
Optimalidade
Fora a redução da sobrecarga (pequena) do algoritmo, deveria ser teoricamente impossível obter um resultado menor. Para conter apenas a entropia do resultado final, 1011717 bytes seriam necessários. Se subtrairmos o buffer extra adicionado por eficiência, esse algoritmo utilizou 1011916 bytes para armazenar o resultado final + sobrecarga.
fonte
Se o fluxo de entrada pudesse ser recebido algumas vezes, isso seria muito mais fácil (nenhuma informação sobre isso, ideia e problema de desempenho de tempo).
Então, poderíamos contar os valores decimais. Com valores contados, seria fácil fazer o fluxo de saída. Comprima contando os valores. Depende do que estaria no fluxo de entrada.
fonte
Se o fluxo de entrada pudesse ser recebido algumas vezes, isso seria muito mais fácil (sem informações sobre isso, ideia e problema de desempenho de tempo). Então, poderíamos contar os valores decimais. Com valores contados, seria fácil fazer o fluxo de saída. Comprima contando os valores. Depende do que estaria no fluxo de entrada.
fonte
A classificação é um problema secundário aqui. Como já foi dito, apenas armazenar os números inteiros é difícil e não pode funcionar em todas as entradas , pois seriam necessários 27 bits por número.
Minha opinião sobre isso é: armazene apenas as diferenças entre os números inteiros consecutivos (classificados), pois eles provavelmente serão pequenos. Em seguida, use um esquema de compactação, por exemplo, com 2 bits adicionais por número de entrada, para codificar em quantos bits o número está armazenado. Algo como:
Deveria ser possível armazenar um número razoável de listas de entrada possíveis dentro da restrição de memória fornecida. A matemática de como escolher o esquema de compactação para que ele funcione com o número máximo de entradas está além de mim.
Espero que você possa explorar o conhecimento específico de domínio de sua entrada para encontrar um esquema de compactação de número inteiro bom o suficiente base nisso.
Ah, e então você faz uma classificação de inserção nessa lista classificada à medida que recebe dados.
fonte
Agora, visando uma solução real, cobrindo todos os casos possíveis de entrada na faixa de 8 dígitos, com apenas 1 MB de RAM. NOTA: trabalho em andamento, amanhã continuará. Usando a codificação aritmética dos deltas das entradas ordenadas, o pior caso para as entradas ordenadas de 1 milhão custaria cerca de 7 bits por entrada (já que 99999999/1000000 é 99 e log2 (99) é quase 7 bits).
Mas você precisa de 1 milhão de inteiros classificados para chegar a 7 ou 8 bits! As séries mais curtas teriam deltas maiores, portanto mais bits por elemento.
Estou trabalhando para colocar o máximo possível e comprimir (quase) no local. O primeiro lote de quase 250K ints precisaria de cerca de 9 bits cada, na melhor das hipóteses. Portanto, o resultado levaria cerca de 275 KB. Repita com a memória livre restante algumas vezes. Em seguida, descompacte-mesclar-in-place-comprimir esses pedaços compactados. Isso é bastante difícil , mas possível. Eu acho que.
As listas mescladas se aproximavam cada vez mais do alvo de 7 bits por número inteiro. Mas não sei quantas iterações seriam necessárias do loop de mesclagem. Talvez 3.
Mas a imprecisão da implementação da codificação aritmética pode tornar isso impossível. Se esse problema for possível, seria extremamente apertado.
Quaisquer voluntários?
fonte
Você só precisa armazenar as diferenças entre os números em sequência e usar uma codificação para compactar esses números de sequência. Temos 2 ^ 23 bits. Vamos dividi-lo em pedaços de 6 bits e deixar o último bit indicar se o número se estende a outros 6 bits (5 bits mais o pedaço estendido).
Assim, 000010 é 1 e 000100 é 2. 000001100000 é 128. Agora, consideramos a pior conversão em representar diferenças na sequência de um número de até 10.000.000. Pode haver 10.000.000 / 2 ^ 5 diferenças maiores que 2 ^ 5, 10.000.000 / 2 ^ 10 diferenças maiores que 2 ^ 10 e 10.000.000 / 2 ^ 15 diferenças maiores que 2 ^ 15, etc.
Então, adicionamos quantos bits serão necessários para representar nossa sequência. Temos 1.000.000 * 6 + arredondamento (10.000.000 / 2 ^ 5) * 6 + arredondamento (10.000.000 / 2 ^ 10) * 6 + arredondamento (10.000.000 / 2 ^ 15) * 6 + arredondamento (10.000.000 / 2 ^ 20) * 4 = 7935479.
2 ^ 24 = 8388608. Como 8388608> 7935479, devemos ter facilmente memória suficiente. Provavelmente precisaremos de mais um pouco de memória para armazenar a soma de onde estão quando inserimos novos números. Depois, percorremos a sequência e descobrimos onde inserir nosso novo número, diminuímos a próxima diferença, se necessário, e mudamos tudo depois dela.
fonte
Se não soubermos nada sobre esses números, ficaremos limitados pelas seguintes restrições:
Se essas suposições persistirem, não há como executar sua tarefa, pois você precisará de pelo menos 26.575.425 bits de armazenamento (3.321.929 bytes).
O que você pode nos dizer sobre seus dados?
fonte
O truque é representar o estado dos algoritmos, que é um conjunto múltiplo inteiro, como um fluxo compactado de "contador de incremento" = "+" e "contador de saída" = "!" personagens. Por exemplo, o conjunto {0,3,3,4} seria representado como "! +++ !! +!", Seguido por qualquer número de caracteres "+". Para modificar o multi-conjunto, você transmite os caracteres, mantendo apenas uma quantidade constante descompactada por vez, e faz as alterações no local antes de transmiti-las novamente na forma compactada.
Detalhes
Sabemos que existem exatamente 10 ^ 6 números no conjunto final, portanto, existem no máximo 10 ^ 6 "!" personagens. Também sabemos que nosso intervalo tem tamanho 10 ^ 8, o que significa que existem no máximo 10 ^ 8 "+" caracteres. O número de maneiras pelas quais podemos organizar 10 ^ 6 "!" S entre 10 ^ 8 "+" s é
(10^8 + 10^6) choose 10^6
e, portanto, especificar um arranjo específico leva ~ 0,965 MiB `de dados. Isso vai ser um ajuste apertado.Podemos tratar cada personagem como independente, sem exceder nossa cota. Existem exatamente 100 vezes mais caracteres "+" que "!" caracteres, o que simplifica as chances de 100: 1 de cada caractere ser um "+" se esquecermos que eles são dependentes. As probabilidades de 100: 101 correspondem a ~ 0,08 bits por caractere , para um total quase idêntico de ~ 0,965 MiB (ignorar a dependência tem um custo de apenas ~ 12 bits neste caso!).
A técnica mais simples para armazenar caracteres independentes com probabilidade anterior conhecida é a codificação de Huffman . Observe que precisamos de uma árvore impraticávelmente grande (uma árvore huffman para blocos de 10 caracteres tem um custo médio por bloco de cerca de 2,4 bits, para um total de ~ 2,9 Mib. Uma árvore huffman para blocos de 20 caracteres tem um custo médio por bloco de cerca de 3 bits, que é um total de ~ 1,8 MiB. Provavelmente precisaremos de um bloco de tamanho da ordem de cem, implicando mais nós em nossa árvore do que todo o equipamento de computador que já existiu pode armazenar. ) No entanto, a ROM é tecnicamente "gratuita" de acordo com o problema e as soluções práticas que tiram vantagem da regularidade na árvore terão a mesma aparência.
Pseudo-código
fonte
Temos 1 MB - 3 KB de RAM = 2 ^ 23 - 3 * 2 ^ 13 bits = 8388608 - 24576 = 8364032 bits disponíveis.
Recebemos 10 ^ 6 números em um intervalo de 10 ^ 8. Isso dá uma diferença média de ~ 100 <2 ^ 7 = 128
Vamos primeiro considerar o problema mais simples de números com espaçamento uniforme quando todas as lacunas são <128. Isso é fácil. Apenas armazene o primeiro número e as lacunas de 7 bits:
(27 bits) + 10 ^ 6 números de gap de 7 bits = 7000027 bits necessários
Observe que os números repetidos têm intervalos de 0.
Mas e se tivermos lacunas maiores que 127?
OK, digamos que um tamanho de intervalo <127 seja representado diretamente, mas um tamanho de intervalo 127 é seguido por uma codificação contínua de 8 bits para o comprimento real do intervalo:
etc.
Observe que essa representação numérica descreve seu próprio comprimento, para que possamos saber quando o próximo número do intervalo será iniciado.
Com apenas pequenas lacunas <127, isso ainda requer 7000027 bits.
Pode haver até (10 ^ 8) / (2 ^ 7) = 781250 número de gap de 23 bits, exigindo 16 * 781.250 extra = 12.500.000 bits, o que é demais. Precisamos de uma representação mais compacta e lentamente crescente das lacunas.
O tamanho médio do intervalo é 100, portanto, se os reordenarmos como [100, 99, 101, 98, 102, ..., 2, 198, 1, 199, 0, 200, 201, 202, ...] e indexar isso com uma base binária de Fibonacci densa e sem pares de zeros (por exemplo, 11011 = 8 + 5 + 2 + 1 = 16) com números delimitados por '00', acho que podemos manter a representação do intervalo curta o suficiente, mas ela precisa mais análise.
fonte
Ao receber o fluxo, siga estas etapas.
1º definir um tamanho razoável de pedaço
Ideia do pseudo-código:
Continue as 4 primeiras etapas ao receber o fluxo. A etapa final seria falhar se você exceder a memória ou começar a produzir o resultado depois que todos os dados forem coletados, começando a classificar os intervalos e cuspir os resultados em ordem e descompactar os que precisam ser descompactados e classificá-los quando você chega a eles.
fonte