定数倍高速化

提供: MonoBook
2018年10月31日 (水) 03:07時点におけるimported>Administratorによる版
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
ナビゲーションに移動 検索に移動

定数倍高速化とは、アルゴリズムの改善による高速化とは違い、計算処理の方法を改善することにより計算量オーダーを変えずに処理を高速化することである。

概要[編集 | ソースを編集]

競技プログラミングにおいてはほとんどの場合意味がないが、たまに定数倍高速化で無理矢理通せる場合や、想定解アルゴリズムだけど自分の実装が悪いので定数倍高速化しないと通らない場合など、定数倍高速化が役に立つ場面がある。

[編集 | ソースを編集]

なるべく除算をしない[編集 | ソースを編集]

unsigned long long repeat_add(
		unsigned long long a,unsigned long long b,unsigned long long c) {
	unsigned long long result=0;
	while(b>0) {
		if(b&1)result=(result+a)%c;
		a=(a<<1)%c;
		b>>=1;
	}
	return result;
}

このコードは、a,bがULLONG_MAX/2以下、cがULLONG_MAX/2+1以下のとき、 (a*b) mod cをオーバーフローしないように気をつけながら求めるプログラムである。

しかし、よく考えると、最初に与えられるaがc未満のとき、常にresult+a<2*c,(a<<1)<2*cが成り立つことがわかる。 よって、次のように書くことができ、重い除算が比較的軽い減算になるため高速化できる。

/* suppose that a<c */
unsigned long long repeat_add(
		unsigned long long a,unsigned long long b,unsigned long long c) {
	unsigned long long result=0;
	while(b>0) {
		if(b&1) {
			result+=a;
			if(result>=c)result-=c;
		}
		a+=a;
		if(a>=c)a-=c;
		b>>=1;
	}
	return result;
}

なるべく再帰を使わない[編集 | ソースを編集]

再帰を使ったプログラムは、再帰を使わない処理に比べて、 関数の呼び出しによるスタックの確保・復帰処理が入るため低速になることが多い。

コンパイラに最適化してもらう[編集 | ソースを編集]

#include <stdio.h>
#include <string.h>

#define MOD_BY 100000007ULL

typedef unsigned long long ull;

void matrix_mul(ull in1[50][50],ull in2[50][50],ull out[50][50],int n) {
	ull result[50][50];
	int i,j,k;
	for(i=0;i<n;i++) {
		for(j=0;j<n;j++) {
			result[i][j]=0;
			for(k=0;k<n;k++) {
				result[i][j]+=(in1[i][k]*in2[k][j])%MOD_BY;
			}
			result[i][j]%=MOD_BY;
		}
	}
	memcpy(out,result,sizeof(result));
}

void matvec_mul(ull mat[50][50],ull vec[50],ull out[50],int n) {
	ull result[50];
	int i,j;
	for(i=0;i<n;i++) {
		result[i]=0;
		for(j=0;j<n;j++) {
			result[i]+=(mat[i][j]*vec[j])%MOD_BY;
		}
		result[i]%=MOD_BY;
	}
	memcpy(out,result,sizeof(result));
}

void make_matrix(ull mat[50][50],int n) {
	int i,j;
	for(i=0;i<n;i++) {
		for(j=0;j<n;j++)mat[i][j]=0;
		mat[0][i]=1;
		if(i>0)mat[i][i-1]=1;
	}
}

void matrix_kaizyo(ull out[50][50],int n,ull kai) {
	ull matrix[50][50];
	int i,j;
	for(i=0;i<n;i++) {
		for(j=0;j<n;j++)out[i][j]=0;
		out[i][i]=1;
	}
	make_matrix(matrix,n);
	for(i=0;i<64 && kai;i++,kai>>=1) {
		if(kai & 1)matrix_mul(matrix,out,out,n);
		matrix_mul(matrix,matrix,matrix,n);
	}
}

int main(void) {
	int k;
	ull n;
	ull ans_matrix[50][50];
	ull init_vector[50]={1};
	ull ans_vector[50];
	while(1) {
		scanf("%d%I64u",&k,&n);
		if(k==0 && n==0ULL)break;
		matrix_kaizyo(ans_matrix,k,n-1);
		matvec_mul(ans_matrix,init_vector,ans_vector,k);
		printf("%I64u\n",ans_vector[0]);
	}
	return 0;
}

このソースコードは、直前のk項の数のを次の項の値とする数列(ただし第1項は1、第n(n≦0)項は0とみなす)の第n項の値を100000007で割った余りを求めるプログラムである。

このコードgcc4.7.2でコンパイルした場合、-O2の最適化をかけたバイナリは、 同じ入力に対し、最適化オプションをつけずにコンパイルしたバイナリの約43%の実行時間で答えを出すことができた。

OpenMPを使う[編集 | ソースを編集]

OpenMPを使うと、数行のおまじないとコンパイルオプションの追加により、 実行中のCPU使用率を上げる代わりに実行時間を短くすることができる。

詳しくは、OpenMPのページを見ていただきたい。