CODEWITHSUNDEEP
javascript
nashcheez
nashcheez

Reputation: 5183

Caching in Javascript without usage of global variable

I am trying to optimise the usage of a function to check whether a number is prime or not.

I have written the following function:

function isPrime(num) {
    var start = 2;

    // code to check whether num has already been checked for Prime

    while(start <= Math.sqrt(num)) {
      if (num % start++ < 1) {
        return false;
      }
    }
    return num > 1;
}

However, before the execution of my while loop I want to check if a number already has been passed through my isPrime function, so that I can return whether it is prime or not without having to execute the while loop.

Note, I want to do this without the usage of a global variable or without extending Object.prototype.

Upvotes: 3

Views: 2960

Answers (3)

Abhinav Galodha
Abhinav Galodha

Reputation: 9878

You can use the technique of Memoization .

Memoization is a programming technique which attempts to increase a function’s performance by caching its previously computed results.

The basic idea is that we build a empty Object and then add Keys as the hash value or the argument value and then if we get a argument which is already available on the Object keys then we return the Object value for that key.

There are several variation of the below function, but this one performs much better then other implementation. A code Snippet Taken from Addy Osmani article here .

function memoize( fn ) {
        return function () {
            var args = Array.prototype.slice.call(arguments),
                hash = "",
                i = args.length;
            currentArg = null;
            while (i--) {
                currentArg = args[i];
                hash += (currentArg === Object(currentArg)) ?
                JSON.stringify(currentArg) : currentArg;
                fn.memoize || (fn.memoize = {});
            }
            return (hash in fn.memoize) ? fn.memoize[hash] :
            fn.memoize[hash] = fn.apply(this, args);
        };
    }

Usage:

var cachedIsPrime = memoize(isPrime);
var isPrime = cachedIsPrime(2);
isPrime = cachedIsPrime(3);

And then you can pass the function which needs to be Memoized.

OP Notes: For the above context with a single argument, a simple memoize function like the following does work:

var memoize = function(passedFunc) {
    var cache = {};
    return function(x) {
        if (x in cache) return cache[x];
        return cache[x] = passedFunc(x);
    };
};

Upvotes: 3

GG.
GG.

Reputation: 21834

What you are looking for is the memoization pattern.

From Wikipedia:

In computing, memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

You can write your own memoize function (as suggested by the other answers) or you can use one of the many optimized and well-tested implementations available on npm, like fast-memoize.js or memoizee. If you already use Lodash, it also has its own _.memoize function.

Example:

var isPrime = memoize(/* your function */)

isPrime(2) // => true
isPrime(2) // => true (from the cache)

Upvotes: 1

Quentin
Quentin

Reputation: 943157

Declare the variable inside an IIFE to create a closure.

var isPrime = (function () {
    var checked_numbers = [];

    function isPrime(num) { ... }

    return isPrime;
}();

checked_numbers is in scope for the returned isPrime function (which is accessible outside the IIFE because it (the function itself) is assigned to a global variable), but nothing outside the IIFE can touch it.

Upvotes: 3

Related Questions