algorithm - optimizacion - ¿Cómo puedo optimizar un algoritmo de conmutación/caso múltiple(matriz)?
metodo de newton optimizacion no lineal (11)
¿Es posible optimizar este tipo de algoritmo (matriz)?
// | case 1 | case 2 | case 3 |
// ------|--------|--------|--------|
// | | | |
// case a| a1 | a2 | a3 |
// | | | |
// case b| b1 | b2 | b3 |
// | | | |
// case c| c1 | c2 | c3 |
// | | | |
switch (var)
{
case 1:
switch (subvar)
{
case a:
process a1;
case b:
process b1;
case c:
process c1;
}
case 2:
switch (subvar)
{
case a:
process a2;
case b:
process b2;
case c:
process c2;
}
case 3:
switch (subvar)
{
case a:
process a3;
case b:
process b3;
case c:
process c3;
}
}
El código es bastante simple, pero debe imaginarse más complejo con más "interruptor / caja".
Yo trabajo con 3 variables Según ellos toman los valores 1, 2, 3 o a, b, c o alfa, beta, charlie tienen diferentes procesos para lograr. ¿Es posible optimizarlo de otra manera que a través de una serie de "switch / case"?
(Pregunta ya hecha en francés aquí ).
Editar : (a partir de las respuestas de Dran Dane a los comentarios a continuación. ¡Estos también podrían estar en este lugar más prominente!)
" optimizar " debe entenderse en términos de tener que escribir menos código , menos "interruptor / caja". La idea es mejorar la legibilidad, el mantenimiento , no el rendimiento.
Tal vez haya una forma de escribir menos código a través de una "cadena de responsabilidad", pero esta solución no es óptima en todos los puntos, ya que requiere la creación de muchos objetos en la memoria.
No hay buenas respuestas a esta pregunta :-(
porque gran parte de la respuesta depende de
- Los objetivos efectivos (lo que se entiende por "optimizar", lo que no es placentero con los conmutadores anidados)
- El contexto en el que se va a aplicar este constructo (cuáles son las necesidades finales implícitas para la aplicación)
TokenMacGuy fue sabio al preguntar sobre los objetivos. Me tomé el tiempo de verificar la pregunta y sus respuestas en el sitio francés y todavía estoy desconcertado en cuanto a los objetivos ... La última respuesta de Dran Dane parece apuntar a disminuir la cantidad de código / mejorar la legibilidad, pero revisemos con seguridad:
- Velocidad de procesamiento: no es un problema que los conmutadores anidados sean bastante eficientes, posiblemente un poco menos de 3 multiplicaciones para obtener un índice en una tabla de mapas, pero tal vez ni siquiera.
- Legibilidad: sí, posiblemente, un problema. A medida que el número de variables y niveles aumenta, la explosión combinatoria entra en acción, y también el formato de la instrucción switch tiende a extender el punto de bifurcación y los valores asociados en un tramo vertical largo. En este caso, una tabla de 3 dimensiones (o más) se inicializó con fct. punteros vuelve a juntar los valores de bifurcación y la función a llamar en una sola línea.
- Escribir menos código: Perdón, no mucha ayuda aquí; al final del día, necesitamos dar cuenta de un número relativamente alto de combinaciones y el "mapa", sea cual sea su forma, debe escribirse en alguna parte. Los generadores de código como TokenMacGuy pueden ser útiles, en este caso parece un poco exagerado. Los generadores tienen su lugar, pero no estoy seguro de que sea el caso aquí. Uno de dos casos: si el número de variables y el nivel es lo suficientemente pequeño, el generador no vale la pena (toma más tiempo configurarlo que escribir el código real en primer lugar), si el número de variables y niveles es significativo, el código generado es difícil de leer, difícil de mantener ...)
En pocas palabras, mi recomendación con respecto a hacer que el código sea más legible (y un poco más rápido de escribir) es el enfoque de tabla / matriz descrito en el sitio francés.
Esta solución es en dos partes:
una inicialización única de una matriz tridimensional (para 3 niveles); (o una estructura de contenedor "más elegante" si se prefiere: un árbol, por ejemplo). Esto se hace con un código como:
// This is positively more compact / readable
...
FctMap[1][4][0] = fctAlphaOne;
FctMap[1][4][1] = fctAlphaOne;
..
FctMap[3][0][0] = fctBravoCharlie4;
FctMap[3][0][1] = NULL; // impossible case
FctMap[3][0][2] = fctBravoCharlie4; // note how the same fct may serve in mult. places
Y un fragmento relativamente simple donde sea que se necesiten las funciones:
if (FctMap[cond1][cond2][cond3]) {
retVal = FctMap[cond1][cond2][cond3](Arg1, Arg2);
if (retVal < 0)
DoSomething(); // anyway we''re leveraging the common api to these fct not the switch alternative ....
}
Un caso que puede provocar que uno NO use la solución anterior es si el espacio de combinación está relativamente poco poblado (muchas "ramas" en el "árbol" de conmutación no se usan) o si algunas de las funciones requieren un conjunto diferente de parámetros ; Para estos dos casos, me gustaría conectar una solución que Joel Goodwin propuso aquí primero , y que esencialmente combina las distintas claves para varios niveles en una clave más larga (con el carácter de separador si es necesario), básicamente reduciendo el problema a un enunciado de cambio de nivel largo pero único .
Ahora...
La discusión real debería ser sobre por qué necesitamos ese mapa / árbol de decisión en primer lugar . Desafortunadamente, para responder esto se requiere comprender la verdadera naturaleza de la aplicación subyacente. Para estar seguro, no estoy diciendo que esto sea indicativo de un mal diseño. Una gran sección de envío puede tener sentido en algunas aplicaciones. Sin embargo, incluso con el lenguaje C (que los autores del sitio francés parecían descalificar al diseño orientado a objetos), es posible adoptar patrones y metodología orientados a objetos. De todos modos estoy divergiendo ...) Es posible que la aplicación en general esté mejor servida con patrones de diseño alternativos donde el "árbol de información sobre qué llamar cuando" se ha distribuido en varios módulos y / o varios objetos.
Disculpas por hablar de esto en términos bastante abstractos, es solo la falta de detalles específicos de la aplicación ... El punto sigue siendo: cuestionar la idea de que necesitamos este gran árbol de despacho; pensar en enfoques alternativos a la aplicación en general.
Alors, bonne chance! ;-)
Dependiendo del idioma, alguna forma de hash map con el par (var, subvar) como clave y funciones de primera clase como los valores (o lo que sea que tu lenguaje ofrezca para aproximarlo mejor, por ejemplo instancias de clases que extienden una interfaz adecuada en Java ) es probable que proporcione un rendimiento superior, y la total concisión de obtener la función apropiada (o lo que sea ;-) del mapa basado en la clave, y ejecutarla, conduce a una alta legibilidad para los lectores familiarizados con el idioma y tales modismos funcionales .
La idea de un puntero a función es probablemente la mejor (según mjv, Shhnap). Pero, si el código en cada caso es bastante pequeño, puede ser excesivo y dar lugar a más ofuscación de lo previsto. En ese caso, podría implementar algo ágil y rápido de leer como este:
string decision = var1.ToString() + var2.ToString() + var3.ToString();
switch(decision)
{
case "1aa":
....
case "1ab":
....
}
No está familiarizado con su escenario particular, por lo que tal vez las sugerencias anteriores sean más apropiadas.
Parece que lo que quieres es una ''Máquina de estados finitos'' donde al usar esos casos puedes activar diferentes procesos o ''estados''. En C, esto generalmente se hace con una matriz (matriz) de indicadores de función.
Entonces, esencialmente haces una matriz y colocas los punteros de función correctos en las indicaciones correctas y luego usas tu ''var'' como un índice para el ''proceso'' correcto y luego lo llamas. Puedes hacer esto en la mayoría de los idiomas. De esta forma, diferentes entradas a la máquina activan diferentes procesos y los llevan a diferentes estados. Esto es muy útil para numerosas aplicaciones; Yo mismo lo uso todo el tiempo en el desarrollo de MCU.
Editar: Valya señaló que probablemente debería mostrar un modelo básico:
stateMachine[var1][var2](); // calls the right ''process'' for input var1, var2
Quizás lo que quieres es generación de código?
#! /usr/bin/python
first = [1, 2, 3]
second = [''a'', ''b'', ''c'']
def emit(first, second):
result = "switch (var)/n{/n"
for f in first:
result += " case {0}:/n switch (subvar)/n {{/n".format(f)
for s in second:
result += " case {1}:/n process {1}{0};/n".format(f,s)
result += " }/n"
result += "}/n"
return result
print emit(first,second)
#file("autogen.c","w").write(emit(first,second))
Esto es bastante difícil de leer, por supuesto, y es posible que desee un lenguaje de plantilla más agradable para hacer su trabajo sucio, pero esto facilitará algunas partes de su tarea.
Sí, definitivamente hay una manera más fácil de hacerlo, tanto más rápido como más simple . La idea es básicamente la misma que propuso Alex Martelli. En lugar de ver su problema como bi-dimensional, véalo como una tabla de búsqueda de una dimensión.
Significa combinar var, subvar, subsubvar, etc. para obtener una clave única y usarla como punto de entrada de la tabla de búsqueda.
La forma de hacerlo depende del idioma utilizado. Con python combinando var, subvar etc. para construir una tupla y usarla como clave en un dictionario es suficiente.
Con C o similar suele ser más fácil convertir cada una de las claves en enumeraciones, luego combinarlas usando operadores lógicos para obtener solo un número que puede usar en su conmutador (también es una manera fácil de usar el conmutador en lugar de comparizones de cadena con ifs en cascada). También obtienes otro beneficio al hacerlo. Es bastante habitual que varios tratamientos en diferentes ramas del cambio inicial sean los mismos. Con la forma inicial es bastante difícil hacerlo tan obvio. Probablemente tengas algunas llamadas a las mismas funciones pero está en diferentes puntos en el código. Ahora puede agrupar los casos idénticos al escribir el interruptor.
Utilicé dicha transformación varias veces en el código de producción y es fácil de hacer y mantener.
En resumen, puede obtener algo como esto ... la función de mezcla obviamente depende de los detalles de su aplicación.
switch (mix(var, subvar))
{
case a1:
process a1;
case b1:
process b1;
case c1:
process c1;
case a2:
process a2;
case b2:
process b2;
case c2:
process c2;
case a3:
process a3;
case b3:
process b3;
case c3:
process c3;
}
Si C ++ es una opción, trataría de usar la función virtual y tal vez el doble despacho. Eso podría hacerlo mucho más limpio. Pero probablemente solo pague solo si tiene muchos más casos.
Este artículo en DDJ.com podría ser una buena entrada.
Si solo está tratando de eliminar las instrucciones de conmutación / caso de dos niveles (y ahorra espacio vertical), puede codificar los dos valores de variable en un solo valor y luego activarlo:
// Assumes var is in [1,3] and subvar in [1,3]
// and that var and subvar can be cast to int values
switch (10*var + subvar)
{
case 10+1:
process a1;
case 10+2:
process b1;
case 10+3:
process c1;
//
case 20+1:
process a2;
case 20+2:
process b2;
case 20+3:
process c2;
//
case 30+1:
process a3;
case 30+2:
process b3;
case 30+3:
process c3;
//
default:
process error;
}
Si su idioma es C #, y sus opciones son lo suficientemente cortas y no contienen caracteres especiales, puede usar el reflejo y hacerlo con solo unas pocas líneas de código. De esta manera, en lugar de crear y mantener manualmente una matriz de punteros de función, utilice uno que proporcione el marco.
Me gusta esto:
using System.Reflection;
...
void DispatchCall(string var, string subvar)
{
string functionName="Func_"+var+"_"+subvar;
MethodInfo m=this.GetType().GetMethod(fName);
if (m == null) throw new ArgumentException("Invalid function name "+ functionName);
m.Invoke(this, new object[] { /* put parameters here if needed */ });
}
void Func_1_a()
{
//executed when var=1 and subvar=a
}
void Func_2_charlie()
{
//executed when var=2 and subvar=charlie
}
Solución de developpez.com Sí, puedes optimizarlo y hacerlo mucho más limpio. No puede usar tal "Cadena de Responsabilidad" con una Fábrica:
public class ProcessFactory {
private ArrayList<Process> processses = null;
public ProcessFactory(){
super();
processses = new ArrayList<Process>();
processses.add(new ProcessC1());
processses.add(new ProcessC2());
processses.add(new ProcessC3());
processses.add(new ProcessC4());
processses.add(new ProcessC5(6));
processses.add(new ProcessC5(22));
}
public Process getProcess(int var, int subvar){
for(Process process : processses){
if(process.canDo(var, subvar)){
return process;
}
}
return null;
}
}
Entonces, al igual que sus procesos implementan un proceso de interfaz con canXXX, puede usarlo fácilmente:
new ProcessFactory().getProcess(var,subvar).launch();
Tuve exactamente el mismo problema una vez, aunque por un lío inmanente de un interruptor anidado de 5 parámetros. Pensé, ¿por qué escribir todos estos casos O (N 5 ) yo mismo, por qué incluso inventar nombres de funciones "anidados" si el compilador puede hacer esto por mí? Y todo esto dio como resultado un ''interruptor de plantilla especializado anidado'' que se refiere a una ''base de datos de plantillas especializadas''.
Es un poco complicado de escribir. Pero encontré que valió la pena: da como resultado una base de datos de ''conocimiento'' que es muy fácil de mantener, depurar, agregar, etc. Y debo admitir: un sentido de orgullo.
// the return type: might be an object actually _doing_ something
struct Result {
const char* value;
Result(): value(NULL){}
Result( const char* p ):value(p){};
};
Algunos tipos de variables para el cambio:
// types used:
struct A { enum e { a1, a2, a3 }; };
struct B { enum e { b1, b2 }; };
struct C { enum e { c1, c2 }; };
Una ''declaración avanzada'' de la base de conocimiento: la ''api'' del interruptor anidado.
// template database declaration (and default value - omit if not needed)
// specializations may execute code in stead of returning values...
template< A::e, B::e, C::e > Result valuedb() { return "not defined"; };
La lógica de conmutación real (condensada)
// template layer 1: work away the first parameter, then the next, ...
struct Switch {
static Result value( A::e a, B::e b, C::e c ) {
switch( a ) {
case A::a1: return SwitchA<A::a1>::value( b, c );
case A::a2: return SwitchA<A::a2>::value( b, c );
case A::a3: return SwitchA<A::a3>::value( b, c );
default: return Result();
}
}
template< A::e a > struct SwitchA {
static Result value( B::e b, C::e c ) {
switch( b ) {
case B::b1: return SwitchB<a, B::b1>::value( c );
case B::b2: return SwitchB<a, B::b2>::value( c );
default: return Result();
}
}
template< A::e a, B::e b > struct SwitchB {
static Result value( C::e c ) {
switch( c ) {
case C::c1: return valuedb< a, b, C::c1 >();
case C::c2: return valuedb< a, b, C::c2 >();
default: return Result();
}
};
};
};
};
Y la base de conocimiento misma
// the template database
//
template<> Result valuedb<A::a1, B::b1, C::c1 >() { return "a1b1c1"; }
template<> Result valuedb<A::a1, B::b2, C::c2 >() { return "a1b2c2"; }
Así es como se puede usar.
int main()
{
// usage:
Result r = Switch::value( A::a1, B::b2, C::c2 );
return 0;
}