La sabiduría en programación sugiere que convertir una tarea de programación cíclica en una lineal, la vectorización, mejora el tiempo de cálculo. ¿Pero es esto cierto? ¿Bajo que condiciones? ¿Por cuanto? El desafío 1 brindó una gran oportunidad para descubrirlo. Para responder las cuatro preguntas del desafío, decidí que para cada conjunto de siete letras haría:
- Cuente el número de veces que apareció cada letra en una palabra del diccionario. Esto me permitió encontrar respuestas a los ítems 2, 3 y 4.
- Determina si una palabra tenía letras que no están en el conjunto de siete letras. Esto era necesario para el punto 1.
Desafío 1, prueba 1. JSL cuenta utilizando fórmulas de columna basadas en las funciones Longitud y Regex . Se utilizan algunas fórmulas de columnas adicionales para que el código sea más fácil de leer. El único bucle se utiliza para reevaluar las funciones para cada conjunto de letras. El tiempo de ejecución es de poco menos de 29 segundos (todos los tiempos se promedian en 10 carreras). No esta mal, pero tampoco grandioso. ¿Es la complejidad de las fórmulas o porque la evaluación de la fórmula debería haberse realizado utilizando un bucle (sobre una lista o matriz) en lugar de una columna? Utilicé test simple.JSL y test full.JSL para investigar. Además de comparar columnas versus bucles, miré para ver si era más rápido leer los valores de entrada directamente desde la tabla o desde una lista. ¿Agrega tiempo para leer primero los valores de la tabla en una lista o matriz?
Los resultados a continuación (en segundos) muestran que, a medida que las fórmulas se vuelven más complejas, la diferencia entre fórmula y bucle es menos evidente. Las funciones utilizadas para construir las fórmulas tuvieron un impacto mucho mayor en el tiempo. Las funciones de búsqueda generales ( Regex y Loc ) eran mucho más lentas que las funciones de búsqueda específicas ( Contiene y Substr ).
|
Funciones
|
Fórmula
|
Lista + Acceso a lista
|
Acceso a lista + tabla
|
|
Longitud
|
0.0525
|
0,1398
|
0.1311
|
|
Lugar + Elementos
|
0.4187
|
0.5462
|
0.5383
|
|
Length + expresión regular
|
9.3744
|
9.2745
|
9.3911
|
|
Bucles + Contiene + Substr
|
3.3255
|
3.4139
|
3.5444
|
Poniendo este conocimiento en práctica, creé dos nuevos guiones. Desafío 1, intento 2. JSL usa fórmulas con un bucle dentro de una fórmula para contar las letras. Desafío 2 Prueba 3. JSL usa listas en lugar de fórmulas. También aprovecha la condición de que para que cualquier palabra cumpla con los elementos 1, 2 y 3, debe contener las siete letras del conjunto de letras al menos una vez. Los tiempos de ejecución fueron 15,50 y 10,40 segundos, respectivamente. En este caso, el bucle probablemente fue más rápido porque había menos funciones para evaluar. Cualquiera de las mejoras es mucho mejor que mi intento inicial, pero aún no es la más rápida. Las mejoras tendrían que provenir de funciones más rápidas, menos bucles/evaluaciones de funciones o un método diferente para responder las preguntas desafiantes. Dado que los dos primeros enfoques parecían tener menos posibilidades de producir posibilidades fructíferas, se buscó un método diferente.
El script Challenge 1 Pattern Matching.JSL es de @Craige_Hales . Craige se retiró recientemente de JMP Development pero sigue siendo muy activo en la comunidad. Fue responsable de la funcionalidad de coincidencia de patrones y expresiones regulares en JMP . La solución de Craige vectoriza el problema convirtiendo primero la lista del diccionario en una cadena larga y luego aplica la coincidencia de patrones para analizar las palabras en grupos de soluciones. Se ejecuta en 3,71 segundos y ofrece un gran ejemplo de la amplitud y flexibilidad de la combinación de patrones. La solución más rápida, en 2,76 segundos, fue de @brady_brady . En lugar de aplicar cada conjunto de letras a las palabras del diccionario, comienza contando el número de apariciones de cada letra del alfabeto en cada palabra del diccionario. Si bien esto, inicialmente, aumenta el número de comparaciones de letras de 7 a 26, solo es necesario hacerlo una vez, evitando la reevaluación para cada nuevo conjunto de letras. Las palabras de respuesta se encuentran extrayendo las columnas apropiadas de la matriz alfabética inicial, lo que lleva a una solución mucho más rápida. También es el guión más corto con 1146 caracteres.
Aquí está la clasificación después del primer desafío:
¡Estén atentos al Desafío 2 que saldrá el 1 de mayo!
@MathStatChem Elimino los comentarios y los espacios en blanco antes de contar los caracteres. Su nuevo script se ejecuta en aproximadamente 3,6 segundos en mi máquina en su estado actual. Más lento que el de Brady pero más rápido que el de Craige. ¡Diferencia bastante dramática para algunos pequeños cambios! Sin embargo, algunos de los ítems no se responden correctamente. A continuación se muestran los conjuntos de letras que utilicé junto con las respuestas.
//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"}
Las longitudes de los scripts nuevos y antiguos fueron 2461 y 2469 respectivamente.
Así que utilicé básicamente la misma lógica que @brady_brady , pero mi código inicial de conteo de letras era muy ineficaz y usaba más bucles y llamadas a listas.Sustituí su enfoque y, efectivamente, mi script se ejecutó en unos 3 segundos.¡Muy genial!
La función items() es realmente clave para esto.No me di cuenta de que haría esto.Convierte una cadena en una lista de sus caracteres individuales (en orden, con letras repetidas como elementos separados en la lista) con solo
elementos (cadena);
entonces items("easypeasy","") devuelve {"e", "a", "s", "y", "p", "e", "a", "s", "y"}.
Luego, usar contiene para hacer referencia al índice de la letra del alfabeto también fue un buen truco.
contiene("abcedfghijklmnopqrstuvwxyz","a") devuelve 1,
contiene("abcedfghijklmnopqrstuvwxyz","b") devuelve 2, ...
Hice mi código y mi salida al registro un poco más detallados, no estoy seguro si eliminaste los comentarios antes de contar los caracteres.
Aquí está mi código (mejorado con el enfoque más rápido):
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 );
