「定数倍高速化」を編集中
ナビゲーションに移動
検索に移動
この編集を取り消せます。 下記の差分を確認して、本当に取り消していいか検証してください。よろしければ変更を保存して取り消しを完了してください。
最新版 | 編集中の文章 | ||
1行目: | 1行目: | ||
− | + | 定数倍高速化とは、[[アルゴリズム]]の改善による[[高速化]]とは違い、 | |
+ | 計算処理の方法を改善することにより[[計算量]]の[[オーダー]]を変えずに処理を高速化することである。 | ||
− | + | [[競技プログラミング]]においてはほとんどの場合意味がないが、 | |
− | [[競技プログラミング]] | + | たまに定数倍高速化で無理矢理通せる場合、 |
+ | [[想定解]]のアルゴリズムだけど自分の[[実装]]が悪いので定数倍高速化しないと通らない場合など、 | ||
+ | 定数倍高速化が役に立つ場面がある。 | ||
==例== | ==例== | ||
19行目: | 22行目: | ||
</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 */ | ||
42行目: | 45行目: | ||
===なるべく再帰を使わない=== | ===なるべく再帰を使わない=== | ||
− | [[再帰]] | + | [[再帰]]を使ったプログラムは、再帰を使わない処理に比べて、 |
[[関数]]の呼び出しによる[[スタック]]の確保・復帰処理が入るため低速になることが多い。 | [[関数]]の呼び出しによる[[スタック]]の確保・復帰処理が入るため低速になることが多い。 | ||
121行目: | 124行目: | ||
} | } | ||
</source> | </source> | ||
− | + | このソースコードは、直前のk項の数の和を次の項の値とする数列(ただし第1項は1、第n(n≦0)項は0とみなす) | |
+ | の第n項の値を[[100000007]]で割った余りを求めるプログラムである。 | ||
− | + | このコードを[[gcc]]4.7.2で[[コンパイル]]した場合、-O2の[[最適化]]をかけた[[バイナリ]]は、 | |
− | + | 同じ入力に対し、最適化オプションをつけずにコンパイルしたバイナリの約43%の実行時間で答えを出すことができた。 | |
===OpenMPを使う=== | ===OpenMPを使う=== | ||
− | + | OpenMPを使うと、数行のおまじないとコンパイルオプションの追加により、 | |
実行中の[[CPU]]使用率を上げる代わりに実行時間を短くすることができる。 | 実行中の[[CPU]]使用率を上げる代わりに実行時間を短くすることができる。 | ||
詳しくは、[[OpenMP]]のページを見ていただきたい。 | 詳しくは、[[OpenMP]]のページを見ていただきたい。 | ||
− | |||
− |