Hace una semana publicaba la solución a un problema de entrevista tipo que hacen en google, la pregunta era la siguiente:
La solución que publiqué no solo daba la solución si no que brindaba los pisos desde los que se debía arrojar los objetos. Antonio Ognio complementó mi solución con una muy buena explicación del problema.
Ya había dado por cerrado el tema, hasta que Eduardo Morales, el ingeniero de Google que presentó el problema, dejó unos comentarios interesantes.
El principal reparo de Eduardo con mi solución es que no es eficiente. Es un algoritmo "O(n^2)". Como le comentaba a Eduardo, no era mi propósito hacer una solución eficiente, solo necesitaba una solución y nada más. La optimización prematura es la raiz de todos los males mencioné parafraseando a Knuth, y en este caso no necesitaba de ninguna optimización, ya que el enunciado del problema no pide un algoritmo óptimo (solo pide hayar una solución rompiendo el menor número de objetos). Para este problema, en mi opinión, optimizar representaba un costo (mi tiempo) y ningún beneficio.
Pero al mencionar Eduardo que el problema se puede optimizar hasta O(1), pues me pareció un buen ejercicio, y la optimización de código, cuando es estrictamente necesaria, puede ser bastante gratificante. Tenía entonces ahora un beneficio para optimizar: podía publicar el proceso de optimización, dedicado especialmente para aquellos que mostraron interés en mi solución original (y varios al parecer, según me comentan por privado, están leyendo a Knuth :-)
Así que veamos el proceso de optimización, si no lo han hecho, pediría que lean primero mi (ineficiente) solución original y la explicación detallada de Antonio.
Comencemos entonces por la primera optimización:
Gracias a este algoritmo tenemos esta solución en Python:
def findworst(num):
for res in range(1, num+1):
if res*(res+1)/2 >= num:
break
return res
Pero esto se puede optimizar aún mas, como podemos apreciar:
Lo que nos deja con este código en Python:
def findworst_o1(num):
return math.ceil((math.sqrt(num*8+1)-1)/2)
que es una solución O(1), constante, y en una línea de código.
Podemos sacar algunas lecciones con todo esto:
- La optimización prematura no es necesaria. El algoritmo original, a pesar de no ser óptimo, nos daba una solución correcta. El costo de optimizar (tiempo) era mas alto que los beneficios (nulos). Esto cambió con los comentarios de Eduardo ya que apareció un beneficio: mostrar el proceso de optimización para los lectores.
- Tener una base matemática es muy importante. De no haber aplicado matemáticas la solución se hubiera hallado con "fuerza bruta" pero no con eficiencia.
Comentarios?
tags: edificio, entrevista, google, knuth, nerd, solucion, taocp, optimizacion, algoritmos, python
