関数が何回呼ばれたかを記録してみる
プログラムの最適化を図るためには、どの関数が実行中に何回呼ばれたかを知らなくてはいけない。なぜかというと、最適化はすべての関数に対してする必要がないことと、使用頻度が少ない関数を最適化するより、多い関数を最適化したほうが効率がいいためである。つまり、最小限の努力で最大限の成果を上げるためにも必要なことである。これをプロファイリング と呼ぶ。
プロファイリングのやり方
まずは次のような簡単なソースコードをエディタで入力することから始める。これはヒープソートのアルゴリズムのコードである。これをプロファイリングにかけてみる。そしてプロファイリングのための引数をつけてコンパイルしてみる。
> gcc -pg heapsort.c
heapsort.c
http://www.geocities.jp/ky_webid/algorithm/022.htmlより引用
#include <stdio.h>
#include <stdlib.h>
#define HEAP_SIZE (50) /* ヒープの最大サイズ */
#define ARRAY_SIZE (10) /* ソートする配列のサイズ */
/* グローバル変数 */
int g_heap[HEAP_SIZE]; /* ヒープ */
int g_index; /* 未使用になっている最後のヒープ領域の添字 */
/* プロトタイプ宣言 */
void heap_sort(int array[], int size);
void insert_heap(int array[], int size);
void up_heap(int index);
int get_root(void);
void down_heap(void);
void print_array(int array[], int size);
int main(void)
{
int array[ARRAY_SIZE] = { 20, 40, 90, 30, 60, 0, 50, 70, 10, 80 };
print_array( array, ARRAY_SIZE );
heap_sort( array, ARRAY_SIZE );
print_array( array, ARRAY_SIZE );
return 0;
}
/*
ヒープソートを実行する。
引数 array : ソート対象とする配列。
size : 配列の要素数。
*/
void heap_sort(int array[], int size)
{
int i;
/* データをヒープに挿入する */
insert_heap( array, size );
/* ヒープから根を取り出す。根には常に最小の値があるため、この操作で昇順に並ぶ */
for( i = 0; i < size; ++i )
{
array[i] = get_root();
}
}
/*
ヒープにデータを挿入する。
引数 array : ソート対象とする配列。
size : 配列の要素数。
*/
void insert_heap(int array[], int size)
{
int i;
for( i = 0; i < size; ++i )
{
/* ヒープが一杯ではないか確認する */
if( g_index >= HEAP_SIZE )
{
fprintf( stderr, "ヒープが一杯です\n" );
exit( 1 );
}
/* 要素をヒープの最後に挿入する */
++g_index;
g_heap[g_index] = array[i];
/* 挿入した要素を、適切な位置に並ぶように移動させる */
up_heap( g_index );
}
}
/*
ヒープの指定要素を、適切な位置に浮かび上がらせる。
引数 index : 移動させる要素の添字。
*/
void up_heap(int index)
{
int tmp = g_heap[index]; /* 対象とする要素の値を保存 */
/*
条件① index > 1・・・indexが指す位置は根に到達していない
条件② g_heap[index / 2] > tmp・・・親の方がindexが指す要素より大きい
*/
while( index > 1 && g_heap[index / 2] > tmp )
{
g_heap[index] = g_heap[index / 2]; /* 親の値を、子に移動させる */
index /= 2; /* 親の位置に添字を動かす */
}
g_heap[index] = tmp; /* 最終的に決定した移動位置に、値をコピーする */
}
/*
ヒープの根の要素を取り出す。
戻り値 根の要素。
*/
int get_root(void)
{
int tmp;
/* ヒープが空でないか確認する */
if( g_index < 1 )
{
fprintf( stderr, "ヒープが空です\n" );
exit( 1 );
}
/* 戻り値として返す根の値を保存しておく */
tmp = g_heap[1];
/* ヒープの最後にある要素を、先頭に移動する */
g_heap[1] = g_heap[g_index];
--g_index;
/* 先頭に移動させた要素を、正しい位置に沈める */
down_heap();
return tmp;
}
/*
ヒープの根の値を、適切な位置に沈める。
*/
void down_heap(void)
{
int i, j;
int tmp = g_heap[1]; /* 根の値を保存しておく */
i = 1;
/*
条件 g_indexの位置にある要素が、子を持っている間は繰り返す
*/
while( i <= g_index / 2 )
{
j = i * 2; /* 添字を２倍することにより、左の子を指す添字が得られる */
/*
条件① j + 1 <= g_index・・・ヒープの最後に達していない
条件② g_heap[j] > g_heap[j + 1]・・・左の子の方が、右の子より大きい
*/
if( j + 1 <= g_index && g_heap[j] > g_heap[j + 1] )
{
j = j + 1; /* jはg_heap[i]の右の子の添字になる */
}
/* 根の値として保存しておいた値より、子の方が大きいならwhileループを抜ける */
if( tmp <= g_heap[j] )
{
break;
}
g_heap[i] = g_heap[j]; /* 子の値を、親の位置に代入 */
i = j; /* 子の位置を、新たな注目点とする */
}
g_heap[i] = tmp; /* 最初に保存しておいた根の値を代入 */
}
/*
配列の要素を出力。
引数 array：出力する配列。
size：配列の要素数。
*/
void print_array(int array[], int size)
{
int i;
int *p = &array[0];
for( i = 0; i < size; ++i )
{
printf( "%d ", *p );
++p;
}
printf( "\n\n" );
}
プロファイリングの実行結果を知る
> gprof a.exe gmon.out
とすると、次のような結果が得られる。（一部抜粋）
% cumulative self self total time seconds seconds calls Ts/call Ts/call name 0.00 0.00 0.00 10 0.00 0.00 down_heap 0.00 0.00 0.00 10 0.00 0.00 get_root 0.00 0.00 0.00 10 0.00 0.00 up_heap 0.00 0.00 0.00 2 0.00 0.00 print_array 0.00 0.00 0.00 1 0.00 0.00 heap_sort 0.00 0.00 0.00 1 0.00 0.00 insert_heap
