第4回ビルドツール、関数ポインタ、アルゴリズム4

本日の講義内容

GNU Make
関数ポインタ
連続最適化

GNU Make

ビルドツールは、コンパイルなどを自動化するためのツールです。これまで手動で実行していた面倒な作業をビルドツールに任せることで、ソースコードから実行可能ファイルなどを効率的かつ再現しやすいかたちで生成できます。そのようなビルドツールの代表的なものとして、今回はmakeを使ってみましょう。

これまで複数のソースファイルを用いて分割コンパイルをおこなっていると、各ファイルの管理や、何度もコンパイルを繰り返す手順について面倒を感じることもあったと思います。あるいは、ソースコードを修正したのに全然修正が反映されておらず、あとでコンパイルやリンクを忘れていたことに気付く、といったこともあったのではないでしょうか。こうした問題を解消するためにmakeがあります。

Makefile

Makefileはプログラムをコンパイルするために必要な情報を記述したファイルで、どのファイルがどのファイルで使われるかといった依存関係を適切に記述することで、適切な順序でコンパイルをおこなってくれます。Makefileが存在するディレクトリでmakeコマンドを実行すると、用意されたMakefileを参照してコンパイルを実行してくれます。

target: prerequisites
    command

ここで

target: 生成したいファイル
prerequisites: targetを生成するのに必要なファイル
command: 実行するコマンド

を表します。注意すべき点として個々のcommandの前にはタブが必要です。

以下は具体例です。

Makefile
main.o: main.c
    gcc -c main.c

上記は

main.oを作成するためには、main.cが必要
main.o作成のためのコマンドは、gcc –c main.cである

ということを示しています。

Makefileの記述内容を実際に実行する場合は、Makefileが存在するディレクトリで以下のようなコマンドを実行します。

$ make target

targetは生成したいファイルの名前によって変わります。これによって指定したcommandが実行されtargetが作成されます。なお、実行の際にはprerequisitesのタイムスタンプがチェックされ、更新されている場合にのみcommandが実行されます。すなわちプログラムの再コンパイルの必要がない場合にはコンパイルされず、ファイルが修正された場合にのみコンパイルが実行されます。

なお、

$ make

のようにtargetを省略した場合は、Makefileで最初に定義されているtargetが作成されます。

Makefileの具体例

第1回で示した、行列ベクトル演算のプログラムについて、改めてMakefileを使ってコンパイルしてみましょう。このプログラムは、main.c、vector.c、matrix.cの3つのソースファイルからなるものでした。それぞれのソースファイルをコンパイルして、最終的にcalcという実行可能ファイルを作成しましょう。

Makefile
# コメントは#から行末まで
calc: main.o vector.o matrix.o
    gcc -o calc main.o vector.o matrix.o

main.o: main.c
    gcc -c main.c

vector.o: vector.c
    gcc -c vector.c

matrix.o: matrix.c
    gcc -c matrix.c

main.c
#include "matrix.h"
#include "vector.h"

int main() {
    Vector x = (Vector){ .v = { 1.0, 2.0 } };
    Vector y = (Vector){ .v = { 3.0, 4.0 } };
    Matrix A = (Matrix){ .v = { 1.0, -1.0, -1.0, 1.0} };

    // c = 2.0 x + y
    Vector c = axpy(2.0, x, y);
    // d = 2.0 Ax + y
    Vector d = gemv(2.0, A, x, 1.0, y);

    print_vector(c);
    print_vector(d);
    return 0;
}

vector.c
#include <stdio.h>
#include "vector.h"

Vector axpy(double alpha, Vector a, Vector b) {
    return (Vector){ .v = { alpha * a.v[0] + b.v[0], alpha * a.v[1] + b.v[1]}};
}

void print_vector(Vector a) {
    printf("[%f %f]\n",a.v[0],a.v[1]);
}

matrix.c
#include <stdio.h>
#include "matrix.h"
#include "vector.h"

Vector gemv(double alpha, Matrix A, Vector x, double beta, Vector y) {
    return (Vector){ .v = {alpha * (A.v[0]*x.v[0]+A.v[1]*x.v[1]) + beta * y.v[0], alpha * (A.v[2]*x.v[0]+A.v[3]*x.v[1]) + beta * y.v[1]}};
}

void print_matrix(Matrix m) {
    printf("[%f %f ;%f %f]\n",m.v[0],m.v[1],m.v[2],m.v[3]);    
}

vector.h
#pragma once
typedef struct {
    double v[2];
} Vector;

// ax + y の形 (BLAS level1と同じ命名)
Vector axpy(double alpha, Vector a, Vector b);
void print_vector(Vector a);

matrix.h
#pragma once
#include "vector.h"

typedef struct{
    double v[4]; // 2 x 2
} Matrix;

// プロトタイプ宣言でVector型を知っている必要がある
// alpha * Ax + beta * y (BLAS level2と同じ命名)
Vector gemv(double alpha, Matrix A, Vector x, double beta, Vector y);
void print_matrix(Matrix m);

演習

上記を同一フォルダに置き、makeでコンパイルしてみましょう。

Phony target

makeで指定するtargetは必ずしも生成するファイルでなくてもよく、単なるコマンド用のラベルとして便利に使うことができます。このようなターゲットをphony targetと呼びます。よく使われる名前として、cleanがあります。以下のようにMakefileに記述すると、make cleanと実行することでa.outやオブジェクトファイル等をまとめて消すことができます。

clean:
    rm *.o a.out

例えば全てのソースを1からコンパイルし直したい場合には、以下のように実行します。

$ make clean
$ make

この際にもしcleanというファイルが存在すると意図した挙動をしないため、実際に作成したいファイルではなくコマンド用のラベルであることを明示しておきます。

.PHONY: clean
clean:
    rm *.o a.out

演習

先ほどのMakefileにcleanを追加し、make cleanでファイルを削除してみましょう。

変数

Makefileの中では変数が定義可能です。例えばコンパイラとしてgcc以外を使いたい等、環境に応じて変数への代入を変更することで、異なる挙動を実現できます。

Makefile
CC = gcc

calc: main.o vector.o matrix.o
    $(CC) -o calc main.o vector.o matrix.o

main.o: main.c
    $(CC) -c main.c
vector.o: vector.c
    $(CC) -c vector.c
matrix.o: matrix.c
    $(CC) -c matrix.c

このように、他のプログラムを変数を用いて呼び出すことで、環境に応じて異なる挙動を実現しやすくするのは変数の便利な使い方の一つです。

さらに各commandで使える変数として以下があります。これを用いることで、ファイル名のハードコーディングを回避できます。

$@: targetのファイル名
$<: prerequisitesの最初のファイル名
$^: 全てのprerequisitesのファイル名をスペースで区切ったリスト

また、ルールを定義するために%記号を使うことができます。%は任意の文字列にマッチするワイルドカードです。

%.o: %.c
    $(CC) $(CFLAGS) -c $< -o $@

上記は「任意の.oファイルは、同名の.cファイルから作成される」というルールを表しています。例えばmain.oを作成する場合、%はmainにマッチし、main.cからmain.oが生成されます。これにより、複数のソースファイルに対して同じコンパイルルールを一度に定義できます。

演習

先ほどのMakefileのgccや各種ファイル名を変数で表現してみましょう。

暗黙ルール

実はMakefileはいくつかの言語の基本的なコンパイルパターンについて暗黙のルールを持っていて、ターゲットとして指定されていないファイルがprerequisitesに含まれる場合にも自動的に暗黙ルールに基づくコンパイルをおこなってくれます。例えばfoo.oはfoo.cから

$(CC) $(CPPFLAGS) $(CFLAGS) -c

で作成されるというルールは暗黙ルールに含まれています。そのため、先ほどのMakefileはさらに短縮して記述することができます。

CC = gcc

calc: main.o vector.o matrix.o
    $(CC) main.o vector.o matrix.o

これを活用すると、calcをターゲットにする場合は、結局以下のMakefileだけで分割コンパイルが可能となります。

Makefile
CC = gcc
TARGET = calc
OBJS = main.o vector.o matrix.o

$(TARGET): $(OBJS)
    $(CC) -o $@ $^

演習

第1回でも示した、以下のintlib.h、main.c、intlib.cを

.
├── bin
├── include
│   └── intlib.h
├── lib
└── src
    ├── main.c
    └── intlib.c

のように適切に配置した上で、ライブラリlibinteger.aおよび実行可能ファイルqsortをmakeで作成してみてください。

ヒント: 各ディレクトリについては、$(BINDIR)、$(INCLUDE)、$(LIBDIR)、$(SRCDIR)といった変数を定義するなどして表現することができます。たとえばオブジェクトファイルは$(SRCDIR)に配置することにして、$(SRCDIR)/intlib.oといった形で参照することができます。

main.c
#include <stdio.h> 
#include <stdlib.h>
#include "intlib.h"

int main(int argc, char **argv) {
    if (argc != 2) {
        fprintf(stderr, "usage: %s <number of elements>\n", argv[0]);
        exit(EXIT_FAILURE);
    }

    int n = load_int(argv[1]);
    int v[n];

    for (int i = 0; i < n; i++) {
        v[i] = rand() % 1024;
    }

    printf("[");
    for(int i = 0; i < n; i++){
        printf("%d ", v[i]);
    }
    printf("]\n");

    qsort(v, n, sizeof(int), comp_int);

    for (int i = 0; i < n; i++) {
        printf("v[%d] = %d\n", i, v[i]);
    }

    return 0;
}

intlib.c
#include <stdio.h>
#include <stdlib.h>
#include <errno.h> 
#include <string.h>
#include "intlib.h"  // これはこのファイルのコンパイル自体には不要ですが、ライブラリとペアということで設置

int comp_int(const void *x0, const void *x1) {
    const int *p0 = x0;
    const int y0 = *p0;
    const int *p1 = x1;
    const int y1 = *p1;

    if (y0 > y1) return 1;
    if (y0 < y1) return -1;
    return 0;
}

int load_int(const char *str) {
    errno = 0;
    char *e;
    long n = strtol(str,&e,10);

    if (errno == ERANGE) {
    fprintf(stderr, "%s: %s\n", str, strerror(errno));
    exit(1);
    }
    if ( *e != '\0') {
    fprintf(stderr, "%s: an irregular character '%c' is detected.\n",str,*e);
    exit(EXIT_FAILURE);
    }
    return (int)n;
}

intlib.h
int comp_int(const void *x0, const void *x1);
int load_int(const char *str);

こたえ

生成すべきオブジェクトファイルをディレクトリ名付きで指定することで、暗黙ルールでオブジェクトファイルを生成し、それ以外はコンパイル対象の依存関係だけから適切な順序でコンパイルが実行されます。

Makefile
CC = gcc

BINDIR = ./bin
INCLUDE = ./include
LIBDIR = ./lib
SRCDIR = ./src

CFLAGS = -Wall -I$(INCLUDE) 
LDFLAGS = -L$(LIBDIR)
LDLIBS = -linteger 

SRC = $(SRCDIR)/main.c
OBJ = $(SRCDIR)/intlib.o
LIB = $(LIBDIR)/libinteger.a

TARGET = $(BINDIR)/qsort

$(TARGET): $(SRC) $(LIB)
    $(CC) $(CFLAGS) -o $@ $< $(LDFLAGS) $(LDLIBS)

$(LIB): $(OBJ)
    $(AR) rsv $@ $^

.PHONY: tmpclean clean

tmpclean:
    rm -f $(SRCDIR)/*~
clean: tmpclean
    rm -f $(TARGET) $(LIB) $(OBJ)

演習

第2回で示した、線形リスト版のペイントソフトpaint.cを、複数のヘッダファイル、ソースファイルに分割し、Makefileでコンパイルできるように修正してみましょう。

コンパイルディレクトリを整頓し、makeコマンドのみでコンパイルできるようにする。
main関数を含むファイル名はpaintapp.cとする。適宜分割したソースファイルを用いる。

paint.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <errno.h> // for error catch

// Structure for canvas
typedef struct {
    int width;
    int height;
    char **canvas;
    char pen;
} Canvas;

// Command 構造体と History構造体
// [*]
typedef struct command Command;
struct command{
    char *str;
    size_t bufsize;
    Command *next;
};

typedef struct {
    Command *begin;
    size_t bufsize; 
} History;

// functions for Canvas type
Canvas *init_canvas(int width, int height, char pen);
void reset_canvas(Canvas *c);
void print_canvas(Canvas *c);
void free_canvas(Canvas *c);

// display functions
void rewind_screen(unsigned int line); 
void clear_command(void);
void clear_screen(void);

// enum for interpret_command results
// interpret_command の結果をより詳細に分割
typedef enum res{ EXIT, LINE, UNDO, SAVE, UNKNOWN, ERRNONINT, ERRLACKARGS, NOCOMMAND} Result;
// Result 型に応じて出力するメッセージを返す
char *strresult(Result res);

int max(const int a, const int b);
void draw_line(Canvas *c, const int x0, const int y0, const int x1, const int y1);
Result interpret_command(const char *command, History *his, Canvas *c);
void save_history(const char *filename, History *his);

// [*] list.c のpush_backと同じ
Command *push_command(History *his, const char *str);

int main(int argc, char **argv) {
    //for history recording

    const int bufsize = 1000;

    // [*]
    History his = (History){ .begin = NULL, .bufsize = bufsize};

    int width;
    int height;
    if (argc != 3){
        fprintf(stderr,"usage: %s <width> <height>\n",argv[0]);
        return EXIT_FAILURE;
    }
    else {
        char *e;
        long w = strtol(argv[1],&e,10);
        if (*e != '\0'){
            fprintf(stderr, "%s: irregular character found %s\n", argv[1],e);
            return EXIT_FAILURE;
        }
        long h = strtol(argv[2],&e,10);
        if (*e != '\0'){
            fprintf(stderr, "%s: irregular character found %s\n", argv[2],e);
            return EXIT_FAILURE;
        }
        width = (int)w;
        height = (int)h;    
    }
    char pen = '*';


    char buf[bufsize];

    Canvas *c = init_canvas(width,height, pen);

    printf("\n"); // required especially for windows env

    while(1){
        // [*]
        // hsize はひとまずなし
        // 作る場合はリスト長を調べる関数を作っておく
        print_canvas(c);
        printf("* > ");
        if(fgets(buf, bufsize, stdin) == NULL) break;

        const Result r = interpret_command(buf, &his, c);

        if (r == EXIT) break;

        // 返ってきた結果に応じてコマンド結果を表示
        clear_command();
        printf("%s\n",strresult(r));
        // LINEの場合はHistory構造体に入れる
        if (r == LINE) {
            // [*]
            push_command(&his,buf);
        }

        rewind_screen(2); // command results
        clear_command(); // command itself
        rewind_screen(height+2); // rewind the screen to command input

    }

    clear_screen();
    free_canvas(c);

    return 0;
}

Canvas *init_canvas(int width,int height, char pen) {
    Canvas *new = (Canvas *)malloc(sizeof(Canvas));
    new->width = width;
    new->height = height;
    new->canvas = (char **)malloc(width * sizeof(char *));

    char *tmp = (char *)malloc(width*height*sizeof(char));
    memset(tmp, ' ', width*height*sizeof(char));
    for (int i = 0 ; i < width ; i++){
        new->canvas[i] = tmp + i * height;
    }

    new->pen = pen;
    return new;
}

void reset_canvas(Canvas *c) {
    const int width = c->width;
    const int height = c->height;
    memset(c->canvas[0], ' ', width*height*sizeof(char));
}


void print_canvas(Canvas *c) {
    const int height = c->height;
    const int width = c->width;
    char **canvas = c->canvas;

    // 上の壁
    printf("+");
    for (int x = 0 ; x < width ; x++) printf("-");
    printf("+\n");

    // 外壁と内側
    for (int y = 0 ; y < height ; y++) {
        printf("|");
        for (int x = 0 ; x < width; x++){
            const char c = canvas[x][y];
            putchar(c);
        }
        printf("|\n");
    }

    // 下の壁
    printf("+");
    for (int x = 0 ; x < width ; x++) printf("-");
    printf("+\n");
    fflush(stdout);
}

void free_canvas(Canvas *c) {
    free(c->canvas[0]); //  for 2-D array free
    free(c->canvas);
    free(c);
}

void rewind_screen(unsigned int line) {
    printf("\e[%dA",line);
}

void clear_command(void) {
    printf("\e[2K");
}

void clear_screen(void) {
    printf("\e[2J");
}

int max(const int a, const int b) {
    return (a > b) ? a : b;
}

void draw_line(Canvas *c, const int x0, const int y0, const int x1, const int y1) {
    const int width = c->width;
    const int height = c->height;
    char pen = c->pen;

    const int n = max(abs(x1 - x0), abs(y1 - y0));
    if ( (x0 >= 0) && (x0 < width) && (y0 >= 0) && (y0 < height)) c->canvas[x0][y0] = pen;
    for (int i = 1; i <= n; i++) {
        const int x = x0 + i * (x1 - x0) / n;
        const int y = y0 + i * (y1 - y0) / n;
        if ( (x >= 0) && (x< width) && (y >= 0) && (y < height)) c->canvas[x][y] = pen;
    }
}

void save_history(const char *filename, History *his) {
    const char *default_history_file = "history.txt";
    if (filename == NULL) filename = default_history_file;

    FILE *fp;
    if ((fp = fopen(filename, "w")) == NULL) {
        fprintf(stderr, "error: cannot open %s.\n", filename);
        return;
    }
    // [*] 線形リスト版
    for (Command *p = his->begin ; p != NULL ; p = p->next){
        fprintf(fp, "%s", p->str);
    }

    fclose(fp);
}

Result interpret_command(const char *command, History *his, Canvas *c) {
    char buf[his->bufsize];
    strcpy(buf, command);
    buf[strlen(buf) - 1] = 0; // remove the newline character at the end

    const char *s = strtok(buf, " ");
    if (s == NULL){ // 改行だけ入力された場合
        return UNKNOWN;
    }
    // The first token corresponds to command
    if (strcmp(s, "line") == 0) {
        int p[4] = {0}; // p[0]: x0, p[1]: y0, p[2]: x1, p[3]: x1 
        char *b[4];
        for (int i = 0 ; i < 4; i++){
            b[i] = strtok(NULL, " ");
            if (b[i] == NULL){
                return ERRLACKARGS;
            }
        }
        for (int i = 0 ; i < 4 ; i++){
            char *e;
            long v = strtol(b[i],&e, 10);
            if (*e != '\0'){
                return ERRNONINT;
            }
            p[i] = (int)v;
        }

        draw_line(c,p[0],p[1],p[2],p[3]);
        return LINE;
    }

    if (strcmp(s, "save") == 0) {
        s = strtok(NULL, " ");
        save_history(s, his);
        return SAVE;
    }

    if (strcmp(s, "undo") == 0) {
        reset_canvas(c);
        //[*] 線形リストの先頭からスキャンして逐次実行
        // pop_back のスキャン中にinterpret_command を絡めた感じ
        Command *p = his->begin;
        if (p == NULL){
            return NOCOMMAND;
        }
        else{
            Command *q = NULL; // 新たな終端を決める時に使う
            while (p->next != NULL){ // 終端でないコマンドは実行して良い
                interpret_command(p->str, his, c);
                q = p;
                p = p->next;
            }
            // 1つしかないコマンドのundoではリストの先頭を変更する
            if (q == NULL) {
                his->begin = NULL;
            }
            else{
                q->next = NULL;
            }
            free(p->str);
            free(p);    
            return UNDO;
        }  
    }

    if (strcmp(s, "quit") == 0) {
        return EXIT;
    }
    return UNKNOWN;
}

// [*] 線形リストの末尾にpush する
Command *push_command(History *his, const char *str) {
    Command *c = (Command*)malloc(sizeof(Command));
    char *s = (char*)malloc(his->bufsize);
    strcpy(s, str);

    *c = (Command){ .str = s, .bufsize = his->bufsize, .next = NULL};

    Command *p = his->begin;

    if ( p == NULL) {
        his->begin = c;
    }
    else{
        while (p->next != NULL){
            p = p->next;
        }
        p->next = c;
    }
    return c;
}

char *strresult(Result res) {
    switch(res) {
        case EXIT:
            break;
        case SAVE:
            return "history saved";
        case LINE:
            return "1 line drawn";
        case UNDO:
            return "undo!";
        case UNKNOWN:
            return "error: unknown command";
        case ERRNONINT:
            return "Non-int value is included";
        case ERRLACKARGS:
            return "Too few arguments";
        case NOCOMMAND:
            return "No command in history";
        default:
            return NULL;
    }
    return NULL;
}

こたえ

paintapp.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <errno.h>

#include "canvas.h"
#include "history.h"
#include "display.h"
#include "command.h"

int main(int argc, char **argv) {
    // for history recording
    const int bufsize = 1000;

    History his = (History){.begin = NULL, .bufsize = bufsize};

    int width;
    int height;
    if (argc != 3) {
        fprintf(stderr, "usage: %s <width> <height>\n", argv[0]);
        return EXIT_FAILURE;
    } else {
        char *e;
        long w = strtol(argv[1], &e, 10);
        if (*e != '\0') {
            fprintf(stderr, "%s: irregular character found %s\n", argv[1], e);
            return EXIT_FAILURE;
        }
        long h = strtol(argv[2], &e, 10);
        if (*e != '\0') {
            fprintf(stderr, "%s: irregular character found %s\n", argv[2], e);
            return EXIT_FAILURE;
        }
        width = (int)w;
        height = (int)h;
    }
    char pen = '*';

    char buf[bufsize];

    Canvas *c = init_canvas(width, height, pen);

    printf("\n");  // required especially for windows env

    while (1) {
        print_canvas(c);
        printf("* > ");
        if (fgets(buf, bufsize, stdin) == NULL) break;

        const Result r = interpret_command(buf, &his, c);

        if (r == EXIT) break;

        // 返ってきた結果に応じてコマンド結果を表示
        clear_command();
        printf("%s\n", strresult(r));
        // LINEの場合はHistory構造体に入れる
        if (r == LINE) {
            push_command(&his, buf);
        }

        rewind_screen(2);           // command results
        clear_command();            // command itself
        rewind_screen(height + 2);  // rewind the screen to command input
    }

    clear_screen();
    free_canvas(c);

    return 0;
}

canvas.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "canvas.h"

Canvas *init_canvas(int width, int height, char pen) {
    Canvas *new = (Canvas *)malloc(sizeof(Canvas));
    new->width = width;
    new->height = height;
    new->canvas = (char **)malloc(width * sizeof(char *));

    char *tmp = (char *)malloc(width * height * sizeof(char));
    memset(tmp, ' ', width * height * sizeof(char));
    for (int i = 0; i < width; i++) {
        new->canvas[i] = tmp + i * height;
    }

    new->pen = pen;
    return new;
}

void reset_canvas(Canvas *c) {
    const int width = c->width;
    const int height = c->height;
    memset(c->canvas[0], ' ', width * height * sizeof(char));
}

void print_canvas(Canvas *c) {
    const int height = c->height;
    const int width = c->width;
    char **canvas = c->canvas;

    // 上の壁
    printf("+");
    for (int x = 0; x < width; x++) printf("-");
    printf("+\n");

    // 外壁と内側
    for (int y = 0; y < height; y++) {
        printf("|");
        for (int x = 0; x < width; x++) {
            const char c = canvas[x][y];
            putchar(c);
        }
        printf("|\n");
    }

    // 下の壁
    printf("+");
    for (int x = 0; x < width; x++) printf("-");
    printf("+\n");
    fflush(stdout);
}

void free_canvas(Canvas *c) {
    free(c->canvas[0]);  // for 2-D array free
    free(c->canvas);
    free(c);
}

int max(const int a, const int b) {
    return (a > b) ? a : b;
}

void draw_line(Canvas *c, const int x0, const int y0, const int x1, const int y1) {
    const int width = c->width;
    const int height = c->height;
    char pen = c->pen;

    const int n = max(abs(x1 - x0), abs(y1 - y0));
    if ((x0 >= 0) && (x0 < width) && (y0 >= 0) && (y0 < height)) c->canvas[x0][y0] = pen;
    for (int i = 1; i <= n; i++) {
        const int x = x0 + i * (x1 - x0) / n;
        const int y = y0 + i * (y1 - y0) / n;
        if ((x >= 0) && (x < width) && (y >= 0) && (y < height)) c->canvas[x][y] = pen;
    }
}

command.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "command.h"
#include "canvas.h"
#include "history.h"

Result interpret_command(const char *command, History *his, Canvas *c) {
    char buf[his->bufsize];
    strcpy(buf, command);
    buf[strlen(buf) - 1] = 0;  // remove the newline character at the end

    const char *s = strtok(buf, " ");
    if (s == NULL) {  // 改行だけ入力された場合
        return UNKNOWN;
    }
    // The first token corresponds to command
    if (strcmp(s, "line") == 0) {
        int p[4] = {0};  // p[0]: x0, p[1]: y0, p[2]: x1, p[3]: x1
        char *b[4];
        for (int i = 0; i < 4; i++) {
            b[i] = strtok(NULL, " ");
            if (b[i] == NULL) {
                return ERRLACKARGS;
            }
        }
        for (int i = 0; i < 4; i++) {
            char *e;
            long v = strtol(b[i], &e, 10);
            if (*e != '\0') {
                return ERRNONINT;
            }
            p[i] = (int)v;
        }

        draw_line(c, p[0], p[1], p[2], p[3]);
        return LINE;
    }

    if (strcmp(s, "save") == 0) {
        s = strtok(NULL, " ");
        save_history(s, his);
        return SAVE;
    }

    if (strcmp(s, "undo") == 0) {
        reset_canvas(c);
        // 線形リストの先頭からスキャンして逐次実行
        Command *p = his->begin;
        if (p == NULL) {
            return NOCOMMAND;
        } else {
            Command *q = NULL;  // 新たな終端を決める時に使う
            while (p->next != NULL) {  // 終端でないコマンドは実行して良い
                interpret_command(p->str, his, c);
                q = p;
                p = p->next;
            }
            // 1つしかないコマンドのundoではリストの先頭を変更する
            if (q == NULL) {
                his->begin = NULL;
            } else {
                q->next = NULL;
            }
            free(p->str);
            free(p);
            return UNDO;
        }
    }

    if (strcmp(s, "quit") == 0) {
        return EXIT;
    }
    return UNKNOWN;
}

char *strresult(Result res) {
    switch (res) {
        case EXIT:
            break;
        case SAVE:
            return "history saved";
        case LINE:
            return "1 line drawn";
        case UNDO:
            return "undo!";
        case UNKNOWN:
            return "error: unknown command";
        case ERRNONINT:
            return "Non-int value is included";
        case ERRLACKARGS:
            return "Too few arguments";
        case NOCOMMAND:
            return "No command in history";
        default:
            return NULL;
    }
    return NULL;
}

display.c
#include <stdio.h>
#include "display.h"

void rewind_screen(unsigned int line) {
    printf("\e[%dA", line);
}

void clear_command(void) {
    printf("\e[2K");
}

void clear_screen(void) {
    printf("\e[2J");
}

history.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "history.h"

Command *push_command(History *his, const char *str) {
    Command *c = (Command *)malloc(sizeof(Command));
    char *s = (char *)malloc(his->bufsize);
    strcpy(s, str);

    *c = (Command){.str = s, .bufsize = his->bufsize, .next = NULL};

    Command *p = his->begin;

    if (p == NULL) {
        his->begin = c;
    } else {
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = c;
    }
    return c;
}

void save_history(const char *filename, History *his) {
    const char *default_history_file = "history.txt";
    if (filename == NULL) filename = default_history_file;

    FILE *fp;
    if ((fp = fopen(filename, "w")) == NULL) {
        fprintf(stderr, "error: cannot open %s.\n", filename);
        return;
    }
    // 線形リスト版
    for (Command *p = his->begin; p != NULL; p = p->next) {
        fprintf(fp, "%s", p->str);
    }

    fclose(fp);
}

canvas.h
#pragma once

// Structure for canvas
typedef struct {
    int width;
    int height;
    char **canvas;
    char pen;
} Canvas;

Canvas *init_canvas(int width, int height, char pen);
void reset_canvas(Canvas *c);
void print_canvas(Canvas *c);
void free_canvas(Canvas *c);

int max(const int a, const int b);
void draw_line(Canvas *c, const int x0, const int y0, const int x1, const int y1);

command.h
#pragma once
#include "canvas.h"
#include "history.h"

// enum for interpret_command results
typedef enum res {
    EXIT,
    LINE,
    UNDO,
    SAVE,
    UNKNOWN,
    ERRNONINT,
    ERRLACKARGS,
    NOCOMMAND
} Result;

char *strresult(Result res);

Result interpret_command(const char *command, History *his, Canvas *c);

display.h
#pragma once

// display functions
void rewind_screen(unsigned int line);
void clear_command(void);
void clear_screen(void);

history.h
#pragma once
#include <stddef.h>

// Command構造体とHistory構造体
typedef struct command Command;
struct command {
    char *str;
    size_t bufsize;
    Command *next;
};

typedef struct {
    Command *begin;
    size_t bufsize;
} History;

// 線形リストの末尾にpushする
Command *push_command(History *his, const char *str);

// 履歴をファイルに保存
void save_history(const char *filename, History *his);

Makefile
CC = gcc
CFLAGS = -Wall -I$(INCLUDE)

BINDIR = ./bin
INCLUDE = ./include
SRCDIR = ./src

TARGET = $(BINDIR)/paintapp

SRCS = $(SRCDIR)/paintapp.c $(SRCDIR)/canvas.c $(SRCDIR)/history.c $(SRCDIR)/display.c $(SRCDIR)/command.c
OBJS = $(SRCS:.c=.o)

$(TARGET): $(OBJS)
        $(CC) $(CFLAGS) -o $@ $^

$(SRCDIR)/%.o: $(SRCDIR)/%.c
        $(CC) $(CFLAGS) -c $< -o $@

.PHONY: clean
clean:
        rm -f $(TARGET) $(OBJS)

オープンソースなソフトウェアを自分の環境でビルドする際など、さまざまなところでmakeを見ると思います。また、makeはコンパイルだけに留まらず様々な作業の自動化ツールとして利用できるので、積極的に活用してみるとよいでしょう。

コラム: make以外のビルドツール

makeは長く、あらゆる環境で用いられていますが、ソフトウェアプロジェクトの規模拡大・多言語化・マルチプラットフォーム化などにともなって、make以外のビルドツールもさまざま生まれています。

Ninja
- 高速なビルドツール、以下に示すようなメタなビルドツールを用いてビルド定義を生成することを前提としている。
Bazel
- 様々な言語、マルチプラットフォームをサポートしたビルドツール。
CMake
- Makefileなど、ビルド定義を生成するメタなビルドツール。
Meson
- CMakeと同様のメタなビルドツール。

他に、katiといったツールもあります。

関数ポインタ

関数のアドレス

今日は関数へのポインタを見ていきます。一般に、プログラムを実行するとその構成要素が全てメモリ上に展開されます。つまり変数に加えて、関数の実行コードもメモリ上のどこかに置かれるので、関数が置かれているアドレスというものを考えることができます。

メモリ領域

以下のコードはプログラム中の色々な要素のアドレスを全て表示しています。

print_address.c
#include <stdio.h>
#include <stdlib.h>

int global = 0;

int add_one(int x){

    // 静的領域に変数を確保する
    static int count = 0;

    // 関数内のstatic変数 
    printf("count_in_add_one(%d): %p\n", count, &count);
    // add_one関数の引数x
    printf("x_in_add_one(%d): %p\n", count, &x);

    count++;  // 何回呼び出されたかを記録
    return x + 1;
}

void call(int x, int (*fp)(int)) {
    // call関数の引数x
    printf("x_in_call: %p\n",&x);
    // call関数の引数fp
    printf("fp_in_call: %p\n", &fp);

    fp(x);
}

int main(int argc, char **argv) {
    int x = 10;
    int *a = (int*) malloc(sizeof(int));

    // main関数のアドレス
    printf("function_main: %p\n", &main);

    // main内の変数x
    printf("x_in_main: %p\n", &x);

    // argc
    printf("argc_in_main: %p\n", &argc);

    // argv
    printf("argv_in_main: %p\n", &argv);

    // グローバル変数global
    printf("global: %p\n", &global);

    // mallocされたa
    printf("allocated_a: %p\n", a);

    // ポインタそのもののアドレス
    printf("pointer_a_in_main: %p\n", &a);

    add_one(x);

    // add_one関数のアドレス
    printf("function_add_one: %p\n", &add_one);

    // もう一度呼ぶ
    add_one(x);

    // call経由でadd_one を呼ぶ
    call(x, add_one);

    // call関数のアドレス
    printf("function_call: %p\n", &call);

    free(a);
    return 0;
}

演習

上記のprint_address.cを写経して実行してみましょう。

一般的なUNIX環境において、実行する際に以下のようにsortコマンドに結果をパイプすることで、アドレス順に並べ替えができます。

# コンパイル (-O0 [オーゼロ]は最適化がかからないようにするオプション)
$ gcc -O0 -o print_address print_address.c
# 実行とソート
$ ./print_address | sort -k 2

実行毎に結果は変化しますが、プログラム中の要素がそれぞれが置かれているメモリ領域に応じてある程度固まって配置されていることが読み取れます。

関数へのポインタ

ポインタはアドレスを格納する変数なので、関数に対するポインタを考えることができます。演算子の優先順位から、関数へのポインタは以下のような形式で宣言されます。

// fp は返り値がintで引数がint一つの関数へのポインタ
int (*fp)(int);
// fp は返り値がdoubleで、引数がdouble二つの関数へのポインタ
double (*fp)(double, double);

関数ポインタを宣言する際は、

関数の返り値の型
引数の型

を指定します。これにより同じ入力、出力を持つ関数をこのポインタでひとまとめに扱うことができます。

関数ポインタを実際に用いて関数を実行してみましょう。

example.c
#include <stdio.h>

int add_one(int x){
    return x+1;
}

int main(){
    int (*fp)(int);
    // fp にadd_one関数のアドレスを代入
    fp = &add_one;

    int x = 1;
    // fp で指されている関数を呼び出す
    int y = (*fp)(x);

    printf("%d\n", y);

    return 0;
}

なお、関数のアドレス表示および関数ポインタは「暗黙的な型変換」が適応されるため、かなりいろいろな書き方が許容されます。例えばアドレスを表示や代入の際に以下のように書いても正しく動きます。

// 表示の例
printf("function_add_one: %p\n", add_one);
// 代入の例
fp = add_one;

これは引数なしで関数名を扱うと暗黙的に関数ポインタ型=アドレスに変換されるためです。つまり& の有無が結果に影響をあたえません。

また実行する際も以下のような記述でも動きます。

int y = fp(x);
// 暗黙的な型変換が繰り返された結果、以下もOK（使わないでください）
int y = (*******fp)(x);

関数ポインタの代表的な利用方法として、関数へのポインタを引数として関数に渡し、同一の関数型を持つ複数の関数を実行時に切り替える方法があります。このとき、渡される関数はコールバック関数と呼ばれます。

apply.c
#include <stdio.h>

int add(int x, int y) {
    return x + y;
}

int mul(int x, int y) {
    return x * y;
}

void apply(int v[], int n, int y, int (*fp)(int,int)) {
    for (int i = 0 ; i < n ; i++){
        v[i] = (*fp)(v[i],y);
    }
}

int main() {
    int v[10];
    const int n = sizeof(v)/sizeof(int);
    for (int i = 0 ; i < n ; i++){
        v[i] = i;
    }

    apply(v, n, 2, add);
    apply(v, n, 3, mul);

    for (int i = 0 ; i < n ; i++){
        printf("v[%d] = %d\n", i, v[i]);
    }
}

演習

上記のapply.cを写経して実行してみましょう。

クイックソート

関数ポインタによるコールバック関数をうまく使った標準ライブラリ関数の一つにqsortがあります。qsortはデータの型に依存せずに、配列を決められた基準で並べ替える機能を提供します。

#include <stdlib.h>

// 先頭アドレスがbase、個々の要素がsize、個数membの配列を、比較関数compar の基準で並べ替える
void qsort(void *base, size_t memb, size_t size, int (*compar)(const void *, const void*));

関数ポインタで、要素を比較した時に、同じならば0、大小関係を正負の値で返す関数を指定します。

整数配列ソートの例

標準ライブラリ関数qsortを使ったサンプルコードqsort.cは以下のようになります。コンパイル・実行してみましょう。

qsort.c
#include <stdio.h>
#include <stdlib.h>
#include <errno.h> 　// strtol のエラー判定用
#include <string.h> 　// strerror(errno) のため


int comp_int(const void *x0, const void *x1) {
    const int *p0 = x0; 
    const int y0 = *p0; 
    //  const int y0 = *(int*)x0;  // このように書いてもよい
    const int *p1 = x1;
    const int y1 = *p1;
    //  const int y1 = *(int*)x1;  // このように書いてもよい

    if (y0 > y1) return 1;
    if (y0 < y1) return -1;
    return 0;
}

// 上記の関数は以下のように書いてもよい
// （実際には正負 と 0 の情報だけを用いているため）
/*
  int comp_int(const void *x0, const void *x1) {
      return *(int*)x0 - *(int*)x1;
  }
*/


/* strtol と エラー判定を一つの関数に入れておく*/
int load_int(const char *str) {
    errno = 0;
    char *e;
    long n = strtol(str,&e,10);

    // エラーチェック
    if (errno == ERANGE) {
        fprintf(stderr, "%s: %s\n", str, strerror(errno));
        exit(EXIT_FAILURE);
    }
    if (*e != '\0') {
        fprintf(stderr, "%s: an irregular character '%c' is detected.\n",str,*e);
        exit(EXIT_FAILURE);
    }
    return (int)n;
}


int main(int argc, char **argv) {
    if (argc != 2) {
        fprintf(stderr, "usage: %s <number of elements>\n",argv[0]);
        exit(EXIT_FAILURE);
    }

    int n = load_int(argv[1]);

    int *v = (int*) malloc(sizeof(int) * n);
    errno = 0;
    if (v == NULL) {
        fprintf(stderr, "Error: %s\n",strerror(errno));
        exit(EXIT_FAILURE);
    }

    for (int i = 0 ; i < n ; i++) {
        v[i] = rand()%1024;  // 0 - 1023 で値を入れる
    }

    // sort前表示
    printf("[");
    for (int i = 0 ; i < n ; i++) {
        printf("%d ",v[i]);
    }
    printf("]\n");

    // sort実行
    qsort(v, n, sizeof(int), comp_int);

    // sort後表示
    for (int i = 0; i < n; i++) {
        printf("v[%d] = %d\n", i, v[i]);
    }

    free(v);
    return 0;
}

# コンパイル
$ gcc -o qsort qsort.c
# 実行
$./qsort 100

構造体配列ソートの例

qsortはデータ型に依存しないので、例えば構造体の特定のメンバを基準にした構造体配列の並べ替えなども可能です。構造体配列に対するqsortの例は以下のようになります。

qsort_struct.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct student { 
    int id;
    char name[100];
} Student;

int comp_name(const void* x0, const void *x1) {
    const Student *p0 = (Student*)x0;
    const Student *p1 = (Student*)x1;

    return 0;  // いまはダミーの値を返している 
}


int main(int argc, char **argv) {
    Student v[] = {
        (Student){ .id = 1, .name = "situ"},
        (Student){ .id = 2, .name = "hrs"},
        (Student){ .id = 3, .name = "ire"},
        (Student){ .id = 4, .name = "hsgw"},
        (Student){ .id = 5, .name = "aizw"},
        (Student){ .id = 6, .name = "mti"}
    };
    const int n = sizeof(v) / sizeof(v[0]);

    // before sort
    printf("== before ==\n");
    for (int i = 0 ; i < n ; i++){
        printf("%d: v[%d] = %s\n",v[i].id, i, v[i].name);
    }
    qsort(v,n,sizeof(v[0]),comp_name);

    // after sort
    printf("== after ==\n");
    for (int i = 0 ; i < n ; i++){
        printf("%d: v[%d] = %s\n",v[i].id, i, v[i].name);
    }
    return EXIT_SUCCESS;
}

演習

以下に取り組んでみましょう。

整数配列のソートで、整数値を降順にソートするように修正してみましょう。
構造体配列のソートで、comp_name関数を完成させ、Studentを名前の辞書順でソートするように修正してみましょう。
- ヒント: 文字列比較の関数を使う。

こたえ

整数配列については、昇順の時と返り値の符号を入れ替えます。

int comp_int(const void *x0, const void *x1) {
    return *(int*)x1 - *(int*)x0;
}

構造体配列については、string.hの文字列比較関数であるstrcmpを使います。

int comp_name(const void *x0, const void *x1) {
    const Student *p0 = (Student*)x0;
    const Student *p1 = (Student*)x1;

    return strcmp(p0->name, p1->name);
}

連続最適化

今日は関数ポインタを使いつつ、一般的な連続関数の最適化を扱います。前回触れたナップサック問題や巡回セールスマン問題のように離散的な候補から解を探す離散最適化とは異なり、変数が連続的な値をとる連続最適化の問題です。

ここでは入力がベクトル、出力がスカラーのような関数を考え、この関数の最小値およびそれを実現する入力を計算することを考えます。これは機械学習において、目的関数の最大化/最小化、と呼ばれる最も基本的なプロセスに対応します。入力ベクトルを変化させたときの目的関数の変動（勾配、gradient）がわかっている場合には、勾配法と呼ばれる方法を用いることができます。

1変数関数の場合

たとえば$ f(x) = (x-3)^2 + 1 $ を最小化する$x$ を求めたいとき、$f'(x) = 2(x-3)$ を考えます。人間は$f'(x) = 0 $ を解析的に求めることができますが、計算機を用いてこれを数値的に求める場合、以下のような方法をとります。

適当に $x$ を決める
$f’(x) < 0$ なら右に移動
$f’(x) > 0 $ なら左に移動

として繰り返します。

1変数関数の最適化

2変数関数の場合

例えば$$f(x,y) = (x-3)^4 + (y-2)^2 $$ のような関数を最適化したい場合勾配として

\[\nabla f = \left(\frac{\partial f}{\partial x},\frac{\partial f}{\partial y}\right)=[4(x-3)^3, 2(y-2)]\]

を考えます。この勾配の反対方向に$ (x,y) $ を進めることで最適化を実現します。

2変数関数の最適化

最急降下法

以上を一般的にまとめると、シンプルな勾配法である最急降下法のプロセスは以下のようになります。

適当に初期位置$ x $を決める
$\nabla x $を計算。ノルムが十分小さければ終了
$x \leftarrow x - \alpha \nabla x$として更新　　　　　　　
2に戻り繰り返す

optimize.c
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include "optimize.h"

double calc_norm(const int dim, double v[]) {
    double tmp = 0;
    for (int i = 0; i < dim; i++) {
    tmp += v[i] * v[i];
    }
    tmp = sqrt(tmp);
    return tmp;
}

int optimize(const double alpha, const int dim, double x[], void (*calc_grad)(const double [], double [])) {
    // 勾配ベクトルを記録する領域を確保
    double *g = malloc(dim * sizeof(double));

    int iter = 0;
    while (++iter < 10000) {

        // 引数で渡された関数を使って勾配ベクトルを計算
        (*calc_grad)(x, g);

        // 勾配ベクトルのノルムを評価
        const double norm = calc_norm(dim, g);
        printf("%3d norm = %7.4f", iter, norm);
        for (int i = 0; i < dim; i++) {
            printf(", x[%d] = %7.4f", i, x[i]);
        }
        printf("\n");

        if (norm < 0.01) break;

        // 最急降下法による更新
        for (int i = 0; i < dim; i++) {
            x[i] -= alpha * g[i];
        }
    }

    free(g);

    return iter;
}

optimize.h
#pragma once

int optimize(const double alpha, const int dim, double x[], void (*calc_grad)(const double [], double []));

func.c
#include <math.h>

int f_dimension() {
    return 2;
}

double f_value(const double x[]) {
    return (x[0] - 3) * (x[0] - 3)  * (x[0] - 3)  * (x[0] - 3) + (x[1] - 2) * (x[1] - 2);
}

void f_gradient(const double x[], double g[]) {
    g[0] = 4 * (x[0] - 3) * (x[0] - 3) * (x[0] - 3);
    g[1] = 2 * (x[1] - 2);
}

func.h
#pragma once

int f_dimension();
double f_value(const double x[]);
void f_gradient(const double x[], double g[]);

main.c
#include <stdio.h>
#include <stdlib.h>
#include "optimize.h"
#include "func.h"

int main(const int argc, const char **argv) {
    // 引数の個数が1の時だけ、alpha に第1引数を採用し、それ以外は0.01
    const double alpha = (argc == 2) ? atof(argv[1]) : 0.01;

    const int dim = f_dimension();

    double *x = malloc(dim * sizeof(double));
    for (int i = 0; i < dim; i++) {
        x[i] = 0;
    }

    printf("alpha = %f\n", alpha);

    const int iter = optimize(alpha, dim, x, f_gradient);

    printf("number of iterations = %d\n", iter);

    free(x);

    return 0;
}

Makefile
CC = gcc
CFLAGS = -Wall
LDLIBS = -lm
OBJS = main.o func.o optimize.o
TARGET = optimizer

$(TARGET): $(OBJS)
    $(CC) -o $@ $^ $(LDLIBS)

.PHONY: tmpclean clean
tmpclean:
    rm -f *~
clean: tmpclean
    rm -f $(OBJS) $(TARGET)

演習

以下のようなコマンドでコンパイル・実行してみましょう。

$ make
$ ./optimizer 0.05

optimize.cを修正し、最適化の終了条件を厳しくしてみましょう
最適化の各ステップで関数の値f(x)も表示するように改良してみましょう
- ヒント: 関数optimize()に関数f_value()のポインタを渡すようにする

こたえ

終了条件については、optimize.cにあるbreakを呼び出しているif文を修正すればよいです。一方関数の値も表示する場合は以下のようになります。

optimize.h
#pragma once

int optimize(const double alpha, const int dim, double x[], 
        void (*calc_grad)(const double [], double []),
        double (*calc_value)(const double[]));

optimize.c

int optimize(const double alpha, const int dim, double x[], 
            void (*calc_grad)(const double [], double []),
        double (*calc_value)(const double[])) {
    // 勾配ベクトルを記録する領域を確保
    double *g = malloc(dim * sizeof(double));

    int iter = 0;
    while (++iter < 10000) {

        // 引数で渡された関数を使って勾配ベクトルを計算
        (*calc_grad)(x, g);

        // 勾配ベクトルのノルムを評価
        const double norm = calc_norm(dim, g);
        printf("%3d norm = %7.4f", iter, norm);
        for (int i = 0; i < dim; i++) {
            printf(", x[%d] = %7.4f", i, x[i]);
        }
        printf(", f(x) = %7.4f\n",(*calc_value)(x));

        if (norm < 0.01) break;

        // 最急降下法による更新
        for (int i = 0; i < dim; i++) {
            x[i] -= alpha * g[i];
        }
    }

    free(g);

    return iter;
}

main.c

const int iter = optimize(alpha, dim, x, f_gradient,f_value);

最小二乗法による線形回帰分析

最小二乗基準による線形回帰を勾配法を用いておこなってみましょう。回帰分析はモデルの予測値と観測値の差（誤差）をできるだけ小さくするように、モデルのパラメータを決める問題でした。

最小二乗法による線形回帰

特に最小二乗法による線形回帰の場合、観測データセット $\{(x_1,y_1),\ldots,(x_n,y_n)\}$ が与えられたときに、二乗誤差の和は $E=\sum_{i=1}^N (y_i - ax_i - b)^2$ となり、これが最小になるように $a,b$ を設定する問題となります。

大まかな手順としては、以下のようになります。

$a,b$ を適当な値で初期化
与えられた $(x, y)$ と $a,b$ を用いてパラメータ $a,b$ に対する勾配を求める
$a,b$ の値を上記勾配に基づいて最急降下法で更新
二乗誤差の和が十分小さければ終了
そうでない場合は2-4を繰り返す

今回扱う1次関数の線形回帰において、最小値を与える解は解析的に求めることができます。したがって、勾配法のような手法は必須ではありません。

しかし、昨今流行のニューラルネットワークのようにモデルが複雑になると、解析解を直接求めることは一般に難しくなります。そのため、勾配法のような反復的な最適化手法が基本になります。誤差関数を定義し、それを最小化することでモデルを学習するという今回の流れを覚えておきましょう。

レポート

本日はここまでです。宿題として以下をお願いします。

Slackで配付した宿題リンクから、レポートを提出してください。
- リンクは公開しないでください
- 締切は今回は次の授業翌日の夜23:59までです（今回の場合、2026/1/9, 23:59）
- リポジトリを更新するかたちで提出してください
  - リポジトリのトップ階層、またはsrcディレクトリ以下など、わかりやすい場所に作成したコードを配置してください
  - 自動採点的な機能はありません
- レポートの内容は以下になります

week4_1

最小二乗法により標高と気温の関係を推定するプログラムを実装してみましょう。

以下のdata.csvには、各地の名称と標高、7月の平均気温が記載されています。

data.csv

Nozawa-onsen,   0.576,  22.3 
Iiyama,         0.313,  23.3
Nagano,         0.4182, 23.8
Oomachi,        0.784,  21.1
Sugadaira,      1.253,  18.5
Karuizawa,      0.9991, 19.5
Matsumoto,      0.610,  23.6
Nagawa,         1.068,  19.7
Suwa,           0.760,  22.7
Nobeyama,       1.350,  18.4
Ina,            0.633,  22.7
Nagiso,         0.560,  22.3
Iida,           0.5164, 23.9
Minami-shinano, 0.407,  23.5

data.csvをファイルとして読み込み、得られたパラメータから推測される富士山頂 (標高: 3.776km) の7月の平均気温を表示してください。
あわせて、与えられたデータを標高に基づいてソートし、標高の低い地点から高い地点の順にそれぞれの名称と7月の平均気温を表示してください。
main関数を含むファイル名はmtfuji.cとし、必要に応じて分割したソースファイルを用いてください。

以下のような構造体定義を参考にしてください。

#include <stdio.h>
// 必要に応じてヘッダファイルを追加する

typedef struct {
    char *loc;  // location name
    double alt;  // altitude (km)
    double temp;  // temperature (centigrade)
} Sample;

int f_dimension() {
}

double f_value(const double x[]) {
}

void f_gradient(const double x[], double g[]) {
}

第4回 ビルドツール、関数ポインタ、アルゴリズム4