Skip to content

Instantly share code, notes, and snippets.

@Artanis

Artanis/fibonacci.js

Created September 8, 2011 00:08
Download ZIP

Revisions

  1. Artanis revised this gist Sep 8, 2011. 1 changed file with 2 additions and 0 deletions.
    2 changes: 2 additions & 0 deletions fibonacci.js
    View file
    Original file line number Diff line number Diff line change
    @@ -50,6 +50,8 @@ var fibonacci = function(n) {
    };

    // Replace naïve fibonacci with cachin fibonacci.
    // This is the key step: when the fibonacci function goes to call
    // itself, it finds this new value.
    fibonacci = memoize(fibonacci, true);

    // Generate a ton of numbers in crazy short time.
  2. Artanis revised this gist Sep 8, 2011. 1 changed file with 24 additions and 3 deletions.
    27 changes: 24 additions & 3 deletions fibonacci.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,35 +1,56 @@
    // Take a function and return a function that caches the results of
    // that function.
    //
    // Setting debug to true will print the logic the caching function uses.
    var memoize = function(fn, debug) {
    // Caching object, in the form {args : value}
    var cache = {};

    // Caching function. No explicit args. Any args are fed into the
    // memoized function via apply().
    return function() {
    // Turn arguments object into a real array.
    var arguments = [].slice.apply(arguments)

    // Generate a string suitable for being a key in an object.
    var args = JSON.stringify(arguments);

    // Check for previous call.
    if(cache[args] !== undefined) {
    if(debug === true) {
    print("In cache: (" + args + ", " + cache[args] + ")");
    }

    return cache[args];
    } else {
    // No previous call, call the function.
    // Point of interest: apply() doesn't work without 'this',
    // which is the global object in this case.
    var value = fn.apply(this, arguments);

    if(debug === true) {
    print("Brand new: (" + args + ", " + value + ")");
    }

    // Store the result in the cache, using the arguments as
    // the key.
    cache[args] = value;
    return value;
    }

    // Return the pre-calculated value.
    return cache[args];
    };
    };

    // Generate fibonacci numbers using naïve recursion.
    var fibonacci = function(n) {
    return n === undefined ? 0:
    n == 0 ? 0:
    n == 1 ? 1:
    fibonacci(n-1) + fibonacci(n-2);
    };

    // Replace naïve fibonacci with cachin fibonacci.
    fibonacci = memoize(fibonacci, true);

    print(fibonacci(10));
    // Generate a ton of numbers in crazy short time.
    print(fibonacci(100));
  3. Artanis created this gist Sep 8, 2011.
    35 changes: 35 additions & 0 deletions fibonacci.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,35 @@
    var memoize = function(fn, debug) {
    var cache = {};

    return function() {
    var arguments = [].slice.apply(arguments)
    var args = JSON.stringify(arguments);

    if(cache[args] !== undefined) {
    if(debug === true) {
    print("In cache: (" + args + ", " + cache[args] + ")");
    }

    return cache[args];
    } else {
    var value = fn.apply(this, arguments);

    if(debug === true) {
    print("Brand new: (" + args + ", " + value + ")");
    }
    cache[args] = value;
    return value;
    }
    };
    };

    var fibonacci = function(n) {
    return n === undefined ? 0:
    n == 0 ? 0:
    n == 1 ? 1:
    fibonacci(n-1) + fibonacci(n-2);
    };

    fibonacci = memoize(fibonacci, true);

    print(fibonacci(10));