MemoryCzęść NR.12 Komputery są dobre w zapamiętywaniu rzeczy. Gdy patrzysz na jakąś aplikację biznesową to zapewne nie jesteś zafascynowany tym, co ona może wyliczyć, ale co ona może zapamiętać. To główny cel naszych aplikacji wyświetlić wcześniej zapamiętane dane.
Gdzie te dane są? W plikach, w bazach danych?
Witaj w kolejnym wpisie z kursu programowania funkcyjnego w C#?
To niesamowite jak długo prowadzę ten cykl.
W programowaniu funkcjonalnym koncentruję się na wykonywaniu samych funkcji niż na przetrzymywania stanów pośrednich. Funkcje w programowaniu funkcyjnym mają być czystymi funkcjami.
Funkcyjne programowanie polega na uniknięciu ukrytych wejść i wyjść jak:
- Używanie Wyjątków, aby kontrolować przepływ programu
- Funkcja nie modyfikuje stanu
- Funkcja nie trzyma referencji do obiektu, który miałby być zmieniony
- Funkcja nie zapisuje czegokolwiek w polach statycznych
Z drugiej strony pamiętanie stanów jest częścią aplikacji. Zawsze gdzieś będzie warstwa dostępu do danych.
Mamy jednak kolejne ciekawe założenie programowania funkcyjnego. Zakłada ona, że raz wyliczona nie powinna zostać wyliczana ponownie. Możemy też założyć, że raz pobrana rzecz z bazy danych nie powinna być także odczytana ponownie do jakiegoś limitu czasu.
Czyli mówimy o Cache w naszej aplikacji o możliwości pamiętania tego, co już zrobiliśmy wcześniej, aby nie robić czegoś ponownie z takim samym rezultatem.
Mamy dwa style zapamiętywania rzeczy i omówimy je w tym wpisie.
- Precomputation: Polega na wyliczeniu wartości, zanim faktyczny algorytm się wykona na tych wartościach. Dobrym przykładem jest posiadanie np. zapisu wszystkich wyliczeń rezultatów cosinusów czy sinusów tak, aby nie robić tych operacji.
- Memoization: Polega na zapamiętywania wyników dla danych parametrów, aby nie robić za drugim razem tej samej operacji.
W C# te techniki są opcjonalne w Haskell-u już nie, ale w tym języku programowania istnieją pewne schematyczne gotowce.
Precomputation wyników
Większość programistów nie zna tej techniki no, chyba że programujesz kod, do rysowania grafiki.
Przykładowo trygometryczne kalkulację są bardzo ważne dla animacji 3D. Problem z nim jest jednak taki, że są one kosztowne.
static void ImperativePrecomputation( ) {
double[] sines = new double[360];
for (int i = 0; i < 360; i++) {
sines[i] = Math.Sin(i);
}
// Tutaj twój algorytm korzysta z tablicy sinósów
// zamiast je wyliczać
}Istnieje jednak jasna separacja pomiędzy kalkulacją, która najpierw musi się wykonać, a rzeczywistym algorytmem, który korzysta z tych rezultatów.
W praktyce więc warto wydzielić te wstępne wyliczenie od algorytmu. W programowaniu obiektowym zrobilibyśmy by to tak:
public class PointRotator
{
public PointRotator( )
{
InitLookups( );
}
float[] sines, cosines;
private void InitLookups( )
{
sines = new float[360];
cosines = new float[360];
for (int i = 0; i < 360; i++) {
sines[i] = (float) Math.Sin(ToRad(i));
cosines[i] = (float) Math.Cos(ToRad(i));
}
}
public PointF RotatePointWithLookups(PointF sourcePoint,
double angle)
{
double polarLength = Math.Sqrt(Square(sourcePoint.X) +
Square(sourcePoint.Y));
double polarAngle = ToDeg(Math.Atan(sourcePoint.Y / sourcePoint.X));
int newAngleInt = (int) Math.Round(polarAngle + angle);
float cartesianX = (float) polarLength * Cos(newAngleInt);
float cartesianY = (float) polarLength * Sin(newAngleInt);
return new PointF(cartesianX, cartesianY);
}
private int NormalizeAngle(int angle)
{
return ((angle % 360) + 360) % 360;
}
private float Cos(int angle)
{
return cosines[NormalizeAngle(angle)];
}
private float Sin(int angle)
{
return sines[NormalizeAngle(angle)];
}
static double Square(double x) { return x * x; }
static double ToRad(double deg) { return deg * Math.PI / 180.0; }
static double ToDeg(double rad) { return rad / (Math.PI / 180.0); }
}Ważną częścią nie jest fakt jak obracam ten punkt. Na pewno można napisać to lepiej
Ważniejszym detalem jest fakt , że korzystam z tabeli, która zawiera wyliczone wcześniej cosinusy i sinusy. Zrobiliśmy to w metodzie : "InitLookups"
Oczywiście w tej technice mamy pewne straty. Tracimy tutaj precyzję wyliczeń, ponieważ nierealne jest wyliczenie wszystkich możliwych rezultatów, ale zyskujemy czas kalkulacji, który byłby poświęcony.
Korzystanie z gotowych wyliczeń, które zrobiliśmy na starcie aplikacji daje takie rezultaty.
Jak widzisz warto tutaj dokonać swojej oceny tej techniki, ponieważ nie widać jasno jak czarno na białym czy ta technika będzie lepsza dla Ciebie.
private static void ObjectOrientedPrecomputation( ) {
var rotator = new PointRotator( );
Console.WriteLine(PointRotator.RotatePoint(new PointF(4, 3), 3));
Console.WriteLine(rotator.RotatePointWithLookups(new PointF(4, 3), 3));
Console.WriteLine(PointRotator.RotatePoint(new PointF(10, 25), 74));
Console.WriteLine(rotator.RotatePointWithLookups(new PointF(10, 25), 74));
}Jak to napisać lepiej, aby można było tę technikę wykorzystywać ponownie ? Gdybyśmy chcieli napisać przykład w stylu funkcyjnym to wyglądałby on tak :
static Func<PointF, Func<double, PointF>> CreateFunctionalRotator()
{
Func<double, double> toRad = x => x * Math.PI / 180.0;
Func<double, double> toDeg = x => x / (Math.PI / 180.0);
float[] sines = Functional.InitArray<float>(360,
i => (float)Math.Sin(toRad(i)));
float[] cosines = Functional.InitArray<float>(360,
i => (float)Math.Cos(toRad(i)));
Func<int, int> normalize = v => ((v % 360) + 360) % 360;
Func<int, float> sin = v => sines[normalize(v)];
Func<int, float> cos = v => cosines[normalize(v)];
Func<float, float> square = x => x * x;
return p => a => {
double polarLength = Math.Sqrt(square(p.X) + square(p.Y));
double polarAngle = toDeg(Math.Atan(p.Y / p.X));
int newAngleInt = (int)Math.Round(polarAngle + a);
float cartesianX = (float)polarLength * cos(newAngleInt);
float cartesianY = (float)polarLength * sin(newAngleInt);
return new PointF(cartesianX, cartesianY);
};
}Wymagałoby to instalacji paczki NuGet "FCSlib".
W tym rozwiązaniu tworzy wiele pomocniczych funkcji i tablicę z gotowymi wynikami.
Metoda "InitArray<T>" tworzy gotowe tablice z wynikami cosinusów i sinusów. Jest to funkcja wyższego rzędu, która przyjmuje parametr generyczny, czyli każdą inną metodę.
Gdy wszystkie pomocnicze funkcje zostały utworzone wewnątrz metody CreateFunctionalRotator, która jak widzisz zostanie zwrócona. Jak to możliwe?
Wszystko jest to możliwe dzięki mechanizmu domknięcia. Z każdym nowym wrażeniem lambda, które jest zwrócony w C# zostanie utworzona skrystalizowana metoda z zapisanymi wynikami cosinusów i sinusów.
Działa to podobnie jak klasa w stylu obiektowym, którą napisaliśmy przed chwilą. Mamy tylko tablicę sinusów i kosinusów zapisaną wewnątrz domknięcia.
Oto działanie tej funkcji :
var rotate = CreateFunctionalRotator( );
Console.WriteLine(rotate(new PointF(4, 3))(3));
Console.WriteLine(rotate(new PointF(10, 25))(74));Jak zrobić to samo tylko na łatwiejszym przykładzie
Chcemy stworzyć metodę, która będzie sprawdzać, czy dane są już liście.
static bool IsInList<T> (IEnumerable <T> list, T item) {
var hashSet = new HashSet<T> (list);
return hashSet.Contains(item);
}Dlaczego korzystam z prze-mapowania na HashSet, a nie z innej kolekcji jak Lista czy IEnumerable. Słowniki jak HashSet zostały stworzone z myślą o szukaniu elementów po ich kluczu. Operacja szukania czegoś w Liście czy nawet IEnumerable będzie bardziej kosztowna.
static void Main(string[] args)
{
string[] strings = { "1", "2", "3", "4", "5" };
Console.WriteLine(IsInList(strings, "2"));
Console.WriteLine(IsInList(strings, "Nie na liście"));
}Nasza metoda IsInList nie jest efektywna, ponieważ musimy tworzyć za każdym razem HashSet, nawet gdy operujemy ciągle na tej samej kolekcji.
Co, gdybyśmy mogli zapisać ten stworzony HashSet jako domknięcie naszej funkcji. Musimy tylko zmodyfikować naszą metodę tak, aby zwracała ona nie wyniki działania, ale funkcję z utworzoną już kolekcją HashSet wewnątrz siebie.
static Func<T, bool> CleverListLookup<T>(IEnumerable<T> list)
{
var hashSet = new HashSet<T>(list);
return item => hashSet.Contains(item);
}W ten sposób właśnie sprawiliśmy, że HashSet jest tworzony tylko raz bezwzględu na to ile razy chcemy sprawdzić jego zawartość.
Func<string,bool> lookup = CleverListLookup(strings);
Console.WriteLine(lookup("1"));
Console.WriteLine(lookup("Nie na liście"));Oto ta technika Precomputation, która wykorzystuje domknięcia w C# na prostszym przykładzie.
Memoization
Memoizacja to strategia, która ma cel poprawienia wydajności aplikacji poprzez zapamiętanie wyników działania pewnej kosztownej funkcji, której nie chcemy liczyć za każdym razem
Opakowujemy naszą kosztowną funkcję tak, aby przy każdym jej wywoływaniu był sprawdzany Cache. Jeśli mam zapisany wynik dla danych parametrów to go zwracamy, a sama funkcja się dalej nie wykonuje.
Memoizacja (nie ma takiego słowa) to bardzo popularna technika i szczerze mówiąc miałem z nią styczność po raz pierwszy w języku JavaScript. Oto przykład z mojego Instagrama, na którego wrzucam pytania rekrutacyjne dla web developerów.
Wklei ten kod do konsoli przeglądarki i zobacz co się stanie.
function memoize(func) {
const cache = {};
return value => {
if(cache[value]) {
console.log("Cache works");
return cache[value];
}
const result = func(value);
cache[value] = result;
return result;
}
}
const calc = number => number * number;
const memoizedCalc = memoize(calc);
console.log(memoizedCalc(10));
console.log(memoizedCalc(10));Jak ta sama technika wygląda w C#? Bo jak wiemy C# nie jest językiem w pełni funkcjonalnym? Jest językiem hybrydowym
Jestem jednak przekonany, że jako programista przez przypadek mogłeś zastosować tę technikę nawet nie wiedząc jak się ona nazywa.
static int Addimple(int x) {
return x + x;
}Mamy tutaj prostą funkcję dodawania. Dlaczego tak funkcja jest znakomity kandydatem do Memoizacji? Bo jest ona czystą funkcją, a czysta funkcja jak mówiliśmy wcześniej nie przechowuje jakichś stanów w sobie.
Zanim jednak skorzystasz z tej techniki warto przeanalizować swoją daną funkcję czy spełnia pewne jeszcze inne kryteria:
- Jeśli sama metoda lub funkcja nie robi czegoś, co pochłania czas być może opakowanie jej w tej mechanizm jest bezcelowe i niczego nie przyspieszy, a zwiększy użycie pamięci
- Parametry twojej metody lub funkcji są ważne. Jeśli prawdopodobieństwo wywołania twojej metody lub funkcji z tymi samymi parametrami jest prawie zerowe to nie ma sensu korzystać z tej techniki
- Metoda lub funkcja przeciwieństwie do moich przykładów powinna być złożona i skomplikowana. Jeśli nie jest tak to nie ma to sensu.
Oto przykład techniki Memoization na tej funkcji :
class Program
{
static Dictionary<int, int> addInternalMemory;
private static int AddnternalMemoized(int x)
{
if (addInternalMemory == null)
addInternalMemory = new Dictionary<int, int>();
if (!addInternalMemory.ContainsKey(x))
{
int result = x + x;
addInternalMemory[x] = result;
return result;
}
return addInternalMemory[x];
}
static void Main(string[] args)
{
AddInternalMemoized(10);
AddInternalMemoized(10);
}Za każdym razem, gdy wykonujemy metodę AdInternalMemoized to sprawdzamy, czy w słowniku nie mamy już tej wartości.
Jak ten wzorzec projektowy wykorzystywać ponownie tak, aby nie pisać takich metod na potęgę. Możesz skorzystać z gotowej klasy z paczki NuGet "FCSlib", która ma w sobie zbiór wszystkich słowników, do których odnosisz się po kluczu.
static int AddInternalAutoMemoized(int x)
{
var memory = Memoizer<int, int>.GetMemory("AddInternalMemoized");
if (!memory.HasResultFor(x))
{
int result = x + x;
memory.Remember(x, result);
return result;
}
return memory.ResultFor(x);
}
static void Main(string[] args)
{
AddInternalAutoMemoized(10);
AddInternalAutoMemoized(10);
}Pomysł ze zbiorem takich słowników nie jest zły. W końcu w jednym miejscy zapisujesz wszystkie dane. Dla wydajności lepiej skorzystać z napisanych na żywca nazw metod niż wyciągać je przy pomocy refleksji.
var mInfo = MethodInfo.GetCurrentMethod;
var key = mInfo.DeclaringType.FullName + mInfo.Name;Na razie widzimy jak zrobić tą technikę statyczniej i obiektowo. Jak to rozwiązanie by wyglądałoby, gdybyś skorzystali z funkcjonalnej części języka C#.
Pamiętasz przykład z JavaScript, który opakowywał gotową funkcję. Zrobimy to samo w C#
Oto nasza pomocnicza funkcja:
static Func<P, R> Memoize<P, R>(Func<P, R> f)
{
var memory = new Dictionary<P, R>();
return arg => {
if (!memory.ContainsKey(arg))
memory[arg] = f(arg);
return memory[arg];
};
}Nasza funkcja zwróci nową funkcję, która została opakowana w szukanie w pamięci istniejącego już rezultatu. Słownik, który będzie przechowywał wyniki zostanie skrystalizowany, ze względu na mechanizm domknięcia.
Co, jeśli chcemy opakowywać tak funkcję, która ma więcej niż 1 parametr? Oto przykład :
static Func<P1,P2, R> Memoize<P1, P2, R>(Func<P1,P2, R> f)
{
var name = GetDefaultMemoryKey(f.Method);
var memory = new Dictionary<string, R>();
return (arg1,arg2) => {
if (!memory.ContainsKey(name))
memory[name] = f(arg1, arg2);
return memory[name];
};
}
static string GetDefaultMemoryKey(MethodInfo fInfo)
{
return fInfo.DeclaringType.FullName + "+" +fInfo.Name;
}Tym razem nasz słownik operuje na nazwie metody, gdyż jeden z parametrów nie może być kluczem. Analogicznie trzeba by było utworzyć tak z 16 metod tak, aby zadbać o obsługę Memoizacji każdej metody, niezależnie od tego ile jest tam parametrów.
static int MultiplySimple(int x, int y)
{
return x * y;
}
static void AlgorithmWithSquares()
{
var memoizedSquare =
Memoize<int, int, int>(MultiplySimple);
memoizedSquare(5, 5);
memoizedSquare(5, 5);
var memoizedLambdaSquare =
Memoize<int, int, int>((x, y) => x * x);
memoizedLambdaSquare(3, 3);
memoizedLambdaSquare(3, 3);
}Czy można to zrobić jeszcze lepiej? Pisanie 16 wersji takiej metody wydaje się trochę dziwne.
Mógłbyś opakować funkcję w funkcję, która ma mniej parametrów przy pomocy Curring, ale czy to jest lepsze rozwiązanie?
Oto przykład użycia techniki Memoization z Curring
static Func<P, R> LogMemoize<P, R>(Func<P, R> f) {
var memory = new Dictionary<P, R>( );
return arg => {
if (!memory.ContainsKey(arg)) {
Console.WriteLine("Memory doesn't have result for {0}, calling function... ", arg);
memory[arg] = f(arg);
Console.WriteLine(" ... memorizing result {0}", memory[arg]);
return memory[arg];
}
else {
Console.WriteLine("Returning result {0} for {1} from memory", memory[arg], arg);
return memory[arg];
}
};
}
static void FirstTryMultipleParameters( ) {
Func<int, Func<int, int>> add = x => y => x + y;
var memoizedAdd = LogMemoize(add);
Console.WriteLine("Adding 10 + 3: {0}", memoizedAdd(10)(3));
Console.WriteLine("Adding 10 + 4: {0}", memoizedAdd(10)(4));
Console.WriteLine("Adding 10 + 3: {0}", memoizedAdd(10)(3));
}
static void ManualMultipleParameters( ) {
var memoizedAdd =
LogMemoize<int, Func<int, int>>(x => LogMemoize<int, int>(y => x + y));
Console.WriteLine("Adding 10 + 3: {0}", memoizedAdd(10)(3));
Console.WriteLine("Adding 10 + 4: {0}", memoizedAdd(10)(4));
Console.WriteLine("Adding 10 + 3: {0}", memoizedAdd(10)(3));
}Bazując na tym, że mamy funkcję w funkcji można by było napisać metodą, która będzie wykonywać Memoizacje automatycznie.
W FCSlib istnieje gotowa funkcja na ten problem i wygląda ona tak :
private static MethodInfo deepMemoizeMethodInfo;
private static MethodInfo DeepMemoizeMethodInfo
{
get
{
if (deepMemoizeMethodInfo == null)
{
deepMemoizeMethodInfo = typeof(Functional).GetMethod(
"DeepMemoize", BindingFlags.Public | BindingFlags.Static);
}
return deepMemoizeMethodInfo;
}
}
public static Func<P, R> DeepMemoize<P, R>(this Func<P, R> f)
{
return arg => {
MethodInfo fInfo = f.Method;
string memoryKey = GetDefaultMemoryKey(fInfo);
var memory = Memoizer<P, R>.GetMemory(memoryKey);
if (!memory.HasResultFor(arg))
{
R result = f(arg);
Type resultType = typeof(R);
if (typeof(System.Delegate).IsAssignableFrom(resultType))
{
Type[] parameterTypes = resultType.GetGenericArguments();
MethodInfo typedDeepMemoizeMethod =
DeepMemoizeMethodInfo.MakeGenericMethod(parameterTypes);
R memoizedResult = (R)typedDeepMemoizeMethod.Invoke(
null, new object[] { result });
memory.Remember(arg, memoizedResult);
}
else
memory.Remember(arg, result);
}
return memory.ResultFor(arg);
};
}Jednak ja bym wrócił do pisania 16 metod i więcej, aby rozwiązać ten problem. Po pierwsze taka metoda jak DeepMemoize korzysta mocno z refleksji co jest spowalnia mocno aplikacje. Po drugie moim zdaniem kod z Curring nie koniecznie jest czytelny w swoim działaniu.
Lepiej by było mieć, gotowe metody generyczne, które opakują funkcje bezwzględu na to ile ma ona parametrów.
static Func<P1,P2, R> Memoize<P1, P2, R>(Func<P1,P2, R> f)
{
var name = GetDefaultMemoryKey(f.Method);
var memory = new Dictionary<string, R>();
return (arg1,arg2) => {
if (!memory.ContainsKey(name))
memory[name] = f(arg1, arg2);
return memory[name];
};
}
static Func<P1, P2, P3, R> Memoize<P1, P2, P3, R>(Func<P1, P2, P3, R> f)
{
var name = GetDefaultMemoryKey(f.Method);
var memory = new Dictionary<string, R>();
return (arg1, arg2,arg3) => {
if (!memory.ContainsKey(name))
memory[name] = f(arg1, arg2, arg3);
return memory[name];
};
}
static Func<P1, P2, P3, P4, R> Memoize<P1, P2, P3, P4, R>(Func<P1, P2, P3, P4, R> f)
{
var name = GetDefaultMemoryKey(f.Method);
var memory = new Dictionary<string, R>();
return (arg1, arg2, arg3, arg4) => {
if (!memory.ContainsKey(name))
memory[name] = f(arg1, arg2, arg3, arg4);
return memory[name];
};
}W tym wszystkim nie omówiliśmy także innego problemu związanego z tą techniką. Kiedy te zapisane informacje o wynikach mają wygasać. Warto wtedy utworzyć swój mechanizm, który pozwoli ci czyści tak zgromadzone dane.
Jeśli tak zrobisz to zabezpieczysz się przed nieskończonym wzrostem pamięci Cache oraz będziesz mógł użyć techniki Memoization nie tylko na czystych funkcjach. Nie czystą funkcją byłoby na przykład odpytywanie bazy danych gdzie informacje mogą się zmieniać, a co zatem idzie rezultaty.
A co ze słownikiem, czyli implementacja szukania danych po kluczu?
Słownik Dictionary o ile jest wydajny to w swoim działaniu nie jest bezpieczny wątkowo. Z niego korzysta paczka NuGet "FSClibs" . Trzeba wiec na to uważać.
To wszystko :) Ciesze się, że mogłem dodać kolejny wpis do tego cyklu, który zapewne jeszcze czeka na C# 10, który pokaże jak naprawdę pisać funkcyjny kod. Gdy zaczynałem ten cykl miałem do dyspozycji tylko C# 6.0.
Kto wie może zrobię wpis o tym, jak zrobić Monady w C#. Do zobaczenia.
