Comment détecter le modèle "conversation" dans SQL?

Question

En fait, ce n'est pas spécifique à SQL, et je doute que le "modèle de conversation" soit le nom correct, mais je ne pouvais pas penser à une meilleure légende.

Pour simplifier, imaginez que vous avez un vaste flux d'ints. La tâche consiste à détecter un motif A.{1;max_n}A: Un int vérifie le motif s'il est suivi de n (> 0) autres ints, puis de nouveau l'int original, tandis que n < = max_n.

Exemple:

... 
1 
4 <-- 
7 \ 
3 > n = 3 
3/
4 <-- 
2 
... 

Ici, l'int 4 est répétée avec 3 ints arbitraires entre les deux, de manière à max_n < = 3, le motif est satisfaite pour la valeur 4. La question est, comment puis-je détecter quels entiers dans l'énorme vidage de données suivent ce modèle? Je m'intéresse surtout à l'algorithme lui-même, mais un exemple en SQL ou en C# serait également le bienvenu. L'idée naïve que je suis venu avec est de rassembler d'abord une liste ou tous les ints distincts, puis vérifier le modèle d'une manière directe pour chacun d'eux, mais cela conduirait à un goulot d'étranglement de la performance.

Answer 1

Vous pouvez conserver une structure de dictionnaire (C#) ou de carte (C++) où sera enregistrée la position de la première occurrence de nombres.

Ensuite, pour chaque numéro, vous devriez vérifier s'il est présent sur la carte. Si oui, vous devez comparer la différence de position avec la différence de position maximale avant. Sinon, vous devez enregistrer le numéro et sa position sur la carte.

Answer 2

Eh bien, SQL ne le fera pas de manière optimale, mais il pourrait ne pas être horrible si les colonnes sont indexées.

D'abord, pour parler d'ordre dans SQL, vous devriez avoir une autre colonne. Si cette colonne est en fait égal à un numéro de ligne, vous pouvez:

SELECT DISTINCT 
    t1.number 
FROM 
    table t1, table t2 
WHERE 
    (t1.rownumber-t2.rownumber) <= @max_n AND 
    (t1.rownumber-t2.rownumber) >=1 AND 
    t1.number = t2.number AND