La saggezza della programmazione suggerisce che trasformare un'attività di programmazione ciclica in una lineare, la vettorizzazione, migliora i tempi di calcolo. Ma è vero? A quali condizioni? Di quanto? La sfida 1 ha fornito una grande opportunità per scoprirlo. Per rispondere alle quattro domande di sfida, ho deciso che per ogni serie di sette lettere avrei:
- Conta il numero di volte in cui ciascuna lettera è apparsa in una parola del dizionario. Questo mi ha permesso di trovare le risposte ai punti 2, 3 e 4.
- Determina se una parola aveva lettere non nel set di sette lettere. Era necessario per il punto 1.
Sfida 1 prova 1.JSL esegue il conteggio utilizzando formule di colonna basate su Lunghezza E Regex funzioni. Alcune formule di colonna aggiuntive vengono utilizzate per rendere il codice più facile da leggere. L'unico ciclo viene utilizzato per rivalutare le funzioni per ogni set di lettere. Il tempo di esecuzione è di poco inferiore a 29 secondi (tutti i tempi sono calcolati in media su 10 corse). 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) invece di una colonna? ero solito prova semplice.JSL E prova completo.JSL indagare. Oltre a confrontare la colonna con il ciclo, ho verificato 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 un elenco o matrice?
I risultati seguenti (in secondi) mostrano che, man mano che le formule diventano più complesse, la differenza tra formula e loop 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ù lenti di specifiche funzioni di ricerca ( Contiene E Sost ).
Funzioni
|
Formula
|
Elenco + Accesso elenco
|
Elenco + accesso alla tabella
|
Lunghezza
|
0,0525
|
0,1398
|
0.1311
|
Loc + Elementi
|
0,4187
|
0,5462
|
0,5383
|
Lunghezza + Regex
|
9.3744
|
9.2745
|
9.3911
|
Cicli + Contiene + Sost
|
3.3255
|
3.4139
|
3.5444
|
Mettendo in pratica queste conoscenze, 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 piuttosto che formule. Sfrutta anche la condizione che affinché qualsiasi parola soddisfi i punti 1, 2 e 3, deve contenere tutte e sette le lettere del set di lettere almeno una volta. I tempi di esecuzione sono stati rispettivamente di 15,50 e 10,40 secondi. In questo caso, il ciclo era 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 looping/valutazioni delle funzioni o un metodo diverso per rispondere alle domande di sfida. Poiché i primi due approcci sembravano meno propensi a produrre possibilità fruttuose, è stato cercato un metodo diverso.
IL Sfida 1 Pattern Matching.JSL lo script è da @Craige_Hales . Craige si è recentemente ritirato da JMP Development, ma è ancora molto attivo nella community. Era responsabile del pattern matching e della funzionalità delle espressioni regolari in JMP . La soluzione di Craige vettorializza il problema convertendo prima l'elenco del dizionario in una lunga stringa, quindi applica il pattern matching per analizzare le parole in bucket di soluzioni. Funziona in 3,71 secondi e offre un ottimo esempio dell'ampiezza e della flessibilità del pattern matching. La soluzione più veloce, impiegando 2,76 secondi, era da @brady_brady . Invece di applicare ogni lettera impostata alle parole del dizionario, inizia contando il numero di occorrenze per ogni lettera dell'alfabeto in ogni parola del dizionario. Mentre questo, inizialmente, aumenta il numero di confronti di lettere da 7 a 26, deve essere fatto solo una volta, evitando la 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 lo script 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 lo spazio bianco prima di contare i caratteri. Il tuo nuovo script è in esecuzione in circa 3,6 secondi sulla mia macchina nel suo stato attuale. Più lento di Brady ma più veloce di Craige. Differenza piuttosto drammatica per alcuni piccoli cambiamenti! Tuttavia, ad alcuni elementi non viene data una 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 script nuovi e vecchi erano rispettivamente 2461 e 2469.
Quindi ho usato fondamentalmente la stessa logica di @brady_brady , ma il mio codice iniziale per il conteggio delle lettere era molto inefficiente, poiché utilizzava più cicli e chiamate agli elenchi.Ho sostituito il suo approccio e sicuramente il mio script è stato eseguito in circa 3 secondi.Molto bello!
La funzione items() è davvero la chiave per questo.Non avevo capito 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 usare contains per fare riferimento all'indice della lettera dell'alfabeto è stato anche un bel trucco.
contiene("abcedfghijklmnopqrstuvwxyz","a") restituisce 1,
contiene("abcedfghijklmnopqrstuvwxyz","b") restituisce 2, ...
Ho reso il mio codice e l'output nel registro un po 'più prolisso, 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 );
