Wie schreibe ich eine generische memoize Funktion?
https://stackoverflow.com/questions/129877
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich schreibe eine Funktion Dreieckszahlen und die natürliche Art und Weise zu finden um es zu schreiben ist rekursiv:
function triangle (x)
if x == 0 then return 0 end
return x+triangle(x-1)
end
Aber versuchen, die ersten 100.000 Dreieckszahl berechnen nicht mit einem Stapelüberlauf nach einer Weile. Dies ist eine ideale Funktion memoize , aber ich möchte eine Lösung, die jede Funktion memoize werde ich es passieren .
Lösung
Ich wette so etwas wie dies sollte mit variablen Argumentlisten in Lua arbeiten:
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
Sie könnten wahrscheinlich auch etwas tun klug mit Metatables mit __toString so dass die Argumentliste nur mit einem tostring umgewandelt werden könnte (). Oh die Möglichkeiten.
Andere Tipps
Mathematica hat eine besonders glatte Art und Weise memoization zu tun, auf die Tatsache verlassen, die Hashes und Funktionsaufrufe verwenden die gleiche Syntax:
triangle[0] = 0;
triangle[x_] := triangle[x] = x + triangle[x-1]
Das ist es. Es funktioniert, weil die Regeln für die Pattern-Matching-Funktionsaufrufe sind so, dass es immer eine spezifischere Definition vor einer allgemeineren Definition verwendet.
Natürlich, wie bereits erwähnt wurde, hat dieses Beispiel eine geschlossene Lösung: triangle[x_] := x*(x+1)/2. Fibonacci-Zahlen sind das klassische Beispiel dafür, wie das Hinzufügen memoization eine drastische Beschleunigung ergibt:
fib[0] = 1;
fib[1] = 1;
fib[n_] := fib[n] = fib[n-1] + fib[n-2]
Obwohl das auch eine geschlossene Form Äquivalent hat, wenn auch Messier: http: //mathworld.wolfram. com / FibonacciNumber.html
Ich bin nicht einverstanden mit der Person, der vorschlug, das für memoization unangemessen war, weil man könnte „nur eine Schleife verwenden“. Der Punkt der memoization ist, dass alle Wiederholungsfunktionsaufrufe O (1) Zeit sind. Das ist viel besser als O (n). In der Tat könnte man sogar ein Szenario ausdenken, wo die memoized Implementierung bessere Leistung als die geschlossenen Form Implementierung hat!
Sie sind auch die falsche Frage für Ihr ursprüngliches Problem zu fragen;)
Dies ist eine bessere Art und Weise für diesen Fall:
Dreieck (n) = n * (n - 1) / 2
Darüber hinaus die Formel angenommen hat nicht so eine saubere Lösung hat, würde Memoisation hier noch einen schlechten Ansatz. Sie wären besser dran, nur eine einfache Schleife in diesem Fall zu schreiben. Siehe diese Antwort für eine ausführlichere Diskussion.
In C # 3.0 - für rekursive Funktionen können Sie wie etwas tun:
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;
}
}
Dann können Sie eine memoized Fibonacci-Funktion wie folgt erstellen:
var memoized_fib = Helpers.Memoize<int, int>((n,fib) => n > 1 ? fib(n - 1) + fib(n - 2) : n);
Console.WriteLine(memoized_fib(40));
In Scala (ungetestet):
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
}
}
}
Beachten Sie, dass dies nur für Funktionen von arity arbeitet 1, aber mit currying man könnte es funktionieren. Das subtile Problem ist, dass memoize(f) != memoize(f) für jede Funktion f. Eine sehr hinterhältige Art und Weise, dies zu beheben wäre in etwa wie folgt:
val correctMem = memoize(memoize _)
Ich glaube nicht, dass dies kompilieren, aber es hat die Idee veranschaulichen.
Aktualisieren : Commen haben darauf hingewiesen, dass memoization ein guter Weg ist Rekursion zu optimieren. Zwar hatte ich das vorher nicht bedacht, da ich in der Regel in einer Sprache (C #) arbeiten, wo verallgemeinert memoization zu bauen nicht so trivial ist. Nehmen Sie den Beitrag unten mit diesen Körnchen Salz im Auge behalten.
Ich denke, Luke wahrscheinlich die am besten geeignete Lösung hat für dieses Problem, aber memoization ist im allgemeinen nicht die Lösung für jedes Problem der Stack-Überlauf.
Stack-Überlauf wird in der Regel verursacht durch Rekursion geht tiefer als die Plattform verarbeiten kann. Sprachen unterstützen manchmal „ Endrekursion “, die den Kontext des aktuellen Anrufs wieder verwendet, sondern als einen neuen Kontext für den rekursiven Aufruf zu schaffen. Aber viele Mainstream-Sprachen / Plattformen tun dies nicht unterstützen. C # hat keine inhärente Unterstützung für Schwanz-Rekursion, zum Beispiel. Die 64-Bit-Version von .NET Jitters es als eine Optimierung bei der IL-Ebene anwenden kann, die alle sind, aber nutzlos, wenn Sie 32-Bit-Plattformen unterstützen müssen.
Wenn Sie Ihre Sprache nicht Endrekursion nicht unterstützt, die beste Option zur Vermeidung von Stapelüberlauf entweder ist einen nicht-iterativen Algorithmus auf eine explizite Schleife (viel weniger elegant, aber manchmal notwendig), oder finden zu konvertieren, wie Luke vorgesehen dieses Problem.
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);
Man beachte, dass ein Stapelüberlauf zu vermeiden, Dreieck noch ausgesät werden müßte.
Hier ist etwas, das ohne Umwandlung der Argumente in Strings funktioniert.
Der einzige Nachteil ist, dass es kein Null-Argument umgehen kann. Aber die akzeptierte Lösung kann den Wert nil aus dem String "nil" nicht unterscheiden, so dass wahrscheinlich in Ordnung ist.
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
Ich habe mit dieser Frage inspiriert worden zu implementieren (weiteren) flexible memoize Funktion in Lua.
https://github.com/kikito/memoize.lua
Die wichtigsten Vorteile:
- Akzeptiert eine variable Anzahl von Argumenten
- Ist tostring nicht verwenden; sondern es organisiert den Cache in einer Baumstruktur, die Parameter verwenden, es zu durchqueren.
- Arbeiten mit Funktionen ganz gut, dass die Rückkehr mehr Werte .
Einfügen des Code hier als Referenz:
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
Dies ist eine generische C # 3.0-Implementierung, wenn es helfen könnte:
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;
};
}
}
(Zitiert aus einem französisch Blog-Artikel )
In der Vene memoization in verschiedenen Sprachen veröffentlichen, ich möchte @ onebyone.livejournal.com mit einem Nicht-Sprache verändernden C ++ Beispiel reagieren zu können.
Als erstes wird ein memoizer für einzelne Funktionen arg:
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_;
};
Nur eine Instanz des memoizer erstellen, füttern sie Ihre Funktion und Argument. So stellen Sie sicher nicht das gleiche Memo zwischen zwei verschiedenen Funktionen zu teilen (aber man kann es zwischen verschiedenen Implementierungen der gleichen Funktion teilen).
Als nächstes wird ein Treiber functon, und eine Implementierung. Es müssen nur die Treiberfunktion öffentlich int fib (int); // Treiber int fib_ (int); // Implementierung
Implementiert:
int fib_(int n){
++total_ops;
if(n == 0 || n == 1)
return 1;
else
return fib(n-1) + fib(n-2);
}
Und der Fahrer, memoize
int fib(int n) {
static memoizer1<int,int> memo;
return memo(fib_, n);
}
Permalink zeigt Ausgabe auf codepad.org. Die Anzahl der Anrufe gemessen Richtigkeit zu überprüfen. (Insert Unit-Test hier ...)
Dieses memoizes nur eine Eingabefunktion. Verallgemeinert für mehrere Argumente oder unterschiedlichen Argumente links als Übung für den Leser.
In Perl generic memoization ist leicht zu bekommen. Das Memoize Modul ist Teil des Perl-Kerns und ist sehr zuverlässig, flexibel und einfach zu bedienen.
Das Beispiel ist es manpage:
# This is the documentation for Memoize 1.01
use Memoize;
memoize('slow_function');
slow_function(arguments); # Is faster than it was before
Sie können hinzufügen, entfernen und anpassen memoization von Funktionen zur Laufzeit! Sie können Rückrufe für individuelle Erinnerungs Berechnung zur Verfügung stellen.
Memoize.pm selbst verfügt über Einrichtungen für die Herstellung der Erinnerung Cache persistent, so muss es nicht bei jedem Aufruf des Programms erneut ausgefüllt werden!
Hier ist die Dokumentation: http://perldoc.perl.org/5.8.8 /Memoize.html
Siehe diese Blog-Post für eine generische Lösung Scala, bis zu 4 Argumenten.
Erweiterung der Idee, es ist auch möglich, Funktionen mit zwei Eingabeparameter memoize:
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
Beachten Sie, dass Parameter, um Angelegenheiten im Caching-Algorithmus, also, wenn Parameter, um in den Funktionen keine Rolle spielt die Chancen auf einen Cache-Treffer memoized werden würde durch Sortieren des Parameters erhöht werden, bevor die Cache-Kontrolle.
Aber es ist wichtig zu beachten, dass einige Funktionen nicht profitabel memoized werden können. Ich schrieb memoize2 , um zu sehen, ob die rekursive euklidische Algorithmus für die Suche nach der größte gemeinsame Teiler beschleunigt werden könnte.
function gcd (a, b)
if b == 0 then return a end
return gcd(b, a%b)
end
Wie sich herausstellt, gcd reagiert nicht gut auf memoization. Die Berechnung es tut, ist weit weniger teuer als der Cache-Algorithmus. Immer für eine große Zahl, beendet sie ziemlich schnell. Nach einer Weile wächst der Cache sehr groß. Dieser Algorithmus ist wahrscheinlich so schnell, wie es sein kann.
Rekursion ist nicht erforderlich. Die n-te Dreieck Zahl ist n (n-1) / 2, so ...
public int triangle(final int n){
return n * (n - 1) / 2;
}
Bitte verwenden Sie diese nicht Rekursion. Entweder die x * verwenden (x + 1) / 2 Formel oder einfach die Werte iterieren und memoize wie Sie gehen.
int[] memo = new int[n+1];
int sum = 0;
for(int i = 0; i <= n; ++i)
{
sum+=i;
memo[i] = sum;
}
return memo[n];
