定数倍高速化 - 版の履歴

2018年10月31日 (水) 03:07にimported>Administratorによる

2018-10-31T03:07:57Z

← 古い版		2018年10月31日 (水) 03:07時点における版
131行目:		131行目:

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

			[[category: アルゴリズム]]

126.212.139.214: /* 概要 */

2014-09-11T16:07:56Z

概要

← 古い版		2014年9月11日 (木) 16:07時点における版
2行目:		2行目:

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

	==例==		==例==

2014年9月11日 (木) 16:07に126.212.139.214による

2014-09-11T16:07:23Z

← 古い版		2014年9月11日 (木) 16:07時点における版
1行目:		1行目:
	~~定数倍高速化とは、~~[[アルゴリズム]]の改善による[[高速化]]~~とは違い、~~		'''定数倍高速化'''とは、[[アルゴリズム]]の改善による[[高速化]]とは違い、計算処理の方法を改善することにより[[計算量]]の[[オーダー]]を変えずに処理を高速化することである。
	~~計算処理の方法を改善することにより~~[[計算量]]の[[オーダー]]を変えずに処理を高速化することである。

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

	==例==		==例==
22行目:		19行目:
	</source>		</source>
	このコードは、a,bがULLONG_MAX/2以下、cがULLONG_MAX/2+1以下のとき、		このコードは、a,bがULLONG_MAX/2以下、cがULLONG_MAX/2+1以下のとき、
	(a*b) mod cを[[オーバーフロー]]~~しないように気をつけながら求めるプログラムである。~~		(a*b) mod cを[[オーバーフロー]]しないように気をつけながら求める[[プログラム]]である。

	しかし、よく考えると、最初に与えられるaがc未満のとき、常にresult+a<2c,(a<<1)<2cが成り立つことがわかる。		しかし、よく考えると、最初に与えられるaがc未満のとき、常にresult+a<2c,(a<<1)<2cが成り立つことがわかる。
	~~よって、次のように書くことができ、重い除算が比較的軽い減算になるため高速化できる。~~		よって、次のように書くことができ、重い[[除算]]が比較的軽い減算になるため高速化できる。
	<source lang="c">		<source lang="c">
	/* suppose that a<c */		/* suppose that a<c */
45行目:		42行目:

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

124行目:		121行目:
	}		}
	</source>		</source>
	~~このソースコードは、直前のk項の数の和を次の項の値とする数列~~(ただし第1項は1、第n(n≦0)項は0とみなす)		この[[ソースコード]]は、直前のk項の数の[[和]]を次の項の値とする[[数列]](ただし第1項は1、第n(n≦0)項は0とみなす)の第n項の値を[[100000007]]で割った余りを求める[[プログラム]]である。
	の第n項の値を[[100000007]]~~で割った余りを求めるプログラムである。~~

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

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

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

imported>MikeCAT: 作成

2013-08-21T13:07:23Z

作成

新規ページ

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

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

==例==
===なるべく除算をしない===
<source lang="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=(result+a)%c;
a=(a<<1)%c;
b>>=1;
}
return result;
}
</source>
このコードは、a,bがULLONG_MAX/2以下、cがULLONG_MAX/2+1以下のとき、
(a*b) mod cを[[オーバーフロー]]しないように気をつけながら求めるプログラムである。

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

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

===コンパイラに最適化してもらう===
<source lang="c">
#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;
}
</source>
このソースコードは、直前のk項の数の和を次の項の値とする数列(ただし第1項は1、第n(n≦0)項は0とみなす)
の第n項の値を[[100000007]]で割った余りを求めるプログラムである。

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

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

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