Mise à jour: Premier algorithme décrit ici est rendu obsolète par Armin Rigo, la seconde réponse, qui est beaucoup plus simple et plus efficace. Mais ces deux méthodes ont un inconvénient. Ils ont besoin de plusieurs heures pour trouver le résultat pour un million de nombres entiers. J'ai donc essayé les deux variantes (voir la deuxième moitié de cette réponse) où la portée de la saisie des nombres entiers est supposé être limitée. Cette limitation permet de bien des algorithmes plus rapides. Aussi, j'ai essayé d'optimiser Armin Rigo du code. Voir mes résultats de l'analyse comparative à la fin.
Voici une idée de l'algorithme à l'aide de O(N) de la mémoire. Le temps de la complexité est O(N2 log N), mais peut être réduite à O(N2).
L'algorithme utilise les structures de données suivantes:
-
prev: tableau d'indices pointant vers l'élément précédent (éventuellement incomplet) sous-suite.
-
hash: table de hachage avec clé = différence entre deux paires de sous-suite et valeur = deux autres hashmaps. Pour ces autres hashmaps: clé = de début/fin de l'index de la sous-suite, valeur = paire de (la longueur, la fin de/indice de départ de la sous-suite).
-
pq: file d'attente de priorité pour tous les possible de "différence" des valeurs pour les séquences stockées dans prev et hash.
Algorithme:
- Initialiser
prev avec index i-1. Mise à jour de hash et pq d'enregistrer tous (incomplète) de sous-séquences trouvées sur cette étape et de leurs "différences".
- Obtenir (et supprimer) la plus petite "différence" de l'
pq. Obtenez de l'enregistrement correspondant de hash de numérisation et de celui de de deuxième niveau de hachage cartes. À ce moment, toutes les sous-séquences avec la "différence" sont complètes. Si le deuxième niveau de hachage carte contient la longueur de mieux que trouvé à ce jour, de mettre à jour le meilleur résultat.
- Dans le tableau
prev: pour chaque élément d'une séquence à l'étape #2, décrémenter index et mise à jour de hash et, éventuellement, pq. Alors que la mise à jour de hash, nous pourrions effectuer l'une des opérations suivantes: ajouter une nouvelle sous-suite d'une longueur de 1, ou de pousser certains la par 1, ou de fusionner les deux sous-séquences.
- Supprimer de hachage de la carte d'enregistrement trouvé à l'étape #2.
- Continuer à partir de l'étape #2 en
pq n'est pas vide.
Cet algorithme mises à jour de O(N) éléments d' prev O(N) fois chacun. Et chacun de ces mises à jour peuvent nécessiter d'ajouter un nouveau "différence" pq. Tout cela signifie que le temps de la complexité de O(N2 log N) si nous utilisons de simples tas de mise en œuvre pour l' pq. Pour la réduire à O(N2) on pourrait utiliser plus avancés file d'attente de priorité des implémentations. Certaines de ces possibilités sont répertoriés sur cette page: Files d'attente de Priorité.
Voir le code Python sur Ideone. Ce code ne permet pas de dupliquer des éléments dans la liste. Il est possible de remédier à ce problème, mais ce serait une bonne optimisation de toute façon à supprimer les doublons (et à trouver la plus longue sous-suite-delà de doublons séparément).
Et , du même code, après un peu d'optimisation. Ici, la recherche est terminée dès que la longueur multipliée par d'éventuels sous-suite "différence" dépasse liste des sources de gamme.
Armin Rigo du code est simple et assez efficace. Mais dans certains cas cela fait quelques calculs supplémentaires qui peuvent être évités. La recherche peut être résilié dès que la longueur multipliée par d'éventuels sous-suite "différence" dépasse liste des sources de gamme:
def findLESS(A):
Aset = set(A)
lmax = 2
d = 1
minStep = 0
while (lmax - 1) * minStep <= A[-1] - A[0]:
minStep = A[-1] - A[0] + 1
for j, b in enumerate(A):
if j+d < len(A):
a = A[j+d]
step = a - b
minStep = min(minStep, step)
if a + step in Aset and b - step not in Aset:
c = a + step
count = 3
while c + step in Aset:
c += step
count += 1
if count > lmax:
lmax = count
d += 1
return lmax
print(findLESS([1, 4, 5, 7, 8, 12]))
Si la fourchette de nombres entiers dans la source de données (M) est faible, un algorithme simple est possible avec O(M2) en temps et O(M) de l'espace:
def findLESS(src):
r = [False for i in range(src[-1]+1)]
for x in src:
r[x] = True
d = 1
best = 1
while best * d < len(r):
for s in range(d):
l = 0
for i in range(s, len(r), d):
if r[i]:
l += 1
best = max(best, l)
else:
l = 0
d += 1
return best
print(findLESS([1, 4, 5, 7, 8, 12]))
Il est similaire à la première méthode par Armin Rigo, mais il n'utilise pas toutes les structures de données dynamiques. Je suppose que la source de données n'a pas de doublons. Et (pour simplifier le code), je suppose que le minimum de la valeur d'entrée est non-négative et proche de zéro.
Algorithme précédent peut être améliorée si au lieu d'un tableau de booléens, nous utilisons un bitset structure de données et des opérations bit à bit de données de processus en parallèle. Le code ci-dessous met en œuvre bitset qu'un Python entier. Il a les mêmes hypothèses: pas de doublons, le minimum de la valeur d'entrée est non-négative et proche de zéro. Le temps de la complexité est O(M2 * log L) où L est la longueur optimale des sous-suite, l'espace, la complexité est O(M):
def findLESS(src):
r = 0
for x in src:
r |= 1 << x
d = 1
best = 1
while best * d < src[-1] + 1:
c = best
rr = r
while c & (c-1):
cc = c & -c
rr &= rr >> (cc * d)
c &= c-1
while c != 1:
c = c >> 1
rr &= rr >> (c * d)
rr &= rr >> d
while rr:
rr &= rr >> d
best += 1
d += 1
return best
Repères:
Les données d'entrée (environ 100000 entiers) est généré de cette façon:
random.seed(42)
s = sorted(list(set([random.randint(0,200000) for r in xrange(140000)])))
Et pour le plus rapide des algorithmes j'ai aussi utilisé les données suivantes (environ 1000000 entiers):
s = sorted(list(set([random.randint(0,2000000) for r in xrange(1400000)])))
Tous les résultats montrent de temps en secondes:
Size: 100000 1000000
Second answer by Armin Rigo: 634 ?
By Armin Rigo, optimized: 64 >5000
O(M^2) algorithm: 53 2940
O(M^2*L) algorithm: 7 711
