Оптимизация термина Фибоначчи в Javascript
https://stackoverflow.com/questions/426579
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Недавно я заинтересовался алгоритмами, и последовательность Фибоначчи привлекла мое внимание своей простотой.
Мне удалось собрать что-то на JavaScript, которое вычисляет n-й член последовательности Фибоначчи менее чем за 15 миллисекунд после прочтения большого количества информации в Интернете.Оно достигает 1476...1477 – это бесконечность, а 1478 – NaN (согласно JavaScript!)
Я очень горжусь самим кодом, но это настоящий монстр.
Итак, вот мой вопрос:А) существует ли более быстрый способ вычисления последовательности?Б) есть ли более быстрый/меньший способ умножить две матрицы?
Вот код:
//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.Да, и кстати, произошла волшебная вещь... Я преобразовывал алгоритм Штрассена в нотацию массива JS, и это сработало с первой попытки!Фантастика, правда?:П
Заранее спасибо, если вам удастся найти более простой способ сделать это.
Решение
Не спекулируйте, ориентир:
редактировать: Я добавил свою собственную реализацию матрицы, используя оптимизированные функции умножения, упомянутые в другом моем ответе.Это привело к значительному ускорению, но даже стандартная реализация умножения матриц с циклами 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]
Ваш алгоритм почти так же плох, как некэшируемый цикл.Лучше всего использовать кэширование, за которым следует алгоритм округления, который дает неверные результаты при больших объемах данных. 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]
Другие советы
Для n-го числа Фибоначчи есть решение в замкнутой форме (без циклов).
Возможно, существует более быстрый способ вычисления значений, но я не считаю, что это необходимо.
Рассчитайте их один раз и в своей программе выведите результаты в виде строки фибданных ниже:
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];
}
Тогда это код, который вы отправляете своим клиентам. Это решение O (1) для вас.
Люди часто упускают из виду решение «кэширования». Мне когда-то приходилось писать процедуры тригонометрии для встроенной системы, и вместо того, чтобы использовать бесконечные ряды для их вычисления на лету, у меня просто было несколько таблиц поиска, по 360 записей в каждой для каждой из степеней ввода.
Само собой разумеется, это кричало вперед, по стоимости только приблизительно 1 КБ ОЗУ. Значения были сохранены как 1-байтовые записи, [фактическое значение (0-1) * 16], поэтому мы могли просто выполнить поиск, умножение и сдвиг битов, чтобы получить желаемое значение.
Мой предыдущий ответ немного переполнен, поэтому я опубликую новый:
Вы можете ускорить свой алгоритм, используя умножение матриц ванили 2x2, т.е. замените функцию 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 быстро, не заботитесь о точности и не хотите повторно вызывать функцию.
edit: Вы можете еще больше ускорить вычисления, если будете использовать специализированные функции умножения, исключать общие подвыражения и заменять значения в существующем массиве вместо создания нового массива:
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 - это имя глобальной матричной переменной.
Решение в закрытой форме в JavaScript: 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;
}
Конечно, даже умножение начинает окупаться при работе с огромными числами, но это даст вам ответ. Насколько я знаю, из-за того, что JavaScript округляет значения, он точен только до n = 75. После этого вы получите хорошую оценку, но она не будет абсолютно точной, если вы не захотите сделать что-то хитрое, например, store затем значения в виде строки анализируют их как BigIntegers.
Как насчет запоминания результатов, которые уже рассчитаны, например:
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();
Следует добавить, что из-за технических ограничений (безопасность браузера) аргументами для запомненных функций могут быть только массивы или скалярные значения . Нет объектов.
Ссылка: http://talideon.com/weblog/ 2005/07 / JavaScript-memoization.cfm
Чтобы немного рассказать о ответе Dreas :
1) кеш должен начинаться с [0, 1]
2) что вы делаете с IterMemoFib (5.5) ? ( кеш [5.5] == не определено )
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)
Я только что написал свою собственную маленькую реализацию, использующую Object для хранения уже вычисленных результатов. Я написал это в Node.JS, которому потребовалось 2 мс (согласно моему таймеру), чтобы вычислить Фибоначчи для 1476.
Вот код, сокращенный до чистого 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)
РЕДАКТИРОВАТЬ: я не пробовал запускать это в браузере!
РЕДАКТИРОВАТЬ снова: теперь я сделал. попробуйте jsfiddle: jsfiddle fibonacci Время варьируется от 0 до 2 мс
Гораздо более быстрый алгоритм:
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
