ここからは個別に高速化していこうと思う。
あまり一般的な手法は得られない気がする。
add
// 加算
this.add = function(p) {
var r = this.copy();
if(typeof p == "number")
r.a[0] += p;
else if(p instanceof poly) {
for(var i = 0; i < p.a.length; i++) {
if(i < r.a.length)
r.a[i] += p.a[i];
else
r.a[i] = p.a[i];
}
}
else
throw("unsupported argument in poly::add");
r.normalize();
return r;
}
を、Arrayを使うことすると、
// 加算
function poly_add(p) {
var r = this.copy();
if(typeof p == "number")
r[0] += p;
else if(p instanceof poly) {
for(var i = 0; i < p.length; i++) {
if(i < r.length)
r[i] += p[i];
else
r[i] = p[i];
}
}
else
throw("unsupported argument in poly::add");
r.normalize();
return r;
}
0次から9次の多項式を足し合わせを10万回行うと、
15394msが4258msとなった。
たぶんnormalizeが遅いが、
これは次数を正しくするもので、
要するに最高次の係数が0なら次数を低くするのである。
しかし、同じ次数の多項式の加算以外の結果では
これは起こりえないので、
最初に次数の比較をすると、normalizeの回数を減らせる。
// 3522ms
function poly_add(p) {
var r = this.copy();
if(typeof p == "number")
r[0] += p;
else if(p instanceof poly) {
var r_length = r.length;
var p_length = p.length;
if(r_length > p_length) {
for(var i = 0; i < p_length; i++)
r[i] += p[i];
}
else if(r_length < p_length) {
var i;
for(i = 0; i < r_length; i++)
r[i] += p[i];
for( ; i < p_length; i++)
r[i] = p[i];
}
else {
for(var i = 0; i < p_length; i++)
r[i] += p[i];
if(r[r_length-1] == 0)
r.normalize();
}
}
else
throw("unsupported argument in poly::add");
return r;
}
最初にコピーをしているが、
こうすると、
r[i] = this[i];
r[i] += p[i];
ということだが、
r[i] = this[i] + p[i];
とすると、
プロパティの参照が4回から3回に減らせる。
// 2502ms
function poly_add(p) {
var r = [ ];
var length = this.length;
if(typeof p == "number") {
r[0] = this[0] + p;
for(var i = 1; i < length; i++)
r[i] = this[i];
}
else if(p instanceof poly) {
var p_length = p.length;
if(length > p_length) {
var i;
for(i = 0; i < p_length; i++)
r[i] = this[i] + p[i];
for( ; i < length; i++)
r[i] = this[i];
}
else if(length < p_length) {
var i;
for(i = 0; i < length; i++)
r[i] = this[i] + p[i];
for( ; i < p_length; i++)
r[i] = p[i];
}
else {
for(var i = 0; i < p_length; i++)
r[i] = this[i] + p[i];
if(r[length-1] == 0)
r.normalize();
}
}
else
throw("unsupported argument in poly::add");
return r;
}
まだ嫌なところが残っているが。
