Implementación caché para minimizar cálculos

Una de las reglas de optimización más importantes es la de no repetir cálculos innecesariamente.

Guardando resultados intermedios y reutilizándolos cuando sea posible se mejora el rendimiento espectacularmente, en el ejemplo se consigue una ganancia casi lineal.

La clase NoCache sería la forma tradicional de implementar esta clase, a continuación la clase Cache optimizada para lecturas sucesivas sin repetir el cálculo si no es necesario.

#!/usr/bin/python

class NoCache:
 def __init__(self):
  self.lista = range(1,900000)
 
 def getLista(self):
  return self.lista
  
 def setLista(self,value):
  lista.append(self.value)
 
 def getMedia(self):
  return reduce((lambda n,m:n+m),self.lista) / len(self.lista)
 

class Cache:
 def __init__(self):
  self.lista = range(1,900000)
  self.__actualizado = False
 
 def getLista(self):
  return self.lista
  
 def setLista(self,value):
  self.__actualizado = False
  lista.append(self.value)
 
 def getMedia(self):
  if self.__actualizado:
   return self.__sumaCache
  else:
   self.__sumaCache = reduce((lambda n,m:n+m),self.lista) / len(self.lista)
   self.__actualizado = True
   return self.__sumaCache
 

n = NoCache()
for i in range(5):
 print n.getMedia()
 
 
c = Cache()
for i in range(5):
 print c.getMedia()

El mismo ejemplo en ruby.

#!/usr/bin/ruby

class NoCache
 def initialize
  @lista = Array.new(900000){|i| i+1}
 end

 def getLista
  return @lista
 end
 
 def setLista(value)
  @lista << value
 end
 
 def getMedia
  @lista.inject{|sum, n| sum+n} / @lista.size
 end 
end

class Cache
 def initialize
  @lista = Array.new(900000){|i| i+1}
  @actualizado = false
 end

 def getLista
  return @lista
 end
 
 def setLista(value)
  @actualizado = false
  @lista << value
 end
 
 def getMedia
  if @actualizado
   @sumaCache
  else
   @sumaCache = @lista.inject{|sum, n| sum+n} / @lista.size
   @actualizado = true
   @sumaCache
  end
 end 
end
 
n = NoCache.new
5.times{puts n.getMedia}

c = Cache.new
5.times{puts c.getMedia}

Otro resultado inesperado en este ejemplo es la gran diferencia de velocidad entre estos dos lenguajes.

En python en mi máquina este ejemplo tarda en ejecutarse 7 segundos, en ruby 1 minuto y 28 segundos. Para este ejemplo python es ¡12 veces más rápido que ruby!.