Merci à ceux qui ont essayé le Challenge 7. J'espère que même si vous n'en avez pas eu l'occasion, vous avez suivi les discussions. Comment pouvons-nous résoudre ce défi ? Conceptuellement, l'approche la plus simple consisterait à rechercher des doublons à un seul caractère, puis des doublons à deux caractères, trois caractères, etc., en augmentant d'un caractère jusqu'à ce qu'il n'y ait plus de doublons. Vérifier naïvement toutes les chaînes possibles pour une longueur donnée prend de plus en plus de temps avec la longueur des sous-chaînes. Pour le génome du Covid-19 d'une longueur d'environ 30 000 caractères, même si nous sommes assurés d'avoir des doublons de sous-chaînes de sept caractères avec seulement 4 7 = 16 384 combinaisons uniques, seulement 6 889 se produisent (42 %). Et le nombre de doublons diminue à mesure que la quantité de doublons possibles augmente rapidement à mesure que les sous-chaînes s'allongent. Une méthode efficace pour identifier les doublons doit être trouvée pour que cette approche fonctionne. Nous y reviendrons après avoir examiné d’autres moyens de résoudre ce problème.
Concentrons-nous uniquement sur la recherche du doublon le plus long sans avoir à nous soucier de trouver tous les doublons. Une approche simple serait de commencer la sous-chaîne au premier caractère avec un double de sept caractères puisqu'il doit en exister un. Ensuite, développez-le un caractère à la fois jusqu'à ce qu'il n'y ait plus de doublon. Passez au caractère suivant et à une sous-chaîne en double plus longue. Continuez ainsi jusqu'à ce que vous soyez suffisamment proche de la fin de la chaîne de recherche pour qu'une duplication ne soit pas possible. Dans le génome du Covid-19, une sous-chaîne de huit caractères ATTAAAGG peut être construit à partir du premier caractère. Passer au deuxième caractère, une chaîne de 11 caractères TTAAAGGTTTA regardant la position 2 a un double à la position 20063. Il n’y a pas de doublon de 11 caractères ou plus à partir de la position 3, nous passons donc à la position 4. Et ainsi de suite. Le code ci-dessous a besoin d'environ 5 secondes pour trouver la chaîne dupliquée la plus longue, deux chaînes de 32 caractères qui se chevauchent. UN s. Notez que dans le code ci-dessous, lorsqu'un doublon existe pour une sous-chaîne de longueur égale à la sous-chaîne la plus longue déjà trouvée, Alors que itère au moins une fois de plus avant de terminer. Dans ces situations suivantLen doit être décrémenté de 1.
findLongestDupe = Function({inString,charSet},{parts,nextLen,nextPos=1,longestDupes={""}},
parts = Items(inString,"");
nextLen = Floor(Log(Length(inString))/Log(N Items(charSet)));
While(nextPos <= Length(inString)-nextLen+1,
nextWord = Concat Items(parts[nextPos::(nextPos+nextLen-1)],"");
While(Contains(inString,nextWord,nextPos+1),
nextLen++;
nextWord = Concat Items(parts[nextPos::(nextPos+nextLen-1)],"");
);
nextPos++;
If(Length(nextWord)>Length(longestDupes[1]),
nextLen--; //nextLen will be one more than longest length when Pat Match fails
nextWord = Concat Items(parts[nextPos::(nextPos+nextLen-1)],"");
If(Length(nextWord)==Length(longestDupes[1])+1,
Insert Into(longestDupes,nextWord),
longestDupes = Eval List({nextWord})
);
);
nextChar++;
);
longestDupes;
);
Comme avec @Craige_Hales ' code publié dans l'entrée de blog précédente, j'ai essayé d'implémenter l'approche ci-dessus en utilisant la correspondance de modèles. Étonnamment, les résultats ont pris cinq à six fois plus de temps. Je ne sais pas exactement pourquoi, mais mon intuition est la suivante (comme illustré la dernière fois) Contient est beaucoup plus rapide lorsque la duplication de sous-chaîne se produit moins fréquemment.
Nous pourrions accélérer les choses en tirant parti du outil de recherche de doublons intégré à JMP, le Résumé plateforme de table. Un avantage de cette approche est que nous pouvons commencer avec n’importe quelle longueur de sous-chaîne. Comment devez-vous construire les sous-chaînes ? Deux solutions peuvent être trouvées dans le billet de blog du mois dernier. Le premier atomise et parcourt la chaîne d’entrée.
parts = Items(inString,"");
nInds = Length(inString) - subStringLen + 1;
stringList = {};
For(i=1,i<=nInds,i++,
Insert Into(stringList,Concat Items(parts[i::(i + subStringLen - 1)],""))
);
où inString est la chaîne d'entrée et subStringLen est la longueur des sous-chaînes en cours de construction. Une approche non itérative peut être implémentée à l'aide d'expressions :
parts = Items(inString,"");
nInds = Length(inString) - subStringLen + 1;
stringList = {};
i=1;
stringList[1::nInds] = Expr(Concat Items(parts[i::(i++ + subStringLen - 1)],""));
stringList = Eval List(stringList);
ou correspondance de motifs
stringList = {};
Pat Match(inString, Pat Len(subStringLen) >> nextWord+Pat Test(Insert Into(stringList,nextWord);0));
Pour tester la vitesse de chaque approche, j'ai construit des sous-chaînes de taille 4, 9, 15 et 21 sur une chaîne d'entrée de 1 000 000 de caractères composée de quatre caractères générés aléatoirement. Dix itérations ont été exécutées à chaque longueur. Les résultats ci-dessous montrent la supériorité de la correspondance de modèles. Les résultats complets peuvent être trouvés dans Tester la création de sous-chaînes.JMP .
Algorithme
|
Temps de construction de la longueur de chaîne (sec)
|
4
|
9
|
15
|
21
|
Expressions
|
6.91
|
7h35
|
8.19
|
9.01
|
Boucle
|
2,56
|
2,98
|
3,62
|
4.26
|
Correspondance de motifs
|
1.09
|
1.12
|
1.10
|
1.11
|
Une ANOVA a été réalisée montrant une différence statistique (p << 0,001) pour l'algorithme, la longueur de la chaîne et l'interaction algorithme x longueur de la chaîne. Des tests post-hoc utilisant le HSD de Tukey ont indiqué qu'il n'y avait aucune différence statistique entre les niveaux de longueur de chaîne pour l'algorithme de correspondance de modèles. Pour voir comment cette méthode fonctionnait avec un jeu de caractères plus grand, un test a été exécuté avec une chaîne de 1 000 000 de caractères construite à partir de 26 caractères sélectionnés au hasard. Vingt répétitions ont été exécutées sur les mêmes longueurs de sous-chaînes que ci-dessus, plus des sous-chaînes de 2 et 40 caractères. Même s’il existe des différences statistiques, les différences pratiques sont minimes.
Sous-chaîne
Longueur
|
Temps (s)
|
2
|
1.11
|
4
|
1.08
|
9
|
1.09
|
15
|
1.11
|
24
|
1.13
|
40
|
1,53
|
L'association de la construction de sous-chaînes et de la recherche en double peut ressembler au code ci-dessous. Connaître les lignes associées aux doublons nous permet d'identifier leur emplacement dans la chaîne. Cela jouera à notre avantage un peu plus tard. Rendre les tables privées accélère légèrement les opérations.
stringList = {};
Pat Match(inString, Pat Len(subStringLen) >> nextWord+Pat Test(Insert Into(stringList,nextWord);0));
tmpTbl = New Table("tmp",New Column("tmp",Character,Values(stringList)),Private);
sumTbl = tmpTbl << Summary(Group(:tmp),Private);
dupeLocs = sumTbl << Get Rows Where(:N Rows > 1);
dupes = Column(sumTbl,1)[dupeLocs];
Close(tmpTbl,No Save);
Le tableau ci-dessous donne le temps d'exécution moyen pour une seule itération sur la base de 10 exécutions utilisant le Covid-19 et 1 000 000 de chaînes de caractères. Compte tenu des résultats, il est facile de voir que l'utilisation de cette approche exclusivement et sans optimisation de la taille des sous-chaînes sera problématique à mesure que les chaînes et les sous-chaînes grandissent.
Sous-chaîne
Longueur
|
COVID-19 [feminine
|
1M
|
2
|
0,0517
|
1,68
|
4
|
0,0504
|
4.25
|
9
|
0,1837
|
8.29
|
15
|
0,2226
|
8.63
|
21
|
0,2209
|
8,85
|
40
|
0,2957
|
12h30
|
Même en commençant l’optimisation de la taille des sous-chaînes, nous ne pouvons pas prédire quelle sera la structure des données d’entrée. Une meilleure approche serait d’employer une stratégie hybride. Utiliser Résumé pour identifier les doublons d'une taille donnée, puis, en utilisant ces seuls doublons, trouver les doublons les plus longs qui peuvent être construits à partir d'eux. Cela fonctionnera, car une sous-chaîne du ou des doublons les plus longs doit apparaître dans l'ensemble des doublons créés à partir d'une longueur de sous-chaîne plus courte. Il existe plusieurs approches possibles. Je choisis une approche analogue, mais différente, de la méthode finale qui sera discutée. Pour être honnête, j’ai vu la méthode finale avant de proposer cette approche et j’en ai sans aucun doute été fortement influencé. Le défi de l'approche que j'ai choisie était de créer une structure de données pour garder une trace des positions d'origine des sous-chaînes. Le code est étonnamment court, environ 50 lignes avec un espacement généreux. Il faut environ 0,32 seconde pour trouver tous les doublons dans les données Covid-19 et 13 secondes pour la chaîne de 1 000 000 de caractères. Le code se trouve dans findLongestDupe (Résumé).JSL .
Résumé est utilisé pour trouver les doublons à chaque itération. Bien que cela soit lent pour les grandes tables, il nous suffit de créer des tables aussi grandes que le nombre de doublons de l'étape précédente. En commençant par une sous-chaîne d'un caractère au-delà de la longueur minimale pour garantir les doublons, le nombre total de doublons est susceptible de diminuer sinon immédiatement, du moins très rapidement. Si le nombre de lignes dans les quelques itérations n'est pas trop grand, cette méthode peut être utilisée sans optimisation supplémentaire, par exemple en commençant par des sous-chaînes plus longues. Un avantage de cette méthode est qu’une optimisation supplémentaire peut être utilisée dans ces situations. L'indexation utilisée pour garder une trace des positions initiales des chaînes fonctionne d'une manière qui pourrait être utilisée avec un tableau associatif, ce qui est utilisé dans la méthode finale dont nous discuterons. Commencez par rechercher les emplacements des chaînes en double de longueur initiale et enregistrez-les dans un tableau temporaire. Créez des chaînes d'un caractère plus long à partir de ces emplacements en veillant à supprimer toutes les chaînes qui dépasseraient les limites de la chaîne d'entrée. Recherchez les emplacements des chaînes en double dans cette liste. Nous pouvons relier ces nouveaux indices à l'emplacement d'origine en les utilisant comme indices du tableau précédemment enregistré en ne conservant que les éléments qui ont des indices. Remplacez le tableau précédent par celui-ci. Continuez jusqu'à ce qu'il ne reste plus de doublons, auquel moment le tableau précédent contient les emplacements des doublons les plus longs.
Comme mentionné ci-dessus, la méthode finale a une saveur similaire à la précédente. L'idée de cette approche vient de @brady_brady . Il existe quelques différences importantes. Tout d’abord, il construit toutes les sous-chaînes à partir d’un caractère. Bien que cela semble inefficace, en utilisant des tableaux associatifs et en indexant les caractères de chaîne individuels à l'aide de matrices, cela élimine la recherche directe de la chaîne et évite les combinaisons de caractères qui n'existent pas. En général, elle surpasse la méthode précédente lorsque le jeu de caractères et la chaîne d'entrée deviennent volumineux. Dix essais pour différentes tailles de chaîne d'entrée (50 Ko – 2,5 M) et jeux de caractères (4 à 72) ont été effectués pour comparer les deux approches. Les temps d'exécution moyens sont indiqués ci-dessous pour la méthode Résumé (1) et la méthode Associative Array (2). Les résultats complets sont disponibles dans Comparer les méthodes les plus rapides.JMP.
|
50K
|
100K
|
500K
|
1M
|
2,5 millions
|
Taille du jeu de caractères
|
1
|
2
|
1
|
2
|
1
|
2
|
1
|
2
|
1
|
2
|
4
|
0,5087
|
0,5814
|
0,9081
|
1,2664
|
5.421
|
6.813
|
13.412
|
13.778
|
32.23
|
35,67
|
dix
|
0,2724
|
0,4117
|
0,6251
|
0,9207
|
2.850
|
4.509
|
6.998
|
9.503
|
13.61
|
24h70
|
26
|
0,3098
|
0,3748
|
0,6786
|
0,7441
|
3,625
|
3.981
|
7.363
|
8.537
|
21.68
|
19h58
|
52
|
0,4247
|
0,3265
|
1,0617
|
0,7682
|
4.246
|
4.046
|
9.522
|
7.395
|
30.67
|
18.08
|
72
|
0,3186
|
0,3309
|
0,7308
|
0,7079
|
3.533
|
4.236
|
7.192
|
8.917
|
20.14
|
18.97
|
Comme pour la méthode Summary, cette approche commence par transformer la chaîne d’entrée en caractères uniques. Cependant, plutôt que de travailler directement avec les caractères, leurs positions numériques telles qu'elles apparaissent dans le jeu de caractères sont utilisées. Cela permet de créer des sous-chaînes à l'aide d'opérations matricielles, qui ont tendance à être plus rapides que les opérations sur les chaînes. Plus précisément, la première itération prend une représentation matricielle de chaque position du jeu de caractères comme clé (par exemple, [3] pour G) d'un tableau associé et utilise le vecteur de ses emplacements dans la chaîne d'entrée comme valeur. Chaque itération suivante commence par construire un nouveau tableau associatif en recherchant les valeurs de chaîne d'entrée à 1 plus les valeurs vectorielles pour chaque clé du tableau précédent, en prenant soin de ne pas dépasser le dernier élément de la chaîne d'entrée. La valeur correspondant au premier élément du vecteur incrémenté est utilisée pour rechercher des doublons dans le reste des valeurs vectorielles incrémentées. S'ils existent, les positions auxquelles ils sont associés sont utilisées pour la valeur dans le nouvel élément du tableau. La clé de cet élément est construite en concaténant la valeur du jeu de caractères de l'élément dupliqué à la clé d'origine, ce qui facilite la recréation de la chaîne de caractères. La valeur recherchée et ses doublons, s'ils existent, sont supprimés du vecteur et la recherche se poursuit jusqu'à ce qu'il ne reste plus aucune valeur. Ce processus de construction se produit pour chaque élément du tableau précédent. Une fois terminé, le nouveau tableau associé remplace l'ancien et l'itération suivante commence. Cela continue jusqu'à ce qu'il n'y ait plus de nouvelles clés pour remplacer le tableau précédent. Le tableau précédent contient le(s) doublon(s) le plus long.
Le code de Brady peut être trouvé dans findLongestDupe (AA).JSL . J'ai effectué un ajustement mineur pour permettre l'utilisation de différents jeux de caractères.
La prochaine fois, nous passerons des chaînes aux listes. Comme mentionné dans le blog précédent, éviter les itérations a fait l'objet de deux articles récents de la communauté impliquant transformer des éléments numériques en caractères et indexation de liste . Deux défis pour la prochaine fois. Ils sont basés sur des questions soulevées dans les articles liés. Dans les deux cas. Vous convertissez des valeurs numériques en chaînes de caractères.
- Écrivez une fonction qui convertit une liste de n listes (chacune avec m je Nombres). Ne présumez pas m je est le même pour toutes les listes.
- Écrivez une fonction qui peut transposer la liste de l’élément 1. Voici un petit exemple :
inputList = {{12, 11, 16, 1, 15, ., 23, 8, 16, 17}, {1, 10, ., 4, 25, ., 19, 21, ., 3}, {11, 21,
22, 7, 3, ., 24, 10, 21, 20}, {., ., ., ., ., ., ., ., ., .}, {11, ., 3, ., 9, ., 23,
., 3, 16}};
outputList = {{12, 1, 11, ., 11}, {11, 10, 21, ., .}, {16, ., 22, ., 3}, {1, 4, 7, ., .}, {15, 25,
3, ., 9}, {., ., ., ., .}, {23, 19, 24, ., 23}, {8, 21, 10, ., .}, {16, ., 21, ., 3},
{17, 3, 20, ., 16}}
Bonne chance!
Voici une façon de relever le défi. J'ai décidé "Ne présume pas mi est le même pour toutes les listes", ce qui signifiait que les listes croisées pourraient devoir être complétées par des valeurs manquantes. Répéter({.},10) produit {.,.,.,.,.,.,.,.,.,.}. Insert() ajoute les éléments de la liste, pas la liste (voir Comment insérer une liste dans une autre liste .)
inputList = {
{12, 11, 16, 1, 15, ., 23, 8, 16, 17},
{1, 10, ., 4, 25, ., 19, 21, ., 3},
{11, 21, 22, 7, 3, ., 24, 10, 21, 20},
{1}, // odd across-list
{., ., ., ., ., ., ., ., ., .},
{11, ., 3, ., 9, ., 23, ., 3, 16}};
// find rows and max cols of input:
nrows = N Items( inputList );
ncols = 0;
For( irow = 1, irow <= nrows, irow += 1,
ncols = Max( ncols, N Items( inputList[irow] ) )
);
// if the across-lists are not all the same size, add missing values
For( irow = 1, irow <= nrows, irow += 1,
If( ncols > N Items( inputList[irow] ),
Insert Into( inputList[irow], Repeat( {.}, ncols - N Items( inputList[irow] ), . ) )
)
);
// make a table of numbers from the lists
dt = New Table( "temp", invisible, Add Rows( nrows ), <<ADD multiple="" columns=""></ADD>Ce JSL crée une table de données entièrement manquante avec suffisamment de lignes et de colonnes numériques pour contenir les valeurs numériques de la liste. L'indexation de la table de données n'est pas satisfaite des lignes de longueur inégale et n'est pas satisfaite de la conversion des chiffres en caractères pendant l'affectation. La conversion est effectuée vers la fin en envoyant le message SetDataType à une liste de colonnes (en évitant une boucle JSL explicite.) La liste de nombres transposée est capturée juste avant cela.
L'indexation de la table de données souhaite obtenir et définir via une matrice numérique lorsque les colonnes sont toutes numériques, mais sera volontiers définie à partir d'une liste de listes de nombres. Puisque le get va renvoyer une matrice, mais que le problème est de renvoyer une liste de nombres transposés, AsList() effectue le travail de conversion de la matrice (de la table de données) en liste.
