Thread-sichere Speicherung
Lass uns nehmenWes Dyer Ansatz zur Funktionserinnerung als Ausgangspunkt:
public static Func<A, R> Memoize<A, R>(this Func<A, R> f)
{
var map = new Dictionary<A, R>();
return a =>
{
R value;
if (map.TryGetValue(a, out value))
return value;
value = f(a);
map.Add(a, value);
return value;
};
}
Das Problem ist, wenn es von mehreren Threads verwendet wird, können wir in Schwierigkeiten geraten:
Func<int, int> f = ...
var f1 = f.Memoize();
...
in thread 1:
var y1 = f1(1);
in thread 2:
var y2 = f1(1);
// We may be recalculating f(1) here!
Versuchen wir das zu vermeiden. Einrastenmap
:
public static Func<A, R> Memoize<A, R>(this Func<A, R> f)
{
var map = new Dictionary<A, R>();
return a =>
{
R value;
lock(map)
{
if (map.TryGetValue(a, out value))
return value;
value = f(a);
map.Add(a, value);
}
return value;
};
}
ist eindeutig eine schreckliche Idee, weil sie uns daran hindert, zu rechnenf1
Auf vieleanders Argumente auf einmal. Einrastena
funktioniert nicht wenna
hat einen Wertetyp (und ist auf jeden Fall eine schlechte Idee, da wir nicht kontrollierena
und möglicherweise wird auch ein externer Code darauf gespeichert).
Hier sind zwei Optionen, die ich mir vorstellen kann:
Angenommen, aLazy<T>
Klasse für faule Auswertung (sieheHier):
public static Func<A, R> Memoize<A, R>(this Func<A, R> f)
{
var map = new Dictionary<A, Lazy<R>>();
return a =>
{
Lazy<R> result;
lock(map)
{
if (!map.TryGetValue(a, out result))
{
result = () => f(a);
map.Add(a, result);
}
}
return result.Value;
};
}
Oder halten Sie ein zusätzliches Wörterbuch von Objekten für die Synchronisation:
public static Func<A, R> Memoize<A, R>(this Func<A, R> f)
{
var map = new Dictionary<A, R>();
var mapSync = new Dictionary<A, object>();
return a =>
{
R value;
object sync;
lock(mapSync)
{
if (!mapSync.TryGetValue(a, out sync))
{
sync = new object();
mapSync[a] = sync;
}
}
lock(map)
{
if (map.TryGetValue(a, out value))
return value;
}
lock(sync)
{
value = f(a);
lock(map)
{
map[a] = value;
}
return value;
}
};
}
Bessere Optionen?