今yukicoderで問題を解いているのですが、簡単なアルゴリズムなのに、やたら長いコードを書いている人がいます。しかしよく見ると、そういう長いコードほど実行時間が短いようなのです(どういう内容なのか全然わからないのですが)。実行時間とは、単純にコードの長さに比例するものではないのですか? だとしたら、実行時間とは何によって決まってくるのでしょうか。
気になる質問をクリップする
クリップした質問は、後からいつでもMYページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
回答6件
0
ベストアンサー
見かけの行数が少なくても、ループが多くなると実質の計算量が増えます。
3行を10万回ループすれば30万行分です。
ループの回数を少なくする工夫を施した結果、見かけの行数が多くなる場合もあります。
行数が10行になったとしても、ループ部分が3行でループ回数が100回で済めば
307行分の実行時間で済みます。
例えば、こんな問題→セカンド・イクエイション
愚直に条件を満たすa,b,cを数え上げようとしたらこんなループになります。
java
1for(b = 1; b <= m; b++){ 2 for(a = 1; a <= b * b / 4; a++){ 3 for(c = 1; c <= b * b / 4; c++){ 4 } 5 } 6}
bのループでm回分、その中でaのループをbの2乗比例分、さらにcのループをbの2乗比例分、
bはmに比例して大きくなるので、トータルmの5乗に比例したループがかかります。
このループ回数をなるべく減らすための工夫をこの記事では解説しています。
投稿2015/12/08 16:34
編集2015/12/08 16:54総合スコア20651
0
プログラムの実行時間は設計やアルゴリズムで大きく変化することがあります。
最近の teratail での質問の中では次の質問では、その回答には大きな実行時間の差があります。
何日もかかるものから、数秒のものまで。
- C言語 円内の整数格子点とπ https://teratail.com/questions/20348
投稿2015/12/08 22:49
総合スコア22324
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
たぶん、その長いコードはC++だったりしませんでしょうか?
競技プログラミング(以下、競プロ)のトップレベルの人の中には競プロセットなる自分用のマクロや関数をはじめから用意しておく方がいます。C++は強力な言語ですが、PerlやRubyなどのスクリプト言語に比べると、短くさらっと書けるものが用意されていない場合があります。そこで、ループや配列を駆使した競プロでよく使うパターンをマクロや関数としてはじめから用意しておけば、素早くコーディングできるという事です。実際にはその部分の全てを使っているわけではないため、コンパイルする時点で無駄な部分はなくなり、実行時には本当に必要なロジックだけが残ります。
なお、yukicoderを含めたほとんどの競プロにおいて、実行時間にコンパイル時間は含まれません。コンパイルした後のファイルの実行したときの時間のみになります。ですので、コンパイル言語にとってはソースコードの長さそのものが実行時間に影響することはありません。(スクリプト言語は実行時にソースコードをパースする必要があるため、多少なりとも影響はあります。)
投稿2015/12/08 22:22
総合スコア21735
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
yukicoder とは関係は少ないと思いますが、メモリの1千倍、1万倍も遅いディスクのアクセスで効率が悪いSQLを多く実行して処理時間が天文学的なものになっている案件が時々あります。
正規化がまともに出来ていないためのとっても複雑なSQLを書かなければいけない場合もありますし、ERツールを使ってテーブル設計をする費用をケチったために同じ列名なのにデータ型が違っていて、その列に索引が設定されているのにも関わらず索引が使われずにTABLE ACCESS FULLと全件走査になっていたりとか。
Oracleで50時間以上かかっていたプログラムを全部作り直して5時間ちょっとに改善したこともあります。
投稿2015/12/09 00:26
総合スコア16415
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
yukicoderを始めて知りました。
一般的な観点から言えば、ハード側としては、CPU使用率やメモリ使用率、ネットワーク使用率などのハードに負荷がかからない設計をしているか?
また、プログラム側としては、マルチスレッド処理(多重並行処理)設計をしているか?などが挙げられます。
コードの長さは、関係すると言えば関係しますが、設計によります。
きちんと、処理負荷や処理速度を計算して設計してあるプログラムであれば、コードの長さは関係ありません。
シングルスレッド
A→B→C→D
マルチスレッド
A→B→D
↓→C→↑
投稿2015/12/08 16:41
編集2015/12/08 16:44退会済みユーザー
総合スコア0
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
仮に一行の処理の実行に一行実行時間とすると、下記の式が成り立ちます。
実行時間=行数*一行実行時間
つまり、実行時間は「行数」と「一行実行時間」に比例します。どちらかを一方でも減少するとプログラムの高速化へとつながります。
直感的には行数を減らすことが効果的そうに見えます。しかし、アルゴリズムとはそもそも問題を効率よく解くために存在しています。アルゴリズムを使うために行数が増えてしまっても、一行実行時間を格段に低下させることができます。
簡単なアルゴリズムであっても、ごくわずかな効率化をはかるために、問題を分解したり、解析したりといろいろな方法で展開しているため、行数が多くなっているのではないでしょうか。
投稿2015/12/08 16:28
総合スコア18155
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
あなたの回答
tips
太字
斜体
打ち消し線
見出し
引用テキストの挿入
コードの挿入
リンクの挿入
リストの挿入
番号リストの挿入
表の挿入
水平線の挿入
プレビュー
質問の解決につながる回答をしましょう。 サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。 また、読む側のことを考えた、分かりやすい文章を心がけましょう。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
退会済みユーザー
2015/12/09 02:35