ショッピングモール  


【掲示板ご利用上の注意】

 ※題名は具体的に!
 ※学校の課題の丸投げ禁止!
 ※ソースの添付は「HTML変換ツール」で字下げ!
 ※返信の引用は最小限に!
 ※環境(OSとコンパイラ)や症状は具体的に詳しく!
 ※マルチポスト(多重投稿)は謹んで!

 詳しくはこちら



 本当はこんなに大きく書きたくはないのですが、なかなか守っていただけなくて…。
 守ってくださいね。お願いします。(by管理人)

C言語ソース⇒HTML形式ツール   掲示板1こちら


管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    記事検索    ログ    タグ一覧

No.3038

実行時間の計測
投稿者---マヨ(2004/11/25 06:40:41)


初めましてこんいちわ。
早速ですが、次のプログラムを実行しても正確な時間が得られません。
どこがわるいのでしょうか?
どなたか教えていただけませんでしょうか?
お願いします。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 10

void q_sort(int a[], int left, int right);
void main(void);

void q_sort(int a[], int left, int right)
{
    int i, j;
    int pivot,t;
    int k;
    
    i = left;
    j = right;
    
    pivot = a[(left + right) / 2];
    
    while(1){
              while(a[i] < pivot)
                       i++;
              while(pivot < a[j])
                       j--;
              if(i >= j)
              break;
              
              t = a[i];
              a[i] = a[j];
              a[j] = t;
              
              i++;
              j--;
    }
  
  if(left < i - 1)
       q_sort(a, left, i - 1);
  if(j + 1 <right)
       q_sort(a, j + 1, right);
}

void main(void)
{
    int i, j;
    int a[MAX];
    clock_t start, end;
    long l;

    
    for(i = 0; i < MAX; i++)
        {
            if(scanf("%d",&a[i]) == EOF)
            break;
        }

    start = clock();
    q_sort(a, 0, i - 1);
    end = clock();
    printf("時間: %f秒\n", (double)(end - start) / CLOCKS_PER_SEC);

}



この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:実行時間の計測 3039 monkey 2004/11/25 07:16:12
<子記事> Re:実行時間の計測 3042 nop 2004/11/25 08:55:09
<子記事> Re:実行時間の計測 3045 マヨ 2004/11/25 11:09:00


No.3039

Re:実行時間の計測
投稿者---monkey(2004/11/25 07:16:12)


> 次のプログラムを実行しても正確な時間が得られません

どのような結果を期待していますか。
それに対して、どのような結果でしたか。
結果が正確な時間でないということをどのようにして検証しましたか。
clock関数が返す値の精度は処理系に依存します。開発環境を明示してください。

おそらく、この方法で計測可能な時間より短い時間で処理が終わっているのだと思います。
試しに、"start = clock();"をfor文の前に移動して、入力の時間も含めた経過時間を表示させてみて下さい。


この投稿にコメントする

削除パスワード

No.3040

Re:実行時間の計測
投稿者---マヨ(2004/11/25 08:15:30)


まず、開発環境は
OS:Windows98
コンパイラ:Borland C++ Compiler
エディタ:CPad
です。
どのような結果が得られたいかというと
このプログラムはクイックソートを行うプログラムで
クイックソートにかかる時間を算出するようにしたものなんです。
けれども、データの個数を5000にしても表示される時間が
時間:0.00000sec
となるんです。
ためしに、クイックソートで処理される前の状態と処理後の状態のデータを
表示できるようにしたプログラムを作成し実行してみたところ
体感的なものですが・・・若干の時間がかかっているように思うんです。
でも、先のプログラムだと0secとなるのです。
確実にどこかが間違っていると思うのですが・・・・・・
どこがまちがっているのでしょうか?
教えて下さい。お願いします。


この投稿にコメントする

削除パスワード

No.3041

Re:実行時間の計測
投稿者---Hermit(2004/11/25 08:40:37)


セレ1.2G の環境で、データー数 100000 でやってみたところ、
約 4/100 秒でしたが。


この投稿にコメントする

削除パスワード

No.3043

Re:実行時間の計測
投稿者---もぐりん(2004/11/25 09:35:53)


質問です。
scanfを使用して入力した数字を判定していますが、EOFを検出する条件は?
EOFを見ているってことは、ファイルの終わりを見ているのでは?
標準入力でEOFを検出することはできるのですか?
また、main関数はint型でないのはなぜ?
あと、変数の使い方がいまいち不明です。
q_sort関数内で、変数iとleft、変数jとrightは同じですよね?
if文で判定して真になることがあるのでしょうか?
実測したいのは自作関数であるq_sortの処理時間?
それともqsort関数の処理時間?
他人にソースを見てもらうのなら、せめてコメントを付けましょう。
何をやっているのか読むのが大変です。





この投稿にコメントする

削除パスワード

No.3044

Re:実行時間の計測
投稿者---REE(2004/11/25 10:09:46)


>scanfを使用して入力した数字を判定していますが、EOFを検出する条件は?
>EOFを見ているってことは、ファイルの終わりを見ているのでは?
>標準入力でEOFを検出することはできるのですか?

できますよ。
普通の状態なら、windowsならCtrl+Z、unixならCtrl+DでEOFになります。
リダイレクトしてファイルを入力する場合もEOFはあります。

>q_sort関数内で、変数iとleft、変数jとrightは同じですよね?
>if文で判定して真になることがあるのでしょうか?

if文の前のwhile文の中でi,jが変化する可能性があります。




この投稿にコメントする

削除パスワード

No.3042

Re:実行時間の計測
投稿者---nop(2004/11/25 08:55:09)


>早速ですが、次のプログラムを実行しても正確な時間が得られません。

"より"正確な実行時間を得たいのでしたら、
プロファイルを取ることをお勧めします。


# 最も、どんな方法を用いても、
# "正確な実行時間"は得られないでしょうな。


この投稿にコメントする

削除パスワード

No.3045

Re:実行時間の計測
投稿者---マヨ(2004/11/25 11:09:00)


本当ならば、このプログラムにかかる時間を調べるのが一番良いらしいのですが
それだと、以下の部分までが含まれてしまうのです。
/* データを読み込み配列aへ収納 */
for(i = 0; i < MAX; i++)
        {
            /* 入力行があるだけ読み込み,配列 a に入れる */
        /* 入力行がなくなったら,ループを抜ける      */
       if(scanf("%d",&a[i]) == EOF)
            break;
        }

この部分も含めて時間を計るという作業をしてしまうと
おそらくこの部分だけでそうとうの時間がかかってしまうので
自作関数q_sortだけをはかりたいのですが・・・。

また、自作関数q_sortですが。このようになっています。
/* クイックソート */
void q_sort(int a[], int left, int right)
{
    int i, j;
    int pivot,t;
    int k;
    
    i = left;/* ソートする配列の一番小さい要素の添字 */
    j = right;/* ソートする配列の一番大きい要素の添字 */
    
    pivot = a[(left + right) / 2];/* 基準値を配列の中央付近にとる */

    
    while(1){/* 無限ループ */
              while(a[i] < pivot)/* pivot より大きい値が */
                       i++;/* 出るまで i を増加させる */
              while(pivot < a[j])/* pivot より小さい値が */
                       j--;/*  出るまで j を減少させる */
              if(i >= j)/* i >= j なら */
              break;/* 無限ループから抜ける */
              
              t = a[i];/* a[i]とa[j]の要素を交換 */
              a[i] = a[j];
              a[j] = t;
              
              i++;/* 次のデータ */
              j--;
    }
  
  if(left < i - 1)/* 基準値の左に 2 以上要素があれば */
       q_sort(a, left, i - 1);/* 左の配列をクイックソートする */
  if(j + 1 <right)/* 基準値の右に 2 以上要素があれば */
       q_sort(a, j + 1, right);/* 右の配列をクイックソートする */
}


と、このようになっています。

・・・やはり、Windows98で処理時間を算出するのは難しいのでしょうか?


この投稿にコメントする

削除パスワード

No.3046

Re:実行時間の計測
投稿者---REE(2004/11/25 11:34:35)


>・・・やはり、Windows98で処理時間を算出するのは難しいのでしょうか?

時間が短すぎるため、計りきれなかったのです。
もっと時間がかかる処理なら計れるでしょう。

こういう場合には、同じことを何回もやらせて、その時間を回数で割ればればよいです。

試しに自分の環境でこの方法で試したら10個の時で約400nsでした。


この投稿にコメントする

削除パスワード

No.3047

Re:実行時間の計測
投稿者---マヨ(2004/11/25 13:20:30)


>時間が短すぎるため、計りきれなかったのです。
>もっと時間がかかる処理なら計れるでしょう。

具体的にどういうことですか?
データ数が少ないのでしょうか?
それとも、データを取り込む・クイックソートを行う・結果を出力
まですると実行時間は算出されるかもしれないということでしょうか?



この投稿にコメントする

削除パスワード

No.3050

Re:実行時間の計測
投稿者---Hermit(2004/11/25 14:28:58)


>データ数が少ないのでしょうか?
そういう事だと思います。
通常 1/100sec 単位でしか時間が計れないと思うので、
10msec未満で処理の終わる動作は、clock() を使っても、
0 か、1 しか変化がありません。
REE さんが、計測した値で 400nsec だったら、
clock() の値が 1 上がる確率は 1/25 位かな?

もっと配列データを大きくするか、繰り返しさせないと
clock() の計測時間に引っかからないでしょう。

ただ、データーを大きくすると、
再帰を使っている分、スタックがあふれる可能性があるから
繰り返しでやった方がいいのかな?
それとも、スタックをかなり大きくするか。


この投稿にコメントする

削除パスワード

No.3056

Re:実行時間の計測
投稿者---REE(2004/11/25 17:02:32)


>>データ数が少ないのでしょうか?
>そういう事だと思います。
>通常 1/100sec 単位でしか時間が計れないと思うので、
>10msec未満で処理の終わる動作は、clock() を使っても、
>0 か、1 しか変化がありません。
>REE さんが、計測した値で 400nsec だったら、
>clock() の値が 1 上がる確率は 1/25 位かな?

桁が違います。1/25000ですね



この投稿にコメントする

削除パスワード

No.3087

Re:実行時間の計測
投稿者---KING・王(2004/11/27 01:21:18)


>通常 1/100sec 単位でしか時間が計れないと思うので、

QueryPerformanceCounter()とQueryPerformanceFrequency()を
使用すれば、もう少し細かい時間が取れるのでは?

#はずしていたら、ごめんなさい。



この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    記事検索    ログ    タグ一覧




掲示板提供:Real Integrity