répétition infinie d'entrée avec détection

Question

Quelle est la manière la plus optimale pour trouver la répétition dans une suite infinie d'entiers?

i.e.. si, dans la suite infinie le nombre « 5 » apparaît deux fois alors nous reviendrons « faux » la première fois et « vraie » la deuxième fois.

En fin de compte ce que nous avons besoin est une fonction qui renvoie « true » si l'entier est apparu avant et « faux » si la fonction a reçu l'entier la première fois.

S'il y a deux solutions, on est sage-espace et le second est le temps sage, mentionner alors les deux. Je vais écrire ma solution dans les réponses, mais je ne pense pas que ce soit la solution optimale.

edit: S'il vous plaît ne présumez pas les cas insignifiants (à savoir pas de répétitions, une séquence en constante augmentation). Ce qui me intéresse est de savoir comment réduire la complexité spatiale du cas non trivial (nombres aléatoires avec des répétitions).

Answer 1

J'utilise l'approche suivante:

Utilisez une table de hachage comme structure de données. Pour chaque lecture numérique, le stocker dans votre structure de données. Si elle est déjà stocké avant que vous avez trouvé une répétition.

Si n est le nombre d'éléments dans la séquence du début à la répétition, cela ne nécessite que O (n) et de l'espace. la complexité du temps est optimale, que vous devez lire au moins les éléments de la séquence d'entrée jusqu'au point de répétition.

Combien de temps d'une séquence parle-(avant la répétition a lieu)? Est-ce une répétition même garantie du tout? Pour les cas extrêmes, la complexité de l'espace pourrait devenir problématique. Mais pour l'améliorer, vous aurez probablement besoin de connaître plus d'informations structurelles sur votre séquence.

Mise à jour: Si la séquence est comme vous le dites très long avec des répétitions rarement et vous devez réduire l'encombrement, alors vous pourriez (compte tenu des informations structurelles suffisantes sur la séquence) soit en mesure de réduire le coût de l'espace.

Par exemple: supposons que vous savez que votre séquence infinie a une tendance générale à revenir chiffres qui correspondent à la gamme actuelle de témoins numéros min-max. Ensuite, vous finirez par avoir des intervalles entiers qui ont déjà été contenues dans la séquence. Dans ce cas, vous pouvez économiser de l'espace en stockant ces intervalles au lieu de tous les éléments contenus dans ce document.

Answer 2

A BitSet pour les valeurs d'int (2 ^ 32 chiffres) consommeraient 512Mb. Cela peut être ok si les bitsets sont attribués ne pas souvent, assez rapide et le mem est disponible.

Une alternative sont bitsets comprimés qui fonctionnent le mieux pour bitsets clairsemés.

Answer 3

En fait, si le nombre maximum de valeurs est infini, vous pouvez utiliser tout algorithme de compression sans perte pour une image bitmap monochrome. Si vous imaginez un carré avec au moins autant de pixels que le nombre de valeurs possibles, vous pouvez mapper chaque valeur à un pixel (avec quelques épargner). Ensuite, vous pouvez représenter blanc comme les pixels qui est apparu et noir pour les autres et utiliser un algorithme de compression si l'espace est à une prime (qui est certainement un problème qui a été étudié)

Vous pouvez également stocker des blocs. Le pire des cas est le même dans l'espace O (n), mais pour ce pire des cas, vous avez besoin que le nombre semblait avoir exactement 1 entre eux. Une fois de plus les numéros apparaissent, le stockage diminue: Je vais écrire et je pseudocode utiliser une liste, mais vous pouvez toujours utiliser une structure différente

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
}

Qu'est-ce que ce code est le suivant: il stocke une liste de blocs. Pour chaque numéro que vous ajoutez, elle effectue une itération sur la liste de stockage des blocs de numéros qui apparaissent et des chiffres qui ne sont pas. Permettez-moi d'illustrer par un exemple; Je vais ajouter [) pour illustrer les numéros dans le bloc, le premier numéro est inclus, le dernier est not.In le pseudo-code, il est remplacé par le appeared booléenne. Par exemple, si vous obtenez 5, 9, 6, 8, 7 (dans cet ordre), vous aurez les séquences suivantes après chaque fonction:

[5,6)

[5,6), [9,10)

[5,7), [9,10)

[5,7), [8,10)

[5,10)

Dans la dernière valeur que vous gardez un bloc de 5 chiffres avec seulement 2.

Answer 4

Retour TRUE

Si la séquence est infinie alors il y aura répétition de chaque modèle imaginable.

Si ce que vous voulez savoir est la première place dans la séquence quand il y a un chiffre qui est répété une autre affaire, mais il y a une différence entre votre question et votre exemple.

Answer 5

Eh bien, il semble évident que toute solution, nous aurons besoin de sauver les chiffres qui apparaissaient déjà, si l'espace sage nous toujours un pire cas de O (N) où N < = nombre possible avec la taille des mots de notre type de numéro (par exemple 2 ^ 32 pour C # int) - cela pose problème sur une longue période si la séquence est vraiment infinie / se répète rarement

.

Pour enregistrer les chiffres qui figuraient déjà j'utiliser une table de hachage, puis vérifiez chaque fois que je reçois un nouveau numéro.