Comment écrire une fonction memoize générique?
https://stackoverflow.com/questions/129877
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'écris une fonction pour rechercher les numéros de triangle et la manière naturelle l'écrire est récursivement:
function triangle (x)
if x == 0 then return 0 end
return x+triangle(x-1)
end
Cependant, la tentative de calcul des 100 000 premiers nombres de triangles échoue avec un débordement de pile après un certain temps. C’est une fonction idéale pour mémoize , mais je souhaite une solution qui mémorise toutes les fonctions que je lui transmets. .
La solution
Je parie que quelque chose comme ceci devrait fonctionner avec des listes d'arguments variables dans Lua:
local function varg_tostring(...)
local s = select(1, ...)
for n = 2, select('#', ...) do
s = s..","..select(n,...)
end
return s
end
local function memoize(f)
local cache = {}
return function (...)
local al = varg_tostring(...)
if cache[al] then
return cache[al]
else
local y = f(...)
cache[al] = y
return y
end
end
end
Vous pourriez probablement aussi faire quelque chose d'intelligent avec un méta-tables avec __tostring afin que la liste d'arguments ne soit convertie qu'avec un tostring (). Oh les possibilités.
Autres conseils
Mathematica a une méthode particulièrement simple pour faire de la mémorisation, en s’appuyant sur le fait que les hachages et les appels de fonction utilisent la même syntaxe:
triangle[0] = 0;
triangle[x_] := triangle[x] = x + triangle[x-1]
C'est ça. Cela fonctionne parce que les règles pour les appels de fonction de correspondance de modèle sont tels qu’elle utilise toujours une définition plus spécifique avant une définition plus générale.
Bien sûr, comme cela a été souligné, cet exemple a une solution fermée: triangle [x_]: = x * (x + 1) / 2 . Les chiffres de Fibonacci sont l'exemple classique de l'ajout de la mémoisation à une accélération drastique:
fib[0] = 1;
fib[1] = 1;
fib[n_] := fib[n] = fib[n-1] + fib[n-2]
Bien que cela aussi ait un équivalent sous forme fermée, bien que plus encombrant: http: //mathworld.wolfram. com / FibonacciNumber.html
Je ne suis pas d'accord avec la personne qui a suggéré que cela était inapproprié pour une mémoisation, car vous pouviez "utiliser une boucle". Le point de mémoization est que tous les appels de fonction répétés sont à l'heure O (1). C'est beaucoup mieux que O (n). En fait, vous pourriez même imaginer un scénario dans lequel l’implémentation mémoisée offre de meilleures performances que l’implémentation en forme fermée!
Vous posez également la mauvaise question pour votre problème initial;)
C’est un meilleur moyen pour ce cas:
triangle (n) = n * (n - 1) / 2
De plus, en supposant que la formule n’ait pas une solution aussi nette, la mémorisation serait toujours une mauvaise approche ici. Vous feriez mieux d'écrire une simple boucle dans ce cas. Voir cette réponse pour une discussion plus détaillée.
En C # 3.0 - pour les fonctions récursives, vous pouvez faire quelque chose comme:
public static class Helpers
{
public static Func<A, R> Memoize<A, R>(this Func<A, Func<A,R>, R> f)
{
var map = new Dictionary<A, R>();
Func<A, R> self = null;
self = (a) =>
{
R value;
if (map.TryGetValue(a, out value))
return value;
value = f(a, self);
map.Add(a, value);
return value;
};
return self;
}
}
Ensuite, vous pouvez créer une fonction Fibonacci mémoisée comme ceci:
var memoized_fib = Helpers.Memoize<int, int>((n,fib) => n > 1 ? fib(n - 1) + fib(n - 2) : n);
Console.WriteLine(memoized_fib(40));
En Scala (non testé):
def memoize[A, B](f: (A)=>B) = {
var cache = Map[A, B]()
{ x: A =>
if (cache contains x) cache(x) else {
val back = f(x)
cache += (x -> back)
back
}
}
}
Notez que cela ne fonctionne que pour les fonctions d’arity 1, mais avec le currying vous pourriez le faire fonctionner. Le problème le plus subtil est que memoize (f)! = Memoize (f) pour toute fonction f . Un moyen très sournois de résoudre ce problème pourrait être le suivant:
val correctMem = memoize(memoize _)
Je ne pense pas que cela compilera, mais cela illustre bien l'idée.
Mise à jour : des commentateurs ont souligné que la mémorisation était un bon moyen d'optimiser la récursivité. Certes, je n'avais pas envisagé cela auparavant, car je travaille généralement dans un langage (C #) où la mémorisation généralisée n'est pas si simple à construire. Prenez le message ci-dessous en gardant à l’esprit ce grain de sel.
Je pense que Luke a probablement la solution la plus appropriée à ce problème, mais la mémorisation n’est généralement pas la solution à tout problème de débordement de pile.
Le débordement de pile est généralement causé par une récursion plus profonde que la plate-forme ne peut gérer. Les langues prennent parfois en charge la récursion de la queue " ;, qui réutilise le contexte de l'appel en cours. , plutôt que de créer un nouveau contexte pour l'appel récursif. Mais beaucoup de langages / plates-formes grand public ne le supportent pas. C # n'a pas de support inhérent pour la récursion de queue, par exemple. La version 64 bits du .NET JITter peut l’appliquer en tant qu’optimisation au niveau IL, ce qui est pratiquement inutile si vous devez prendre en charge des plates-formes 32 bits.
Si votre langue ne prend pas en charge la récursion de la queue, la meilleure solution pour éviter les débordements de pile consiste à convertir en une boucle explicite (beaucoup moins élégante, mais parfois nécessaire), ou à rechercher un algorithme non itératif tel que Luke fourni. ce problème.
function memoize (f)
local cache = {}
return function (x)
if cache[x] then
return cache[x]
else
local y = f(x)
cache[x] = y
return y
end
end
end
triangle = memoize(triangle);
Notez que pour éviter un débordement de pile, le triangle doit toujours être ensemencé.
Voici quelque chose qui fonctionne sans convertir les arguments en chaînes.
Le seul inconvénient est qu'il ne peut pas gérer un argument nul. Cependant, la solution acceptée ne permet pas de distinguer la valeur nil de la chaîne "nil" , ce qui est probablement OK.
local function m(f)
local t = { }
local function mf(x, ...) -- memoized f
assert(x ~= nil, 'nil passed to memoized function')
if select('#', ...) > 0 then
t[x] = t[x] or m(function(...) return f(x, ...) end)
return t[x](...)
else
t[x] = t[x] or f(x)
assert(t[x] ~= nil, 'memoized function returns nil')
return t[x]
end
end
return mf
end
J'ai été inspiré par cette question pour mettre en œuvre (encore une autre) fonction de mémorisation flexible dans Lua.
https://github.com/kikito/memoize.lua
Principaux avantages:
- Accepte un nombre variable d'arguments
- N'utilise pas tostring; au lieu de cela, il organise le cache dans une arborescence en utilisant les paramètres pour le parcourir.
- Fonctionne parfaitement avec les fonctions qui renvoient plusieurs valeurs .
Coller le code ici en tant que référence:
local globalCache = {}
local function getFromCache(cache, args)
local node = cache
for i=1, #args do
if not node.children then return {} end
node = node.children[args[i]]
if not node then return {} end
end
return node.results
end
local function insertInCache(cache, args, results)
local arg
local node = cache
for i=1, #args do
arg = args[i]
node.children = node.children or {}
node.children[arg] = node.children[arg] or {}
node = node.children[arg]
end
node.results = results
end
-- public function
local function memoize(f)
globalCache[f] = { results = {} }
return function (...)
local results = getFromCache( globalCache[f], {...} )
if #results == 0 then
results = { f(...) }
insertInCache(globalCache[f], {...}, results)
end
return unpack(results)
end
end
return memoize
Voici une implémentation générique de C # 3.0, si elle peut aider:
public static class Memoization
{
public static Func<T, TResult> Memoize<T, TResult>(this Func<T, TResult> function)
{
var cache = new Dictionary<T, TResult>();
var nullCache = default(TResult);
var isNullCacheSet = false;
return parameter =>
{
TResult value;
if (parameter == null && isNullCacheSet)
{
return nullCache;
}
if (parameter == null)
{
nullCache = function(parameter);
isNullCacheSet = true;
return nullCache;
}
if (cache.TryGetValue(parameter, out value))
{
return value;
}
value = function(parameter);
cache.Add(parameter, value);
return value;
};
}
}
(Cité tiré d'un article de blog français )
Dans la perspective de publier des mémos dans différentes langues, je voudrais répondre à @ onebyone.livejournal.com avec un exemple C ++ ne modifiant pas la langue.
Tout d'abord, un outil de mémorisation pour les fonctions d'argument unique:
template <class Result, class Arg, class ResultStore = std::map<Arg, Result> >
class memoizer1{
public:
template <class F>
const Result& operator()(F f, const Arg& a){
typename ResultStore::const_iterator it = memo_.find(a);
if(it == memo_.end()) {
it = memo_.insert(make_pair(a, f(a))).first;
}
return it->second;
}
private:
ResultStore memo_;
};
Créez simplement une instance du memoizer, alimentez-la avec votre fonction et votre argument. Assurez-vous simplement de ne pas partager le même mémo entre deux fonctions différentes (mais vous pouvez le partager entre différentes implémentations de la même fonction).
Ensuite, une fonction de pilote et une implémentation. seule la fonction de conducteur doit être publique int fib (int); // chauffeur int fib_ (int); // implémentation
Implémenté:
int fib_(int n){
++total_ops;
if(n == 0 || n == 1)
return 1;
else
return fib(n-1) + fib(n-2);
}
Et le pilote, pour mémoriser
int fib(int n) {
static memoizer1<int,int> memo;
return memo(fib_, n);
}
Lien permanent pour afficher la sortie sur codepad.org. Le nombre d'appels est mesuré pour vérifier son exactitude. (insérez le test unitaire ici ...)
Ceci ne mémoise qu'une fonction d'entrée. Généraliser pour des arguments multiples ou des arguments variables reste un exercice pour le lecteur.
En Perl, la mémorisation générique est facile à obtenir. Le module Memoize fait partie du noyau Perl et est extrêmement fiable, flexible et facile à utiliser.
L'exemple de sa page de manuel:
# This is the documentation for Memoize 1.01
use Memoize;
memoize('slow_function');
slow_function(arguments); # Is faster than it was before
Vous pouvez ajouter, supprimer et personnaliser la mémorisation des fonctions au moment de l'exécution! Vous pouvez fournir des rappels pour le calcul du souvenir personnalisé.
Memoize.pm dispose même de fonctionnalités permettant de rendre le cache mémento persistant. Il n'est donc pas nécessaire de le remplir à chaque invocation de votre programme!
Voici la documentation: http://perldoc.perl.org/5.8.8 /Memoize.html
Voir cette publication de blog pour une solution générique Scala, jusqu'à 4 arguments.
En prolongeant l'idée, il est également possible de mémoriser des fonctions avec deux paramètres d'entrée:
function memoize2 (f)
local cache = {}
return function (x, y)
if cache[x..','..y] then
return cache[x..','..y]
else
local z = f(x,y)
cache[x..','..y] = z
return z
end
end
end
Notez que l'ordre des paramètres est important dans l'algorithme de mise en cache. Par conséquent, si l'ordre des paramètres importe peu dans les fonctions à mémoriser, les chances d'obtenir un succès dans le cache seront augmentées en triant les paramètres avant de vérifier le cache.
Mais il est important de noter que certaines fonctions ne peuvent pas être mémorisées de manière rentable. J'ai écrit à memoize2 pour voir si le
La récursivité n'est pas nécessaire. Le nième numéro de triangle est n (n-1) / 2, donc ... public int triangle(final int n){
return n * (n - 1) / 2;
}
S'il vous plaît, ne répétez pas ceci. Utilisez la formule x * (x + 1) / 2 ou parcourez simplement les valeurs et mémorisez-les au fur et à mesure.
int[] memo = new int[n+1];
int sum = 0;
for(int i = 0; i <= n; ++i)
{
sum+=i;
memo[i] = sum;
}
return memo[n];
