MonoBook

「定数倍高速化」の版間の差分

ビジュアルウィキテキスト
imported>MikeCAT
作成
 
imported>Administrator
編集の要約なし
 
(他の1人の利用者による、間の2版が非表示)
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<2*c,(a<<1)<2*cが成り立つことがわかる。
しかし、よく考えると、最初に与えられるaがc未満のとき、常にresult+a<2*c,(a<<1)<2*cが成り立つことがわかる。
よって、次のように書くことができ、重い除算が比較的軽い減算になるため高速化できる。
よって、次のように書くことができ、重い[[除算]]が比較的軽い減算になるため高速化できる。
<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]]のページを見ていただきたい。
[[category: アルゴリズム]]
「https://monobook.org/wiki/定数倍高速化」から取得