جافا سكريبت فيبوناتشي النونية الأجل الأمثل
https://stackoverflow.com/questions/426579
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
لقد أصبحت مهتمة في خوارزميات مؤخرا سلسلة فيبوناتشي أمسك انتباهي بسبب بساطته.
لقد تمكنت من وضع شيء معا في جافا سكريبت التي تحسب أقصى المدى في سلسلة فيبوناتشي في أقل من 15 ميلي ثانية بعد قراءة الكثير من المعلومات على شبكة الإنترنت.فإنه يذهب إلى 1476...1477 هو اللانهاية و 1478 هو نان (وفقا جافا سكريبت!)
أنا فخور جدا من المدونة نفسها, إلا أنها المطلق الوحش.
سؤالي هو:أ) هل هناك طريقة أسرع لحساب التسلسل ؟ ب) هل هناك أسرع/أصغر طريقة ضرب المصفوفات اثنين?
هنا كود:
//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
مصفوفة وظيفة يأخذ حجتين:a و b و يعود a*b حيث a و b هي 2x2 المصفوفات.وفي الجانب علما, السحرية شيء حدث لقد تم تحويل شتراسين الخوارزمية إلى شبيبة تدوين مجموعة وعملت في أول محاولة!رائعة, أليس كذلك ؟ :P
شكرا مقدما إذا كنت تدير للعثور على أسهل طريقة للقيام بذلك.
المحلول
لا للمضاربة ، المعيار:
تحرير: أضفت بلدي مصفوفة التنفيذ باستخدام الأمثل الضرب الوظائف المذكورة في إجابة أخرى.هذا أدى في تسريع, ولكن حتى الفانيليا O(n^3) تنفيذ مصفوفة الضرب مع الحلقات كان أسرع من شتراسين الخوارزمية.
<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>
ينتج
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]
خوارزمية الخاص بك هو تقريبا سيئة كما uncached حلقات.التخزين المؤقت هو أفضل رهان ، تليها التقريب خوارزمية والتي ينتج نتائج غير صحيحة كبيرة n (كما لا مصفوفة الخوارزمية).
أصغر n, الخوارزمية ينفذ حتى أسوأ من أي شيء آخر:
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]
نصائح أخرى
وهناك شكل مغلق (لا حلقات) حل لعدد فيبوناتشي الألف.
قد يكون هناك أيضا طريقة أسرع لحساب القيم ولكن لا اعتقد انه من الضروري.
واحسب لها مرة واحدة، وفي البرنامج، إخراج النتائج كخط fibdata أدناه:
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];
}
وبعد ذلك، وهذا هو الرمز الذي السفينة إلى العملاء. هذا و(1) حل O بالنسبة لك.
والناس غالبا ما تتجاهل "التخزين المؤقت" الحل. كان لي مرة واحدة لكتابة كيفية حساب المثلثات لنظام جزءا لا يتجزأ من و، بدلا من استخدام سلسلة لا نهاية لها لحساب لهم على الطاير، فقط كان لي عدد قليل من جداول البحث، 360 الإدخالات في كل لكل من درجات الإدخال.
وغني عن القول، أنه صرخ على طول، بتكلفة حوالي فقط 1K من ذاكرة الوصول العشوائي. تم تخزين القيم كما إدخالات 1 بايت، [القيمة الفعلية (0-1) * 16] ولذا فإننا يمكن أن مجرد القيام البحث، تتكاثر والتحول قليلا للحصول على القيمة المطلوبة.
إجابتي السابقة حصلت قليلا مزدحمة لذا سوف وظيفة واحدة جديدة:
يمكنك تسريع الخوارزمية باستخدام الفانيليا مصفوفة 2 × 2 الضرب - أي محل matrix() وظيفة هذا:
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]]
];
}
إذا كنت الرعاية دقة و سرعة استخدام التخزين المؤقت إلى حل.إذا دقة ليست مصدر قلق ، ولكن استهلاك الذاكرة ، استخدم التقريب الحل.مصفوفة الحل الوحيد المنطقي إذا كنت تريد نتائج كبيرة n بسرعة لا أهتم دقة و لا أريد أن استدعاء الدالة مرارا وتكرارا.
تحرير: حتى يمكنك مواصلة تسريع حساب إذا كنت تستخدم المتخصصة الضرب وظائف القضاء على الشائعة subexpressions واستبدال القيم في القائمة مجموعة بدلا من إنشاء مجموعة جديدة:
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;
}
ملاحظة: a هو اسم المصفوفة العالمية المتغيرة.
والحل مغلق النموذج في جافا سكريبت: O (1)، دقة تصل ل 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;
}
ومنح، ويبدأ الضرب حتى أن تأخذ نفقتها عند التعامل مع أعداد هائلة، ولكن هذا سوف تعطيك الجواب. وبقدر ما أعرف، بسبب جافا سكريبت التقريب القيم، انها دقيقة فقط حتى ن = 75. الماضي أنه سوف تحصل على تقدير جيد، لكنها لن تكون دقيقة تماما إلا إذا كنت تريد أن تفعل شيئا صعبة مثل مخزن القيم كسلسلة ثم تحليل تلك كما BigIntegers.
ماذا عن memoizing النتائج حيث تحسب بالفعل ، مثل:
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;
}();
أو إذا كنت تريد المزيد من عام التحفيظ وظيفة تمديد 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();
ملاحظة واحدة لإضافة هذا بسبب التقنية (متصفح الأمن) القيود ، الحجج المؤيدة memoized وظائف يمكن أن يكون إلا صفائف أو القيم العددية.أي الكائنات.
المرجع: http://talideon.com/weblog/2005/07/javascript-memoization.cfm
لتوسيع قليلا على Dreas الصورة الجواب:
1) يجب أن تبدأ cache كما [0, 1]
2) ماذا تفعل مع 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)
إذا كنت لا تحب أخطاء الصامتة:
// 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 + ')');
وهنا هو حل سريع جدا لحساب تسلسل فيبوناتشي
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)
لقد كتبت للتو بلدي قليلا التنفيذ باستخدام كائن مخزن بالفعل محسوب النتائج.لقد كتبت في Node.JS التي تحتاج إلى 2ms (حسب توقيت) لحساب فيبوناتشي 1476.
هنا هو رمز جردت أسفل نقية جافا سكريبت:
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)
تحرير:أنا لم أحاول تشغيل هذا في المتصفح!
تحرير مرة أخرى:الآن فعلت.حاول jsfiddle: jsfiddle فيبوناتشي الوقت يختلف بين 0 و 2ms
وأسرع بكثير الخوارزمية:
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
