Merci à ceux qui ont essayé le défi 7. J'espère que même si vous n'avez pas eu la chance, vous avez suivi les discussions. Comment pouvons-nous résoudre ce défi? Conceptuellement, l'approche la plus simple trouverait 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 de Covid-19 d'une longueur d'environ 30K 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 6889 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 façons d'aborder ce problème.
Concentrons-nous 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 doublon 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. Passer au caractère suivant et à une sous-chaîne dupliquée plus longue. Continuez ainsi jusqu'à ce que vous soyez suffisamment proche de la fin de la chaîne de recherche pour qu'un doublon ne soit pas possible. Dans le génome du Covid-19, une sous-chaîne de huit caractères ATTAAAGGG peut être construit à partir du premier caractère. Passage au deuxième caractère, une chaîne de 11 caractères TTAAAGGGTTTA fixant la position 2 a un doublon à la position 20063. Il n'y a pas de doublons 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 nécessite environ 5 secondes pour trouver la chaîne dupliquée la plus longue, deux chaînes de 32 caractères se chevauchant de UN s. Notez que dans le code ci-dessous, lorsqu'un doublon existe pour une sous-chaîne de longueur égale à la plus longue sous-chaîne déjà trouvée, Alors que itère au moins une fois avant de se 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 ' 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 longtemps. Je ne sais pas exactement pourquoi, mais mon intuition est que (comme illustré la dernière fois) Contient est beaucoup plus rapide lorsque le doublon de sous-chaîne se produit moins fréquemment.
Nous pourrions accélérer les choses en tirant parti de l'outil de recherche de doublons intégré de JMP, le Résumé plate-forme 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 itère sur 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 mise en œuvre à 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 créé des sous-chaînes de taille 4, 9, 15 et 21 sur une chaîne d'entrée de 1 000 000 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é du pattern matching. Les résultats complets se trouvent dans Tester les sous-chaînes de construction.JMP .
Algorithme
|
Temps de construction de longueur de chaîne (sec)
|
4
|
9
|
15
|
21
|
Expressions
|
6,91
|
7.35
|
8.19
|
9.01
|
Boucle
|
2,56
|
2,98
|
3.62
|
4.26
|
Correspondance de modèle
|
1.09
|
1.12
|
1.10
|
1.11
|
Une ANOVA a été effectuée montrant une différence statistique (p << 0,001) pour l'algorithme, la longueur de chaîne et l'interaction algorithme x longueur de chaîne. Des tests post-hoc utilisant le HSD de Tukey ont indiqué qu'il n'y avait pas de différence statistique entre les niveaux de longueur de chaîne pour l'algorithme Pattern Matching. Pour voir comment cette méthode fonctionnait avec un jeu de caractères plus grand, un test a été exécuté avec une longue chaîne de 1 000 000 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. Bien qu'il y ait eu des différences statistiques, les différences pratiques étaient minimes.
Sous-chaîne
Longueur
|
Temps (sec)
|
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 de doublons 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 fonctionnera à 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 basée sur 10 exécutions utilisant le Covid-19 et des chaînes de caractères de 1 000 000. Compte tenu des résultats, il est facile de voir que l'utilisation exclusive de cette approche et sans optimisation de la taille des sous-chaînes sera problématique à mesure que les chaînes et les sous-chaînes grossissent.
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 avec le démarrage de l'optimisation de la taille des sous-chaînes, nous ne pouvons pas prédire 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, à partir de ces seuls doublons, trouver les doublons les plus longs qu'il est possible de construire à 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 à discuter. Pour être honnête, j'ai vu la méthode finale avant de proposer cette approche et j'ai été, sans aucun doute, fortement influencé par celle-ci. Le défi de l'approche que j'ai choisie était de créer une structure de données pour suivre les positions des sous-chaînes d'origine. 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 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, nous n'avons qu'à 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, puis 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 autre optimisation, par exemple en commençant par des sous-chaînes plus longues. Un avantage de ces méthodes 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 de la même manière qu'elle pourrait être utilisée avec un tableau associatif, qui est ce qui est utilisé dans la méthode finale à discuter. 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 de plus à 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, moment auquel le tableau précédent contient les emplacements des doublons les plus longs.
Comme mentionné ci-dessus, la méthode finale est similaire à la précédente. L'idée de cette approche est grâce à @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 exécutions pour différentes tailles de chaîne d'entrée (50K - 2,5M) et jeux de caractères (4 à 72) ont été effectuées pour comparer les deux approches. Les temps d'exécution moyens sont indiqués ci-dessous pour la méthode récapitulative (1) et la méthode de tableau associatif (2). Les résultats complets peuvent être trouvés dans Comparer les méthodes les plus rapides.JMP.
|
50K
|
100K
|
500K
|
1M
|
2.5M
|
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
|
24.70
|
26
|
0,3098
|
0,3748
|
0,6786
|
0,7441
|
3.625
|
3.981
|
7.363
|
8.537
|
21.68
|
19.58
|
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 avec la méthode Summary, cette approche commence par transformer la chaîne d'entrée en caractères uniques. Plutôt que de travailler directement avec les caractères, cependant, leurs positions numériques telles qu'elles apparaissent dans le jeu de caractères sont utilisées. Cela permet à la création de sous-chaînes de se produire à l'aide d'opérations matricielles, qui ont tendance à être plus rapides que les opérations de chaîne. Plus précisément, la première itération prend une représentation matricielle de chaque position de jeu de caractères comme clé (par exemple, [3] pour G) vers 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 créer un nouveau tableau associatif en trouvant les valeurs de chaîne d'entrée à 1 plus les valeurs vectorielles pour chaque clé du tableau précédent, en veillant à 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 les 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 de 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 de recherche 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 la prochaine itération 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 ou les doublons les plus longs.
Le code de Brady se trouve dans findLongestDupe (AA).JSL . J'ai fait un ajustement mineur pour permettre l'utilisation de différents jeux de caractères.
Pour la prochaine fois, nous passerons des chaînes aux listes. Comme mentionné dans le blog précédent, éviter l'itération a fait l'objet de deux messages communautaires récents impliquant transformer des éléments numériques en caractère et indexation de liste . Deux défis pour la prochaine fois. Ils sont basés sur des questions qui sont apparues dans les messages liés. Dans les deux cas. Vous convertissez des valeurs numériques en chaînes de caractères.
- Écrire une fonction qui recouvre 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ésumez pas mi est le même pour toutes les listes" signifiait que les listes croisées pourraient avoir besoin d'être remplies avec des valeurs manquantes. Repeat({.},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>Cette JSL crée une table de données entièrement manquantes avec suffisamment de lignes et de colonnes numériques pour contenir les valeurs numériques de la liste. L'abonnement à la table de données n'est pas satisfait des lignes de longueur inégale et n'est pas satisfait de la conversion numérique en caractère 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'abonnement à la table de données veut obtenir et définir via une matrice numérique lorsque les colonnes sont toutes numériques, mais sera volontiers défini à partir d'une liste de listes de nombres. Étant donné que get va renvoyer une matrice, mais que le problème est de renvoyer une liste transposée de nombres, AsList() effectue le travail de conversion de la matrice (à partir de la table de données) en une liste.
