Skip to content

Instantly share code, notes, and snippets.

@fmcat
Last active September 5, 2017 21:08
Show Gist options
  • Save fmcat/a1da0ade9816da7801eaf858f79872eb to your computer and use it in GitHub Desktop.
Save fmcat/a1da0ade9816da7801eaf858f79872eb to your computer and use it in GitHub Desktop.
Memoization Benefits
<div class="container">
<h1>Fibonacci Sequence</h1>
<form>
<div class="form-group">
<label for="number">
Fibonacci sequence number:
</label>
<input type="number" class="form-control" name="number" id="number" min="1" value="1" />
<small class="form-text text-muted">Please enter a number in the fibonacci sequence where n > 0.</small>
</div>
</form>
<hr />
<h2>Calculate using the following methods</h2>
<div class="btn-group" role="group" aria-label="Basic example">
<button class="btn btn-primary" id="calculate-for" >For loop</button>
<button class="btn btn-danger" id="calculate-recursive">Recursive</button>
<button class="btn btn-primary" id="calculate-recursive-memoized">Recursive, memoized</button>
</div>
<button class="btn btn-default" id="clear-results">Clear Results</button>
<hr />
<h3>Results:</h3>
<div id="results"></div>
</div>
class fibonacciApp {
constructor() {
this.tolerableTimeThreshold = '100';
this.elements = {
results: document.getElementById('results'),
number: document.getElementById('number'),
buttons: {
for: document.getElementById('calculate-for'),
recursive: document.getElementById('calculate-recursive'),
recursiveMemoized: document.getElementById('calculate-recursive-memoized'),
clear: document.getElementById('clear-results')
}
};
/**
* TODO: LOL figure out a better way to memoize this
*/
this.fibonacciRecursiveMemoized = (function() {
var memo = {};
function fib(n) {
var value;
if (n === 0 || n === 1) {
value = n;
} else {
if (n in memo) {
value = memo[n];
} else {
value = fib(n-1) + fib(n-2);
memo[n] = value;
}
}
return value;
}
return fib;
})();
this.registerEventListeners();
}
registerEventListeners() {
this.elements.buttons.clear.addEventListener('click', () => {
this.elements.results.innerHTML = ' ';
})
this.elements.buttons.recursiveMemoized.addEventListener('click', () => this.executeAlgorithm(this.fibonacciRecursiveMemoized));
// TODO: Could we not bind this? Makes printing out the funnction a little more difficult.
this.elements.buttons.recursive.addEventListener('click', () => this.executeAlgorithm(this.fibonacciRecursive.bind(this)));
this.elements.buttons.for.addEventListener('click', () => this.executeAlgorithm(this.fibonacciFor));
}
executeAlgorithm(method) {
let value = this.elements.number.value;
try {
let valueInteger = parseInt(value);
if (valueInteger >= 0) {
let startTime = new Date().getTime();
let result = method(valueInteger);
let endTime = new Date().getTime();
this.printResults(
value,
result,
endTime - startTime,
method
)
} else {
throw { message: `Invalid integer ${value}` };
}
} catch (e) {
this.printException(e.message, value, method);
}
}
printResults(n, result, executionTime, method) {
this.elements.results.innerHTML +=
`<div class="alert ${(executionTime>this.tolerableTimeThreshold) ? 'alert-warning' : 'alert-secondary'}">
<ul class="list-group">
<li class="list-group-item active"><strong>Result:</strong> ${result}</li>
<li class="list-group-item"><strong>Method:</strong> ${method.name}</li>
<li class="list-group-item"><strong>Input for parameter n:</strong> ${n}<br></li>
<li class="list-group-item"><strong>Execution Time:</strong> ${executionTime} ms <br></li>
</ul>
<hr>
<h3>What just ran:</h3>
<pre>${method.toString()}</pre>
</div>`;
}
/**
* Add an exception to the list of things printed to the screen
*/
printException(errorText, n, method) {
this.elements.results.innerHTML +=
`<div class="alert alert-danger">
<strong>Method:</strong> ${method.name} <strong>n:</strong> ${n}
<pre>EXCEPTION<br />${errorText}</pre>
</div>`;
}
/*
* Run the fibonacci sequence in a recursive pattern to achieve the result.
* This has a big performance hit after about 32.
* the complexity of this algorithm is about 2^n
*/
fibonacciRecursive(n) {
if (n === 0 || n === 1) {
return n;
}
else {
return this.fibonacciRecursive(n - 1) + this.fibonacciRecursive(n - 2);
}
}
/**
* Fibonnaci sequence completed going in the normal algorithm.
* Although less "elegant", this is significantly less complex.
*/
fibonacciFor(n) {
let accumulator = 1,
previousNMinus1 = 0,
previousNMinus2 = 1;
for (var counter = 1; counter <= n; counter++ ) {
accumulator = previousNMinus1 + previousNMinus2;
previousNMinus2 = previousNMinus1;
previousNMinus1 = accumulator;
}
return accumulator;
}
}
let fib = new fibonacciApp();
<link href="https://cdnjs.cloudflare.com/ajax/libs/twitter-bootstrap/4.0.0-beta/css/bootstrap.min.css" rel="stylesheet" />
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment