「定数倍高速化」の版間の差分
imported>MikeCAT 作成 |
編集の要約なし |
||
| 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とみなす)の第n項の値を[[100000007]]で割った余りを求める[[プログラム]]である。 | |||
の第n項の値を[[100000007]] | |||
この[[コード]]を[[gcc]]4.7.2で[[コンパイル]]した場合、-O2の[[最適化]]をかけた[[バイナリ]]は、 | |||
同じ入力に対し、最適化オプションをつけずに[[コンパイル]]した[[バイナリ]]の約43%の実行時間で答えを出すことができた。 | |||
===OpenMPを使う=== | ===OpenMPを使う=== | ||
[[OpenMP]]を使うと、数行のおまじないとコンパイルオプションの追加により、 | |||
実行中の[[CPU]]使用率を上げる代わりに実行時間を短くすることができる。 | 実行中の[[CPU]]使用率を上げる代わりに実行時間を短くすることができる。 | ||
詳しくは、[[OpenMP]]のページを見ていただきたい。 | 詳しくは、[[OpenMP]]のページを見ていただきたい。 | ||