La sagesse de la programmation suggère que transformer une tâche de programmation cyclique en une tâche linéaire, la vectorisation, améliore le temps de calcul. Mais est-ce vrai ? Sous quelles conditions? De combien? Le défi 1 a fourni une excellente occasion de le découvrir. Pour répondre aux quatre questions du défi, j'ai décidé que pour chaque ensemble de sept lettres, je ferais :
- Comptez le nombre de fois où chaque lettre est apparue dans un mot du dictionnaire. Cela m'a permis de trouver des réponses aux items 2, 3 et 4.
- Déterminez si un mot avait des lettres qui ne font pas partie de l'ensemble de sept lettres. Cela était nécessaire pour le point 1.
Défi 1 essai 1.JSL effectue le comptage à l'aide de formules de colonne basées sur le Longueur et Regex les fonctions. Quelques formules de colonnes supplémentaires sont utilisées pour faciliter la lecture du code. La seule boucle est utilisée pour réévaluer les fonctions pour chaque ensemble de lettres. Le temps d'exécution est d'un peu moins de 29 secondes (tous les temps sont moyennés sur 10 exécutions). Pas mal, mais pas génial. Est-ce la complexité des formules ou parce que l'évaluation de la formule aurait dû être faite en utilisant une boucle (sur une liste ou une matrice) au lieu d'une colonne ? j'ai utilisé tester simple.JSL et test complet.JSL enquêter. En plus de comparer la colonne à la boucle, j'ai cherché à savoir s'il était plus rapide de lire les valeurs d'entrée directement à partir de la table ou d'une liste. Cela ajoute-t-il du temps pour lire d'abord les valeurs de la table dans une liste ou une matrice ?
Les résultats ci-dessous (en secondes) montrent que, à mesure que les formules sont devenues plus complexes, la différence entre la formule et la boucle est moins apparente. Les fonctions utilisées pour construire les formules avaient un impact beaucoup plus important sur le temps. Les fonctions générales de recherche ( Regex et Loc ) étaient beaucoup plus lents que les fonctions de recherche spécifiques ( Contient et Substr ).
Les fonctions
|
Formule
|
Liste + accès à la liste
|
Liste + accès au tableau
|
Longueur
|
0,0525
|
0,1398
|
0,1311
|
Loc + Articles
|
0,4187
|
0,5462
|
0,5383
|
Longueur + Regex
|
9.3744
|
9.2745
|
9.3911
|
Boucles + Contient + Substr
|
3,3255
|
3,4139
|
3.5444
|
Mettant ces connaissances en pratique, j'ai créé deux nouveaux scripts. Défi 1 essai 2.JSL utilise des formules avec une boucle à l'intérieur d'une formule pour compter les lettres. Défi 2 Essayez 3.JSL utilise des listes plutôt que des formules. Il tire également parti de la condition selon laquelle pour que tout mot satisfasse aux éléments 1, 2 et 3, il doit contenir au moins une fois les sept lettres du jeu de lettres. Les temps d'exécution étaient respectivement de 15,50 et 10,40 secondes. Dans ce cas, la boucle était probablement plus rapide car il y avait moins de fonctions à évaluer. Soit l'amélioration est bien meilleure que ma tentative initiale, mais toujours pas la plus rapide. Les améliorations devraient provenir de fonctions plus rapides, de moins d'évaluations de boucles/fonctions ou d'une méthode différente pour répondre aux questions de défi. Étant donné que les deux premières approches semblaient moins susceptibles de donner des possibilités fructueuses, une méthode différente a été recherchée.
Le Défi 1 Pattern Matching.JSL le script vient de @Craige_Hales . Craige a récemment pris sa retraite de JMP Development mais est toujours très actif dans la communauté. Il était responsable de la correspondance de modèles et de la fonctionnalité d'expression régulière dans JMP . La solution de Craige vectorise le problème en convertissant d'abord la liste du dictionnaire en une longue chaîne, puis applique la correspondance de modèle pour analyser les mots dans des compartiments de solution. Il s'exécute en 3,71 secondes et offre un excellent exemple de l'étendue et de la flexibilité de la correspondance de motifs. La solution la plus rapide, prenant 2,76 secondes, provenait de @brady_brady . Plutôt que d'appliquer chaque ensemble de lettres aux mots du dictionnaire, il commence par compter le nombre d'occurrences pour chaque lettre de l'alphabet dans chaque mot du dictionnaire. Bien que cela augmente initialement le nombre de comparaisons de lettres de 7 à 26, cela ne doit être fait qu'une seule fois, évitant ainsi une réévaluation pour chaque nouvel ensemble de lettres. Les mots de réponse sont trouvés en extrayant les colonnes appropriées de la matrice alphabétique initiale, ce qui conduit à une solution beaucoup plus rapide. C'est aussi le script le plus court avec 1146 caractères.
Voici le classement après le premier défi :
Restez à l'écoute pour le défi 2 qui sortira le 1er mai !
@MathStatChem J'enlève les commentaires et les espaces blancs avant de compter les caractères. Votre nouveau script s'exécute en 3,6 secondes environ sur ma machine dans son état actuel. Plus lent que celui de Brady mais plus rapide que celui de Craige. Différence assez dramatique pour quelques petits changements! Certains des éléments ne sont pas répondus correctement, cependant. Vous trouverez ci-dessous les jeux de lettres que j'ai utilisés avec les réponses.
//acehlot
1. {"acacatechol"}
2. {"scientificophilosophical"}
3. {"hypercivilization"}
4. {"macracanthrorhynchiasis", "pancreaticoduodenostomy", "pericardiomediastinitis"}
//ilosuvx
1. {"lixivious"}
2.{"subclavioaxillary"}
3.{"excitovascular"}
4. {"formaldehydesulphoxylate"}
//mnoruwy
1.{"unwormy"}
2.{"countrywoman", "journeywoman", "laundrywoman"}
3.{"jurywoman"}
4.{"formaldehydesulphoxylate"}
Les longueurs de vos nouveaux et anciens scripts étaient respectivement de 2461 et 2469.
J'ai donc utilisé essentiellement la même logique que @brady_brady , mais mon code initial de comptage des lettres était tout simplement très inefficace, utilisant plus de boucles et d'appels aux listes.J'ai remplacé son approche et bien sûr, mon script s'est exécuté en 3 secondes environ.Très cool!
La fonction items() est vraiment la clé de cela.Je ne savais pas que ça ferait ça.Convertit une chaîne en une liste de ses caractères individuels (dans l'ordre, avec des lettres répétées comme éléments séparés dans la liste) avec juste
éléments (chaîne);
donc items("easypeasy","") renvoie {"e", "a", "s", "y", "p", "e", "a", "s", "y"}.
Ensuite, utiliser contains pour référencer l'index de la lettre de l'alphabet était également une très bonne astuce.
contient("abcedfghijklmnopqrstuvwxyz","a") renvoie 1,
contient("abcedfghijklmnopqrstuvwxyz","b") renvoie 2, ...
J'ai rendu mon code et ma sortie dans le journal un peu plus détaillés, je ne sais pas si vous avez supprimé les commentaires avant de compter les caractères.
Voici mon code (amélioré avec l'approche plus rapide):
startTime = Time Of Day( Today() );
letterSetList = {"apouter", "abdcefl", "acouter", "rstlneo", "efghijk"};
alphabet = {"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x",
"y", "z"};
abet="abcedfghijklmnopqrstuvwxyz";
_dt = Current Data Table();
numwords = N Rows( _dt );
_c = Column( _dt, "Words" );
wordlist = _c << get values;
// get lengths of each word in word list
// also create a matrix indicating how many times each letter in the alphabet is used in each word
wordlengths = J( numwords, 1, 0 );
alphacounts = J( numwords, 26, 0 );
For( ii = 1, ii <= numwords, ii++,
its=items(wordlist[ii],"");
wordlengths[ii] = Length( wordlist[ii] );
for(jj=1, jj<=nitems(its), jj++, alphacounts[ii,contains(abet,its[jj])]++);
);
// also create a matrix indicating if a letter in the alphabet is used in each word
alphaindex = alphacounts > 0;
For( ll = 1, ll <= N Items( letterSetList ), ll++,
str = letterSetList[ll];
// create an indicator vector for the letters in the string
str_alphaindex = J( 1, 26, 0 );
For( jj = 1, jj <= 26, jj++,
For( kk = 1, kk <= Length( str ), kk++,
str_alphaindex[1, jj] = str_alphaindex[1, jj] + (Substr( str, kk, 1 ) == alphabet[jj])
)
);
// 1 The longest word using all seven letters and only those seven letters. Letters may be used more than once.
// words that meet this criteria will have a "zero distance" from their letter indicator row and the string letter indicator vector
pickrow1 = Distance( alphaindex, str_alphaindex ) == 0;
// now find the word that has the longest length
pickrow1 = pickrow1 & (wordlengths == Max( wordlengths[Loc( pickrow1 )] ));
Print( "1. Find longest word(s) that uses only the letters <" || str || "> (item " || Char( ll ) || " from itemSetList)" );
If( Dim( Loc( pickrow1 ) )[1],
Print( wordlist[Loc( pickrow1 )] );
Print( "which is in the following row(s) from the Word List table " );
Print( Loc( pickrow1 & (wordlengths == Max( wordlengths[Loc( pickrow1 )] )) ) );
,
Print( "no word(s) found" )
);
Print( "-------------------" );
// 2 The longest word using all seven letters and any other letters.
// words that meet this condition, the sum of their letter indictor rows for the letters in the string should equal 7
pickrow2 = (V Sum( alphaindex[0, Loc( str_alphaindex )]` )` == 7);
// now find the word that has the longest length
pickrow2 = pickrow2 & (wordlengths == Max( wordlengths[Loc( pickrow2 )] ));
Print(
"2. Find longest word(s) that use all letters <" || str || "> (item " || Char( ll ) ||
" from itemSetList) and/or any other letters"
);
If( Dim( Loc( pickrow2 ) )[1],
Print( wordlist[Loc( pickrow2 )] );
Print( "which is in the following row(s) from the Word List table " );
Print( Loc( pickrow2 ) );
,
Print( "no word(s) found" )
);
Print( "-------------------" );
// 3 The longest word using all seven letters and any other letters where no letter
// from the set of seven is used more than once.
// words that meet this condition, meet the condition for the 2nd rule but also the sum of their letter counts for
// the letters in the string has to be equal to 7
pickrow3 = (V Sum( alphaindex[0, Loc( str_alphaindex )]` )` == 7) & (V Sum( alphacounts[0, Loc( str_alphaindex )]` )` == 7);
// now find the word that has the longest length
pickrow3 = pickrow3 & (wordlengths == Max( wordlengths[Loc( pickrow3 )] ));
Print(
"3. Find longest word(s) that use all letters <" || str || "> (item " || Char( ll ) ||
" from itemSetList) only once and/or any other letters "
);
If( Dim( Loc( pickrow3 ) )[1],
Print( wordlist[Loc( pickrow3 )] );
Print( "which is in the following row(s) from the Word List table " );
Print( Loc( pickrow3 ) );
,
Print( "no word(s) found" )
);
Print( "-------------------" );
// 4 The longest word in which 5 of the 7 letters appears.
// Any letter including those outside of the 7 may appear once or more
// except the two unused letters from the list of 7, which may not appear at all.
// words that meet this condition have the sum of their letter indicators (for the letters in the string) equal to 5
pickrow4 = (V Sum( alphaindex[0, Loc( str_alphaindex )]` )` == 5);
// now find the word that has the longest length
pickrow4 = pickrow4 & (wordlengths == Max( wordlengths[Loc( pickrow4 )] ));
Print(
"4. Find longest word(s) that uses only 5 of the 7 letters <" || str || "> (item " || Char( ll ) ||
" from itemSetList) and/or any other letters"
);
If( Dim( Loc( pickrow4 ) )[1],
Print( wordlist[Loc( pickrow4 )] );
Print( "which is in the following row(s) from the Word List table " );
Print( Loc( pickrow4 ) );
,
Print( "no word(s) found" )
);
Print( "-------------------" );
);
endTime = Time Of Day( Today() );
Print( endTime - startTime );
