Wzorzec Memoization w JavaScript

Dziś przedstawiam jeden ze znanych JavaScript’owych wzorców projektowych czyli wzorzec Memoization, a po naszemu po prostu wzorzec zapamiętywania. Wzorzec ten opiera się na właściwości języka JavaScript polegającej na tym, że każda funkcja jest obiektem. A skoro jest obiektem, to może posiadać właściwości… ba, jak pewnie wielu z Was wie, właściwości można do obiektów dodawać w dowolnym momencie. Skoro więc takie możliwości drzemią w naszym ulubionym JavaScripcie to dlaczego nie wykorzystać ich do zapamiętywania wyników działania kosztownych operacji, tak aby przy kolejnym wywołaniu funkcji nie trzeba było wykonywać jej jeszcze raz? No to zobaczmy jak to zrobić.

Wzorzec Memoization - najprostsza implementacja

Załóżmy, że nasza funkcja wykonująca “bardzo kosztowną operację” będzie wyglądała następująco:

var veryExpensiveOperation = function(howManyTimes) {
    var
        i = 0,
        result = 0;

    for (i; i < howManyTimes; i++) {
        result += i;
    }

     return result;
}

alert(veryExpensiveOperation(100));

Myślę, że wyjaśnienie powyższego kodu jest zbędne - tutaj link do jsfiddle z tym przykładem.

Ok. Jak widać, powyższa operacja jest bardzo kosztowna warto by więc było cache’ować ją w jakiś sposób. Zobaczmy jak to zrobić za pomocą podstawowej implementacji wzorca zapamiętywania:

var veryExpensiveOperation = function(howManyTimes) {
    var
        i = 0,
        result = 0;

    if (!veryExpensiveOperation.cachedResults[howManyTimes]) {
        for (i; i < howManyTimes; i++) {
            result += i;
        }

        veryExpensiveOperation.cachedResults[howManyTimes] = result;
    }

    return veryExpensiveOperation.cachedResults[howManyTimes];
}

veryExpensiveOperation.cachedResults = {};

alert(veryExpensiveOperation(100));
alert(veryExpensiveOperation(100));

A więc… w linii 17 (zaznaczona), definiujemy pusty obiekt cachedResults, który jest później wykorzystywany przez funkcję w trakcie jej wywołania. W linii 6 widać, że zanim wykonana zostanie nasza “bardzo kosztowna operacja”, sprawdzane jest czy czasem w obiekcie cachedResults nie ma już zapamiętanego wyniku tej operacji. Jeśli nie, operacja jest wykonywana, a następnie zapamiętywana w cache’u jako klucz używając wartości zmiennej wejściowej funkcji.

Powyższy przykład również, dostępny jest na jsfiddle.

Obsługa wielu argumentów funkcji

No właśnie, w poprzednim przykładzie mieliśmy do czynienia z pojedynczym parametrem wejściowym funkcji. W przypadku gdy funkcja posiada więcej parametrów, nie możemy wykorzystać jednego z argumentów jako klucz do zapamiętania wartości - funkcja może przecież być wywołana wielokrotnie z tym samym pierwszym parametrem, a różnym drugim z nich (lub oczywiście na odwrót). Jak więc obsłużyć przypadek, kiedy to funkcja przyjmuje więcej argumentów? Poniżej jeden ze sposobów:

var veryExpensiveOperation = function(howManyTimes, startPoint) {
    var
        key = Array.prototype.slice.call(arguments);
        i = startPoint,
        result = 0;

    if (!veryExpensiveOperation.cachedResults[key]){
        for (i; i < howManyTimes; i++) {
            result += i;
        }

        veryExpensiveOperation.cachedResults[key] = result;
    }

    return veryExpensiveOperation.cachedResults[key];
}

veryExpensiveOperation.cachedResults = {};

alert(veryExpensiveOperation(100, 50));
alert(veryExpensiveOperation(100, 50));
alert(veryExpensiveOperation(100, 90));
alert(veryExpensiveOperation(100, 90));

Istotna jest tutaj linia numer trzy (odpowiednio oznaczona). Co się tutaj dzieje? Ano bierzemy wszystkie argumenty funkcji, które w JavaScripcie mamy dostępne we właściwości arguments i łączymy je za pomocą funkcji slice będącej metodą klasy Array. W ten sposób w zmiennej key mamy tablicę argumentów, którą możemy następnie wykorzystać jako klucz do zapamiętania obliczonego wyniku “bardzo kosztownej operacji”. Tutaj jsfiddle dla tego przykładu.

Zamiast przedstawionego sposobu, możemy też jako cache dla wyników skorzystać z tablicy wielowymiarowej (czy bardziej “tablicy tablic”). Niech to będzie dla Was zadanie domowe ;) - taki przykład na pewno bez problemu znajdziecie w “Internetach”…

Obiekt jako argument

Jeśli bardzo nie podoba się Wam powyższe rozwiązanie z powodu używania w nim tablicy jako klucza, możecie dodatkowo użyć funkcji JSON.stringify, która dokona serializacji takiej tablicy do formatu JSON. Tak samo należałoby postąpić w przypadku przekazywania do funkcji obiektów, a nie typów prostych (jeśli tego nie zrobimy, obiekt użyty jako klucz zostałby automatycznie przekonwertowany na tekst “[object Object]”). A więc, jeśli argument howManyTimes z pierwszego przykładu byłby obiektem, wówczas klucz mógłby powstać w ten sposób:

var key = JSON.stringify(howManyTimes);

Niestety jest jeden minus takiego rozwiązania. Serializacja powoduje “spłaszczenie” obiektu, więc jeśli dwa obiekty zawierałyby dokładnie te same właściwości i ich wartości, wówczas stanowiłyby dokładnie ten sam klucz w cache’u. Stanowi to więc jedno z ograniczeń wzorca zapamiętywania, o którym powinniśmy pamiętać. Innym ograniczeniem może być też nadmierna konsumpcja pamięci, ponieważ każdy zapamiętany wynik musi być gdzieś przechowywany. Dlatego jeśli chcesz zastosować wzorzec Memoization to najpierw musisz zawsze dobrze to przemyśleć i przetestować tak, aby “plusy nie przesłoniły nam minusów” ;)