Javascript Fibonacci N-TEN Begriff der Optimierung
https://stackoverflow.com/questions/426579
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe Interesse an algorithmen, die in letzter Zeit, und der fibonacci-Folge erregte meine Aufmerksamkeit wegen seiner Einfachheit.
Ich habe es geschafft, etwas zusammen in javascript, berechnet die N-te term in der fibonacci-Sequenz in weniger als 15 Millisekunden nach der Lektüre viele Informationen auf dem web.Es geht bis zu 1476...1477 ist unendlich, und 1478 ist NaN (nach javascript!)
Ich bin ziemlich stolz auf den code selbst, außer es ist einem regelrechten monster.
Also hier ist meine Frage:A) gibt es einen schnelleren Weg, um berechnen Sie die Sequenz?B) gibt es eine schnellere/kleiner Weg zu multiplizieren, zwei Matrizen?
Hier ist der code:
//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
Die matrix-Funktion nimmt zwei Argumente:a und b und liefert a*b, wobei a und b sind 2 x 2-arrays.Oh, und auf einer Seite zur Kenntnis, etwas Magisches passiert ist...ich war die Umwandlung der Strassen-Algorithmus in der JS array-notation und es funktionierte bei meinem ersten Versuch!Fantastisch, richtig?:P
Vielen Dank im Voraus, wenn es Ihnen gelingt, ein einfacher Weg, dies zu tun.
Lösung
Sie nicht spekulieren, Benchmark:
Bearbeiten ich meine eigene Matrix Implementierung mit Hilfe der optimierten Multiplikationsfunktionen in meiner anderen Antwort erwähnt hinzugefügt. Dies führte zu einer großen Beschleunigung, sondern auch das Vanille-O (n ^ 3) Umsetzung der Matrixmultiplikation mit Schleifen wurde schneller als der Strassen-Algorithmus.
<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>
Ausbeuten
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]
Ihr Algorithmus ist fast so schlimm wie uncached Looping. Caching ist die beste Wahl, dicht gefolgt von dem Rundungsalgorithmus gefolgt -., Die zu falschen Ergebnisse für großen n ergibt (wie auch Ihre Matrix-Algorithmus)
Für kleinere n, Ihr Algorithmus führt noch schlimmer als alles andere:
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]
Andere Tipps
Es ist eine geschlossene Form (keine Schleifen) Lösung für die n-te Fibonacci-Zahl.
Es kann gut ein schneller Weg, um die Werte zu berechnen, aber ich glaube nicht, dass es notwendig ist.
Berechnen Sie sie einmal und in Ihrem Programm, gibt die Ergebnisse als die fibdata Zeile unter:
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];
}
Dann, das ist der Code, den Sie an Ihre Kunden versenden. Das ist eine O (1) Lösung für Sie.
Die Leute übersehen oft die ‚Caching‘ Lösung. Ich hatte einmal Trigonometrie Routinen für ein eingebettetes System zu schreiben und, anstatt unendliche Reihe mit ihnen on the fly zu berechnen, ich hatte nur ein paar Lookup-Tabellen, 360 Einträge in jedem für jeden des Grad der Eingabe.
Unnötig zu sagen, es schrie entlang, auf Kosten von nur etwa 1 K RAM. Die Werte wurden als 1-Byte-Einträge gespeichert, [Istwert (0-1) * 16] und so können wir ein Lookup nur tun, multiplizieren und Bit-Verschiebung um den gewünschten Wert zu erhalten.
Meine Vorherige Antwort hat ein bisschen überfüllt, so werde ich nach einer neuen:
Sie können die Geschwindigkeit Ihres Algorithmus durch die Verwendung von Vanille-2x2 matrix-Multiplikation - ie ersetzen Sie Ihre matrix() Funktion mit diesem:
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]]
];
}
Wenn Sie sich für die Genauigkeit und der Geschwindigkeit, verwenden Sie die caching-Lösung.Wenn Genauigkeit ist kein Problem, aber der Speicherverbrauch ist, verwenden Sie die Rundung Lösung.Die matrix-Lösung macht nur Sinn, wenn Sie wollen Ergebnisse für big n schnell, don ' T care für die Genauigkeit und wollen nicht zum Aufruf der Funktion wiederholt.
edit: Sie können sogar noch weiter beschleunigen die Berechnung, wenn Sie spezialisierte Multiplikation Funktionen, beseitigen, gemeinsame Teilausdrücke und ersetzen Sie die Werte in das vorhandene array erstellen, anstatt ein neues 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;
}
Hinweis: a der name der globalen matrix-variable.
geschlossene Lösung in JavaScript: O (1), genau bis zu 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;
}
Zugegeben, beginnt sogar Multiplikation seine Kosten zu übernehmen, wenn sie mit großen Zahlen zu tun, aber das wird Ihnen die Antwort geben. Soweit ich weiß, weil der JavaScript die Werte Runden, dann ist es nur genau bis zu n = 75. Vergangenheit, dass es eine gute Schätzung, aber es wird nicht ganz korrekt sein, wenn Sie etwas heikel wie Speicher tun wollen die Werte als String dann diejenigen, die als BigIntegers analysieren.
Wie wäre es, die Ergebnisse memoizing dass dort, wo bereits berechnet, wie so:
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;
}();
Oder wenn Sie eine allgemeinere memoization Funktion möchten, erweitern den Function Prototyp:
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();
Eine Anmerkung hinzuzufügen ist, dass aufgrund technischer (Browser-Sicherheit) Zwänge, die Argumente für memoized Funktionen nur Arrays oder skalare Werte sein kann: . Keine Objekte.
Referenz: http://talideon.com/weblog/ 2005/07 / javascript-memoization.cfm
Um ein wenig auf Dreas 's Antwort zu erweitern:
1) cache beginnen sollte, als [0, 1]
2) Was tun Sie mit 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)
Wenn Sie nicht stille Fehler mögen:
// 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 + ')');
Hier ist eine sehr schnelle Lösung für die Berechnung der Fibonacci-Sequenz
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)
Ich habe meine eigene kleine Implementierung mit einem Objekt nur geschrieben speichern bereits berechnete Ergebnisse. Ich habe es in Node.JS geschrieben, die 2ms benötigt (nach meinem Timer), um die Fibonacci für 1476 zu berechnen.
Hier ist der Code zum reinen Javascript abgespeckte:
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: Ich habe nicht versucht, diese in einem Browser ausgeführt
!EDIT wieder: jetzt habe ich. versuchen, die jsfiddle: jsfiddle Fibonacci Zeit zwischen 0 und 2 ms
variiertViel schneller Algorithmus:
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
