¿Qué tipo de funciones son candidatas para la memorización?

Question

Me decidí por PostSharp (indistinguible from magic) para leer los atributos y funciones de memoize . El hash de la llamada de función será la clave y el caché (en Velocity ) el resultado se devolverá en lugar de volver a llamar a la función. Fácil peasy, mac-and-cheesy.

Ya he dado arriba en poder detectar efectos secundarios en funciones decoradas, lo que resultó ser un "problema difícil", incluso para los expertos, que ciertamente no lo soy. A continuación, debo averiguar qué otras funciones son candidatas para la memorización.

• ¿Qué sucede con los métodos que toman tipos de referencia complejos como parámetros?
• ¿Qué sucede con los métodos que dependen de los datos dentro de las instancias desde las que se llama?

Los objetos de datos de ActiveRecord-esque vienen a la mente en este último.

¿Tendré que refactorizar el código de una semana para admitir la memorización?

Answer 1

Solo puede memorizar una función si todas sus entradas son tipos de valor o tipos de referencia inmutables, si devuelve un tipo de valor o una nueva instancia de un tipo de referencia, y si no tiene efectos secundarios. Periodo.

La memorización depende de un mapeo determinístico entre entradas y salidas. Cada llamada a F (a, b, c) en la que a, b, yc contienen los mismos valores debe devolver el mismo resultado para que la memorización sea posible.

Si un parámetro es un tipo de referencia, entonces aunque su valor no cambie, las llamadas múltiples a la función que lo usa pueden producir un resultado diferente. Un ejemplo trivial:

public int MyFunction(MyType t)
{
   return t.Value;
}

Console.WriteLine(MyFunction(t));
t.Value++;
Console.WriteLine(MyFunction(t));

De manera similar, si una función depende de un valor externo a ella, entonces múltiples llamadas a esa función con los mismos parámetros pueden devolver resultados diferentes:

int Value = 0;

public int MyFunction(int input)
{
   return Value;
}

Console.WriteLine(MyFunction(1));
Value++;
Console.WriteLine(MyFunction(1));

Y el cielo te ayudará si tu función memoized hace algo más que devolver un valor o un nuevo tipo de referencia:

int Value = 0;

public int MyFunction(int input)
{
   Value++;
   return input;
}

Si llama a esa función 10 veces, Valor será 10. Si lo refactoriza para usar la memoria y luego la llama 10 veces, Valor será 1.

Puedes comenzar a recorrer el camino de averiguar cómo memorizar el estado, para que puedas falsificar una función que memorice un tipo de referencia. Pero lo que realmente está memorizando es el conjunto de valores sobre los que trabaja la función. De manera similar, puede piratear una función memoizada que tiene efectos secundarios para que sus efectos secundarios ocurran antes de la memorización. Pero todo esto está pidiendo problemas.

Si desea implementar la memorización en una función que toma un tipo de referencia, el enfoque adecuado es refactorizar la parte de la función que solo funciona en los tipos de valor, y memorizar esa función, por ejemplo:

public int MyFunction(MyType t)
{
   return t.Value + 1;
}

a esto:

public int MyFunction(MyType t)
{
   return MyMemoizableFunction(t.Value);
}

private int MyMemoizableFunction(int value)
{
   return value + 1;
}

Cualquier otro enfoque para implementar la memoización que tome a) hace lo mismo, a través de medios más oscuros, o b) no funcionará.

Answer 2

Bueno, cualquier función, en teoría, es un candidato para la memorización. Sin embargo, recuerde que la memoria tiene que ver con intercambiar espacio por velocidad -

En general, esto significa que, cuanto más estado requiera o dependa una función para calcular una respuesta, mayor será el costo de espacio, lo que reduce la conveniencia de memorizar el método.

Ambos ejemplos son básicamente casos en los que se necesita guardar más estados. Esto tiene dos efectos secundarios.

Primero, esto requerirá mucho más espacio de memoria para memorizar la función, ya que será necesario guardar más información.

Segundo, esto potencialmente ralentizará la función memorizada, ya que cuanto mayor sea el espacio, mayor será el costo de la búsqueda de la respuesta, así como mayor el costo para determinar si un resultado se guardó o no previamente.

En general, tiendo a considerar solo las funciones que tienen pocas entradas posibles y bajos requisitos de almacenamiento, a menos que haya un costo muy alto al calcular la respuesta.

Reconozco que esto es vago, pero esto es parte del "arte". en arquitectura No hay "correcto" responda sin implementar ambas opciones (funciones memorizadas y no memorizadas), creación de perfiles y medición.

Answer 3

Ya ha pensado en una forma de proporcionar una solución AOP para proporcionar una memorización en torno a la función Foo , entonces, ¿qué queda por resolver?

Sí, puede pasar un objeto de complejidad arbitraria como parámetro a una función memorizada, siempre que sea inmutable, como lo son todas las cosas de las que depende. Nuevamente, esto no es fácil de descubrir estáticamente en este momento.

¿Sigues pensando en la idea de que puedes examinar el código de forma estática para asesorar a los usuarios sobre la pregunta " ¿Es una buena idea aplicar la memorización para funcionar Foo ? "

Si cumple uno de sus requisitos, se unirá a un esfuerzo de investigación global que ha durado muchos años hasta ahora. Depende de lo ambicioso que seas, supongo.