La sagesse en matière de 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 été une belle occasion de le découvrir. Pour répondre aux quatre questions du défi, j'ai décidé que pour chaque série de sept lettres, je :
- 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 faisaient pas partie de l'ensemble de sept lettres. Cela était nécessaire pour le point 1.
Défi 1, essayez 1.JSL effectue le comptage à l'aide de formules de colonnes basées sur les fonctions Longueur et Regex . Quelques formules de colonnes supplémentaires sont utilisées pour rendre le code plus facile à lire. La seule boucle est utilisée pour réévaluer les fonctions pour chaque jeu de lettres. La durée d'exécution est d'un peu moins de 29 secondes (tous les temps sont calculés en moyenne 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 effectuée à l'aide d'une boucle (sur une liste ou une matrice) au lieu d'une colonne ? J'ai utilisé test simple.JSL et test full.JSL pour enquêter. En plus de comparer la colonne par rapport à la boucle, j'ai regardé s'il était plus rapide de lire les valeurs d'entrée directement à partir du tableau ou d'une liste. Cela ajoute-t-il du temps pour lire d'abord les valeurs du tableau dans une liste ou une matrice ?
Les résultats ci-dessous (en secondes) montrent que, à mesure que les formules deviennent 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 de recherche générales ( Regex et Loc ) étaient beaucoup plus lentes que les fonctions de recherche spécifiques ( Contains et Substr ).
|
Les fonctions
|
Formule
|
Liste + Accès à la liste
|
Accès liste + table
|
|
Longueur
|
0,0525
|
0,1398
|
0,1311
|
|
Lieu + Articles
|
0,4187
|
0,5462
|
0,5383
|
|
Length + Expression régulière
|
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 profite également de la condition selon laquelle pour qu'un mot satisfasse aux éléments 1, 2 et 3, il doit contenir au moins une fois les sept lettres de l'ensemble de lettres. Les temps d'exécution étaient respectivement de 15,50 et 10,40 secondes. Dans ce cas, le bouclage était probablement plus rapide car il y avait moins de fonctions à évaluer. L’une ou l’autre 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. Puisque les deux premières approches semblaient moins susceptibles de donner lieu à des possibilités fructueuses, une méthode différente a été recherchée.
Le script Challenge 1 Pattern Matching.JSL provient de @Craige_Hales . Craige a récemment pris sa retraite de JMP Development mais est toujours très actif au sein de la communauté. Il était responsable de la fonctionnalité de correspondance de modèles et d'expressions régulières dans JMP . La solution de Craige vectorise le problème en convertissant d'abord la liste de dictionnaires en une longue chaîne, puis applique la correspondance de modèles pour analyser les mots dans des compartiments de solutions. Il s'exécute en 3,71 secondes et offre un excellent exemple de l'étendue et de la flexibilité de la correspondance de modèles. La solution la plus rapide, prenant 2,76 secondes, provenait de @brady_brady . Plutôt que d’appliquer chaque lettre aux mots du dictionnaire, il commence par compter le nombre d’occurrences de 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 Je supprime 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. Une différence assez spectaculaire pour quelques petits changements ! Cependant, certains éléments ne reçoivent pas de réponse correcte. Vous trouverez ci-dessous les ensembles de lettres que j'ai utilisés ainsi que 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 2 461 et 2 469.
J'ai donc utilisé essentiellement la même logique que @brady_brady , mais mon code initial de comptage de lettres était tout simplement très inefficace, utilisant plus de boucles et d'appels à des 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é pour cela.Je ne pensais 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 contain 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 verbeux, 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 );
