数理情報工学演習第一 C ( 第 12 回 ) 2016/07/11 DEPARTMENT OF MATHEMATICAL INFORMATICS 1
今日の内容 : ファイルの入出力 コマンドライン引数 2 分探索 クイックソート ( ライブラリ ) 文字列検索 2
ファイル操作の手続き : ファイル操作 ファイルからのデータ読み込み ファイルへのデータ書き出し 基本的な手順 読みこむ / 書き出すファイルを開く (fopen) 読み込み / 書き出しの操作 (fscanf/fprintf) ファイルを閉じる (fclose) 3
ファイルを開く / 閉じる : fopen/fclose fopen( ファイル名, モード ) モード :r( 読み込み ), w( 書き込み ), a( 追記 ) FILE *fp; // ファイルポインタの宣言 fp = fopen( input.txt, r ) ; // 読み込みモードで input.txt を開く 各種ファイル処理 fclose(fp); // 閉じる 4
ファイルへの書き込み 読み込み : ファイルポインタ以外はprintf/scanfと同様 書き出し :fprintf( ファイルポインタ, ) fprintf(fp, %d n, i) 読み込み :fscanf( ファイルポインタ, ) 整数は %d, 実数は %lf int x; double y; fscanf(fp, %d %lf, &x, &y); ファイルの最後に到達した場合 EOF を返す if ( fscanf( ) == EOF ){. 5
#include <stdio.h> #include <stdlib.h> void read_file(char *filename) { double x; FILE *fp; fp = fopen(filename, r ); if (fp == NULL) { printf( cannot open %s n, filename); exit(1); while (!feof(fp)) { if (scanf("%lf", &x) < 1) { break; fprintf(stdout, %lf n, x); fclose(fp); int main(argc, char *argv[]) { read_file( test.txt ); return 0; 6
コマンドライン引数の利用./a.out input.txt 10 0.1 と引数をつけて実行したとき argc = 4; argv[0] =./a.out ; プログラム名 argv[1] = input.txt ; argv[2] = 10 ; argv[3] = 0.1 ; int main(int argc, char *argv[]) { FILE *f; int n; double x; if (argc < 4) exit(1); // 引数が足りない f = fopen(argv[1], r ); n = atoi(argv[2]); // 文字列を整数に x = atof(argv[3]); // 文字列を実数に 7
最終レポート 疎行列の 2 乗を計算し, 実行時間を測定する 入力は Matrix Market のデータを用いる http://math.nist.gov/matrixmarket/matrices.html 形式を変換したものを用意しています http://researchmap.jp/mub2jpgrp-1587/#_1587 ファイルから行列を読み込み, その 2 乗を計算しファイルに出力する./a.out ( 入力 ) ( 出力 ) 実行時間は time コマンドで測る time./a.out bcspwr01.txt bcspwr01-2.txt 8
実行時間のグラフを作る 行列のデータ構造や乗算アルゴリズムは複数用いてそれらの違いを調べる 密行列 (2 次元配列 ), 疎行列 ( リストの配列 ) など 疎行列でも乗算のアルゴリズムによって時間は異なる それぞれのデータ構造, アルゴリズムの概略も説明する 締切 :7/25( 月 ) 16:00 宛先 :miprogramming2016+final@gmail.com 9
レポートについての注意 メールの題名 : 学生証番号 8 桁ハイフンなし ( 半角スペース ) 氏名 ( 半角スペース ) 最終レポート提出 例 : 03150699 定兼邦彦最終レポート提出 添付ファイル : レポート ( 学生証番号 8 桁.pdf 5 枚以内 ) ソースコードを圧縮したもの ( 学生証番号 8 桁.zip) 例 : 03150699.pdf 例 : 03150699.zip レポートについて タイトル 所属 学生証番号 氏名 日付を一ページ目に書くこと ( 独立させたページにはしなくてよい 1. 課題内容 2. 手法 ( データ構造 アルゴリズム ) の説明 3. 結果 4. 考察の章立てで書くこと A4 5 枚以下に収めること 以下は本レポートに限らず留意のこと グラフにはタイトル 縦軸 横軸 ( 単位も ) 凡例を忘れずに 表のタイトルを忘れずに グラフ 表のタイトルは本文を読まなくても何が書いてあるかわかるように 10
二分探索 アルゴリズムとデータ構造で重要な概念 全順序集合の探索を高速化する 集合 S の要素を L, E, G に分ける L = {x x S, x < p (p より小さい要素 ) E = {x x S, x = p (p と等しい要素 ) G = {x x S, x > p (p より大きい要素 ) k を探索するとき p = k ならば探索終了 ( 見つかった ) p < k ならば G を二分探索 p > k ならば L を二分探索 11
既ソート配列での二分探索 E は配列の中央の要素 (p = S[n/2]) L は中央より左側の要素 (S[0..n/2 1]) G は中央より右側の要素 (S[n/2+1..n 1]) 集合が配列のl 番目からh 番目で表されているとき m = (l+h) / 2 とする S[m]=k ならば探索終了 (k が存在した ) S[m]<k ならば k はL, E には存在しない G を探索 S[m]>k ならば k はG, E には存在しない L を探索 l m h < p p > p 12 L E G
int search(dic_sortedarray *S, int k) { int high, low, mid; low = 0; // 探索の範囲は最初は配列全体 [0..n-1] high = S->n-1; while (low <= high) { mid = (low + high) / 2; if (S->key[mid] == k) { // 見つかった return mid; else if (S->key[mid] < k) { low = mid + 1; // 探索範囲を後半だけにする else { high = mid - 1; // 探索範囲を前半だけにする return -1; // 見つからなかった 13
クイックソート 二分探索を行うには, 要素がキーの順にソートされている必要がある 今回はC 言語の標準ライブラリにある qsort() を用いる #include <stdlib.h> void qsort( void *data, // ソートしたいデータ size_t data_cnt, // データの個数 size_t data_size, // データ1 個当たりのバイト数 int(*func )(const void *, const void *)); // 比較関数 14
比較関数 int(*func )(const void *, const void *); 2 つの引数は, 比較したいデータへのポインタ 第 1 引数 < 第 2 引数の場合は負の整数を返す 第 1 引数 = 第 2 引数の場合はゼロを返す 第 1 引数 > 第 2 引数の場合は正の整数を返す データが整数の配列に格納されているとき int int_compare(const void *pa, const void *pb) { int a, b; a = *(int *)pa; b = *(int *)pb; return a - b; 15
データが文字列で, 文字列へのポインタが配列に入っているとき int str_compare(const void *ppa, const void *ppb) { char *pa, *pb; pa = *(char **)ppa; pb = *(char **)ppb; return strcmp(pa, pb); ソートしたい配列は ( 文字列へのポインタ ) の配列 比較関数の引数はデータへのポインタ この場合は ( 文字列へのポインタ ) へのポインタ 文字列へのポインタを得るには,1 度ポインタの中身を参照する strcmp の返り値は比較関数の条件を満たすのでそのまま使う 16
int A[5] = {5, 3, 2, 4, 1; char *S[3] = { abc, xyz, def ; qsort(a, 5, sizeof(int), int_compare); qsort(s, 3, sizeof(char *), str_compare); 17
文字列検索 ( 接尾辞配列 ) 文字列 T の長さを n とする. T の接尾辞配列 SA は長さ n の配列で, SA[i] = ( 辞書順で i 番目の接尾辞のポインタ ) (0 i n-1) T の全接尾辞をソートすればSAを構築できる. char **SA; // 文字列へのポインタのポインタ 配列 SA[i] = T+i と初期化する 配列 SA を str_compare に従って qsort する. T = banana (n=6) SA[0] = a SA[1] = ana SA[2] = anana SA[3] = banana SA[4] = na SA[5] = nana 18
接尾辞配列を用いた文字列検索 あるパタン P の,T 上での出現位置を求める 接尾辞配列上で二分探索を行う 二分探索を行う際の大小比較は,strncmp を用いる len = strlen(p); strncmp(p, SA[m], len); つまり, 接尾辞配列を, 長さ len の文字列を辞書順に格納したものだとみなす. 接尾辞の方の長さが len 未満の場合もあるが, 問題は無い T = banana (n=6) SA[0] = a SA[1] = ana SA[2] = anana SA[3] = banana SA[4] = na SA[5] = nana 19
今はパタンの全ての出現位置を求めたい ただし最初の二分探索の説明では, そのうちの 1 つしか求めていない 1つ一致が見つかったら, 接尾辞配列上でその前後の接尾辞を見て, 一致を全て見つける 本来はこれも二分探索で行うべき T = banana (n=6) SA[0] = a SA[1] = ana SA[2] = anana SA[3] = banana SA[4] = na SA[5] = nana 20
課題 接尾辞配列を用いて文字列を検索する 入力 : ( 標準入力より ) T の長さ T 検索するパタン (0 個以上 ) 出力 : 各検索パタンに対し出現個数出現位置 1 出現位置 2 出現位置は小さい順にソートする 7/11( 水 ) 16:00 までに提出 入力例 6 banana a b na x 出力例 3 1 3 5 1 0 2 2 4 0 T = banana (n=6) SA[0] = a SA[1] = ana SA[2] = anana SA[3] = banana SA[4] = na SA[5] = nana 21
#include <stdio.h> #include <stdlib.h> #include "suffixarray.h" int main(int argc, char *argv[]) { FILE *f; char *str; sarray *SA; int i, n; char pattern[100]; int c, l, r; // f = fopen(argv[1], "rb"); f = stdin; fscanf(f, "%d", &n); str = malloc(n+1); fscanf(f, "%s", str); str[n] = 0; SA = sarray_build(n, str); while (1) { if (fscanf(f, "%s", pattern) < 1) break; c = sarray_search(sa, pattern, &l, &r); printf("%d", c); if (c > 0) { for (i=l; i<=r; i++) printf( %d ", SA->SA[i] - SA->T); printf(" n"); 注 : これだと出現位置の小さい順にソートされていないので, 一旦答えを別の配列に入れて qsort でソートしてから出力する return 0; 22
接尾辞配列の構造体 typedef struct { int n; // 文字列の長さ char *T; // 文字列 char **SA; // 接尾辞配列 sarray; 23
作成する関数 sarray *sarray_build(int n, char *T); 長さ n の文字列 T が与えられたときに, 接尾辞配列の構造体を作る int sarray_search(sarray *SA, char *pattern, int *l, int *r); 接尾辞配列の構造体 SA, 検索パタン pattern が与えられる 返り値は pattern の出現回数 出現回数が 0 でないときは,pattern に対応する接尾辞配列の区間を l と r に入れる 24