ChichaPlanet

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

que es una solución O(n)

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.

Muchas gracias Eduardo por tus comentarios, espero que estos posts despierten el interés de mis lectores técnicos para investigar estos temas. Y para mis lectores no técnicos (se supone que este es mi blog no-nerd), mil disculpas, prometo volver pronto a la normalidad ;-)

Comentarios?

tags: edificio, entrevista, google, knuth, nerd, solucion, taocp, optimizacion, algoritmos, python

by tabo at 4:08 AM under algoritmos , edificio , entrevista , google , knuth , nerd , optimizacion , python , solucion , taocp

#!/usr/bin/env python

def findsteps(numpisos):
res = 1
while True:
l = []
val = 0
for step in range(res, 0, -1):
val += step
if val >= numpisos:
l.append(numpisos)
break
l.append(val)
if val >= numpisos:
break
res += 1
return l

if __name__ == '__main__':
import sys
if len(sys.argv) > 1:
try:
numpisos = int(sys.argv[1])
except ValueError, errmsg:
sys.stdout.write('ERROR: num de pisos debe ser un entero\n')
sys.exit(-1)
else:
numpisos = 100
if numpisos < 1:
sys.stdout.write('ERROR: num de pisos debe ser un >= 1\n')
sys.exit(-1)
print '# Pisos-intervalo para edificio de %d pisos: \n' % (numpisos,)
res = findsteps(numpisos)
print res
print '# %d intentos en el peor escenario' % (res[0],)

ChichaPlanet

ChichaPlanet

What people talk about