質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
87.20%
C#

C#はマルチパラダイムプログラミング言語の1つで、命令形・宣言型・関数型・ジェネリック型・コンポーネント指向・オブジェクティブ指向のプログラミング開発すべてに対応しています。

受付中

時間計算量の実測値と理論値が大きく異なる理由

unigorou
unigorou

総合スコア0

C#

C#はマルチパラダイムプログラミング言語の1つで、命令形・宣言型・関数型・ジェネリック型・コンポーネント指向・オブジェクティブ指向のプログラミング開発すべてに対応しています。

0回答

-1評価

0クリップ

120閲覧

投稿2022/01/14 16:45

時間計算量(処理にかかる時間)を実際にテストしてみたくて以下のコードを書きました。
内容はシンプルです。

0~nの整数を1ずつ加算してコンソールにn行表示させる処理を、Stopwatchクラスで経過時間を求めてms単位で結果を出力させます。
コードにはn=10000と書きましたが、nに様々な値を代入して何度か実行して平均的な経過時間を求めました。
for文によりn回のConsole.WriteLine()を実行するので、経過時間はnに依存すると考えました。
つまりnを2倍にすれば経過時間も2倍近くになるだろうという予想です。
しかし予想は外れました。

n=10,000の時の経過時間は6732ms(倍率1.00)
n=20,000の時の経過時間は8305ms(倍率1.23)
n=100,000の時の経過時間は19490ms(倍率2.89)

nを2倍、10倍と増やしても経過時間は比例しませんでした。
これは一体なぜでしょうか。

using System; using System.Diagnostics; namespace SortTest { class Program { static void Main(string[] args) { int n = 10000; Stopwatch stopWatch = new Stopwatch(); stopWatch.Start(); // timer start for (int i = 0; i < n; i++) Console.WriteLine(i); // timer stop stopWatch.Stop(); TimeSpan ts = stopWatch.Elapsed; Console.WriteLine($"経過時間:{ts.Seconds * 1000 + ts.Milliseconds}m秒"); } } }

良い質問の評価を上げる

以下のような質問は評価を上げましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

  • プログラミングに関係のない質問
  • やってほしいことだけを記載した丸投げの質問
  • 問題・課題が含まれていない質問
  • 意図的に内容が抹消された質問
  • 過去に投稿した質問と同じ内容の質問
  • 広告と受け取られるような投稿

評価を下げると、トップページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

KOZ6.0
KOZ6.0

2022/01/14 20:06 編集

・Console.WriteLine(i); ではなく、Console.WriteLine(i.ToString("00000000")); として桁数をそろえてみましょう ・デバッグ実行すると、デバッガの影響を受けるので、コマンドプロンプトから実行してみましょう。 ・その際、引数で回数を指定できるようにしておくといいですね。 ・ばらつきが出るので、複数回試行して平均を求めてみましょう。
Zuishin
Zuishin

2022/01/14 23:12

> Console.WriteLine これを使っているからです。 誤差が大きくなるので、計算時間を計る時には出力は必ずループの外に出すのが鉄則です。
unigorou
unigorou

2022/01/15 17:11

アドバイスありがとうございます。 昨日の質問ではVisual Studio2019の「デバッグ無しで実行」で得られた結果を載せました。 ご指摘の通り、Console.WriteLine(i)の箇所に変更を加え、コマンドプロンプト上で実行しました。 結果は以下の通りです。いずれも何度か実行した結果の平均値です。 n=10000の時、経過時間は980ms(倍率1.00) n=20000の時、経過時間は1877ms(倍率1.91) n=100000の時、経過時間は9193ms(倍率9.38) 今回の結果は前回とは対照的にnに比例した数値となりました。 新たな疑問点として、 ①コマンドプロンプトの実行と「デバッグ無しで実行」では両者共にデバッガが走らないと思いますが、こういった実行速度の差ができるのは何か他に要因があるのでしょうか。 ②Console.WriteLine(i) → Console.WriteLine(i.ToString("00000000"))の修正前後において、コマンドプロンプト上で実行した結果、経過時間が異なりました。Console.WriteLine(i)の方が経過時間が長く(n=10000の時、経過時間は1353ms)、実行速度に差が出る上に桁数の大きいほうが速いということが意外だったのですが、こちらもなぜそうなるのか検討がつかず、可能であればご助言頂けると幸いです。
Zuishin
Zuishin

2022/01/15 21:47

だから言ってるじゃないか。コンソールバッファについて調べてきたらいい。
unigorou
unigorou

2022/01/16 08:50

アドバイスありがとうございます。 調べてみます。

まだ回答がついていません

会員登録して回答してみよう

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
87.20%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

C#

C#はマルチパラダイムプログラミング言語の1つで、命令形・宣言型・関数型・ジェネリック型・コンポーネント指向・オブジェクティブ指向のプログラミング開発すべてに対応しています。