Gere um número inteiro que não esteja entre quatro bilhões de dados

691

Recebi esta pergunta da entrevista:

Dado um arquivo de entrada com quatro bilhões de números inteiros, forneça um algoritmo para gerar um número inteiro que não esteja contido no arquivo. Suponha que você tenha 1 GB de memória. Siga o que você faria se tivesse apenas 10 MB de memória.

Minha análise:

O tamanho do arquivo é 4 × 10 9 × 4 bytes = 16 GB.

Podemos fazer uma classificação externa, informando o intervalo dos números inteiros.

Minha pergunta é qual é a melhor maneira de detectar o número inteiro ausente nos grandes conjuntos inteiros classificados?

Meu entendimento (depois de ler todas as respostas):

Supondo que estamos falando de números inteiros de 32 bits, existem 2 32 = 4 * 10 9 inteiros distintos.

Caso 1: temos 1 GB = 1 * 10 9 * 8 bits = 8 bilhões de bits de memória.

Solução:

Se usarmos um bit representando um número inteiro distinto, é suficiente. nós não precisamos de classificação.

Implementação:

int radix = 8;
byte[] bitfield = new byte[0xffffffff/radix];
void F() throws FileNotFoundException{
    Scanner in = new Scanner(new FileReader("a.txt"));
    while(in.hasNextInt()){
        int n = in.nextInt();
        bitfield[n/radix] |= (1 << (n%radix));
    }

    for(int i = 0; i< bitfield.lenght; i++){
        for(int j =0; j<radix; j++){
            if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j);
        }
    }
}

Caso 2: 10 MB de memória = 10 * 10 6 * 8 bits = 80 milhões de bits

Solução:

Para todos os possíveis prefixos de 16 bits, existem 2 16 números inteiros = 65536, precisamos de 2 16 * 4 * 8 = 2 milhões de bits. Precisamos construir 65536 baldes. Para cada bloco, precisamos de 4 bytes com todas as possibilidades, porque o pior caso é que todos os 4 bilhões de números inteiros pertencem ao mesmo bloco.

  1. Crie o contador de cada balde através da primeira passagem pelo arquivo.
  2. Digitalize os baldes, encontre o primeiro com menos de 65536 acertos.
  3. Crie novos buckets cujos altos prefixos de 16 bits são encontrados na etapa 2 até a segunda passagem do arquivo
  4. Examine os baldes construídos na etapa 3, encontre o primeiro balde que não tem sucesso.

O código é muito semelhante ao acima.

Conclusão: diminuímos a memória através do aumento da passagem de arquivos.


Um esclarecimento para quem chega atrasado: a pergunta, como feita, não diz que há exatamente um número inteiro que não está contido no arquivo - pelo menos não é assim que a maioria das pessoas o interpreta. Muitos comentários no segmento de comentários são sobre essa variação da tarefa, no entanto. Infelizmente, o comentário que o introduziu no tópico foi posteriormente excluído por seu autor, agora parece que as respostas órfãs a ele apenas entendiam tudo errado. É muito confuso, desculpe.

SecureFish
fonte
32
@trashgod, errado. Para 4294967295 números inteiros únicos, você terá 1 número inteiro restante. Para encontrá-lo, você deve somar todos os números inteiros e subtraí-lo da soma pré-calculada de todos os números possíveis.
Nakilon
58
Esta é a segunda "pérola" de "Programming Pearls", e eu sugiro que você leia toda a discussão no livro. Veja books.google.com/…
Alok Singhal em
8
@ Richard um int de 64 bits seria mais do que suficiente.
cftarnas
79
int getMissingNumber(File inputFile) { return 4; }( referência )
johnny
14
Não importa que você não possa armazenar a soma de todos os números inteiros de 1 a 2 ^ 32, porque o tipo inteiro em idiomas como C / C ++ SEMPRE preserva propriedades como associatividade e comunicatividade. O que isto significa é que, embora a soma não seja a resposta certa, se você calcular o esperado com estouro, a soma real com estouro e subtrair, o resultado ainda estará correto (desde que ele não esteja cheio).
thedayturns

Respostas:

530

Supondo que "número inteiro" signifique 32 bits : 10 MB de espaço é mais que suficiente para você contar quantos números existem no arquivo de entrada com um prefixo de 16 bits, para todos os prefixos de 16 bits possíveis em uma passagem pelo Arquivo de entrada. Pelo menos um dos baldes será atingido menos de 2 16 vezes. Faça uma segunda passagem para descobrir qual dos números possíveis nesse intervalo já está sendo usado.

Se isso significa mais do que 32 bits, mas ainda de tamanho limitado : faça o seguinte, ignorando todos os números de entrada que estiverem fora do intervalo de 32 bits (assinado ou não; sua escolha).

Se "número inteiro" significa número inteiro matemático : leia a entrada uma vez e acompanhe o maior número de comprimento do número mais longo que você já viu. Quando terminar, imprima o máximo mais um número aleatório com mais um dígito. (Um dos números no arquivo pode ser um bignum que leva mais de 10 MB para representar exatamente, mas se a entrada for um arquivo, você poderá pelo menos representar o comprimento de qualquer coisa que se encaixe nele).

hmakholm deixou sobre Monica
fonte
24
Perfeito. Sua primeira resposta requer apenas 2 passagens pelo arquivo!
precisa saber é o seguinte
47
Um bignum de 10 MB? Isso é muito extremo.
Mark Ransom
12
@ Legate, apenas pule números em excesso e não faça nada sobre eles. Como você não produzirá um número excessivo de qualquer maneira, não há necessidade de acompanhar quais deles você já viu.
hmakholm deixou Monica em 23/08/11
12
A coisa boa da solução 1 é que você pode diminuir a memória aumentando as passagens.
Yousf 23/08/11
11
@ Barry: A pergunta acima não indica que há exatamente um número ausente. Também não diz que os números no arquivo não se repitam. (Na sequência da pergunta realmente pediu é provavelmente uma boa idéia em uma entrevista, direito ;-)?)
Christopher Creutzig
197

Algoritmos estatisticamente informados resolvem esse problema usando menos passagens do que abordagens determinísticas.

Se números inteiros muito grandes forem permitidos , será possível gerar um número que provavelmente será único no tempo O (1). Um número inteiro pseudo-aleatório de 128 bits, como um GUID , só colidirá com um dos quatro bilhões de inteiros existentes no conjunto em menos de um em cada 64 bilhões de bilhões de casos.

Se os números inteiros estiverem limitados a 32 bits , é possível gerar um número que provavelmente será único em uma única passagem usando muito menos que 10 MB. As probabilidades de um número inteiro pseudo-aleatório de 32 bits colidir com um dos 4 bilhões de inteiros existentes são de cerca de 93% (4e9 / 2 ^ 32). A probabilidade de que 1000 inteiros pseudo-aleatórios colidam é menor que uma em 12.000 bilhões de bilhões de bilhões (probabilidade de uma colisão ^ 1000). Portanto, se um programa mantém uma estrutura de dados contendo 1000 candidatos pseudo-aleatórios e itera pelos números inteiros conhecidos, eliminando correspondências dos candidatos, é quase certo que você encontrará pelo menos um número inteiro que não esteja no arquivo.

Ben Haley
fonte
32
Tenho certeza de que os números inteiros são limitados. Se não fossem, então mesmo um programador novato pensaria do algoritmo de "tomar uma passagem pelos dados para encontrar o número máximo, e adicionar 1 a ela"
Adrian Petrescu
12
Literalmente adivinhar uma saída aleatória, provavelmente, não vai chegar a muitos pontos em uma entrevista
Brian Gordon
6
@ Adrian, sua solução parece óbvia (e foi para mim, eu a usei em minha própria resposta), mas não é óbvia para todos. É um bom teste para ver se você consegue encontrar soluções óbvias ou se vai complicar demais tudo o que toca.
Mark Ransom
19
@ Brian: Eu acho que essa solução é criativa e prática. Eu, pelo menos, daria muitos elogios por esta resposta.
Richard H
6
ah, aqui está a linha entre engenheiros e cientistas. Ótima resposta Ben!
TrojanName
142

Uma discussão detalhada sobre esse problema foi discutida em Jon Bentley "Coluna 1. Quebrando a ostra" Pérolas de programação Addison-Wesley pp.3-10

Bentley discute várias abordagens, incluindo ordenação externa, Merge Sort usando vários arquivos externos etc., mas o melhor método Bentley sugere é um único algoritmo de passagem usando campos de bits , que ele ironicamente chama de "Maravilha Sort" :) Vindo para o problema, 4 bilhões números podem ser representados em:

4 billion bits = (4000000000 / 8) bytes = about 0.466 GB

O código para implementar o conjunto de bits é simples: (retirado da página de soluções )

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];

void set(int i) {        a[i>>SHIFT] |=  (1<<(i & MASK)); }
void clr(int i) {        a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int  test(int i){ return a[i>>SHIFT] &   (1<<(i & MASK)); }

O algoritmo de Bentley faz uma única passagem sobre o arquivo, setmarcando o bit apropriado na matriz e, em seguida, examina essa matriz usando a testmacro acima para encontrar o número ausente.

Se a memória disponível for menor que 0,466 GB, Bentley sugere um algoritmo k-pass, que divide a entrada em intervalos, dependendo da memória disponível. Para dar um exemplo muito simples, se apenas 1 byte (ou seja, memória para processar 8 números) estivesse disponível e o intervalo fosse de 0 a 31, dividimos isso em intervalos de 0 a 7, 8-15, 16-22 e assim por diante e lide com esse intervalo em cada uma das 32/8 = 4passagens.

HTH.

vinha
fonte
12
Eu não conheço o livro, mas não há razão para chamá-lo de "Wonder Sort", pois é apenas um bucketsort, com um contador de 1 bit.
flolo
3
Embora mais portátil, esse código será aniquilado por código escrito para utilizar instruções vetoriais suportadas por hardware . Eu acho que o gcc pode converter automaticamente código para usar operações vetoriais em alguns casos.
27611 Brian Brian
3
@ Brian Eu não acho que Jon Bentley estava permitindo essas coisas em seu livro sobre algoritmos.
David Heffernan
8
@BrianGordon, o tempo gasto no RAM será insignificante em comparação com o tempo gasto na leitura do arquivo. Esqueça de otimizá-lo.
24612 Ian
1
@BrianGordon: Ou você estava falando sobre o loop no final para encontrar o primeiro pedaço não definido? Sim, os vetores acelerarão isso, mas percorrerão o campo de bits com números inteiros de 64 bits, procurando por um que != -1ainda sature a largura de banda da memória em execução em um único núcleo (este é o SIMD dentro de um registro, SWAR, com bits como elementos). (Para projetos recentes da Intel / AMD). Você só precisa descobrir qual bit está desmarcado depois de encontrar o local de 64 bits que o contém. (E, para isso, você pode not / lzcnt.) É lógico que o loop em um teste de bit único pode não ser otimizado.
Peter Cordes
120

Como o problema não especifica que precisamos encontrar o menor número possível que não esteja no arquivo, podemos apenas gerar um número maior que o próprio arquivo de entrada. :)

Andris
fonte
6
A menos que o maior número no arquivo é max int, então você só vai estouro
KBusc
Qual seria o tamanho desse arquivo em um programa do mundo real que pode precisar gerar um novo número inteiro e anexá-lo ao arquivo "números inteiros usados" 100 vezes?
Michael
2
Eu estava pensando isso. Assumindo que intsão 32bits, apenas saída 2^64-1. Feito.
imallett
1
Se for um int por linha tr -d '\n' < nums.txt > new_num.txt:: D
Shon
56

Para a variante de 1 GB de RAM, você pode usar um vetor de bits. Você precisa alocar 4 bilhões de bits == 500 MB de matriz de bytes. Para cada número que você lê da entrada, defina o bit correspondente como '1'. Depois de terminar, repita os bits e encontre o primeiro que ainda é '0'. Seu índice é a resposta.

Itay Maman
fonte
4
O intervalo de números na entrada não está especificado. Como esse algoritmo funciona se a entrada consiste em todos os números pares entre 8 bilhões e 16 bilhões?
Mark Ransom
27
@ Mark, apenas ignore as entradas que estão fora da faixa 0..2 ^ 32. Você não produzirá nenhum deles, então não há necessidade de lembrar qual deles evitar.
hmakholm deixou Monica em 22/08/11
@ Marque o algoritmo que você usa para determinar como uma string de 32 bits é mapeada para um número real. O processo ainda é o mesmo. A única diferença é como você o imprime como um número real na tela.
precisa saber é o seguinte
4
Em vez de ficar repetindo-se que você pode usar bitSet.nextClearBit(0): download.oracle.com/javase/6/docs/api/java/util/...
starblue
3
Seria útil mencionar que, independentemente do intervalo dos números inteiros, é garantido que pelo menos um bit seja 0 no final da passagem. Isso se deve ao princípio do buraco de pombo.
Rafał Dowgird 23/08
46

Se forem números inteiros de 32 bits (provavelmente da escolha de ~ 4 bilhões de números próximos a 2 32 ), sua lista de 4 bilhões de números ocupará no máximo 93% dos números possíveis possíveis (4 * 10 9 / (2 32 ) ) Portanto, se você criar uma matriz de bits de 2 32 bits com cada bit inicializado em zero (que ocupará 2 29 bytes ~ 500 MB de RAM; lembre-se de um byte = 2 3 bits = 8 bits), leia a lista inteira e para cada int, defina o elemento da matriz de bits correspondente de 0 a 1; e depois leia sua matriz de bits e retorne o primeiro bit que ainda é 0.

No caso de você ter menos RAM (~ 10 MB), esta solução precisa ser ligeiramente modificada. 10 MB ~ 83886080 bits ainda são suficientes para fazer uma matriz de bits para todos os números entre 0 e 83886079. Portanto, você pode ler sua lista de entradas; e registre somente #s que estão entre 0 e 83886079 em sua matriz de bits. Se os números são distribuídos aleatoriamente; com probabilidade esmagadora (difere em 100% em cerca de 10 -2592069 ), você encontrará um int ausente. De fato, se você escolher apenas os números de 1 a 2048 (com apenas 256 bytes de RAM), ainda assim encontrará um número ausente em uma porcentagem esmagadora (99,999999999999999999999999999999999999999999999999999999999999995%).

Mas digamos que em vez de ter cerca de 4 bilhões de números; você tinha algo como 2 32 - 1 números e menos de 10 MB de RAM; portanto, qualquer pequena faixa de entradas tem apenas uma pequena possibilidade de não conter o número.

Se você tivesse a garantia de que cada int na lista fosse exclusivo, poderia somar os números e subtrair a soma com um # ausente na soma completa (½) (2 32 ) (2 32 - 1) = 9223372034707292160 para encontrar o int ausente . No entanto, se um int ocorrer duas vezes, esse método falhará.

No entanto, você sempre pode dividir e conquistar. Um método ingênuo seria ler a matriz e contar o número de números que estão na primeira metade (0 a 2 31 -1) e na segunda metade (2 31 , 2 32 ). Em seguida, escolha o intervalo com menos números e repita dividindo esse intervalo ao meio. (Diga se havia dois números a menos em (2 31 , 2 32 ), sua próxima pesquisa contaria os números no intervalo (2 31 , 3 * 2 30 -1), (3 * 2 30 , 2 32 ). repetindo até encontrar um intervalo com número zero e você tiver a sua resposta.Deve levar O (lg N) ~ 32 para ler o array.

Esse método foi ineficiente. Estamos usando apenas dois números inteiros em cada etapa (ou cerca de 8 bytes de RAM com um número inteiro de 4 bytes (32 bits)). Um método melhor seria dividir em sqrt (2 32 ) = 2 16 = 65536 posições, cada uma com 65536 números em uma posição. Cada compartimento requer 4 bytes para armazenar sua contagem, então você precisa de 2 18 bytes = 256 kB. Portanto, o compartimento 0 é (0 a 65535 = 2 16 -1), o compartimento 1 é (2 16 = 65536 a 2 * 2 16 -1 = 131071), o compartimento 2 é (2 * 2 16 = 131072 a 3 * 2 16 - 1 = 196607). Em python, você teria algo como:

import numpy as np
nums_in_bin = np.zeros(65536, dtype=np.uint32)
for N in four_billion_int_array:
    nums_in_bin[N // 65536] += 1
for bin_num, bin_count in enumerate(nums_in_bin):
    if bin_count < 65536:
        break # we have found an incomplete bin with missing ints (bin_num)

Leia a lista inteira de ~ 4 bilhões; e conte quantas polegadas caem em cada uma das 2 16 posições e encontre um incomplete_bin que não tenha todos os números 65536. Então você lê a lista inteira de 4 bilhões novamente; mas desta vez só observe quando números inteiros estão nesse intervalo; lançando um pouco quando você os encontra.

del nums_in_bin # allow gc to free old 256kB array
from bitarray import bitarray
my_bit_array = bitarray(65536) # 32 kB
my_bit_array.setall(0)
for N in four_billion_int_array:
    if N // 65536 == bin_num:
        my_bit_array[N % 65536] = 1
for i, bit in enumerate(my_bit_array):
    if not bit:
        print bin_num*65536 + i
        break
dr jimbob
fonte
3
Uma resposta tão impressionante. Isso realmente funcionaria; e tem resultados garantidos.
23611 Jonathan Dickinson
@ jimbob, e se houver apenas um número em uma lixeira e esse número único tiver 65535 duplicatas? Nesse caso, o compartimento ainda conta 65536, mas todos os números 65536 são iguais.
Alcott
@Alcott - Presumi que você tivesse 2 ^ 32-1 (ou menos) números, portanto, pelo princípio do pigeonhole, é garantido que você tenha uma lixeira com menos de 65536 contagens para verificar mais detalhes. Estamos tentando encontrar apenas um número inteiro ausente, nem todos. Se você tivesse 2 ^ 32 ou mais números, não poderá garantir um número inteiro ausente e não seria capaz de usar esse método (ou terá uma garantia desde o início de que existe um número inteiro ausente). Sua melhor aposta seria força bruta (por exemplo, leia a matriz 32 vezes; verificando os primeiros 65536 #s pela primeira vez; e parando assim que a resposta fosse encontrada).
dr jimbob
O inteligente método superior-16 / inferior-16 foi publicado anteriormente por Henning: stackoverflow.com/a/7153822/224132 . Eu amei a ideia de adicionar um conjunto único de números inteiros que faltam exatamente um membro.
Peter Cordes
3
@ PeterCordes - Sim, a solução de Henning é anterior à minha, mas acho que minha resposta ainda é útil (trabalhando várias coisas com mais detalhes). Dito isso, Jon Bentley, em seu livro Programming Pearls, sugeriu uma opção de várias passagens para esse problema (veja a resposta de Vine), muito antes da existência do stackoverflow (não que eu esteja afirmando que algum de nós roubou conscientemente de lá ou que Bentley foi o primeiro a analise esse problema - é uma solução bastante natural para se desenvolver). Duas passagens parecem mais naturais quando a limitação é que você não tem mais memória suficiente para uma solução de 1 passagem com uma matriz de bits gigante.
precisa saber é o seguinte
37

Por que torná-lo tão complicado? Você pede um número inteiro não presente no arquivo?

De acordo com as regras especificadas, a única coisa que você precisa armazenar é o maior número inteiro encontrado até agora no arquivo. Depois que o arquivo inteiro tiver sido lido, retorne um número 1 maior que isso.

Não há risco de atingir maxint ou algo assim, porque, de acordo com as regras, não há restrição ao tamanho do número inteiro ou ao número retornado pelo algoritmo.

Pete
fonte
4
Isso funcionaria a menos que o int max estava no arquivo, que é inteiramente possível ...
Pearsonartphoto
13
As regras não especificam que são 32 bits ou 64 bits ou algo assim; portanto, de acordo com as regras especificadas, não há int máximo. Inteiro não é um termo de computador, é um termo matemático que identifica números inteiros positivos ou negativos.
Pete
É verdade, mas não se pode presumir que seja um número de 64 bits ou que alguém não se esgueiraria apenas no número máximo de int apenas para confundir esses algoritmos.
precisa saber é o seguinte
24
A noção inteira de "max int" não é válida no contexto se nenhuma linguagem de programação foi especificada. por exemplo, veja a definição de Python de um inteiro longo. É ilimitado. Não há teto. Você sempre pode adicionar um. Você está assumindo que ele está sendo implementado em um idioma que possui um valor máximo permitido para um número inteiro.
Pete
32

Isso pode ser resolvido em muito pouco espaço usando uma variante da pesquisa binária.

  1. Comece com o intervalo permitido de números, 0para 4294967295.

  2. Calcule o ponto médio.

  3. Faça um loop pelo arquivo, contando quantos números foram iguais, menores ou maiores que o valor do ponto médio.

  4. Se nenhum número for igual, você está pronto. O número do ponto médio é a resposta.

  5. Caso contrário, escolha o intervalo com menos números e repita o passo 2 com este novo intervalo.

Isso exigirá até 32 verificações lineares no arquivo, mas usará apenas alguns bytes de memória para armazenar o intervalo e as contagens.

Isso é essencialmente o mesmo que a solução de Henning , exceto que ele usa dois compartimentos em vez de 16k.

hammar
fonte
2
É com isso que eu comecei, antes de começar a otimizar para os parâmetros fornecidos.
hmakholm deixou Monica em 24/08/11
@ Henning: Legal. É um bom exemplo de algoritmo em que é fácil ajustar a troca espaço-tempo.
hammar
@hammar, mas e se houver esses números que aparecem mais de uma vez?
Alcott
@ Alcott: então o algoritmo selecionará o compartimento mais denso em vez do escasso, mas pelo princípio do buraco de pombo, ele nunca poderá escolher um compartimento completamente cheio. (A menor das duas contagens será sempre menor do que a faixa bin.)
Peter Cordes
27

EDIT Ok, isso não foi bem pensado, pois assume que os números inteiros no arquivo seguem alguma distribuição estática. Aparentemente, eles não precisam, mas mesmo assim deve-se tentar o seguinte:


Existem .34,3 bilhões de números inteiros de 32 bits. Não sabemos como eles são distribuídos no arquivo, mas o pior caso é aquele com a maior entropia de Shannon: uma distribuição igual. Nesse caso, a probabilidade de um número inteiro não ocorrer no arquivo é

((2³²-1) / 2³²) ⁴ ⁰⁰⁰ ⁰⁰⁰ ⁰⁰⁰ .4

Quanto menor a entropia de Shannon, maior é a probabilidade em média, mas mesmo para o pior dos casos, temos 90% de chance de encontrar um número não-recorrente após 5 tentativas com números inteiros aleatórios. Basta criar esses números com um gerador pseudo-aleatório, armazená-los em uma lista. Em seguida, leia int após int e compare-o com todos os seus palpites. Quando houver uma correspondência, remova esta entrada da lista. Depois de passar por todo o arquivo, é provável que você tenha mais de um palpite. Use qualquer um deles. No evento raro (10%, na pior das hipóteses), sem suposição, obtenha um novo conjunto de números inteiros aleatórios, talvez mais desta vez (10-> 99%).

Consumo de memória: algumas dezenas de bytes, complexidade: O (n), sobrecarga: não aceitável, pois a maior parte do tempo será gasta nos acessos inevitáveis ​​ao disco rígido, em vez de comparar as entradas de qualquer maneira.


O pior caso real, quando não assumimos uma distribuição estática, é que todo número inteiro ocorre no máximo. uma vez, porque somente 1 - 4000000000 / 2³² ≈ 6% de todos os números inteiros não ocorrem no arquivo. Portanto, você precisará de mais palpites, mas isso ainda não custará muito dinheiro.

leftaroundabout
fonte
5
Fico feliz em ver alguém pensar nisso, mas por que está aqui embaixo? Este é um algoritmo de 1 passagem… 10 MB são suficientes para suposições de 2,5 M e 93% ^ 2,5M ≈ 10 ^ -79000 é uma chance desprezível de precisar de uma segunda varredura. Devido à sobrecarga da pesquisa binária, fica mais rápido se você usar menos palpites! Isso é ideal no tempo e no espaço.
Potatoswatter
1
@ Potatoswatter: bom que você mencionou a pesquisa binária. Provavelmente isso não vale a pena quando se utiliza apenas 5 palpites, mas certamente vale 10 ou mais. Você pode até fazer as suposições de 2 M, mas deve armazená-las em um conjunto de hash para obter O (1) para a pesquisa.
usar o seguinte comando
1
Resposta equivalente do @Potatoswatter Ben Haley é perto do topo
Brian Gordon
1
Eu gosto dessa abordagem, mas sugeriria uma melhoria na economia de memória: se houver N bits de armazenamento indexado disponível, além de algum armazenamento constante, defina uma função de embaralhamento reversível configurável de 32 bits (permutação), escolha uma permutação arbitrária e limpe tudo bits indexados. Em seguida, leia cada número do arquivo, embaralhe-o e, se o resultado for menor que N, defina o bit correspondente. Se algum bit não estiver definido no final do arquivo, inverta a função de embaralhamento em seu índice. Com 64 KB de memória, é possível testar efetivamente mais de 512.000 números quanto à disponibilidade em uma única passagem.
supercat
2
Obviamente, com esse algoritmo, o pior caso é aquele em que os números foram criados pelo mesmo gerador de números aleatórios que você está usando. Supondo que você possa garantir que não seja esse o caso, sua melhor tática é usar um gerador linear de números aleatórios congruentes para gerar sua lista, para que você percorra o espaço numérico de maneira pseudo-aleatória. Isso significa que, se você, de alguma forma, falhar, poderá continuar gerando números até cobrir toda a gama de entradas (de encontrar uma lacuna), sem nunca duplicar seu esforço.
Dewi Morgan
25

Se você tiver um número inteiro ausente no intervalo [0, 2 ^ x - 1], basta xorotá-los todos juntos. Por exemplo:

>>> 0 ^ 1 ^ 3
2
>>> 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 6 ^ 7
5

(Eu sei que isso não responde exatamente à pergunta , mas é uma boa resposta para uma pergunta muito semelhante.)

rfrankel
fonte
1
Sim, é fácil provar [ ] que funciona quando um número inteiro está ausente, mas freqüentemente falha se mais de um estiver faltando. Por exemplo, 0 ^ 1 ^ 3 ^ 4 ^ 6 ^ 7é 0. [ Escreva 2 x para 2 a x'és de potência e a ^ b para a xor b, o xor de todos os k <2 x é zero - k ^ ~ k = (2 ^ x) - 1 para k <2 ^ (x-1) e k ^ ~ k ^ j ^ ~ j = 0 quando j = k + 2 ** (x-2) - então o xor de todos, exceto um número, é o valor do desaparecido]
James Waldby - jwpat7
2
Como mencionei em um comentário na resposta da ircmaxell: O problema não diz que "um número está faltando", ele diz que encontra um número não incluído nos 4 bilhões de números no arquivo. Se assumirmos números inteiros de 32 bits, cerca de 300 milhões de números podem estar ausentes no arquivo. A probabilidade de o xor dos números presentes corresponderem a um número ausente é de apenas 7%.
precisa saber é o seguinte
Esta é a resposta em que eu estava pensando quando li a pergunta inicialmente, mas, olhando mais de perto, acho que a pergunta é mais ambígua do que isso. FYI, esta é a pergunta que eu estava pensando: stackoverflow.com/questions/35185/...
Lee Netherton
18

Eles podem estar olhando para ver se você ouviu falar de um Filtro Bloom probabilístico que pode determinar com muita eficiência absolutamente se um valor não faz parte de um conjunto grande (mas só pode determinar com alta probabilidade que seja um membro do conjunto).

Paulo
fonte
4
Com provavelmente mais de 90% dos valores possíveis configurados, seu Bloom Filter provavelmente precisará degenerar no campo de bits que muitas respostas já usam. Caso contrário, você acabará com uma cadeia de bits inútil e completamente preenchida.
Christopher Creutzig
@Christopher Meu entendimento de filtros Bloom é que você não conseguir um bitarray preenchido até chegar a 100%
Paul
... caso contrário, você obteria falsos negativos.
Paul
@Paul uma matriz de bits preenchida fornece falsos positivos, que são permitidos. Nesse caso, o filtro de bloom provavelmente se degeneraria no caso em que a solução, que seria negativa, retornasse um falso positivo.
Ataylor
1
@Paul: você pode obter um bitarray preenchido assim que o número de funções de hash multiplicado pelo número de entradas for tão grande quanto o comprimento do seu campo. Obviamente, esse seria um caso excepcional, mas a probabilidade aumentará muito rapidamente.
Christopher Creutzig
17

Com base na redação atual da pergunta original, a solução mais simples é:

Encontre o valor máximo no arquivo e adicione 1 a ele.

oosterwal
fonte
5
E se o MAXINT estiver incluído no arquivo?
quer
@ Petr Peller: Uma biblioteca BIGINT essencialmente removeria as limitações no tamanho inteiro.
Oosterwal
2
@osteroster, se essa resposta for permitida, você nem precisa ler o arquivo - apenas imprima o maior número possível.
Nakilon
1
@oosterwal, se o seu grande número aleatório fosse o maior que você poderia imprimir e estivesse no arquivo, essa tarefa não poderia ser resolvida.
Nakilon
3
@Nakilon: +1 Seu ponto de vista é correto. É aproximadamente equivalente a calcular o número total de dígitos no arquivo e imprimir um número com tantos dígitos.
Oosterwal
14

Use a BitSet. 4 bilhões de números inteiros (supondo até 2 ^ 32 números inteiros) compactados em um BitSet a 8 por byte é 2 ^ 32/2 ^ 3 = 2 ^ 29 = aproximadamente 0,5 Gb.

Para adicionar um pouco mais de detalhe - sempre que você ler um número, defina o bit correspondente no BitSet. Em seguida, passe pelo BitSet para encontrar o primeiro número que não está presente. De fato, você pode fazer isso com a mesma eficácia, escolhendo repetidamente um número aleatório e testando se ele estiver presente.

Na verdade, BitSet.nextClearBit (0) informará o primeiro bit não definido.

Observando a API BitSet, ela parece suportar apenas 0..MAX_INT, portanto, você pode precisar de 2 BitSets - um para números + e cinco e números anteriores - mas os requisitos de memória não mudam.

dty
fonte
1
Ou se você não quiser usar um BitSet... tente uma matriz de bits. Faz a mesma coisa;)
jcolebrand
12

Se não houver limite de tamanho, a maneira mais rápida é obter o tamanho do arquivo e gerar o tamanho do arquivo + 1 número de dígitos aleatórios (ou apenas "11111 ..." s). Vantagem: você nem precisa ler o arquivo e pode minimizar o uso de memória quase até zero. Desvantagem: você imprimirá bilhões de dígitos.

No entanto, se o único fator estivesse minimizando o uso da memória e nada mais for importante, essa seria a solução ideal. Pode até dar a você o prêmio de "pior abuso das regras".

vsz
fonte
11

Se assumirmos que o intervalo de números sempre será 2 ^ n (uma potência par de 2), então exclusivo - ou funcionará (como mostrado em outro pôster). Quanto ao motivo, vamos provar:

A teoria

Dado qualquer intervalo de inteiros baseado em 0 que tenha 2^nelementos com um elemento ausente, você pode encontrar esse elemento faltante simplesmente xorando os valores conhecidos juntos para gerar o número ausente.

A prova

Vejamos n = 2. Para n = 2, podemos representar 4 números inteiros únicos: 0, 1, 2, 3. Eles têm um padrão de bits de:

  • 0 - 00
  • 1 - 01
  • 2 - 10
  • 3 - 11

Agora, se olharmos, cada bit é definido exatamente duas vezes. Portanto, uma vez que é definido um número par de vezes, e exclusivo - ou dos números produzirá 0. Se um único número estiver ausente, o exclusivo - ou produzirá um número que, quando exclusivo com o número ausente, resultará em 0. Portanto, o número ausente e o número exclusivo ored resultante são exatamente iguais. Se removermos 2, o xor resultante será 10(ou 2).

Agora, vejamos n + 1. Vamos ligar para o número de vezes que cada bit é definido em n, xeo número de vezes que cada bit é definido no n+1 y. O valor de yserá igual a, y = x * 2porque existem xelementos com o n+1bit definido como 0 e xelementos com o n+1bit definido como 1. E, como 2xsempre será par, n+1sempre terá cada bit definido um número par de vezes.

Portanto, como n=2funciona e n+1funciona, o método xor funcionará para todos os valores de n>=2.

O algoritmo para intervalos baseados em 0

Isto é bem simples. Ele usa 2 * n bits de memória, portanto, para qualquer intervalo <= 32, 2 inteiros de 32 bits funcionarão (ignorando qualquer memória consumida pelo descritor de arquivo). E faz uma única passagem do arquivo.

long supplied = 0;
long result = 0;
while (supplied = read_int_from_file()) {
    result = result ^ supplied;
}
return result;

O algoritmo para intervalos arbitrários

Esse algoritmo funcionará para intervalos de qualquer número inicial a qualquer número final, contanto que o intervalo total seja igual a 2 ^ n ... através do arquivo (o primeiro a obter o mínimo, o segundo a calcular o int ausente).

long supplied = 0;
long result = 0;
long offset = INT_MAX;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    result = result ^ (supplied - offset);
}
return result + offset;

Intervalos arbitrários

Podemos aplicar esse método modificado a um conjunto de intervalos arbitrários, pois todos os intervalos cruzarão uma potência de 2 ^ n pelo menos uma vez. Isso funciona apenas se houver um único bit ausente. São necessárias duas passagens de um arquivo não classificado, mas ele sempre encontrará o número ausente:

long supplied = 0;
long result = 0;
long offset = INT_MAX;
long n = 0;
double temp;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    n++;
    result = result ^ (supplied - offset);
}
// We need to increment n one value so that we take care of the missing 
// int value
n++
while (n == 1 || 0 != (n & (n - 1))) {
    result = result ^ (n++);
}
return result + offset;

Basicamente, baseia novamente o intervalo em torno de 0. Em seguida, conta o número de valores não classificados a serem acrescentados enquanto calcula o exclusivo-ou. Em seguida, adiciona 1 à contagem de valores não classificados para cuidar do valor ausente (conte o valor ausente). Em seguida, continue xorando o valor n, incrementado em 1 a cada vez até que n seja uma potência de 2. O resultado será então baseado novamente na base original. Feito.

Aqui está o algoritmo que testei em PHP (usando uma matriz em vez de um arquivo, mas o mesmo conceito):

function find($array) {
    $offset = min($array);
    $n = 0;
    $result = 0;
    foreach ($array as $value) {
        $result = $result ^ ($value - $offset);
        $n++;
    }
    $n++; // This takes care of the missing value
    while ($n == 1 || 0 != ($n & ($n - 1))) {
        $result = $result ^ ($n++);
    }
    return $result + $offset;
}

Alimentado em uma matriz com qualquer faixa de valores (eu testei incluindo negativos) com uma dentro dessa faixa que está faltando, ele encontrou o valor correto a cada vez.

Outra abordagem

Como podemos usar a classificação externa, por que não apenas verificar uma lacuna? Se assumirmos que o arquivo está classificado antes da execução desse algoritmo:

long supplied = 0;
long last = read_int_from_file();
while (supplied = read_int_from_file()) {
    if (supplied != last + 1) {
        return last + 1;
    }
    last = supplied;
}
// The range is contiguous, so what do we do here?  Let's return last + 1:
return last + 1;
ircmaxell
fonte
3
O problema não diz "está faltando um número", diz encontrar um número não incluído nos 4 bilhões de números no arquivo. Se assumirmos números inteiros de 32 bits, cerca de 300 milhões de números podem estar ausentes no arquivo. A probabilidade de o xor dos números presentes corresponderem a um número ausente é de apenas 7%.
precisa saber é o seguinte
Se você tiver um intervalo contíguo, mas ausente, que não seja baseado em zero, adicione em vez de xor. sum(0..n) = n*(n+1)/2. Então missing = nmax*(nmax+1)/2 - nmin*(nmin+1)/2 - sum(input[]). (ideia soma da resposta de @ Hammar.)
Peter Cordes
9

Truque de pergunta, a menos que tenha sido citado incorretamente. Basta ler o arquivo uma vez para obter o número inteiro máximo ne retornar n+1.

É claro que você precisaria de um plano de backup, caso n+1cause um estouro de número inteiro.

Mark Ransom
fonte
3
Aqui está uma solução que funciona ... exceto quando não funciona. Útil! :-)
dty
A menos que tenha sido citado incorretamente, a pergunta não colocou um limite no tipo de número inteiro, ou mesmo no idioma usado. Muitos idiomas modernos têm números inteiros limitados apenas pela memória disponível. Se o maior número inteiro do arquivo for> 10 MB, azar, tarefa impossível para o segundo caso. Minha solução favorita.
Jürgen Strobel
9

Verifique o tamanho do arquivo de entrada e, em seguida, imprima qualquer número que seja muito grande para ser representado por um arquivo desse tamanho. Isso pode parecer um truque barato, mas é uma solução criativa para um problema de entrevista, claramente evita o problema de memória e, tecnicamente, O (n).

void maxNum(ulong filesize)
{
    ulong bitcount = filesize * 8; //number of bits in file

    for (ulong i = 0; i < bitcount; i++)
    {
        Console.Write(9);
    }
}

Deve imprimir 10 bits - 1 , que sempre será maior que 2 bits . Tecnicamente, o número que você precisa vencer é de 2 bits - (4 * 10 9 - 1) , pois você sabe que existem (4 bilhões - 1) outros números inteiros no arquivo e, mesmo com a compactação perfeita, eles ocupam pelo menos um pouco cada.

Justin Morgan
fonte
Por que não apenas em Console.Write( 1 << bitcount )vez do loop? Se houver n bits no arquivo, qualquer número de bits (_n_ + 1) com um 1 à esquerda é absolutamente garantido como maior.
Emmet
@ Emmet - Isso causaria apenas um excesso de número inteiro, a menos que o arquivo fosse menor que o tamanho de um int (4 bytes em C #). O C ++ pode permitir que você use algo maior, mas o C # parece não permitir nada além de entradas de 32 bits com o <<operador. De qualquer forma, a menos que você role seu próprio tipo inteiro gigantesco, será um tamanho de arquivo muito pequeno. Demo: rextester.com/BLETJ59067
Justin Morgan,
8
  • A abordagem mais simples é encontrar o número mínimo no arquivo e retornar 1 a menos que isso. Isso usa armazenamento O (1) e tempo O (n) para um arquivo de n números. No entanto, ele falhará se o intervalo de números for limitado, o que pode fazer com que min-1 não seja um número.

  • O método simples e direto de usar um bitmap já foi mencionado. Esse método usa O (n) tempo e armazenamento.

  • Um método de 2 passagens com 2 ^ 16 baldes de contagem também foi mencionado. Ele lê 2 * n inteiros, portanto, usa O (n) time e O (1) de armazenamento, mas não pode manipular conjuntos de dados com mais de 2 ^ 16 números. No entanto, é facilmente estendido para (por exemplo) 2 ^ 60 números inteiros de 64 bits executando 4 passagens em vez de 2 e adaptado facilmente ao uso de memória minúscula, usando apenas o número de posições necessárias na memória e aumentando o número de passagens correspondentemente, em Nesse caso, o tempo de execução não é mais O (n), mas sim O (n * log n).

  • O método de XOR'inging todos os números juntos, mencionados até agora por rfrankel e longamente por ircmaxell responde à pergunta feita no stackoverflow # 35185 , como ltn100 apontou. Ele usa O (1) armazenamento e O (n) tempo de execução. Se por enquanto assumimos números inteiros de 32 bits, o XOR tem 7% de probabilidade de produzir um número distinto. Justificativa: dado ~ 4G números distintos XOR'd juntos, e ca. 300M fora do arquivo, o número de bits definidos em cada posição de bit tem chances iguais de serem ímpares ou pares. Assim, 2 ^ 32 números têm a mesma probabilidade de surgir que o resultado XOR, dos quais 93% já estão no arquivo. Observe que, se os números no arquivo não forem todos distintos, a probabilidade de sucesso do método XOR aumentará.

James Waldby - jwpat7
fonte
7

Por alguma razão, assim que li esse problema, pensei em diagonalização. Estou assumindo números inteiros arbitrariamente grandes.

Leia o primeiro número. Deixe o teclado esquerdo com zero bits até você ter 4 bilhões de bits. Se o primeiro bit (de ordem superior) for 0, saída 1; else output 0. (Você realmente não precisa usar o teclado esquerdo: você apenas gera 1 se não houver bits suficientes no número.) Faça o mesmo com o segundo número, exceto usar o segundo bit. Continue com o arquivo dessa maneira. Você produzirá um número de 4 bilhões de bits, um bit de cada vez, e esse número não será o mesmo que o existente no arquivo. Prova: era o mesmo número enésimo, então eles concordariam com o enésimo bit, mas não por construção.

Jonathan Amsterdam
fonte
+1 para criatividade (e a menor saída de pior caso para uma solução de passagem única até agora).
hmakholm deixou Monica em 24/08/11
Mas não há 4 bilhões de bits para diagonalizar, existem apenas 32. Você acabará com um número de 32 bits diferente dos primeiros 32 números da lista.
Brian Gordon
@ Henning É quase um passe único; você ainda precisa converter de unário para binário. Edit: Bem, eu acho que é uma passagem sobre o arquivo. Deixa pra lá.
Brian Gordon
@ Brian, onde há algo "unário" aqui? A resposta está construindo uma resposta binária um pouco por vez e só lê o arquivo de entrada uma vez, tornando-o uma única passagem. (Se a saída decimal for necessária, as coisas ficam problemáticas - é melhor você construir um dígito decimal por três números de entrada e aceitar um aumento de 10% no log do número de saída).
hmakholm deixou Monica em 24/08/11
2
@ Henning O problema não faz sentido para números inteiros arbitrariamente grandes porque, como muitas pessoas apontaram, é trivial encontrar o maior número e adicionar um, ou construir um número muito longo a partir do próprio arquivo. Essa solução de diagonalização é particularmente inadequada porque, em vez de se ramificar no ith bit, você pode gerar 1 bit 4 bilhões de vezes e lançar 1 extra no final. Eu estou bem com ter números inteiros arbitrariamente grandes no algoritmo, mas acho que o problema é gerar um número inteiro de 32 bits ausente. Simplesmente não faz sentido de outra maneira.
Brian Gordon
6

Você pode usar sinalizadores de bit para marcar se um número inteiro está presente ou não.

Depois de percorrer o arquivo inteiro, verifique cada bit para determinar se o número existe ou não.

Supondo que cada número inteiro seja 32 bits, eles caberão convenientemente em 1 GB de RAM se a sinalização de bit for concluída.

Shamim Hafiz
fonte
0,5 Gb, a menos que você redefiniu byte a ser 4 bits ;-)
dty
2
@ Dty eu acho que ele quer dizer "confortavelmente", pois haverá muito espaço no 1Gb.
precisa saber é o seguinte
6

Retire o espaço em branco e os caracteres não numéricos do arquivo e acrescente 1. Seu arquivo agora contém um número único não listado no arquivo original.

Do Reddit por Carbonetc.

Ashley
fonte
Adoro! Mesmo que não seja exatamente a resposta que ele estava procurando ...: D
Johann du Toit
6

Apenas por uma questão de integridade, aqui está outra solução muito simples, que provavelmente levará muito tempo para ser executada, mas usa muito pouca memória.

Permita que todos os números inteiros possíveis sejam o intervalo de int_minaté int_maxe bool isNotInFile(integer)uma função que retorne true se o arquivo não contiver um determinado número inteiro e false mais (comparando esse número inteiro com cada número inteiro no arquivo)

for (integer i = int_min; i <= int_max; ++i)
{
    if (isNotInFile(i)) {
        return i;
    }
}
deg
fonte
A questão era exatamente sobre o algoritmo para a isNotInFilefunção. Certifique-se de entender a pergunta antes de responder.
Aleks G 24/08
2
não, a pergunta era "qual número inteiro não está no arquivo", não "é o número inteiro x no arquivo". uma função para determinar a resposta para a última pergunta poderia, por exemplo, comparar todos os números inteiros no arquivo com os números inteiros em questão e retornar verdadeiro em uma correspondência.
deg
Eu acho que essa é uma resposta legítima. Exceto para E / S, você precisa apenas de um número inteiro e de um sinalizador bool.
Brian Gordon
@ Aleks G - Não vejo por que isso está marcado como errado. Todos concordamos que é o algoritmo mais lento de todos :-), mas funciona e precisa apenas de 4 bytes para ler o arquivo. A pergunta original não estipula que o arquivo possa ser lido apenas uma vez, por exemplo.
Simon Mourier
1
@Aleks G - Certo. Eu também nunca disse que você disse isso. Dizemos apenas que IsNotInFile pode ser implementado trivialmente usando um loop no arquivo: Open; While Not Eof {Read Inteiro; Return False se Inteiro = i; Else Continue;}. Ele precisa apenas de 4 bytes de memória.
Simon Mourier
5

Para a restrição de memória de 10 MB:

  1. Converta o número em sua representação binária.
  2. Crie uma árvore binária em que esquerda = 0 e direita = 1.
  3. Insira cada número na árvore usando sua representação binária.
  4. Se um número já tiver sido inserido, as folhas já terão sido criadas.

Quando terminar, basta seguir um caminho que não foi criado antes para criar o número solicitado.

Número de 4 bilhões = 2 ^ 32, o que significa que 10 MB podem não ser suficientes.

EDITAR

Uma otimização é possível, se duas folhas de extremidade tiverem sido criadas e tiverem um pai comum, elas poderão ser removidas e o pai sinalizado como não uma solução. Isso corta ramificações e reduz a necessidade de memória.

EDIT II

Não há necessidade de construir a árvore completamente também. Você só precisará criar ramificações profundas se os números forem semelhantes. Se também cortamos galhos, essa solução pode funcionar de fato.

Jérôme Verstrynge
fonte
6
... e como isso se encaixará em 10 MB?
hmakholm deixou Monica em 22/08/11
Que tal: limitar a profundidade do BTree a algo que caberia em 10 MB; isso significa que você teria resultados no conjunto {falso positivo | positivo} e você pode percorrer isso e usar outras técnicas para encontrar valores.
23611 Jonathan Dickinson
5

Vou responder a versão de 1 GB:

Não há informações suficientes na pergunta, então vou declarar algumas suposições primeiro:

O número inteiro é 32 bits com intervalo -2.147.483.648 a 2.147.483.647.

Pseudo-código:

var bitArray = new bit[4294967296];  // 0.5 GB, initialized to all 0s.

foreach (var number in file) {
    bitArray[number + 2147483648] = 1;   // Shift all numbers so they start at 0.
}

for (var i = 0; i < 4294967296; i++) {
    if (bitArray[i] == 0) {
        return i - 2147483648;
    }
}
BobTurbo
fonte
4

Enquanto estivermos dando respostas criativas, aqui está outra.

Use o programa de classificação externa para classificar o arquivo de entrada numericamente. Isso funcionará para qualquer quantidade de memória que você tenha (ele usará o armazenamento de arquivos, se necessário). Leia o arquivo classificado e produza o primeiro número que está faltando.

Rhialto apoia Monica
fonte
3

Eliminação de bits

Uma maneira é eliminar bits, no entanto, isso pode realmente não resultar em um resultado (é provável que não ocorra). Psuedocode:

long val = 0xFFFFFFFFFFFFFFFF; // (all bits set)
foreach long fileVal in file
{
    val = val & ~fileVal;
    if (val == 0) error;
}

Contagens de bits

Acompanhe as contagens de bits; e use os bits com as menores quantidades para gerar um valor. Novamente, isso não tem garantia de gerar um valor correto.

Range Logic

Acompanhe os intervalos ordenados de uma lista (ordenados pelo início). Um intervalo é definido pela estrutura:

struct Range
{
  long Start, End; // Inclusive.
}
Range startRange = new Range { Start = 0x0, End = 0xFFFFFFFFFFFFFFFF };

Passe por cada valor no arquivo e tente removê-lo do intervalo atual. Este método não tem garantias de memória, mas deve funcionar muito bem.

Jonathan Dickinson
fonte
3

2 128 * 10 18 + 1 (que é (2 8 ) 16 * 10 18 + 1) - não pode ser uma resposta universal para hoje? Isso representa um número que não pode ser mantido no arquivo 16 EB, que é o tamanho máximo do arquivo em qualquer sistema de arquivos atual.

Michael Sagalovich
fonte
E como você imprimiria o resultado? Você não pode colocá-lo em um arquivo e a impressão na tela levaria alguns bilhões de anos. Não é provável que haja um tempo de atividade nos computadores atuais.
vsz 29/08
nunca se diz que precisamos imprimir o resultado em qualquer lugar, apenas 'gerá-lo'. portanto, depende do que você quer dizer com gerar. de qualquer maneira, a minha resposta é apenas um truque para evitar a elaboração de um algoritmo de reais :)
Michael Sagalovich
3

Acho que esse é um problema resolvido (veja acima), mas há um caso secundário interessante a ser lembrado, pois pode ser perguntado:

Se houver exatamente 4.294.967.295 (2 ^ 32 - 1) números inteiros de 32 bits sem repetições e, portanto, apenas um estiver faltando, haverá uma solução simples.

Inicie um total em execução em zero e, para cada número inteiro no arquivo, adicione esse número inteiro com estouro de 32 bits (efetivamente, runningTotal = (runningTotal + nextInteger)% 4294967296). Depois de concluído, adicione 4294967296/2 ao total em execução, novamente com estouro de 32 bits. Subtraia isso de 4294967296 e o ​​resultado será o número inteiro ausente.

O problema "apenas um número inteiro ausente" é solucionável com apenas uma execução e apenas 64 bits de RAM dedicados aos dados (32 para o total em execução, 32 para leitura no próximo número inteiro).

Corolário: A especificação mais geral é extremamente simples de corresponder se não estivermos preocupados com quantos bits o resultado inteiro deve ter. Nós apenas geramos um número inteiro grande o suficiente para que ele não possa estar contido no arquivo que recebemos. Novamente, isso ocupa uma quantidade mínima de RAM. Veja o pseudocódigo.

# Grab the file size
fseek(fp, 0L, SEEK_END);
sz = ftell(fp);
# Print a '2' for every bit of the file.
for (c=0; c<sz; c++) {
  for (b=0; b<4; b++) {
    print "2";
  }
}
Sintaxe
fonte
@Nakilon e TheDayTurns apontaram isso nos comentários para a pergunta original #
Brian Gordon
3

Como Ryan disse basicamente, classifique o arquivo e repasse os números inteiros e quando um valor for ignorado, você o terá :)

EDITAR em downvoters: o OP mencionou que o arquivo poderia ser classificado, portanto este é um método válido.

catraca arrepiante
fonte
Uma parte crucial é que você deve fazê-lo à medida que avança, dessa forma, você só precisa ler uma vez. O acesso à memória física é lento.
Ryan Amos
ordenação externa @ Ryan é na maioria dos casos, um merge sort assim no último merge você pode fazer o check :)
aberração catraca
Se os dados estiverem no disco, eles deverão ser carregados na memória. Isso acontece automaticamente pelo sistema de arquivos. Se precisarmos encontrar um número (o problema não indica o contrário), a leitura do arquivo classificado uma linha por vez é o método mais eficiente. Ele usa pouca memória e não é mais lento que qualquer outra coisa - o arquivo deve ser lido.
Tony Ennis
Como você classificará 4 bilhões de números inteiros quando tiver apenas 1 GB de memória? Se você usar memória virtual, levará muito tempo, pois os blocos de memória serão paginados dentro e fora da memória física.
Klas Lindbäck
4
@klas merge sort é projetado para que
catraca aberração
2

Se você não assumir a restrição de 32 bits, basta retornar um número de 64 bits gerado aleatoriamente (ou 128 bits, se você for pessimista). A chance de colisão é1 in 2^64/(4*10^9) = 4611686018.4 (aproximadamente 1 em 4 bilhões). Você estaria certo na maioria das vezes!

(Brincando ... mais ou menos.)

Peter Gibson
fonte
Eu vejo isso já foi sugerido :) upvotes para aquelas pessoas
Peter Gibson
O paradoxo do aniversário faz com que esse tipo de solução não valha o risco, sem verificar o arquivo para ver se sua suposição aleatória era realmente uma resposta válida. (Aniversário paradoxo não se aplica neste caso, mas repetidamente chamar esta função para gerar novos valores exclusivos cria uma situação de aniversário paradoxo.)
Peter Cordes
@PeterCordes gerados aleatoriamente números de 128 bits é precisamente como UUIDs trabalho - eles ainda mencionar o paradoxo do aniversário ao calcular a probabilidade de uma colisão na Wikipedia página UUID
Peter Gibson
Variante: encontre o máximo no conjunto, adicione 1.
Phil
Classificaria rapidamente a matriz original (sem armazenamento adicional.) E marcharia pela matriz e relataria o primeiro número inteiro 'ignorado'. Feito. Respondeu a pergunta.
Level 42