22 abril 2013

Optimizaciones básicas de código

Cuando no basta con resolver un problema, sino que además la solución tiene que ser rápida, convendrá trabajar en dos etapas:


  1. En una primera fase, tendremos que resolver el problema, de la forma más simple posible, para garantizar que no hay errores, y deberemos hacer pruebas para intentar garantizar que se comporta bien en la mayor cantidad de casos posibles.
  2. En una segunda fase, si es necesario, buscaremos optimizaciones para mejorar su velocidad.

Vamos a ver un ejemplo básico: un programa que calcule números primos y alguna cosa más.

Nuestro programa calculará la suma de los "emirps" hasta un cierto número. Un "emirp" es un número que es primo, que también es primo cuando se invierte el orden de sus cifras, y que no es igual al número invertido. Por ejemplo, 13 y 31 son "emirps", pero 23 no lo es, porque al invertirlo se obtiene 32, que no es primo. Lo mismo ocurre con 11, que al invertirlo... se queda como estaba.

Un programa (en C#) que resolviera esto podría ser así:


 1: using System;
 2: 
 3: public class Emirps
 4: {
 5:     public static long reversed(long n)
 6:     {
 7:         string txt = Convert.ToString(n);
 8:         string txtReversed = "";
 9:         for (int i=0; i<txt.Length; i++)
10:             txtReversed = txt[i] + txtReversed;
11: 
12:         return Convert.ToInt64(txtReversed);
13:     }
14: 
15: 
16:     public static bool IsPrime(long number)
17:     {
18:         long dividers=0;
19: 
20:         for(long i=1; i <= number; i++)
21:             if(number%i==0)
22:                 dividers++;
23: 
24:         if (dividers == 2)
25:             return true;
26:         else
27:             return false;
28:     }
29: 
30: 
31:     public static bool IsEmirp(long number)
32:     {
33:         return ((number != reversed(number))
34:                 && IsPrime(number)
35:                 && IsPrime(reversed(number)));
36:     }
37: 
38: 
39:     public static void Main()
40:     {
41:         Console.Write("Enter number: ");
42:         long n = Convert.ToInt64(Console.ReadLine());
43: 
44:         long sum = 0;
45: 
46:         long startTime = Environment.TickCount;        
47: 
48:         for (long i=11; i<=n; i++)
49:             if (IsEmirp(i))
50:                 sum += i;
51: 
52:         long endTime = Environment.TickCount;
53:         long timeUsed = endTime - startTime;
54: 
55:         Console.WriteLine("Sum: "+ sum);
56:         Console.WriteLine("Milliseconds: "+timeUsed);
57:     }
58: }


Las ideas principales son:

  • El cuerpo del programa ("Main") es poco más que un "for" que suma los números hasta el que nos indiquen, si son Emirps.
  • La función "IsEmirp" aplica la definición "tal cual": debe ser distinto de el número al revés, debe ser primo y si le damos la vuelta también debe ser primo.
  • Las función "IsPrime" comprueba si el número es primo, y lo hace de la forma más ¿natural? pero también más lenta: un número es primo si sólo es divisible por sí mismo y por 1, así que buscamos todos sus divisores, y, si sólo encontramos dos, es que era primo.
  • La función "reversed" calcula el número "dado la vuelta": convierte a una cadena y va recolocando dígito a dígito en orden inverso.


Vamos a ver tiempos:

  • Para n pequeños, el tiempo es despreciable.
  • Para n=99999, un Intel i7 3630 QM, 2.40 Ghz tarda 58.234 seg
  • Si duplicamos el número, el tiempo se multiplica casi por 6: para n=222222, tarda 329.954 seg


Una primera optimización muy simple, que a veces se pasa por alto, y que puede ser muy efectiva, es cambiar el orden de las condiciones múltiples en los "if". La mayoría de lenguajes actuales usan "evaluación en cortocircuito": en cuanto se sabe que la condición no puede ser cierta (porque uno de las sub-condiciones que se compara es falsa), no se sigue analizando el resto de sub-condiciones.

En este caso, podemos probar a cambiar el orden del "if" y ver qué ocurre:


31:     public static bool IsEmirp(long number)
32:     {
33:         return (IsPrime(number)
34:                 && IsPrime(reversed(number))
35:                 && (number != reversed(number)));
36:     }


Obtenemos:

  • Para n=99999: 55.218 seg
  • Para n=222222: 311.656 seg

En este caso, como ninguna de las sub-condiciones es claramente más rápida (todavía) que la otra, la ganancia es mínima: apenas un 5% (y sí, es desconcertante que sea más rápido comprobar si es primo que si es el mismo número cuando se le da la vuelta).


Una segunda optimización es no recalcular valores que ya hemos calculado previamente: por ejemplo, calculamos dos veces el valor de "reversed(number)"; podríamos calcularlo una sola vez


31:     public static bool IsEmirp(long number)
32:     {
33:         long rev = reversed(number);
34:         return (IsPrime(number)
35:                 && IsPrime(rev)
36:                 && (number != rev));
37:     }


Pero en este caso, no hay ninguna mejora, porque el cálculo de "reversed" es más lento que el de "IsPrime".


Normalmente, las mayores mejoras vienen de analizar el algoritmo que estamos usando: ¿necesitamos realmente calcular todos los divisores y contarlos para saber si el número es primo? No. En cuanto encontremos un divisor (que no sea 1 ni el número), podemos afirmar que no era primo, y dejar de analizar, así que podríamos reescribir la función así:


16:     public static bool IsPrime(long number)
17:     {
18:         for(long i=2; i < number; i++)
19:             if(number%i==0)
20:                 return false;
21: 
22:         return true;
23:     }


En este caso, la ganancia sí es muy grande:

  • Para n=99999: 5.516 seg
  • Para n=222222: 36.570 seg

Ahora es casi 10 veces más rápido. Y con un pequeño cambio lo podemos hacer más rápido aún: si no es divisible por 2, tampoco lo será entre 4 ni entre ningún número par, así que podemos comprobar los divisores impares, saltando de 2 en 2:


16:     public static bool IsPrime(long number)
17:     {
18:         if(number%2==0)
19:             return false;
20:         for(long i=3; i < number; i+=2)
21:             if(number%i==0)
22:                 return false;
23: 
24:         return true;
25:     }



Y obtenemos:

  • Para n=99999: 2.766 seg
  • Para n=222222: 18.344 seg

Con ese pequeño cambio vuelve a ser casi el doble de rápido. Pero estamos volviendo a calcular números primos que ya habíamos calculado antes. Podemos ir crear una lista con los números primos, y luego buscar si están en la lista:


 1: using System;
 2: using System.Collections.Generic;
 3: 
 4: public class Emirps
 5: {
 6:     public static List<long> ListOfPrimes = new List<long>();
 7: 
 8:     public static void GeneratePrimes(long max)
 9:     {
10:         ListOfPrimes.Add(2);
11:         for (int n = 3; n <= max; n += 2)
12:         {
13:             int i;
14:             for (i = 3; i <= n; i += 2)
15:                 if (n % i == 0)
16:                     break;
17:             if (i>=n)
18:                 ListOfPrimes.Add(n);
19:         }
20:                 
21:     }
22: 
23: 
24:     public static long reversed(long n)
25:     {
26:         string txt = Convert.ToString(n);
27:         string txtReversed = "";
28:         for (int i = 0; i < txt.Length; i++)
29:             txtReversed = txt[i] + txtReversed;
30: 
31:         return Convert.ToInt64(txtReversed);
32:     }
33: 
34: 
35:     public static bool IsPrime(long number)
36:     {
37:         return (ListOfPrimes.BinarySearch(number) > -1);
38:     }
39: 
40: 
41:     public static bool IsEmirp(long number)
42:     {
43:         long reverse = reversed(number);
44:         return (IsPrime(number)
45:                 && IsPrime(reverse)
46:                 && (number != reverse));
47:     }
48: 
49: 
50:     public static void Main()
51:     {
52:         Console.Write("Enter number: ");
53:         long n = Convert.ToInt64(Console.ReadLine());
54: 
55:         long sum = 0;
56: 
57:         long startTime = Environment.TickCount;
58: 
59:         GeneratePrimes(n);
60: 
61:         for (long i = 11; i <= n; i++)
62:             if (IsEmirp(i))
63:                 sum += i;
64: 
65:         long endTime = Environment.TickCount;
66:         long timeUsed = endTime - startTime;
67: 
68:         Console.WriteLine("Sum: " + sum);
69:         Console.WriteLine("Milliseconds: " + timeUsed);
70:     }
71: }



Y obtenemos:

  • Para n=99999: 0.985 seg
  • Para n=222222: 4.422 seg
  • Para n=999999: 77.515 seg

Es casi 100 veces más rápido que el original. Pero aún es fácilmente mejorable: para calcular números primos existe un algoritmo muy eficiente, que ni siquiera supone hacer divisiones. Se trata de la "criba de Erastótenes". Si la aplicamos, el programa se convierte en:

 1: using System;
 2: using System.Collections.Generic;
 3: 
 4: public class Emirps
 5: {
 6:     public static bool[] IsTaggedAsPrime;
 7: 
 8:     public static void GeneratePrimes(long max)
 9:     {
10:         IsTaggedAsPrime = new bool[max + 1];
11:         for (int i = 1; i <= max; i++)
12:             IsTaggedAsPrime[i] = true;
13: 
14:         // Sieve of Eratosthenes
15:         for (int i = 2; i <= (long) Math.Sqrt(max); i++)
16:             if (IsTaggedAsPrime[i])
17:                 for (int j = i*i; j <= max; j+=i)
18:                     IsTaggedAsPrime[j] = false;
19:     }
20: 
21: 
22:     public static long reversed(long n)
23:     {
24:         string txt = Convert.ToString(n);
25:         string txtReversed = "";
26:         for (int i = 0; i < txt.Length; i++)
27:             txtReversed = txt[i] + txtReversed;
28: 
29:         return Convert.ToInt64(txtReversed);
30:     }
31: 
32: 
33:     public static bool IsPrime(long number)
34:     {
35:         try
36:         {
37:             return IsTaggedAsPrime[number];
38:         }
39:         catch (IndexOutOfRangeException)
40:         {
41:             return false;
42:         }
43:     }
44: 
45: 
46:     public static bool IsEmirp(long number)
47:     {
48:         long reverse = reversed(number);
49:         return (IsPrime(number)
50:                 && IsPrime(reverse)
51:                 && (number != reverse));
52:     }
53: 
54: 
55:     public static void Main()
56:     {
57:         Console.Write("Enter number: ");
58:         long n = Convert.ToInt64(Console.ReadLine());
59: 
60:         long sum = 0;
61: 
62:         long startTime = Environment.TickCount;
63: 
64:         GeneratePrimes(n);
65: 
66:         for (long i = 11; i <= n; i++)
67:             if (IsEmirp(i))
68:                 sum += i;
69: 
70:         long endTime = Environment.TickCount;
71:         long timeUsed = endTime - startTime;
72: 
73:         Console.WriteLine("Sum: " + sum);
74:         Console.WriteLine("Milliseconds: " + timeUsed);
75:     }
76: }

Y obtenemos:

  • Para n=99999: 0.047 seg
  • Para n=222222: 0.438 seg
  • Para n=999999: 0.516 seg
Es decir, con números grandes (999.999) es casi 150 veces más rápido que la versión anterior. Todavía se podrían hacer pequeñas mejoras, pero lo nuestro fuente ahora es cerca de 10.000 veces más rápido que al principio... lo hemos acelerado lo suficiente como para ganarnos un descanso por hoy... ;-D


1 comentario:

ficion dijo...

Dios mío, ¿cómo nadie ha publicado un comentario por esta gran entrada?

Me encantan este tipo de entradas, la verdad. ¿Cómo se pueden identificar puntos optimizables fácilmente?