La sabiduría de la 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 proporcionó una gran oportunidad para averiguarlo. Para responder a las cuatro preguntas de desafío, decidí que para cada conjunto de siete letras haría lo siguiente:
- 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.
- Determinar si una palabra tenía letras que no estaban en el conjunto de siete letras. Esto era necesario para el artículo 1.
Desafío 1 intento 1.JSL hace el conteo usando fórmulas de columna basadas en el Longitud y expresión regular funciones Se utilizan algunas fórmulas de columna adicionales para que el código sea más fácil de leer. El único bucle se utiliza para reevaluar las funciones de cada conjunto de letras. El tiempo de ejecución es de poco menos de 29 segundos (todos los tiempos se promedian en 10 ejecuciones). 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 hecho usando un bucle (sobre una lista o matriz) en lugar de una columna? solía prueba simple.JSL y prueba completa.JSL investigar. Además de comparar la columna con el ciclo, busqué si era más rápido leer los valores de entrada directamente de la tabla o de una lista. ¿Agrega tiempo 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 ciclo es menos evidente. Las funciones utilizadas para construir las fórmulas tuvieron un impacto mucho mayor en el tiempo. Las funciones generales de búsqueda ( expresión regular y ubicación ) eran mucho más lentos que las funciones de búsqueda específicas ( Contiene y Sust. ).
Funciones
|
Fórmula
|
Lista + Acceso a lista
|
Acceso a lista + tabla
|
Longitud
|
0.0525
|
0.1398
|
0.1311
|
ubicación + Elementos
|
0.4187
|
0.5462
|
0.5383
|
Longitud + expresión regular
|
9.3744
|
9.2745
|
9.3911
|
Bucles + Contiene + Sust.
|
3.3255
|
3.4139
|
3.5444
|
Poniendo en práctica este conocimiento, creé dos nuevos scripts. 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 utiliza listas en lugar de fórmulas. También aprovecha la condición de que para que cualquier palabra satisfaga 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. Cualquier mejora es mucho mejor que mi intento inicial, pero aún así no es la más rápida. Las mejoras tendrían que provenir de funciones más rápidas, menos ciclos/evaluaciones de funciones o un método diferente para responder las preguntas de seguridad. Dado que los primeros dos enfoques parecían menos probables de producir posibilidades fructíferas, se buscó un método diferente.
El Desafío 1 Coincidencia de patrones.JSL el guion 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 cubos de solución. Se ejecuta en 3,71 segundos y ofrece un gran ejemplo de la amplitud y flexibilidad de la coincidencia de patrones. La solución más rápida, que tomó 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 ocurrencias 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 debe hacerse 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 conduce a una solución mucho más rápida. También es el guión más corto con 1146 caracteres.
Aquí está la tabla de clasificación después del primer desafío:
¡Estén atentos al Desafío 2 que sale el 1 de mayo!
@MathStatChem Elimino los comentarios y espacios en blanco antes de contar los caracteres. Su nueva secuencia de comandos 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 por algunos pequeños cambios! Sin embargo, algunos de los elementos 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 sus scripts nuevos y antiguos fueron 2461 y 2469 respectivamente.
Así que usé básicamente la misma lógica que @brady_brady , pero mi código inicial de conteo de letras era muy ineficiente, usaba más bucles y llamadas a listas.Sustituí su enfoque y, efectivamente, mi guión 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 truco muy bueno.
contiene("abcedfghijklmnopqrstuvwxyz","a") devuelve 1,
contiene("abcedfghijklmnopqrstuvwxyz","b") devuelve 2, ...
Hice mi código y la salida al registro un poco más detallado, no estoy seguro si eliminó 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 );
