Javascript Fibonacci nth Term Optimization
https://stackoverflow.com/questions/426579
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ultimamente mi sono interessato agli algoritmi e la sequenza dei fibonacci ha attirato la mia attenzione per la sua semplicità.
Sono riuscito a mettere insieme qualcosa in javascript che calcola l'ennesimo termine nella sequenza fibonacci in meno di 15 millisecondi dopo aver letto molte informazioni sul web. Va fino al 1476 ... 1477 è infinito e 1478 è NaN (secondo javascript!)
Sono abbastanza orgoglioso del codice stesso, tranne per il fatto che è un mostro assoluto.
Quindi, ecco la mia domanda: A) esiste un modo più veloce per calcolare la sequenza? B) esiste un modo più veloce / più piccolo per moltiplicare due matrici?
Ecco il codice:
//Fibonacci sequence generator in JS
//Cobbled together by Salty
m = [[1,0],[0,1]];
odd = [[1,1],[1,0]];
function matrix(a,b) {
/*
Matrix multiplication
Strassen Algorithm
Only works with 2x2 matrices.
*/
c=[[0,0],[0,0]];
c[0][0]=(a[0][0]*b[0][0])+(a[0][1]*b[1][0]);
c[0][1]=(a[0][0]*b[0][1])+(a[0][1]*b[1][1]);
c[1][0]=(a[1][0]*b[0][0])+(a[1][1]*b[1][0]);
c[1][1]=(a[1][0]*b[0][1])+(a[1][1]*b[1][1]);
m1=(a[0][0]+a[1][1])*(b[0][0]+b[1][1]);
m2=(a[1][0]+a[1][1])*b[0][0];
m3=a[0][0]*(b[0][1]-b[1][1]);
m4=a[1][1]*(b[1][0]-b[0][0]);
m5=(a[0][0]+a[0][1])*b[1][1];
m6=(a[1][0]-a[0][0])*(b[0][0]+b[0][1]);
m7=(a[0][1]-a[1][1])*(b[1][0]+b[1][1]);
c[0][0]=m1+m4-m5+m7;
c[0][1]=m3+m5;
c[1][0]=m2+m4;
c[1][1]=m1-m2+m3+m6;
return c;
}
function fib(n) {
mat(n-1);
return m[0][0];
}
function mat(n) {
if(n > 1) {
mat(n/2);
m = matrix(m,m);
}
m = (n%2<1) ? m : matrix(m,odd);
}
alert(fib(1476)); //Alerts 1.3069892237633993e+308
La funzione matrice prende due argomenti: a e b, e restituisce a * b dove aeb sono matrici 2x2. Oh, e su una nota a margine, è successa una cosa magica ... Stavo convertendo l'algoritmo Strassen in notazione di array JS e ha funzionato al mio primo tentativo! Fantastico, vero? : P
Grazie in anticipo se riesci a trovare un modo più semplice per farlo.
Soluzione
Non speculare, benchmark:
modifica: ho aggiunto la mia implementazione della matrice usando le funzioni di moltiplicazione ottimizzate menzionate nell'altra mia risposta. Ciò ha comportato un notevole aumento di velocità, ma anche l'implementazione O vanilla (n ^ 3) della moltiplicazione di matrici con loop è stata più veloce dell'algoritmo di Strassen.
<pre><script>
var fib = {};
(function() {
var sqrt_5 = Math.sqrt(5),
phi = (1 + sqrt_5) / 2;
fib.round = function(n) {
return Math.floor(Math.pow(phi, n) / sqrt_5 + 0.5);
};
})();
(function() {
fib.loop = function(n) {
var i = 0,
j = 1;
while(n--) {
var tmp = i;
i = j;
j += tmp;
}
return i;
};
})();
(function () {
var cache = [0, 1];
fib.loop_cached = function(n) {
if(n >= cache.length) {
for(var i = cache.length; i <= n; ++i)
cache[i] = cache[i - 1] + cache[i - 2];
}
return cache[n];
};
})();
(function() {
//Fibonacci sequence generator in JS
//Cobbled together by Salty
var m;
var odd = [[1,1],[1,0]];
function matrix(a,b) {
/*
Matrix multiplication
Strassen Algorithm
Only works with 2x2 matrices.
*/
var c=[[0,0],[0,0]];
var m1=(a[0][0]+a[1][1])*(b[0][0]+b[1][1]);
var m2=(a[1][0]+a[1][1])*b[0][0];
var m3=a[0][0]*(b[0][1]-b[1][1]);
var m4=a[1][1]*(b[1][0]-b[0][0]);
var m5=(a[0][0]+a[0][1])*b[1][1];
var m6=(a[1][0]-a[0][0])*(b[0][0]+b[0][1]);
var m7=(a[0][1]-a[1][1])*(b[1][0]+b[1][1]);
c[0][0]=m1+m4-m5+m7;
c[0][1]=m3+m5;
c[1][0]=m2+m4;
c[1][1]=m1-m2+m3+m6;
return c;
}
function mat(n) {
if(n > 1) {
mat(n/2);
m = matrix(m,m);
}
m = (n%2<1) ? m : matrix(m,odd);
}
fib.matrix = function(n) {
m = [[1,0],[0,1]];
mat(n-1);
return m[0][0];
};
})();
(function() {
var a;
function square() {
var a00 = a[0][0],
a01 = a[0][1],
a10 = a[1][0],
a11 = a[1][1];
var a10_x_a01 = a10 * a01,
a00_p_a11 = a00 + a11;
a[0][0] = a10_x_a01 + a00 * a00;
a[0][1] = a00_p_a11 * a01;
a[1][0] = a00_p_a11 * a10;
a[1][1] = a10_x_a01 + a11 * a11;
}
function powPlusPlus() {
var a01 = a[0][1],
a11 = a[1][1];
a[0][1] = a[0][0];
a[1][1] = a[1][0];
a[0][0] += a01;
a[1][0] += a11;
}
function compute(n) {
if(n > 1) {
compute(n >> 1);
square();
if(n & 1)
powPlusPlus();
}
}
fib.matrix_optimised = function(n) {
if(n == 0)
return 0;
a = [[1, 1], [1, 0]];
compute(n - 1);
return a[0][0];
};
})();
(function() {
var cache = {};
cache[0] = [[1, 0], [0, 1]];
cache[1] = [[1, 1], [1, 0]];
function mult(a, b) {
return [
[a[0][0] * b[0][0] + a[0][1] * b[1][0],
a[0][0] * b[0][1] + a[0][1] * b[1][1]],
[a[1][0] * b[0][0] + a[1][1] * b[1][0],
a[1][0] * b[0][1] + a[1][1] * b[1][1]]
];
}
function compute(n) {
if(!cache[n]) {
var n_2 = n >> 1;
compute(n_2);
cache[n] = mult(cache[n_2], cache[n_2]);
if(n & 1)
cache[n] = mult(cache[1], cache[n]);
}
}
fib.matrix_cached = function(n) {
if(n == 0)
return 0;
compute(--n);
return cache[n][0][0];
};
})();
function test(name, func, n, count) {
var value;
var start = Number(new Date);
while(count--)
value = func(n);
var end = Number(new Date);
return 'fib.' + name + '(' + n + ') = ' + value + ' [' +
(end - start) + 'ms]';
}
for(var func in fib)
document.writeln(test(func, fib[func], 1450, 10000));
</script></pre>
rendimenti
fib.round(1450) = 4.8149675025003456e+302 [20ms]
fib.loop(1450) = 4.81496750250011e+302 [4035ms]
fib.loop_cached(1450) = 4.81496750250011e+302 [8ms]
fib.matrix(1450) = 4.814967502500118e+302 [2201ms]
fib.matrix_optimised(1450) = 4.814967502500113e+302 [585ms]
fib.matrix_cached(1450) = 4.814967502500113e+302 [12ms]
Il tuo algoritmo è quasi cattivo quanto il loop non memorizzato nella cache. La memorizzazione nella cache è la soluzione migliore, seguita da vicino dall'algoritmo di arrotondamento - che produce risultati errati per il grande n (così come il tuo algoritmo a matrice).
Per n più piccoli, il tuo algoritmo funziona anche peggio di tutto il resto:
fib.round(100) = 354224848179263100000 [20ms]
fib.loop(100) = 354224848179262000000 [248ms]
fib.loop_cached(100) = 354224848179262000000 [6ms]
fib.matrix(100) = 354224848179261900000 [1911ms]
fib.matrix_optimised(100) = 354224848179261900000 [380ms]
fib.matrix_cached(100) = 354224848179261900000 [12ms]
Altri suggerimenti
Esiste una soluzione in forma chiusa (senza loop) per l'ennesimo numero di Fibonacci.
Potrebbe esserci un modo più veloce per calcolare i valori, ma non credo sia necessario.
Calcolali una volta e, nel tuo programma, emetti i risultati come la riga fibdata di seguito:
fibdata = [1,1,2,3,5,8,13, ... , 1.3069892237633993e+308]; // 1476 entries.
function fib(n) {
if ((n < 0) || (n > 1476)) {
** Do something exception-like or return INF;
}
return fibdata[n];
}
Quindi, questo è il codice che spedisci ai tuoi clienti. Questa è una soluzione O (1) per te.
Le persone spesso trascurano la soluzione di "memorizzazione nella cache". Una volta ho dovuto scrivere routine di trigonometria per un sistema incorporato e, anziché utilizzare serie infinite per calcolarle al volo, avevo solo alcune tabelle di ricerca, 360 voci in ciascuna per ciascuno dei gradi di input.
Inutile dire che ha urlato, al costo di solo circa 1K di RAM. I valori sono stati memorizzati come voci a 1 byte, [valore effettivo (0-1) * 16] in modo da poter semplicemente effettuare una ricerca, moltiplicare e spostare i bit per ottenere il valore desiderato.
La mia risposta precedente era un po 'affollata, quindi ne posterò una nuova:
Puoi accelerare il tuo algoritmo usando la moltiplicazione della matrice 2x2 vaniglia, ovvero sostituisci la tua funzione matrix () con questa:
function matrix(a, b) {
return [
[a[0][0] * b[0][0] + a[0][1] * b[1][0],
a[0][0] * b[0][1] + a[0][1] * b[1][1]],
[a[1][0] * b[0][0] + a[1][1] * b[1][0],
a[1][0] * b[0][1] + a[1][1] * b[1][1]]
];
}
Se ti interessa la precisione e la velocità, usa la soluzione di memorizzazione nella cache. Se la precisione non è un problema, ma lo è il consumo di memoria, utilizzare la soluzione di arrotondamento. La soluzione matrice ha senso solo se vuoi risultati veloci per n , non preoccuparti dell'accuratezza e non vuoi chiamare ripetutamente la funzione.
modifica: puoi persino accelerare ulteriormente il calcolo se usi funzioni di moltiplicazione specializzate, elimina le sottoespressioni comuni e sostituisci i valori nell'array esistente invece di creare un nuovo array:
function square() {
var a00 = a[0][0],
a01 = a[0][1],
a10 = a[1][0],
a11 = a[1][1];
var a10_x_a01 = a10 * a01,
a00_p_a11 = a00 + a11;
a[0][0] = a10_x_a01 + a00 * a00;
a[0][1] = a00_p_a11 * a01;
a[1][0] = a00_p_a11 * a10;
a[1][1] = a10_x_a01 + a11 * a11;
}
function powPlusPlus() {
var a01 = a[0][1],
a11 = a[1][1];
a[0][1] = a[0][0];
a[1][1] = a[1][0];
a[0][0] += a01;
a[1][0] += a11;
}
Nota: a è il nome della variabile di matrice globale.
Soluzione in formato chiuso in JavaScript: O (1), preciso fino a n = 75
function fib(n){
var sqrt5 = Math.sqrt(5);
var a = (1 + sqrt5)/2;
var b = (1 - sqrt5)/2;
var ans = Math.round((Math.pow(a, n) - Math.pow(b, n))/sqrt5);
return ans;
}
Certo, anche la moltiplicazione inizia a farsi carico quando si ha a che fare con numeri enormi, ma questo ti darà la risposta. Per quanto ne so, a causa dell'arrotondamento dei valori di JavaScript, è accurato solo fino a n = 75. Oltre questo, otterrai una buona stima, ma non sarà del tutto accurato se non vuoi fare qualcosa di complicato come negozio i valori come stringa quindi analizzano quelli come BigIntegers.
Che ne dici di memorizzare i risultati che erano già calcolati, come tali:
var IterMemoFib = function() {
var cache = [1, 1];
var fib = function(n) {
if (n >= cache.length) {
for (var i = cache.length; i <= n; i++) {
cache[i] = cache[i - 2] + cache[i - 1];
}
}
return cache[n];
}
return fib;
}();
O se si desidera una funzione di memoization più generica, estendere il prototipo Function :
Function.prototype.memoize = function() {
var pad = {};
var self = this;
var obj = arguments.length > 0 ? arguments[i] : null;
var memoizedFn = function() {
// Copy the arguments object into an array: allows it to be used as
// a cache key.
var args = [];
for (var i = 0; i < arguments.length; i++) {
args[i] = arguments[i];
}
// Evaluate the memoized function if it hasn't been evaluated with
// these arguments before.
if (!(args in pad)) {
pad[args] = self.apply(obj, arguments);
}
return pad[args];
}
memoizedFn.unmemoize = function() {
return self;
}
return memoizedFn;
}
//Now, you can apply the memoized function to a normal fibonacci function like such:
Fib = fib.memoize();
Una nota da aggiungere è che a causa di vincoli tecnici (sicurezza del browser), gli argomenti per le funzioni memorizzate possono essere solo matrici o valori scalari . Nessun oggetto.
Riferimento: http://talideon.com/weblog/ 2005/07 / javascript-memoization.cfm
Per espandere un po 'la la risposta di Dreas :
1) cache dovrebbe iniziare come [0, 1]
2) cosa fai con IterMemoFib (5.5) ? ( cache [5.5] == undefined )
fibonacci = (function () {
var FIB = [0, 1];
return function (x) {
if ((typeof(x) !== 'number') || (x < 0)) return;
x = Math.floor(x);
if (x >= FIB.length)
for (var i = FIB.length; i <= x; i += 1)
FIB[i] = FIB[i-1] + FIB[i-2];
return FIB[x];
}
})();
alert(fibonacci(17)); // 1597 (FIB => [0, 1, ..., 1597]) (length = 17)
alert(fibonacci(400)); // 1.760236806450138e+83 (finds 18 to 400)
alert(fibonacci(1476)); // 1.3069892237633987e+308 (length = 1476)
Se non ti piacciono gli errori silenziosi:
// replace...
if ((typeof(x) !== 'number') || (x < 0)) return;
// with...
if (typeof(x) !== 'number') throw new TypeError('Not a Number.');
if (x < 0) throw new RangeError('Not a possible fibonacci index. (' + x + ')');
Ecco una soluzione molto veloce per calcolare la sequenza fibonacci
function fib(n){
var start = Number(new Date);
var field = new Array();
field[0] = 0;
field[1] = 1;
for(var i=2; i<=n; i++)
field[i] = field[i-2] + field[i-1]
var end = Number(new Date);
return 'fib' + '(' + n + ') = ' + field[n] + ' [' +
(end - start) + 'ms]';
}
var f = fib(1450)
console.log(f)
Ho appena scritto la mia piccola implementazione usando un oggetto per memorizzare i risultati già calcolati. L'ho scritto in Node.JS, che aveva bisogno di 2ms (secondo il mio timer) per calcolare il fibonacci per il 1476.
Ecco il codice ridotto al puro Javascript:
var nums = {}; // Object that stores already computed fibonacci results
function fib(n) { //Function
var ret; //Variable that holds the return Value
if (n < 3) return 1; //Fib of 1 and 2 equal 1 => filtered here
else if (nums.hasOwnProperty(n)) ret = nums[n]; /*if the requested number is
already in the object nums, return it from the object, instead of computing */
else ret = fib( n - 2 ) + fib( n - 1 ); /* if requested number has not
yet been calculated, do so here */
nums[n] = ret; // add calculated number to nums objecti
return ret; //return the value
}
//and finally the function call:
fib(1476)
EDIT: non ho provato a eseguirlo in un browser!
EDIT di nuovo: ora l'ho fatto. prova il jsfiddle: jsfiddle fibonacci Il tempo varia tra 0 e 2ms
Algoritmo molto più veloce:
const fib = n => fib[n] || (fib[n-1] = fib(n-1)) + fib[n-2];
fib[0] = 0; // Any number you like
fib[1] = 1; // Any number you like
