Optimización BUD

Esta es una de las técnicas sino la técnica de optimización más conocidas. BUD es un acrónimo en ingles que describe 3 pasos en los cuales tú algoritmo podría ser mas eficiente.

• 🍼 Cuellos de Botella (Bottlenecks)
• 👷 Trabajo innecesario (Unnecessary Work)
• 📚 Trabajo duplicado (Duplicated Work)

Esta técnica podría ser una de tus primeras opciones después de desarrollar una solución a fuerza bruta. Ya que se enfoca en detectar maneras en las cuales podríamos mejorar el tiempo (Runtime) de tu algoritmo.

🍼 Cuellos de Botella

Esto se refiere a una o unas partes especificas de tu algoritmo que incrementan el tiempo total de tú algoritmo. Esto ocurre de dos formas:

1. Sí tienes un algoritmo de varias etapas y uno de los runtimes es mayor que los otros - un cuello de botella ocurrirá naturalmente. Por ejemplo sí tienes un algoritmo que primero ordena los elementos del Array O(N log N) y después busca un elemento dentro del array O(N). Te podrías enfocar en reducir el segundo paso a algo como O(Log N) o incluso O(1), pero aun tendrías el problema de que el primer paso del algoritmo es (N Log N). Por lo tanto este debería ser el enfoque de tu optimización.
2. Cuando tienes un trozo de trabajo en el cual se repiten muchas operaciones - por ejemplo una búsqueda O(N) - esto probablemente se podría llegar a optimizar a O(Log N) o O(N).

Ejemplo

Sí tienes una función que tiene dos argumentos, el primero un array que cuenta únicamente con números distintos. El segundo un número (K) que sera utilizado para encontrar las parejas de números que tienen esa diferencia. Por ejemplo Array {1, 7, 5, 9, 2, 12, 3} y K = {2}. Habrán cuatro pares de números dentro del array con diferencia de dos: (1, 3), (3, 5), (5, 7), (7, 9).

Un algoritmo a fuerza bruta haría algo como tener 2 loops para ir comparando cada elemento contra los otros elementos del array e incrementando un contador por cada par que tiene la diferencia que queremos. Esto es bastante ineficiente ya que tenemos un loop dentro de otro loop O(N ˆ 2).

Una forma de optimizar este tiempo seria ordenar primero el array O(N Log N) y después tener un loop para hacer las comparaciones O(N). Pero aun así este tiempo se podría mejorar. Habría alguna forma de optimizar el tiempo cuando tenemos un array no ordenada?

La respuesta es con un HashMap. Después podremos iterar sobre el array viendo si el elemento es + K o - K. Y esto tendrá un tiempo estimado de O(N).

😦 Trabajo innecesario

Muchas veces después de llegar a una solución a fuerza bruta, una pregunta que nos podríamos hacer es, podríamos reformular la solución? Un ejemplo:

Pregunta: Imprima todos los números enteros positivos de esta ecuación, A2 + B2 = C2 + D2 donde A, B, C y D son números enteros entre 1 y 1000.

Solución a fuerza bruta: 4 loops - cada uno dentro del otro. Que nos daría un runtime de O(N ^ 4)

n = 1000

for a from 1 to n {
  for b from 1 to n {
    for c from 1 to n {
      for d from 1 to n {
        if (a^2 + b^2 == c^2 + d^2)
          print a, b, c, d
      }
    }
  }
}

Esto se podría mejorar si re-escribimos la ecuación así: a2 + b2 = c2 + d2 d = sqrt(a2 + b2 - c2)

n = 1000

for a from 1 to n {
  for b from 1 to n {
    for c from 1 to n {
      d = Math.sqrt(Math.pow(a^2 + b^2 - c^2))
      if (a^2 + b^2 == c^2 + d^2)
        print a, b, c, d
    }
  }
}

😟 Trabajo duplicado

Si utilizamos el mismo problema y una solución a fuerza bruta igual a la anterior, nos podemos dar cuenta de que tenemos trabajo duplicado que podríamos simplemente guardar en un HashMap.

// pseudo codigo
n = 1000
myMap[resultado][listaDeParejas]

for c from 1 to n {
  for d from 1 to n {
    resultado = c^2 + d^2
    append (c,d) to myMap[resultado]
  }
}

forEach resultado in myMap {
  forEach pair1 in listaDeParejas {
    forEach pair2 in listaDeParejas {
      print (pair1, pair2)
    }
  }
}

Utilizando el HashMap para guardar cada resultado que ya hemos computado podríamos reducir el tiempo a O(N ^ 2).

Ejemplos prestados del libro “Cracking the coding interview”