cjohansen.no

Memoisering av funksjoner

Noen ganger trenger vi kode som forgreiner seg basert på objekters tilstand, nettleserens ferdigheter eller andre omstendigheter - omstendigheter som kan være krevende ytelsesmessig. Memoisering kan i slike tilfeller ofte by på forenkling av logikk og/eller bedre ytelse.

Memoisering?

In computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously-processed inputs.

Memoisering er kort sagt caching på metodenivå.

Fibonacci

I matematikken er Fibonacci-tallene kjent som en tallrekke der første tall er 0, andre tall er 1 og påfølgende tall er gitt som summen av de to foregående tallene. Med andre ord (uttrykt som en enhetstest med jsunittest.js):

new Test.Unit.Runner({
    testFibonacci: function() { with(this) {
        assertEqual(0, fibonacci(0));
        assertEqual(1, fibonacci(1));
        assertEqual(1, fibonacci(2));
        assertEqual(2, fibonacci(3));
        assertEqual(3, fibonacci(4));
        assertEqual(6765, fibonacci(20));
    }}
}, { testLog: "testlog" });

Kjør test.

For en illustrasjon av styrken ved memoisering kan vi implementere funksjonen fibonacci(num) slik den er definert ovenfor: for et tall n, returner det nte tallet i Fibonacci-rekka.

// Only for n >= 0
function fibonacci(n) {
    if (n === 0) {
        return 0;
    } else if (n === 1) {
        return 1;
    }

    return fibonacci(n - 1) + fibonacci(n - 2);
}

Denne metoden løser rekka rekursivt og gjør jobben ( kjør suksessfull test). Men, den er langt fra optimal. En rask titt i Firebug avslører at metoden kalles i alt 21.891 ganger for å løse fibonacci(20);. Hva kommer dette av?

For å forstå problemet kan vi tenke oss gjennom noen kjøringer:

1. fibonacci(20) kaller rekursivt fibonacci(19) og fibonacci(18)
2. fibonacci(19) kaller rekursivt fibonacci(18) og fibonacci(17)
3. fibonacci(18) kaller rekursivt fibonacci(17) og fibonacci(16)
4. osv

Her ser vi fort at funksjonen vår gjør mye jobb om igjen. Når vi regner ut for 20 gjør vi dette ved å først regne ut først for 19, deretter 18. Når fibonacci(19) er regnet ut og vi skal begynne på fibonacci(18) er dette tallet allerede regnet ut, men snarere enn å bruke det tidligere resultatet gjøres hele beregningen på nytt.

Her kommer memoisering inn.

Memoisering via oppslagstabeller

En oppslagstabell er blant de enkleste former for memoisering. Funksjonen har en intern oppslagstabell hvor den lagrer verdier før den returnerer. Før den beregner verdier på nytt sjekkes tabellen om verdien allerede er beregnet. En rask implementasjon i fibonacci() gir noe ala:

// Only for n >= 0
function fibonacci(n) {
    // Define global (and public) lookup table
    if (!fibonacci.numbers) {
        fibonacci.numbers = [0, 1];
    }

    // Return memoized value if it exists
    if (fibonacci.numbers[n] || n === 0) {
        return fibonacci.numbers[n];
    }

    fibonacci.numbers[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return fibonacci.numbers[n];
}

Denne passerer fortsatt testene - ergo fungerer den - og Firebug bekrefter at vi nå er nede i 39 kall og betraktelig bedre ytelse. Men nå har vi sølet sammen memoisering/cachelogikk og funksjonens egentlige virke - Fibonaccitall. Dessuten er oppslagstabellen offentlig tilgjengelig via fibonacci.numbers, noe som ikke er så stilig.

Noen tanker senere kommer vi opp med en løsning som er hakket mer elegant, og fordi den unngår å konstant sjekke om oppslagstabellen må defineres også er raskere:

window.fibonacci = (function() {
    // Lookup table
    var lookup = [];

    // Calculate fibonacci number
    // Still only works correctly for positive ns
    function fibonacciNumber(n) {
        return n === 0 || n === 1 ? n : fibonacci(n - 1) + fibonacci(n - 2);
    }

    // The public function
    return function(num) {
        // Check cache
        if (typeof lookup[num] !== "undefined") {
            return lookup[num];
        }

        // Cache empty, calculate value, update cache, return
        return (lookup[num] = fibonacciNumber(num));
    };
})();

Testene kjører stadig. Her ser vi også praktisk bruk av den anonyme funksjonen som kjøres umiddelbart for å lage en closure. Jeg har i tillegg dratt nytte av at returverdien er n når n er 0 eller 1.

Memoisering ved definering av funksjon

En annen måte å øke ytelsen på kan være å unngå komplisert forgreiningslogikk (eller triviell forgreiningslogikk som kanskje kjøres mye).

Et kremeksempel på dette er "Ajax"-objektet, XMLHttpRequest, som finnes i en rekke varianter, avhengig av nettleser. Vanligvis abstraheres dette på følgende måte ( via):

function createXMLHttpRequest() {
    if (typeof XMLHttpRequest != "undefined") {
        return new XMLHttpRequest();
    } else if (typeof ActiveXObject != "undefined") {
        return new ActiveXObject("Microsoft.XMLHTTP");
    } else {
        throw new Error("XMLHttpRequest not supported");
    }
}

Vel og bra, men nettleseren forandrer seg strengt tatt ikke så lenge scriptet er lastet. En mer effektiv måte å gjøre dette på er å sjekke på forhånd hva nettleseren støtter for deretter å definere metoden:

window.createXMLHttpRequest = (function() {
    if (typeof XMLHttpRequest != "undefined") {
        return function() {
            return new XMLHttpRequest();
        };
    } else if (typeof ActiveXObject != "undefined") {
        return function() {
            return new ActiveXObject("Microsoft.XMLHTTP");
        };
    } else {
        return function() {
            throw new Error("XMLHttpRequest not supported");
        };
    }
})();

Her har vi flytta om på forgreiningslogikken slik at den kjøres kun én gang per sidevisning, fremfor en gang hver gang vi oppretter et XHR-objekt.

Hvis vi vil være skikkelig fine på det kan vi klage på at denne løsningen kjører forgreiningen én gang uansett om vi spør etter et XHR-objekt eller ikke. Dette kan også fikses ved å redefinere metoden første gang den kalles:

window.createXMLHttpRequest = function() {
    if (typeof XMLHttpRequest != "undefined") {
        // Redefine method
        window.createXMLHttpRequest = function() {
            return new XMLHttpRequest();
        };
    } else if (typeof ActiveXObject != "undefined") {
        // Redefine method
        window.createXMLHttpRequest = function() {
            return new ActiveXObject("Microsoft.XMLHTTP");
        };
    } else {
        // Redefine method
        window.createXMLHttpRequest = function() {
            throw new Error("XMLHttpRequest not supported");
        };
    }

    // Run redefined method. This will only happen one time -
    // before the method redefines itself
    return window.createXMLHttpRequest();
};

Det beste fra to verdener!

Dermed har vi sett på tre måter å gjøre memoisering i JavaScript: med oppslagstabell, ved å "if-e" definisjonen av metoden, og ved å redefinere metoden fra metoden selv, første gang den kjøres.

I morgen skal vi se hvordan vi kan synliggjøre slike forbedringer i enhetstestene våre.

Tweet this

Muligens relatert

• Objektorientering via closures
• Navnerom

Ny kommentar

Navn: *

E-mail: *

URL:

Kommentar:

Dette feltet er ment å beskytte cjohansen.no mot spam. Vennligst oppgi tallet 718 i feltet.

Noe HTML tillatt: strong, em, blockquote, pre, code, ul, ol og li. Lenker ikke tillatt, men URL-er autolenkes. Inline kode-eksempler med <code>, kodeblokker med <pre>.