Detectando repetição com entrada infinita

Question

Qual é a maneira mais ideal de encontrar repetição em uma sequência infinita de números inteiros?

ou seja, se na sequência infinita o número '5' aparecer duas vezes, então retornaremos 'falsos' na primeira vez e 'verdadeiro' na segunda vez.

No final, o que precisamos é de uma função que retorne 'verdadeiro' se o número inteiro aparecer antes e 'falso' se a função receber o número inteiro pela primeira vez.

Se houver duas soluções, uma é espacial e a segunda é em termos de tempo, mencione as duas. Vou escrever minha solução nas respostas, mas não acho que seja a ideal.

EDIT: Por favor, não assuma os casos triviais (ou seja, nenhuma repetição, uma sequência em constante crescente). O que me interessa é como reduzir a complexidade espacial do caso não trivial (números aleatórios com repetições).

Answer 1

Eu usaria a seguinte abordagem:

Use uma tabela de hash como suaestrutura de dados. Para cada número leia, armazene -o em suaestrutura. Se já estiver armazenado antes de encontrar uma repetição.

Se n é o número de elementos na sequência do início à repetição, isso requer apenas o tempo e o espaço o (n). A complexidade do tempo é ideal, pois você precisa pelo menos ler os elementos da sequência de entrada até o ponto de repetição.

Quanto tempo estamos falando de uma sequência (antes que a repetição ocorra)? Uma repetição é garantida? Para casos extremos, a complexidade do espaço pode se tornar problemática. Mas para melhorá -lo, você provavelmente precisará conhecer mais informações estruturais em sua sequência.

ATUALIZAÇÃO: Se a sequência for como você diz muito tempo com repetições raramente e você precisar reduzir o requisito de espaço, você poderá (receber informações estruturais suficientes sobre a sequência) poderá reduzir o custo do espaço.

Como exemplo: digamos que você saiba que sua sequência infinita tem uma tendência geral de retornar números que se encaixam na gama atual de números Min-Max testemunhados. Então você terá intervalos inteiros que já foram contidos na sequência. Nesse caso, você pode economizar espaço armazenando esses intervalos em vez de todos os elementos contidos nele.

Answer 2

Um bitset para os valores int (2^32 números) consumiria 512 MB. Isso pode ser bom se os bitsets forem alocados com frequência, rápido o suficiente e o MEM estiver disponível.

Uma alternativa são Bitsets comprimidos Isso funciona melhor para bitsets esparsos.

Answer 3

Na verdade, se o número máximo de valores for infinito, você poderá usar qualquer algoritmo de compactação sem perdas para um bitmap monocromático. Se você imaginar um quadrado com pelo menos tantos pixels quanto o número de valores possíveis, poderá mapear cada valor para um pixel (com alguns de sobra). Então você pode representar o branco como os pixels que apareceram e pretos para os outros e usar qualquer algoritmo de compressão se o espaço for um prêmio (isso certamente é um problema que foi estudado)

Você também pode armazenar blocos. O pior caso é o mesmo no Space O (n), mas, para o pior caso, você precisa que o número aparecesse tenha exatamente 1 entre eles. Depois de mais números aparecerem, o armazenamento diminuirá: escreverei pseudocódigo e usarei uma lista, mas você sempre pode usar uma estrutura diferente

List changes // global

boolean addNumber(int number):
  boolean appeared = false
  it = changes.begin()
  while it.hasNext():
    if it.get() < number:
      appeared != appeared
      it = it.next()
    else if it.get() == number:
      if !appeared: return true
      if it.next().get() == number + 1
        it.next().remove() // Join 2 blocks 
      else 
        it.insertAfter(number + 1)  // Insert split and create 2 blocks
      it.remove()
        return false
    else: // it.get() > number
      if appeared: return true
      it.insertBefore(number)
      if it.get() == number + 1:
        it.remove() // Extend next block
      else:
        it.insertBefore(number + 1)  
  }
  return false
}

Qual é esse código: ele armazena uma lista de blocos. Para cada número que você adicionar, ele itera sobre os blocos de armazenamento de números que apareceram e números que não o fizeram. Deixe -me ilustrar com um exemplo; Vou adicionar [) para ilustrar quais números no bloco, o primeiro número está incluído, o último não é. No pseudocódigo, ele é substituído pelo booleano appeared. Por exemplo, se você receber as 5, 9, 6, 8, 7 (nesta ordem), terá as seguintes sequências após cada função:

[5,6)

[5,6),[9,10)

[5,7),[9,10)

[5,7),[8,10)

[5,10)

No último valor, você mantém um bloco de 5 números com apenas 2.

Answer 4

Retornar verdadeiro

Se a sequência for infinita, haverá repetição de todo padrão concebível.

Se o que você quer saber é o primeiro lugar na sequência quando há um dígito repetido que é outra questão, mas há alguma diferença entre sua pergunta e seu exemplo.

Answer 5

Bem, parece óbvio que, em qualquer solução, precisamos salvar os números que já apareceram, então o espaço sempre Tenha um pior caso de O (n) em que n <= números possíveis com o tamanho da palavra do nosso tipo de número (ou seja, 2^32 para C# int) - Isso é problemático por um longo tempo se a sequência for realmente infinita/raramente repetir em si.

Para salvar os números que já apareceram, eu usaria uma tabela de hash e depois a verificar cada vez que recebo um novo número.