La saggezza della programmazione suggerisce che trasformare un compito di programmazione ciclico in uno lineare, la vettorizzazione, migliora il tempo di calcolo. Ma è vero? A quali condizioni? Di quanto? La sfida 1 ha offerto una grande opportunità per scoprirlo. Per rispondere alle quattro domande sfida, ho deciso che per ogni serie di sette lettere avrei:
- Contare il numero di volte in cui ciascuna lettera è apparsa in una parola del dizionario. Ciò mi ha permesso di trovare le risposte ai punti 2, 3 e 4.
- Determina se una parola contiene lettere che non rientrano nel set di sette lettere. Ciò era necessario per l'articolo 1.
Sfida 1 tentativo 1.JSL esegue il conteggio utilizzando formule di colonna basate sulle funzioni Length e Regex . Vengono utilizzate alcune formule di colonna aggiuntive per rendere il codice più semplice da leggere. L'unico ciclo viene utilizzato per rivalutare le funzioni per ciascun set di lettere. Il tempo di esecuzione è di poco inferiore a 29 secondi (tutti i tempi sono la media di 10 esecuzioni). Non male, ma non eccezionale. È la complessità delle formule o perché la valutazione della formula avrebbe dovuto essere eseguita utilizzando un ciclo (su un elenco o una matrice) anziché una colonna? Ho utilizzato test simple.JSL e test full.JSL per indagare. Oltre a confrontare la colonna con il ciclo, ho cercato di vedere se fosse più veloce leggere i valori di input direttamente dalla tabella o da un elenco. Aggiunge tempo per leggere prima i valori dalla tabella in una lista o matrice?
I risultati seguenti (in secondi) mostrano che, man mano che le formule diventano più complesse, la differenza tra formula e ciclo diventa meno evidente. Le funzioni utilizzate per costruire le formule hanno avuto un impatto molto maggiore sul tempo. Le funzioni di ricerca generali ( Regex e Loc ) erano molto più lente delle funzioni di ricerca specifiche ( Contiene e Substr ).
|
Funzioni
|
Formula
|
Elenco + Accesso all'elenco
|
Elenco + Accesso alla tabella
|
|
Lunghezza
|
0,0525
|
0,1398
|
0,1311
|
|
Posto + Elementi
|
0,4187
|
0,5462
|
0,5383
|
|
Length + Regex
|
9.3744
|
9.2745
|
9.3911
|
|
Loop + Contiene + Substr
|
3.3255
|
3.4139
|
3.5444
|
Mettendo in pratica questa conoscenza, ho creato due nuovi script. Sfida 1 prova 2.JSL utilizza formule con un ciclo all'interno di una formula per contare le lettere. Sfida 2 Prova 3.JSL utilizza elenchi anziché formule. Si avvale inoltre della condizione che, affinché qualsiasi parola soddisfi i punti 1, 2 e 3, deve contenere tutte e sette le lettere dell'insieme di lettere almeno una volta. I tempi di esecuzione erano rispettivamente di 15,50 e 10,40 secondi. In questo caso, il looping è stato probabilmente più veloce perché c'erano meno funzioni da valutare. Entrambi i miglioramenti sono molto migliori del mio tentativo iniziale, ma non sono ancora i più veloci. I miglioramenti dovrebbero provenire da funzioni più veloci, meno valutazioni di loop/funzioni o da un metodo diverso per rispondere alle domande della sfida. Poiché i primi due approcci sembravano meno propensi a produrre possibilità fruttuose, è stato cercato un metodo diverso.
Lo script della sfida 1 Pattern Matching.JSL proviene da @Craige_Hales . Craige si è recentemente ritirato da JMP Development ma è ancora molto attivo nella comunità. Era responsabile della funzionalità di corrispondenza dei modelli e delle espressioni regolari in JMP . La soluzione di Craige vettorizza il problema convertendo prima l'elenco dei dizionari in una lunga stringa, quindi applica la corrispondenza dei modelli per analizzare le parole in contenitori di soluzioni. Funziona in 3,71 secondi e offre un ottimo esempio dell'ampiezza e della flessibilità della corrispondenza dei modelli. La soluzione più veloce, impiegando 2,76 secondi, è stata di @brady_brady . Invece di applicare ogni lettera impostata alle parole del dizionario, inizia contando il numero di occorrenze di ogni lettera dell'alfabeto in ciascuna parola del dizionario. Anche se inizialmente questo aumenta il numero di confronti di lettere da 7 a 26, è necessario farlo solo una volta, evitando una rivalutazione per ogni nuovo set di lettere. Le parole di risposta vengono trovate estraendo le colonne appropriate dalla matrice alfabetica iniziale, portando a una soluzione molto più rapida. È anche la sceneggiatura più breve con 1146 caratteri.
Ecco la classifica dopo la prima sfida:
Resta sintonizzato per la Sfida 2 in uscita il 1 maggio!
@MathStatChem Rimuovo i commenti e gli spazi bianchi prima di contare i caratteri. Il tuo nuovo script verrà eseguito in circa 3,6 secondi sul mio computer nello stato attuale. Più lento di quello di Brady ma più veloce di quello di Craige. Differenza piuttosto drammatica per alcuni piccoli cambiamenti! Tuttavia, ad alcuni elementi non viene data risposta corretta. Di seguito sono riportati i set di lettere che ho usato insieme alle risposte.
//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"}
Le lunghezze dei tuoi nuovi e vecchi script erano rispettivamente 2461 e 2469.
Quindi ho usato sostanzialmente la stessa logica di @brady_brady , ma il mio codice iniziale per il conteggio delle lettere era semplicemente molto inefficiente, poiché utilizzava più cicli e chiamate agli elenchi.Ho sostituito il suo approccio e, come previsto, la mia sceneggiatura è stata eseguita in circa 3 secondi.Molto bello!
La funzione items() è davvero fondamentale per questo.Non avevo realizzato che avrebbe fatto questo.Converte una stringa in un elenco dei suoi singoli caratteri (in ordine, con lettere ripetute come elementi separati nell'elenco) con just
elementi(stringa);
quindi items("easypeasy","") restituisce {"e", "a", "s", "y", "p", "e", "a", "s", "y"}.
Quindi anche usare contiene per fare riferimento all'indice della lettera dell'alfabeto è stato davvero un bel trucco.
contiene("abcedfghijklmnopqrstuvwxyz","a") restituisce 1,
contiene("abcedfghijklmnopqrstuvwxyz","b") restituisce 2, ...
Ho reso il codice e l'output nel registro un po' più dettagliati, non sono sicuro di aver rimosso i commenti prima di contare i caratteri.
Ecco il mio codice (migliorato con l'approccio più veloce):
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 );
