algorithm - traduccion - ¿Puedes simplificar este algoritmo?
refactoring guru (27)
Uno para los matemáticos. Esto ha dado la vuelta a la oficina y queremos ver quién puede ofrecer una versión mejor optimizada.
(((a+p) <= b) && (a == 0 || a > 1) && (b >= p)) &&
((b - (a + p) == 0) || (b - (a + p) > 1))
Editar : todos los datos son positivos
Editar : Mejor == refactorizado para simplificar
Siento que (a! = 1) && (a + p <= b) && (a + p! = B - 1) es un poco más claro. Otra opción es:
int t = bp; (a! = 1 && a <= t && a! = t-1)
Básicamente a es 0, t o está entre 2 y t-2 inclusive.
Refactor por simplicidad al introducir más variables locales que indican el significado de cada expresión. Esto es difícil para nosotros hacer sin tener idea de qué significan a, byp.
Añadí esto como un comentario a la respuesta de Nickf, pero pensé en ofrecerlo como una respuesta por sí mismo. Las buenas respuestas parecen ser una variación de la suya, incluida la mía. Pero dado que no dependemos del compilador para la optimización (si los OP estuvieran, ni siquiera estaríamos haciendo esto), luego reducir esto de 3 Y a la siguiente significa que habrá valores en los que solo 2 de las 3 porciones necesitará ser evaluado. Y si esto se hace en un script, sería una diferencia en comparación con el código compilado.
(a != 1) && ((b > (a + p + 1)) || (b == (a + p))))
Basado en un comentario, voy a agregar que esto es mejor que la versión AND:
Supongo que depende de si su conjunto de datos de resultados verdaderos es mayor que el 50 por ciento de los conjuntos de entrada. Cuanto más a menudo la entrada sea verdadera, mejor será mi variación. Entonces, con esta ecuación, parece que el estilo AND será mejor (al menos para mi conjunto de datos de entrada de 0-500).
Bien
((b - (a + p) == 0) || (b - (a + p) > 1))
Would be better writen as:
(b - (a + p) >= 0)
Applying this to the whole string you get:
((a+p) <= b) && (a > 1) && (b >= p)) && (b - (a + p) >= 0)
(a + p) <= b is the same thing as b - (a + p) >= 0
Para que puedas deshacerte de eso:
((a+p) <= b) && (a > 1) && (b >= p))
Como los enteros no tienen signo, (a == 0 || a> 1) se puede sustituir por (a! = 1).
Con un primer pase, puede reducirlo a esto:
uint sum = a + p;
return ((sum <= b) && (a != 1) && (b >= p)) && (b - sum != 1);
Además, sería mucho más legible si pudieras dar nombres más significativos a las variables. Por ejemplo, si a y p son presiones, entonces a + p podría sustituirse como PressureSum.
Como todas son positivas, se puede eliminar una gran parte de la repetición:
Entonces, como primer paso,
(((a+p) <= b) && (a == 0 || a > 1) && (b >= p)) && ((b - (a + p) == 0) || (b - (a + p) > 1))
se convierte
((a+p) <= b) && (a != 1) && (b >= p)) && ((b - (a + p) != 1)
Para mayor claridad, esto solo está reemplazando el patrón (foo == 0 || foo > 1) con foo != 1
Ese patrón aparece dos veces más arriba, una vez con foo = a, y una vez con foo = (b - (a+p))
Esto es tan simple como podría obtenerlo.
def calc(a, b, p):
if (a != 1):
temp = a - b + p
if temp == 0 or temp < -1:
return True
return False
También podría escribirse como:
def calc(a, b, p):
temp = a - b + p
return a != 1 and (temp == 0 or temp < -1)
O como:
def calc(a, b, p):
temp = a - b + p
return a != 1 and temp <= 0 and temp != -1
No haría todas las matemáticas en esa expresión. Tal como b - (a + p) se evalúa dos veces. Si es posible, divídalos en variables en su lugar.
Además, escribir un árbol de notificación polaco podría ayudarlo a optimizarlo, todo lo que ve dos veces puede volver a usarse.
Probado con a, b, p de 0 a 10000:
a != 1 && a != (b-p-1) && a <= (b-p);
Creo que se puede simplificar aún más.
Si a, b y p son enteros positivos (suponiendo que el rango positivo incluya el valor 0), entonces la expresión (((a + p) <= b) && (a == 0 || a> 1) && (b> = p)) && ((b - (a + p) == 0) || (b - (a + p)> 1)) se puede reducir a ((a + p) <= b) && (a! = 1) && ((b- (a + p))! = 1)
Permítanme demostrarlo: en la primera parte de la expresión hay una condición, ((a + p) <= b) , que si se evalúa verdadero hace que la segunda parte sea verdadera: ((b - (a + p) == 0 ) || (b - (a + p)> 1)) . Si es verdad que (b> = (a + p)) entonces (b - (a + p)) tiene que ser mayor o igual a 0 , debemos asegurarnos de que (b- (a + p))! = 1 . Deje este término de lado por un tiempo y continúe.
Ahora podemos concentrar nuestros esfuerzos en la primera parte (((a + p) <= b) && (a == 0 || a> 1) && (b> = p)) && ((b- (a + p))! = 1)
Si a es positivo, siempre es> = 0, por lo que podemos descartar la prueba (a == 0 || a> 1) si favorecemos a (a! = 1) y reducimos la primera parte de la expresión a (((a + p) <= b) && (b> = p) && (a! = 1)) .
Para el siguiente paso de la reducción puede considerar que si b> = (a + p) entonces, obviamente b> = p ( a es positivo) y la expresión se puede reducir a
((a + p) <= b) && (a! = 1) && ((b- (a + p))! = 1)
Si la fórmula funciona y proviene de las reglas de su negocio, no hay una necesidad real de simplificarla. El compilador probablemente sepa mejor que nosotros cómo optimizar la fórmula.
Lo único que debe hacer es usar mejores nombres de variables que reflejen la lógica comercial.
Tenga cuidado con la aplicación de la solución propuesta antes de probarla por separado.
cómo es la siguiente lógica, por favor coméntela:
((a == 0 || a > 1) && ((b-p) > 1) )
(((a+p) <= b) && (a == 0 || a > 1) && (b >= p)) && ((b - (a + p) == 0) || (b - (a + p) > 1))
dado que a> = 0 (enteros positivos), el término (a == 0 || a> 1) siempre es verdadero
if ((a + p) <= b) then (b> = p) es verdadero cuando a, b, p son> = 0
por lo tanto ((a + p) <= b) && (a == 0 || a> 1) && (b> = p)) && ((b - (a + p) == 0) reduce a
b>=(a+p)
(b - (a + p) == 0) || (b - (a + p)> 1) es equivalente a b> = (a + p)
por lo tanto, la ecuación completa se reduce a
**b>= (a+p)**
(a + p <= b) && (a != 1) && (b - a - p != 1);
(a!=1) && ((b==a+p) || (b>1+a+p))
Puede que no sea el más simple, pero debería ser el más fácil de leer.
b >= p && b != p+1
EDITAR: Ok, eso no funcionó, pero este sí lo hace:
a != 1 && b >= a+p && b-a-p != 1
bap = b - (a + p)
bap >= 0 && bap != 1 && a != 1
EDITAR: Ahora tengo -2 por un intento honesto de ayudar y también por lo que me parece una respuesta válida. Para ti que puedes usar Python, aquí hay dos funciones, una con la pregunta y otra con mi respuesta:
def question(a, b, p):
return (((a+p) <= b) and (a == 0 or a > 1) and (b >= p)) or ((b - (a + p) == 0) or (b - (a + p) > 1))
def answer(a, b, p):
bap = b - (a + p)
return bap >= 0 and bap != 1 and a != 1
s = a + p
b >= s && a != 1 && b - s - 1 > 0
Controlado, devuelve el mismo valor booleano que la pregunta.
Programa que he usado para verificar: (me divertí escribiéndolo)
#include <iostream>
using namespace std;
typedef unsigned int uint;
bool condition(uint a, uint b, uint p)
{
uint s = a + p;
return uint( b >= s && a != 1 && b - s - 1 > 0 )
== uint( (((a+p) <= b) && (a == 0 || a > 1) && (b >= p))
&& ((b - (a + p) == 0) || (b - (a + p) > 1)) );
}
void main()
{
uint i = 0;
uint j = 0;
uint k = 0;
const uint max = 50;
for (uint i = 0; i <= max; ++i)
for (uint j = 0; j <= max; ++j)
for (uint k = 0; k <= max; ++k)
if (condition(i, j, k) == false)
{
cout << "Fails on a = " << i << ", b = " << j;
cout << ", p = " << k << endl;
int wait = 0;
cin >> wait;
}
}
(((a + p) <= b) && (a == 0 || a> 1) && (b> = p)) && ((b - (a + p) == 0) || (b - (a + p)> 1))
1) (a == 0 || a> 1) es (a! = 1)
2) (b> = p) es (b - p> = 0)
(a + p <= b) es (b - p> = a), que es más fuerte que (b - p> = 0).
Primera condición reducida a (a! = 1) && (b - p> = a) .
3) (b - (a + p) == 0) is (b - a - p == 0) is (b - p == a).
(b - (a + p)> 1) es (b - a - p> 1) es (b - p> 1 + a).
Como teníamos (b - p> = a) y estamos usando && operation, podemos decir que (b - p> = a) cubre (b - p == a && b - p> 1 + a).
Por lo tanto, toda la condición se reducirá a
(a! = 1 && (b - p> = a))
Hay una tentativa de reducirlo más a (b> = p), pero esta reducción no cubrirá la prohibición de b = p + 1, por lo tanto (a! = 1 && (b - p> = a)) es la condición.
De acuerdo, espero que hice mis cálculos aquí, pero si estoy en lo correcto, entonces esto se simplifica bastante. De acuerdo, al final no se ve igual, pero la lógica del núcleo debería ser la misma.
// Initial equation
(((a + p) <= b) && (a == 0 || a > 1) && (b >= p)) && ((b - (a + p) == 0) || (b - (a + p) > 1))
// ((a + p) <= b) iif a = 0 && p = b; therefore, b = p and a = 0 for this to work
(b == p) && ((b - (a + p) == 0) || (b - (a + p) > 1))
// Simplification, assuming that b = p and a = 0
(b == p) && (a == 0)
Sin embargo, si estamos operando bajo la suposición de que cero no es ni positivo ni negativo , eso implica que cualquier valor para a proporcionado a la ecuación será mayor o igual a uno. Esto a su vez significa que la ecuación siempre se evaluará como falsa debido al hecho de que lo siguiente:
(a == 0 || a > 1)
Solo evaluaría a verdadero cuando a> = 2; Sin embargo, si lo siguiente también es cierto:
(b >= p)
Entonces eso significa que p es al menos igual a b, por lo tanto:
((a + p) <= b)
Por sustitución se convierte en:
((2 + b) <= b)
Que claramente nunca puede evaluar a verdadero.
Esta pregunta ya se ha respondido bastante cómodamente en la práctica, pero hay un punto que menciono a continuación que aún no he visto a nadie más.
Como se nos dijo que asumiéramos a> = 0, y la primera condición asegura que b - (a + p)> = 0, el corchete || las pruebas se pueden convertir en pruebas contra la desigualdad con 1:
(a + p <= b) && (a! = 1) && (b> = p) && (b - a - p! = 1)
Es tentador eliminar el cheque (b> = p), que daría la expresión de nickf. Y esta es casi con certeza la solución práctica correcta. Desafortunadamente, necesitamos saber más sobre el dominio del problema antes de poder decir si es seguro hacerlo.
Por ejemplo, si usa C e Ints sin signo de 32 bits para los tipos de a, byp, considere el caso donde a = 2 ^ 31 + 7, p = 2 ^ 31 + 5, b = 13. Tenemos un > 0, (a + p) = 12 <b, pero b <p. (Estoy usando ''^'' para indicar exponenciación, no C bit a bit xor).
Probablemente sus valores no se acercarán al tipo de rangos en los que este tipo de desbordamiento es un problema, pero debe verificar esta suposición. Y si resulta ser una posibilidad, agregue un comentario con esa expresión explicando esto para que un optimizador futuro celoso no elimine descuidadamente la prueba (b> = p).
jjngy aquí tiene razón. Aquí hay una prueba de que su fórmula simplificada es equivalente a la original utilizando el Asistente de prueba Coq .
Require Import Arith.
Require Import Omega.
Lemma eq : forall (a b p:nat),
(((a+p) <= b) // ((a = 0) // (a > 1)) // (b >= p)) //
((b - (a + p) = 0) // (b - (a + p) > 1)) <->
((a + p <= b) // ~ (a= 1) // ~ (b - a - p = 1)).
Proof. intros; omega. Qed.
mis disculpas por el error en la derivación original. ¡Esto es lo que sucede cuando no te molestas en probar la unidad después de refactorizar!
la derivación corregida sigue, en la forma de un programa de prueba.
La respuesta corta es:
((a > 1) && (skeet == 0)) || ((a > 1) && (jon > 0) && (skeet < -1));
dónde
jon = (b - p)
skeet = (a - jon);
class Program
{
static void Main(string[] args)
{
bool ok = true;
for (int a = 1; a < 100; a++)
{
Console.Write(a.ToString());
Console.Write("...");
for (int b = 1; b < 100; b++)
{
for (int p = 1; p < 100; p++)
{
bool[] results = testFunctions(a, b, p);
if (!allSame(results))
{
Console.WriteLine(string.Format(
"Fails for {0},{1},{2}", a, b, p));
for (int i = 1; i <= results.Length; i++)
{
Console.WriteLine(i.ToString() + ": " +
results[i-1].ToString());
}
ok = false;
break;
}
}
if (!ok) { break; }
}
if (!ok) { break; }
}
if (ok) { Console.WriteLine("Success"); }
else { Console.WriteLine("Failed!"); }
Console.ReadKey();
}
public static bool allSame(bool[] vals)
{
bool firstValue = vals[0];
for (int i = 1; i < vals.Length; i++)
{
if (vals[i] != firstValue)
{
return false;
}
}
return true;
}
public static bool[] testFunctions(int a, int b, int p)
{
bool [] results = new bool[16];
//given: all values are positive integers
if (a<=0 || b<=0 || p<=0)
{
throw new Exception("All inputs must be positive integers!");
}
//[1] original expression
results[0] = (((a+p) <= b) && (a == 0 || a > 1) && (b >= p)) &&
((b - (a + p) == 0) || (b - (a + p) > 1));
//[2] a==0 cannot be true since a is a positive integer
results[1] = (((a+p) <= b) && (a > 1) && (b >= p)) &&
((b - (a + p) == 0) || (b - (a + p) > 1));
//[3] rewrite (b >= p) && ((a+p) <= b)
results[2] = (b >= p) && (b >= (a+p)) && (a > 1) &&
((b - (a + p) == 0) || (b - (a + p) > 1));
//[4] since a is positive, (b>=p) guarantees (b>=(p+a)) so we
//can drop the latter term
results[3] = (b >= p) && (a > 1) &&
((b - (a + p) == 0) || (b - (a + p) > 1));
//[5] separate the two cases b>=p and b=p
results[4] = ((b==p) && (a > 1) && ((b - (a + p) == 0) ||
(b - (a + p) > 1))) || ((b > p) && (a > 1) &&
((b - (a + p) == 0) || (b - (a + p) > 1)));
//[6] rewrite the first case to eliminate p (since b=p
//in that case)
results[5] = ((b==p) && (a > 1) && ((-a == 0) ||
(-a > 1))) || ((b > p) && (a > 1) &&
(((b - a - p) == 0) || ((b - a - p) > 1)));
//[7] since a>0, neither (-a=0) nor (-a>1) can be true,
//so the case when b=p is always false
results[6] = (b > p) && (a > 1) && (((b - a - p) == 0) ||
((b - a - p) > 1));
//[8] rewrite (b>p) as ((b-p)>0) and reorder the subtractions
results[7] = ((b - p) > 0) && (a > 1) && (((b - p - a) == 0) ||
((b - p - a) > 1));
//[9] define (b - p) as N temporarily
int N = (b - p);
results[8] = (N > 0) && (a > 1) && (((N - a) == 0) || ((N - a) > 1));
//[10] rewrite the disjunction to isolate a
results[9] = (N > 0) && (a > 1) && ((a == N) || (a < (N - 1)));
//[11] expand the disjunction
results[10] = ((N > 0) && (a > 1) && (a == N)) ||
((N > 0) && (a > 1) && (a < (N - 1)));
//[12] since (a = N) in the first subexpression we can simplify to
results[11] = ((a == N) && (a > 1)) ||
((N > 0) && (a > 1) && (a < (N - 1)));
//[13] extract common term (a > 1) and replace N with (b - p)
results[12] = (a > 1) && ((a == (b - p)) ||
(((b - p) > 0) && (a < (b - p - 1))));
//[14] extract common term (a > 1) and replace N with (b - p)
results[13] = (a > 1) && (((a - b + p) == 0) ||
(((b - p) > 0) && ((a - b + p) < -1)));
//[15] replace redundant subterms with intermediate
//variables (to make Jon Skeet happy)
int jon = (b - p);
int skeet = (a - jon); //(a - b + p) = (a - (b - p))
results[14] = (a > 1) && ((skeet == 0) ||
((jon > 0) && (skeet < -1)));
//[16] rewrite in disjunctive normal form
results[15] = ((a > 1) && (skeet == 0)) ||
((a > 1) && (jon > 0) && (skeet < -1));
return results;
}
}
// In one line:
return (a != 1) && ((b-a-p == 0) || (b-a-p > 1))
// Expanded for the compiler:
if(a == 1)
return false;
int bap = b - a - p;
return (bap == 0) || (bap > 1);
Si publica el procesador que está utilizando, puedo optimizarlo para el ensamblaje. =]
a! = 1 && ((b == a + p) || (b - p> a + 1))
Primera iteración:
bool bool1 = ((a+p) <= b) && (a == 0 || a > 1) && (b >= p);
bool bool2 = (b - (a + p) == 0) || (b - (a + p) > 1);
return bool1 && bool2;
Segunda iteración:
int value1 = b - (a + p);
bool bool1 = (value1 >= 0) && (a == 0 || a > 1) && (b >= p);
bool bool2 = (value1 == 0) || (value1 > 1);
return bool1 && bool2;
Tercera iteración (todos positivos)
int value1 = b - (a + p);
bool bool1 = (value1 >= 0) && (a != 1) && (b >= p);
bool bool2 = (value1 == 0) || (value1 > 1);
return bool1 && bool2;
4ta iteración (todos positivos)
int value2 = b - p;
int value1 = value2 - a;
bool bool1 = (value1 >= 0) && (a != 1) && (b - p >= 0);
bool bool2 = (value1 == 0) || (value1 > 1);
return bool1 && bool2;
Quinta iteración:
int value2 = b - p;
int value1 = value2 - a;
bool bool1 = (value1 >= 0) && (a != 1) && (value2 >= 0);
bool bool2 = (value1 == 0) || (value1 > 1);
return bool1 && bool2;
b >= (a+p) && a>=1
incluso b >= p es redundante ya que este siempre será el caso para a >= 1