¿Bibliotecas de memorización para C?

memoization

Question

Para un proyecto en el que estoy trabajando, hay una serie de estados en los que se puede confiar en los cálculos para obtener los mismos resultados (y no tener efectos secundarios). La solución obvia sería utilizar la memoria para todas las funciones costosas.

Necesitaría una memoria que maneje más de un estado (para poder invalidar un conjunto de caché sin invalidar otro). ¿Alguien sabe una buena biblioteca de C para este tipo de cosas? (Tenga en cuenta que no puede ser C ++, estamos hablando de C.)

He trabajado con algunas buenas implementaciones en Python que usan decoradores para poder memorizar de manera flexible un montón de funciones diferentes. Me pregunto si hay una biblioteca genérica que podría hacer cosas similares con C (aunque probablemente con una función explícita ajustada en lugar de una sintaxis conveniente). Simplemente creo que sería una tontería tener que agregar el almacenamiento en caché a cada función de forma individual. Cuando se trata de un problema suficientemente común, debe haber algunas soluciones listas para usar.

Las características que buscaría son las siguientes:

1. Puede almacenar en caché funciones con varios tipos de entrada y salida
2. Administra múltiples cachés diferentes (para que pueda tener caché a corto y largo plazo)
3. Tiene buenas funciones para invalidar cachés.
4. Diseñado para ser usado por funciones de envoltura, en lugar de alterar funciones existentes

¿Alguien sabe una implementación de C que pueda manejar todos o la mayoría de estos requisitos?

Answer 1

¿Por qué, simplemente no puede ser C ++?

Solo por un punto de partida, mire a esta función de memoria:

declaración:

template<typename T, typename F>
auto Memoize(T key, F function) {
  static T memory_key = key;
  static auto memory = function(memory_key);
  if (memory_key != key) {
    memory_key = key;
    memory = function(memory_key);
  }

  return memory;
}

Ejemplo de uso:

auto index = Memoize(value, IndexByLetter);

Answer 2

De acuerdo, ya que no había bibliotecas de memoización para C y estaba buscando una solución inmediata para memorizar las funciones de C existentes en una base de código, hice mi propia pequeña biblioteca de memoización que estoy liberando bajo el APL 2.0. Con suerte, la gente lo encontrará útil y no se estrellará ni quemará en otros compiladores. Si tiene problemas, envíeme un mensaje aquí y lo investigaré cada vez que tenga el tiempo (que probablemente se mediría en incrementos de meses).

Esta biblioteca no está diseñada para la velocidad, pero funciona y se ha probado para garantizar que sea bastante fácil de usar y no muestre ninguna pérdida de memoria en mis pruebas. Fundamentalmente, esto me permite agregar memoria a funciones similares al patrón de decoración al que estoy acostumbrado en Python.

La biblioteca se encuentra actualmente en SourceForge como la Biblioteca C-Memo . Viene con un pequeño manual de usuario y un par de bibliotecas de terceros con licencia permisiva para hashing genérico. Si la ubicación cambia, intentaré actualizar este enlace. Encontré esto útil para trabajar en mi proyecto, espero que otros lo encuentren útil para sus proyectos.

Answer 3

memoization está casi incorporada en el lenguaje haskell. Puedes llamar a esta funcionalidad desde c

Actualizar:
Todavía estoy aprendiendo sobre programación funcional, pero sé que la memorización es bastante común en la programación funcional porque las características del lenguaje lo hacen fácil. Estoy aprendiendo f #. No sé haskell, pero es el único lenguaje funcional que conozco que interactuará con c. Es posible que pueda encontrar otro lenguaje de programación funcional que interactúe con c de una manera más adecuada que la que proporciona haskell.