Détection de répétition avec entrée infinie

Question

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

Si, dans la séquence infinie, le nombre '5' apparaît deux fois, nous retournerons 'faux' la première fois et 'vrai' la deuxième fois. En fin de compte, nous avons besoin d'une fonction qui retourne 'true' si l'entier est apparu avant et 'false' si la fonction a reçu l'entier la première fois.

S'il existe deux solutions, l'une est spatiale et la seconde est temporelle, puis mentionnez les deux. Je vais écrire ma solution dans les réponses, mais je ne pense pas que ce soit la meilleure.

edit: Veuillez ne pas supposer les cas triviaux (c'est-à-dire aucune répétition, une séquence en constante augmentation). Ce qui m'intéresse, c'est comment réduire la complexité de l'espace du cas non trivial (nombres aléatoires avec répétitions).

Answer 1

j'utiliser l'approche suivante:

Utilisez une table de hachage comme structure de données. Pour chaque numéro lu, stockez-le dans votre infrastructure de données. Si c'est déjà stocké avant de trouver une répétition.

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

Quelle est la durée d'une séquence (avant que la répétition ne se produise)? Une répétition est-elle même garantie? Pour les cas extrêmes, la complexité de l'espace peut devenir problématique. Mais pour l'améliorer, vous aurez probablement besoin de plus d'informations structurelles sur votre séquence. Mise à jour: Si la séquence est très longue avec rarement des répétitions et que vous devez réduire l'espace requis, vous pourriez (avec des informations structurelles suffisantes sur la séquence) réduire le coût de l'espace. Par exemple: disons que vous savez que votre séquence infinie a une tendance générale à renvoyer des nombres qui correspondent à la plage actuelle des nombres min-max observés. Ensuite, vous aurez éventuellement des intervalles entiers qui ont déjà été contenus dans la séquence. Dans ce cas, vous pouvez économiser de l'espace en stockant de tels intervalles au lieu de tous les éléments qu'il contient.

Answer 2

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 le premier endroit de la séquence où il y a un autre chiffre répété, mais il y a une différence entre votre question et votre exemple.

Answer 3

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 = < nombres possibles avec la taille des mots de notre type de nombre (ie 2^32 pour C# int) - ceci est problématique sur une longue période si la séquence est vraiment infinie/se répète rarement elle-même. Pour enregistrer les numéros déjà apparus, j'utiliserais une table de hachage, puis je la vérifierais chaque fois que je recevrais un nouveau numéro.

Answer 4

Un BitSet pour les valeurs int (2^32 nombres) consommerait 512Mb. Cela peut être correct si les BitSets sont alloués pas souvent, assez rapidement et que le mem est disponible.

Une alternative est compressed BitSets qui fonctionne le mieux pour BitSets épars.

Answer 5

En fait, si le nombre maximal de valeurs est infini, vous pouvez utiliser n'importe quel algorithme de compression sans perte pour un 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-uns à épargner). Vous pouvez alors représenter le blanc comme les pixels apparus et noir pour les autres et utiliser n'importe quel algorithme de compression si l'espace est limité (c'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 le pire des cas, il faut que le nombre apparaisse avoir exactement 1 entre eux. Une fois de plus les numéros apparaissent, le stockage diminue: Je vais écrire pseudocode et je vais 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 des blocs. Pour chaque numéro que vous ajoutez, il parcourt la liste en stockant les blocs de nombres apparus et les nombres qui ne l'ont pas été. Laissez-moi illustrer avec un exemple; Je vais ajouter [] pour illustrer quels nombres dans le bloc, le premier nombre est inclus, le dernier ne l'est pas. Dans le pseudo-code, il est remplacé par le booléen appeared. 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 le dernière valeur vous conservez un bloc de 5 chiffres avec seulement 2.