実行時間ってなに？

Question

今yukicoderで問題を解いているのですが、簡単なアルゴリズムなのに、やたら長いコードを書いている人がいます。しかしよく見ると、そういう長いコードほど実行時間が短いようなのです（どういう内容なのか全然わからないのですが）。実行時間とは、単純にコードの長さに比例するものではないのですか？ だとしたら、実行時間とは何によって決まってくるのでしょうか。

Answer 1

見かけの行数が少なくても、ループが多くなると実質の計算量が増えます。
3行を10万回ループすれば30万行分です。
ループの回数を少なくする工夫を施した結果、見かけの行数が多くなる場合もあります。
行数が10行になったとしても、ループ部分が3行でループ回数が100回で済めば
307行分の実行時間で済みます。

例えば、こんな問題→セカンド・イクエイション

愚直に条件を満たすa,b,cを数え上げようとしたらこんなループになります。

for(b = 1; b <= m; b++){
    for(a = 1; a <= b * b / 4; a++){
        for(c = 1; c <= b * b / 4; c++){
        }
    }
}

bのループでm回分、その中でaのループをbの2乗比例分、さらにcのループをbの2乗比例分、
bはmに比例して大きくなるので、トータルmの5乗に比例したループがかかります。
このループ回数をなるべく減らすための工夫をこの記事では解説しています。

Comments

[退会済みユーザー]

swordone様の回答が一番しっくりきたのでベストアンサーとさせていただきます。回答をしていただいたほかの方にも、この場を借りてお礼を申し上げます。

Answer 2

プログラムの実行時間は設計やアルゴリズムで大きく変化することがあります。
最近の teratail での質問の中では次の質問では、その回答には大きな実行時間の差があります。
何日もかかるものから、数秒のものまで。

• C言語 円内の整数格子点とπ https://teratail.com/questions/20348

Answer 3

たぶん、その長いコードはC++だったりしませんでしょうか？

競技プログラミング(以下、競プロ)のトップレベルの人の中には競プロセットなる自分用のマクロや関数をはじめから用意しておく方がいます。C++は強力な言語ですが、PerlやRubyなどのスクリプト言語に比べると、短くさらっと書けるものが用意されていない場合があります。そこで、ループや配列を駆使した競プロでよく使うパターンをマクロや関数としてはじめから用意しておけば、素早くコーディングできるという事です。実際にはその部分の全てを使っているわけではないため、コンパイルする時点で無駄な部分はなくなり、実行時には本当に必要なロジックだけが残ります。

なお、yukicoderを含めたほとんどの競プロにおいて、実行時間にコンパイル時間は含まれません。コンパイルした後のファイルの実行したときの時間のみになります。ですので、コンパイル言語にとってはソースコードの長さそのものが実行時間に影響することはありません。(スクリプト言語は実行時にソースコードをパースする必要があるため、多少なりとも影響はあります。)

Comments

[退会済みユーザー]

>実行時間にコンパイル時間は含まれません。
>コンパイル言語にとってはソースコードの長さそのものが実行時間に影響することはありません。

なるほどです。ちなみに言語はJava 8 でした。

Answer 4

yukicoder とは関係は少ないと思いますが、メモリの1千倍、1万倍も遅いディスクのアクセスで効率が悪いSQLを多く実行して処理時間が天文学的なものになっている案件が時々あります。

正規化がまともに出来ていないためのとっても複雑なSQLを書かなければいけない場合もありますし、ERツールを使ってテーブル設計をする費用をケチったために同じ列名なのにデータ型が違っていて、その列に索引が設定されているのにも関わらず索引が使われずにTABLE ACCESS FULLと全件走査になっていたりとか。

Oracleで50時間以上かかっていたプログラムを全部作り直して5時間ちょっとに改善したこともあります。

Answer 5

yukicoderを始めて知りました。
一般的な観点から言えば、ハード側としては、CPU使用率やメモリ使用率、ネットワーク使用率などのハードに負荷がかからない設計をしているか？
また、プログラム側としては、マルチスレッド処理（多重並行処理）設計をしているか？などが挙げられます。
コードの長さは、関係すると言えば関係しますが、設計によります。
きちんと、処理負荷や処理速度を計算して設計してあるプログラムであれば、コードの長さは関係ありません。

シングルスレッド

A→B→C→D

マルチスレッド

A→B→D

↓→C→↑

Answer 6

仮に一行の処理の実行に一行実行時間とすると、下記の式が成り立ちます。
実行時間＝行数*一行実行時間
つまり、実行時間は「行数」と「一行実行時間」に比例します。どちらかを一方でも減少するとプログラムの高速化へとつながります。

直感的には行数を減らすことが効果的そうに見えます。しかし、アルゴリズムとはそもそも問題を効率よく解くために存在しています。アルゴリズムを使うために行数が増えてしまっても、一行実行時間を格段に低下させることができます。

簡単なアルゴリズムであっても、ごくわずかな効率化をはかるために、問題を分解したり、解析したりといろいろな方法で展開しているため、行数が多くなっているのではないでしょうか。