Durante mi carrera universitaria, en diversas materias nos hacían optimizar el código para obtener los mejores resultados posibles en lo que a eficiencia / tiempo de ejecución se refiere. Ha día de hoy esto parece no ser tan importante: hay supercomputadoras incluso en el mismo escritorio del usuario final que lo hacen todo rapidísimo aun metiéndole auténtica basura (las cosas como son). De ahí la crítica de los desarrolladores backend hacia los frontend (en teoría, INSISTO, en teoría, los menos eficientes en lo que a optimación de código se refiere).
¿Qué hacéis metiendo un for dentro de otro for y luego dentro de otro for más? En mis tiempos, eso podía romper el programa. Otro ejemplo son los SELECT que se hacen sobre las bases de datos por parte de algunos junios (y no tan juniors), donde se extrae información innecesaria para lo que se necesita (una fecha, una cantidad de artículos que quedan en stock, etc. son suficientes en algunos casos).
De cara a mostraros como trabajo (OJO, seguro que hay mil cosas que encontraréis que se puedan mejorar, se agradecen comentarios), os pondré un ejemplo que me ha «llegado» para su optimización: realizar una comprobación masiva de si un conjunto de números son de forma individual primos o no.
Podéis descargar el código desde mi GitHub: https://github.com/irotdev (dentro de PHPLogicProblems, MyInvestigations, con el nombre de prime-numbers.php)
Para realizar esta pequeña prueba, lo primero que hago es crearme funciones básicas. Una de ella es un generador de números a comprobar, los cuales tienen en cuenta la cantidad de números que se desea probar ($numbersToCheck) y el valor máximo que puede tener dicho número ($maxNumber). Esos números se obtienen de forma aleatoria por lo que la ejecución de las comprobaciones puede tardar menos o más (aunque normalmente tiempos similares), lo cual depende también de mi sistema y de lo que esté haciendo en ese momento.
function getRandomListOfNumbers($numbersToCheck, $maxNumber): Array {
$listOfNumbers = array();
for ($i = 0; $i < $numbersToCheck; $i++) $listOfNumbers[] = rand(2, $maxNumber);
return $listOfNumbers;
}Hay otras funciones que creo para cosas secundarias como la propia para obtener el listado de números primos (la cual utiliza la función isPrime0 e isPrime1, las menos eficientes) y una función para mostrar la lista de dichos números primos:
function listOfPrimeNumbers($numMaxToCheck): array {
$primeNumbers = array();
$primeNumbers[] = 2;
for ($i = 3; $i <= $numMaxToCheck; $i++) {
$isPrime = true;
foreach ($primeNumbers as $value) {
if ($i % $value == 0) {
$isPrime = false;
break;
}
}
if ($isPrime) $primeNumbers[] = $i; // Add a new number prime
}
return $primeNumbers;
}
function showListOfPrimeNumbers($numMaxToCheck) {
$listPrimeNumbers = listOfPrimeNumbers($numMaxToCheck);
foreach ($listPrimeNumbers as $value)
echo $value . " ";
}Como es lógico, hay una función principal que es la que uso para llamar a las funciones que comprobarán uno a uno si un valor es o no primo con una u otra función, lo cual se utilizará para comprobar su tiempo de ejecución y por tanto su eficiencia:
function theChecker($numbersToCheck, $maxNumber): void {
echo "<br><br>**************************************************<br>";
echo "***** [$numbersToCheck] numbers to check with a maximum of [$maxNumber]";
echo "<br>**************************************************<br><br>";
$listOfNumbersToCheck = getRandomListOfNumbers($numbersToCheck, $maxNumber);
// isPrime0
echo "Checking 'isPrime0':<br>";
$time_start = microtime(true);
foreach ($listOfNumbersToCheck as $value) {
echo " [$value is" . (isPrime0($value, $maxNumber) ? " TRUE" : " FALSE") . "] ";
}
$time_end = microtime(true);
$diff = $time_end - $time_start;
echo "<br>isPrime0 TIME: " . number_format($diff, 10) . "<br><br><br>";
// isPrime1
echo "Checking 'isPrime1':<br>";
$time_start = microtime(true);
$listPrimeNumbers = listOfPrimeNumbers($maxNumber);
foreach ($listOfNumbersToCheck as $value) {
echo " [$value is" . (isPrime1($value, $listPrimeNumbers) ? " TRUE" : " FALSE") . "] ";
}
$time_end = microtime(true);
$diff = $time_end - $time_start;
echo "<br>isPrime1 TIME: " . number_format($diff, 10) . "<br><br><br>";
...
}Prueba para 1 número con el número más grande de hasta 100000:
Para empezar las pruebas, utilizaré 4 funciones para hacer lo mismo pero de forma distinta.
Por un lado, isPrime0 e isPrime1, los cuales comprueban si el número pasado está dentro de la lista de números primos generada con anterioridad (isPrime0 lo genera en cada llamada e isPrime1 lo genera una vez para todas las llamadas que se haga a esa función). Ambos usan la función listOfPrimeNumbers antes indicada:
function isPrime0($num, $maxNumberToCheck): bool {
$listPrimeNumbers = listOfPrimeNumbers($maxNumberToCheck);
foreach ($listPrimeNumbers as $numPrime)
if ($num == $numPrime)
return true;
return false;
}
function isPrime1($num, $listPrimeNumbers): bool {
return in_array($num, $listPrimeNumbers);
}Por otro lado, isPrime2 e isPrime3, los cuales recorren y comprueban 1 a 1 desde el número 2. Los diferencia una cosa muy sencilla pero que ahorrará tiempo, y es que isPrime3 no recorre todos los números desde 2 hasta el número actual a comprobar, sino hasta la raíz cuadrada de dicho número a comprobar. ¿El motivo? Si un número no es divisible por su un valor inferior al de su raíz cuadrada, no será divisible por ningún otro (esto son matemáticas básicas).
function isPrime2($num): bool {
for ($i = 2; $i < $num; $i++)
if ($num % $i == 0)
return false;
return true;
}
function isPrime3($num): bool {
for ($i = 2; $i <= sqrt($num); $i++)
if ($num % $i == 0)
return false;
return true;
}Además, añado isPrime4, el cual me «ahorra» el calcular la raíz cuadrada en cada vuelta del bucle. Lo que hago es almacenarla en una variable y cuando hay muchas comprobaciones (el número a comprobar si es primo es muy elevado) entonces mejorará el tiempo de ejecución:
function isPrime4($num): bool {
$max = sqrt($num);
for ($i = 2; $i <= $max; $i++)
if ($num % $i == 0)
return false;
return true;
}En las pruebas realizadas se nota una clara diferencia entre las funciones isPrime0 e isPrime1 respecto a las de isPrime2 e isPrime3. En algunos casos marca 0.0000000000 de tiempo de ejecución y en otros 0.0000009537 (entre otros), siendo esta última cifra muy repetida, lo que me lleva a pensar que es un tiempo mínimo que coge mi máquina (podría investigar sobre ello pero no me llama la atención, es un tiempo ínfimo).
Tiempos para el número máximo de 100:
- isPrime4: 0.0000009537
- isPrime3: 0.0000009537
- isPrime2: 0.0000009537
- isPrime1: 0.0000159740
- isPrime0: 0.0000209808
Tiempos para el número máximo de 100000:
- isPrime4: 0.0000009537
- isPrime3: 0.0000009537
- isPrime2: 0.0000009537
- isPrime1: 0.8091838360
- isPrime0: 0.8060331345
Prueba para 5 números con el número más grande 100000 (1 millón, aumentando 1 cero):
Dado que los resultados eran bastante simples, decidí aumentar a 5 pruebas (números a comprobar) y con unos máximos más grandes (hasta 1 millón puede ser cada uno de esos números). Aquí los resultados evidenciaban que los códigos de isPrime0 e isPrime1 eran mucho menos eficiente. No es buena idea, al menos con 5 números a comprobar, realizar un listado con todos los primos posibles:
Tiempos para el número máximo de 100:
- isPrime4: 0.0000009537
- isPrime3: 0.0000021458
- isPrime2: 0.0000050068
- isPrime1: 0.0000109673
- isPrime0: 0.0000531673
Tiempos para el número máximo de 100000:
- isPrime4: 0.0000040531
- isPrime3: 0.0000059605
- isPrime2: 0.0000038147
- isPrime1: 0.8105370998
- isPrime0: 4.0665309429
Dados los resultados y viendo que isPrime0 e isPrime1 no pueden competir con las otras funciones, las descarto para las siguientes pruebas.
Prueba para 50 números con el número más grande 10000000 (10 millones, aumentando otro cero):
Al aumentar significativamente la cantidad de números a comprobar si son o no primos, el tiempo de ejecución aumenta significativamente en la función de isPrime2, y apenas un poco en isPrime3 e isPrime4. En todo caso, aquí si que no hay lugar a dudas y muestra cómo isPrime4 es mejor a isPrime3 que a su vez es mejor a isPrime2.
Tiempos para el número máximo de 100:
- isPrime4: 0.0000100136
- isPrime3: 0.0000121593
- isPrime2: 0.0000159740
Tiempos para el número máximo de 10000000:
- isPrime4: 0.0003030300
- isPrime3: 0.0005500317
- isPrime2: 0.5178680420
Buscando el límite en la peor función, prueba para 100 números con el número más grande 1000000000 (añado dos 0, ya son 1000 millones):
Pues si, me quedé en el borde de mi i5 de 11ª generación y 64GB de RAM… Se puede ampliar el tiempo de ejecución de PHP (no sé si lo sabréis) pero no me hizo falta. Aquí me va «sobrando» el caso de isPrime2, el cual disparó mi tiempo de ejecución a 35 segundos en el peor de los casos. Las otras funciones, sin embargo, ni media centésima de segundo. Destaco los dos casos más grandes:
Tiempos para el número máximo de 100000000:
- isPrime4: 0.0011880398
- isPrime3: 0.0018908978
- isPrime2: 6.6131939888
Tiempos para el número máximo de 1000000000:
- isPrime4: 0.0018699169
- isPrime3: 0.0033600330
- isPrime2: 35.8763570786
Optimizando el código, añadiendo una nueva función a partir de la idea de recorrer «la mitad».
A partir de aquí dejaré atrás la función isPrime2, tras ver que su tiempo de ejecución se dispara. La idea de una nueva función, isPrime5, es la de «saltar» de 2 en 2 las comprobaciones ya que, teniendo en cuenta que todos los números pares no son primos (a excepción del 2), es absurdo comprobar que un número muy grande es primo (como 938416837, el cual es primo) y, para llegar hasta ahí, se haya comprobado si es divisible entre los números 4, 6, 8, 10, 12, …. 12992132132, 12992132134… Con solo comprobar si es divisible entre 2 sería más que suficiente.
function isPrime5($num): bool {
$max = sqrt($num);
if ($num % 2 == 0) return false;
for ($i = 3; $i <= $max; $i+=2)
if ($num % $i == 0)
return false;
return true;
}Eso provocaría que el número de comprobaciones pasase a la mitad cuando hay un número primo grande impar (si hay muchos primos grandes, el tiempo se dispararía). Los resultados fueron los predecibles:
Tiempos para el número máximo de 100000000:
- isPrime5: 0.0007750988
- isPrime4: 0.0011410713
- isPrime3: 0.0025339127
Tiempos para el número máximo de 1000000000:
- isPrime5: 0.0019609928
- isPrime4: 0.0033550262
- isPrime3: 0.0071518421
Optimizando lo optimizado, atajando los números pares y los divisibles entre 3.
Dándole una vuelta más, creo isPrime6 y paso a la siguiente lógica: Ya había quitado para que no analizase los números pares. Ahora quiero quitar que analice los números divisibles entre 3. Ahora bien, el sumatorio ya no queda igual de bonito ($i+=2), sino que quedaría como un ($i+=6) pero haciendo la comprobación también de +2 de $i, es decir, 2 comprobaciones: el nuevo $i y el $i+2:
| Valor $i | Divisible 2 | Divisible 3 | Acción a realizar |
|---|---|---|---|
| 2 | SI | ||
| 3 | SI | ||
| 4 | SI | ||
| 5 | Comprobar si es primo | ||
| 6 | SI | SI | |
| 7 | Comprobar si es primo | ||
| 8 | SI | ||
| 9 | SI | ||
| 10 | SI | ||
| 11 | Comprobar si es primo | ||
| 12 | SI | SI | |
| 13 | Comprobar si es primo | ||
| 14 | SI | ||
| 15 | SI | ||
| 16 | SI | ||
| 17 | Comprobar si es primo | ||
| 18 | SI | SI | |
| 19 | Comprobar si es primo | ||
| 20 | SI |
Viendo esto, se ve el salto de 5 y 7 hacia 11 y 13, y luego hacia 17 y 19. Es decir, hay que añadir un salto de 6 (el resultado de 2×3), cogiendo dicho resultado y sumando 2 (5+6 = 11 y sumando 2 es = 13). Los resultados son incluso mejor que lo esperado:
function isPrime6($num): bool {
$max = sqrt($num);
if (($num % 2 == 0) || ($num % 3 == 0)) return false;
for ($i = 5; $i <= $max; $i+=6)
if (($num % $i == 0) || ($num % ($i+2) == 0))
return false;
return true;
}Tiempos para el número máximo de 1000000000:
- isPrime6: 0.0008680820
- isPrime5: 0.0017590523
- isPrime4: 0.0033211708
- isPrime3: 0.0060191154
En principio, si se añade esto para los números divisibles entre 5, 7, 11, 13, 17, 19 y algunos números primos más iniciales, la eficiencia puede crecer más. La pregunta es, ¿es necesario? Depende. Si me piden calcular una cantidad disparatada de números de un tamaño bastante grande SI merecería la pena. Pero viendo que la comprobación de 100 números de un valor de hasta 1000000000 (1.000.000.000, es decir, 1000 millones) es de solo 6 centésimas de segundo… muy disparatada debe de ser la cantidad de números.
Podría ampliarse en una ampliación de pruebas para ello. No obstante, si alguno es tan friki como yo como para haber llegado hasta esta línea, siéntete libre de bajarte el código de GitHub y seguir haciendo pruebas. Se agradece un enlace o reconocimiento en tal caso please ;-)
joseMMsimo 
Debe estar conectado para enviar un comentario.