とあるプログラムも作りました
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
typedef struct data Data;
typedef struct data *DataP;
struct data{
int val;
DataP prev;
};
DataP add_data(int i,DataP last);
void print_data(DataP last);
void free_list(DataP last);
int main()
{
int i,k,f,n;
DataP last=NULL;
for(i=2;i<=MAX;i++)
{
k=0;
f=i/2;
for(n=2;f>=n;n++)
{
if((i%n)==0)
{
k= 1;
break;
}
}
if(k==0)
{
printf("%d\n",i);
}
last=add_data(i,last);
}
print_data(last);/*outputの表示を逆にする*/
exit(0);
}
DataP add_data(int i, DataP last)
{
DataP new;
DataP n=last;
while(n!=NULL){
if(i % n->val==0){ /*検索をやめる*/
break;
}
n=n->prev;
}
if(n==NULL){ /*素数なのでリストに加える*/
if((new=(DataP)malloc(sizeof(Data)))==NULL){
fprintf(stderr,"data allocation error !\n");
exit(1);
}
new->val=i;
new->prev=last;
}else{ /*そのまま返す*/
new=last;
}
return new;
}
void print_data(DataP last)
{
while(last!=NULL){
printf("output data %d\n",last->val);
last=last->prev;
}
}
void free_list(DataP last)
{
DataP olast;
while(last!=NULL){
olast=last;
last=last->prev;
free(olast);
}
}
一応、コンパイルしてうまく言ったのですが、これに計算量とメモリの使用量を調べよといわれたのですが、正直どうすればいいのかわかりません。計算量とメモリの使用量がわかるソフトもしくは定義を教えてほしいです。箱を用意して考えろといわれたのですが、何のことかわかりません
よろしくお願いします”!!
メモリの使用量がわかりません!!
Re: メモリの使用量がわかりません!!
「計算量」で検索すると用語説明がいっぱいヒットします。
そのなかから一つを紹介。
http://www.kogures.com/hitoshi/webtext/ ... index.html
この中に
「このように、アルゴリズムでの主要な操作に着目して、解に達するまでに必要な操作回数のことを計算量(注)(オーダー)といい、O (nの式) で表現します。」
と説明されています。
計算量を計測することも可能ですが、ふつうはアルゴリズムをみて、繰り返しがどれだけあるかを考えます。
一般に、与えられた数 n に対して繰り返し回数が n に比例するなら O(n)、
for文が二重になっていて繰り返し回数が n^2 に比例するなら O(n^2)、
for文が三重になっていて繰り返し回数が n^3 に比例するなら O(n^3)、
となります。
さて、あなたのプログラムで一番多く実行されている部分は何回実行されているでしょうか?
また、MAX の値を変えたとき、そこは何回実行されているでしょうか?
その実行回数とMAXの値の関係が計算量です。
メモリの使用量はいろいろな観点で見ることができます。
例えば、それそれの関数のローカル変数が占めるサイズ、
例えば、プログラムそのものが占めるサイズ、
例えば、プログラム中で明示的に確保するメモリのサイズ
設問で求めていることは、これらについて考察することであり、メモリ使用量はどれだけという定量的な答えを求めているものではないと思われます。
たぶん今回は、プログラム中で明示的に確保するメモリのサイズについて答えればよいでしょう。
さて、このプログラムでは何回 malloc して、一回当たりのサイズはどれだけでしょう?
MAXの値を変えたとき、それはどうなるでしょう?
そのなかから一つを紹介。
http://www.kogures.com/hitoshi/webtext/ ... index.html
この中に
「このように、アルゴリズムでの主要な操作に着目して、解に達するまでに必要な操作回数のことを計算量(注)(オーダー)といい、O (nの式) で表現します。」
と説明されています。
計算量を計測することも可能ですが、ふつうはアルゴリズムをみて、繰り返しがどれだけあるかを考えます。
一般に、与えられた数 n に対して繰り返し回数が n に比例するなら O(n)、
for文が二重になっていて繰り返し回数が n^2 に比例するなら O(n^2)、
for文が三重になっていて繰り返し回数が n^3 に比例するなら O(n^3)、
となります。
さて、あなたのプログラムで一番多く実行されている部分は何回実行されているでしょうか?
また、MAX の値を変えたとき、そこは何回実行されているでしょうか?
その実行回数とMAXの値の関係が計算量です。
メモリの使用量はいろいろな観点で見ることができます。
例えば、それそれの関数のローカル変数が占めるサイズ、
例えば、プログラムそのものが占めるサイズ、
例えば、プログラム中で明示的に確保するメモリのサイズ
設問で求めていることは、これらについて考察することであり、メモリ使用量はどれだけという定量的な答えを求めているものではないと思われます。
たぶん今回は、プログラム中で明示的に確保するメモリのサイズについて答えればよいでしょう。
さて、このプログラムでは何回 malloc して、一回当たりのサイズはどれだけでしょう?
MAXの値を変えたとき、それはどうなるでしょう?
Re: メモリの使用量がわかりません!!
道具を使う場合にはプロファイラが使えると思います。素人 さんが書きました:とあるプログラムも作りました
一応、コンパイルしてうまく言ったのですが、これに計算量とメモリの使用量を調べよといわれたのですが、正直どうすればいいのかわかりません。計算量とメモリの使用量がわかるソフトもしくは定義を教えてほしいです。箱を用意して考えろといわれたのですが、何のことかわかりません
よろしくお願いします”!!
例えば、gccだと
gcc -pg example.c
でコンパイルすればプロファイラの組み込まれた実行ファイルが生成されます。
実行すれば
$ ./a.out
$ ls a.out.*
a.out.gmon
gmonという拡張子の実行経過を記録したファイルが作られます。
gprofファイルで処理すればどの関数が何回呼ばれてそれに何ミリ秒/何マイクロ秒かかったとか統計情報を表示してくれます。
$ gprof a.out
gccに限らず様々なコンパイラでプロファイラが含まれているかと思います。
※ unix系だとgprofではなくprofかも知れないし、GNUのツール(Linuxなど)だとgprofだろうし。Microsoft系だと製品版には含まれているが無料で入手できる限定版には含まれてないかも知れません。
詳しく調べたい場合はgprofコマンドのオプションで細かく解析する詳細をせっていできます。