JavaScript fibonacci Nth 용어 최적화
https://stackoverflow.com/questions/426579
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는 최근에 알고리즘에 관심을 갖게되었고, Fibonacci 시퀀스는 단순성 때문에 내 관심을 끌었습니다.
나는 웹에서 많은 정보를 읽은 후 15 밀리 초 이내로 Fibonacci 시퀀스의 N 번째 용어를 계산하는 JavaScript로 무언가를 합할 수있었습니다. 1477은 무한대이고 1478은 Nan입니다 (JavaScript에 따르면!)
코드 자체가 완전히 자랑 스럽습니다.
그래서 여기 내 질문이 있습니다. a) 시퀀스를 계산하는 더 빠른 방법이 있습니까? b) 두 행렬을 곱할 수있는 더 빠르거나 작은 방법이 있습니까?
코드는 다음과 같습니다.
//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 어레이입니다. 아, 그리고 부수적으로, 마법의 일이 일어났습니다 ... 나는 strassen 알고리즘을 JS 배열 표기법으로 변환하고 있었고 첫 시도에서 작동했습니다! 환상적입니까? :피
더 쉬운 방법을 찾으면 미리 감사드립니다.
해결책
추측하지 마십시오, 벤치 마크 :
편집하다: 다른 답변에 언급 된 최적화 된 곱셈 함수를 사용하여 자체 행렬 구현을 추가했습니다. 이로 인해 주요 속도가 크게 높아졌지만 루프를 사용한 매트릭스 곱셈의 바닐라 O (N^3) 구현조차도 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>
수율
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]
다른 팁
Nth Fibonacci 번호에 대한 닫힌 양식 (루프 없음) 솔루션이 있습니다.
값을 계산하는 더 빠른 방법이있을 수 있지만 값이 필요하다고 생각하지 않습니다.
한 번 계산하고 프로그램에서 결과를 아래의 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];
}
그런 다음 이것이 고객에게 배송되는 코드입니다. 그것은 당신을위한 O (1) 솔루션입니다.
사람들은 종종 '캐싱'솔루션을 간과합니다. 나는 임베디드 시스템에 대한 삼각법 루틴을 작성해야했고, 무한 시리즈를 사용하여 즉시 계산하기보다는 각 입력 정도에 대해 각각의 조회 테이블, 360 개의 항목이있었습니다.
말할 것도없이, 그것은 약 1k의 RAM의 비용으로 비명을 질렀습니다. 값은 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 빠르게, 정확성을 신경 쓰지 않고 반복적으로 함수를 호출하고 싶지 않습니다.
편집하다: 전문화 된 곱셈 기능을 사용하고 공통 하위 표현을 제거하고 새 배열을 만드는 대신 기존 배열의 값을 교체하는 경우 계산 속도를 높일 수 있습니다.
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;
}
물론, 곱셈조차도 막대한 숫자를 다룰 때 비용이 들기 시작하지만 이로 인해 답을 얻을 수 있습니다. 내가 아는 한, 값을 반올림하기 때문에 N = 75까지 정확합니다. 과거에는 좋은 견적을 얻을 수 있지만 상점과 같은 까다로운 일을하고 싶지 않으면 완전히 정확하지 않습니다. 문자열로서의 값은 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
약간 확장하려면 드레스답변 :
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 + ')');
다음은 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)
방금 이미 계산 된 결과를 저장하기 위해 객체를 사용하여 나만의 작은 구현을 작성했습니다. 1476 년 Fibonacci를 계산하기 위해 2ms (내 타이머에 따라)가 필요한 Node.js로 작성했습니다.
다음은 순수한 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과 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
