yumetodoの旅とプログラミングとかの記録

旅や登山の記録やプログラミング関連の話とかフリーソフト紹介とか

深夜テンションでC言語プログラムを解説するPart 1

きっかけは、Mincraftの魔術mod、Witcherryの解説動画といえばこの人、
まとらさんの
http://www.nicovideo.jp/user/17540909
http://com.nicovideo.jp/community/co2082219
のこのツイート。

ちょうど一般化学実験が終わり、意気揚々と中央線に運良く座りながら帰っていた私は、意気揚々とノートPCを立ち上げ、C89版とC++14版の回答プログラムを書いた。
そうしたら

という返信が来た。もちろんマトラさんみたいなComputerCraftに触れる人ならすぐに上達するだろうから私の解説は不要だろう。
しかし今私はサークルでC言語を教えている。せっかく飛び込んできた材料を無駄にする手はない。
というわけで1/3くらい下書きのつもりで解説をしていく。
残り2/3は?知らん。

プログラミングでもっとも大切なこと

これに関してはMineCraft1.2.5工業化勢最高峰のめいさん
http://www.nicovideo.jp/user/20215125
http://com.nicovideo.jp/community/co2061778
http://dic.nicovideo.jp/a/めい(ゆっくり実況主)
がとてもためになる言葉を、意図してかはともかく、述べている。それは

めんd

である。利用できるものは利用し、コピペできるところはコピペで済ます。どこまでも面倒臭がって初めて良いプログラムはできる、ということだ。ああ、耳が痛い、なんでだろうなぁ。なぜならば

プログラム 書かなければ バグらない

からだ。さて本題に入ろうか。

マトラ氏作のプログラム

まずは問題のプログラムを見てみよう。

#include <stdio.h>
#include <string.h>

int main(void)
{
	int kingaku[50];
	char shouhin[50][10], work[10];
	int i, a, b, count = 0;
	char i;

	printf("データ(商品コード、 金額)を入力してください\n");
	while(scanf("%s %d", &i, &j) != EOF){
		shouhin[count][0] = i;
		kingaku[count] = j;
		count++
	}
	for(a = 0; a < count; a++){
		for(b = a + 1; b < count - 1; b++){
			if(shouhin[a][0] > shouhin[b][0]){
				work[0]=shouhin[a][0];
				j=kingaku[a];
				shouhin[b][0] = work[0];
				kingaku[b] = j;
			}
		}
	}
	for(j = 0; j < 50; j++){
		printf("%s %d\n", shouhin[j][0], kingaku[j]);
	}
	return 0;
}

で、中央線に乗っていた過去の私は何を思ったのか、配列の中身を逆順に並び替えるプログラムと勘違いしてこんな
http://ideone.com/jjo8aC
http://ideone.com/aTGu2f
プログラムを書いていたが、思うにマトラさんのやりたいことはそうではない。
ここでこのプログラムの要件をまとめる

入力を受ける
12~16行目が該当
ソート
バブルソートを使用。判断基準は文字列データ。17~26行目が該当。
画面表示
27~29行目が該当

「ようはstd::reverseがしたいんだろ?」
と思っていた過去の私、違いますよ?
マトラさんがしたいのはバブルソートですよ?マトラさんがびっくりしていますよ?
std::reverseじゃないですよ?
しかし編集中の私の声はどうあがいても届かない。

マトラ氏作のプログラムの問題点

変数名がローマ字だったりわかりにくい

冗談抜きで著しく可読性を下げる。変数名が長くても実行速度には影響しないのだから、英語で長くわかりやすく書けばいいのである

即値がおおい

そこかしこに即値、すなわち直接数字(整数リテラル)が書いてある。これまた可読性を下げ、後の修正可能性を下げるので避ける。
今回は配列の宣言に使われているので変数にするわけにいかないので#defineマクロを利用する。C++11ならconstexpr使うんだけどね。
とりあえずこんな感じ。ついでなのでちと数を増やしといた。

#define INPUT_LIMITS 100
#define INPUT_STR_LIMITS 50

ソートさせるデータが2つある

ソート部分の可読性を大きく下げているのは変数名'shouhin'と'kingaku'が常にひとまとめに扱われているにもかかわらず、2つの変数にわかれていることである。
解決策は簡単だ、構造体を使えばいい。

typedef struct{
	char name[INPUT_STR_LIMITS];
	int price;
} record_data_t;

ソート部分がmain関数内にある

今回は31行に収まっていますが、可能な限り関数化したほうが可読性が上がります。
C言語にはqsortというクイックソートする標準関数があるのでそれを参考に関数を作りましょう。といっても今回はわかりやすさを優先し、第3引数は省略します。
第1引数でポインタ型がなにから派生したかがわかれば必要ありませんからね。

void bubblesort(void *base, size_t num, size_t size, int (*compare)(const void*, const void*)){
	/* 中略 */
}

scanf関数の使い方が混乱している

	while(scanf("%s %d", &i, &j) != EOF){

12行目を見てください。ここでiの型は何でしょうか?

	char i;

scanfの型変換指定子は'%s'になっていますから、文字列を受けたかったのだと思いますが、char型で受けられるのは文字であって文字列では無いですよ?

そもそもscanf系関数で数値入力を受けてはいけない

これに関しては
[迷信] scanf ではバッファオーバーランを防げない
http://www.kijineko.co.jp/tech/superstitions/buffer-overrun-of-scanf.html
に投げます。
ざっというと、もしint型で表せない範囲の数値が入力されてもscanfでは検知する方法がない、という、いわゆるオーバーフロー、アンダーフロー問題です。
今回はこの記事を参考にpueseIntという関数を作成しています。

int purseInt(char* str){
	long t;
	errno = 0;
	t = strtol(str, nullptr, 10);
	if (0 != errno || t < INT_MIN || INT_MAX < t){
		return -1;
	}
	return (int)t;
}

printf関数が謎

		printf("%s %d\n", shouhin[j][0], kingaku[j]);

28行目に注目してください。
型変換子は'%s'なのでchar*型を受けないといけません。しかし'shouhin[j][0]'と指定しています。それ、char型ですよ?
ちなみに'shouhin[j]'としても、'char[INPUT_STR_LIMITS]'型じゃないか、と思うかもしれませんが、配列は式中では、sizeof演算子と&演算子(アドレス演算子)のオペランドと配列初期化時の文字列リテラルと(lvalue)参照に代入するときは以外は常にポインタ型に読み替えられます。だからchar*型に読み替えられます。

C89規格に沿って書いたプログラムと問題点

という感じで修正してみたのが以下のプログラムです。

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>//in gcc
#include <limits.h>//in gcc
#include <string.h>
#define INPUT_LIMITS 100
#define INPUT_STR_LIMITS 50

#ifndef __cplusplus
#define nullptr NULL
#endif
typedef struct{
	char name[INPUT_STR_LIMITS];
	int price;
} record_data_t;
int purseInt(char* str){
	long t;
	errno = 0;
	t = strtol(str, nullptr, 10);
	if (0 != errno || t < INT_MIN || INT_MAX < t){
		return -1;
	}
	return (int)t;
}
void swap_record_data_t(record_data_t* a, record_data_t* b){
	record_data_t tmp;
	tmp = *a;/* 構造体だからこそ'='でコピーが出来る。 */
	*a = *b;
	*b = tmp;
}
int compare_record_data_t(void* a, void* b){
	int tmp;
	tmp = strcmp(((record_data_t*)(a))->name, ((record_data_t*)(b))->name);
	return (tmp) ? tmp : ((record_data_t*)(a))->price - ((record_data_t*)(b))->price;
}
void bubble_sort(record_data_t *base, size_t num, int (*compare)(const void*, const void*)){
	int i, j, temp;
    for (i = 0; i < num - 1; i++) {
        for (j = num - 1; j > i; j--) {
            if (0 < compare(&base[j - 1], &base[j])) {
        		swap_record_data_t(&base[j - 1], &base[j]);
            }
        }
   	}
}
int main(void){
	int i, j, inputed_num;
	char buf[INPUT_STR_LIMITS] = { 0 };/* 念のため初期化 */
	char buf_to_num[INPUT_STR_LIMITS] = { 0 };/* 念のため初期化 */
	record_data_t shouhin[INPUT_LIMITS] = { 0 };/* 念のため初期化 */
	/* input data */
	for(i = 0; i < INPUT_LIMITS && NULL != fgets(buf, INPUT_STR_LIMITS, stdin); i++){
		sscanf(buf, "%s %s", shouhin[i].name, buf_to_num);/* 数値も一度文字列として読み込む */
		shouhin[i].price = purseInt(buf_to_num);/* 整数型(int)に変換 */
	}
	/* この時iは入力したデータ数(1起算)になっている。配列は0から始まることに注意 */
	inputed_num = i;
	/* バブルソート */
	bubble_sort(shouhin, inputed_num, compare_record_data_t);
	/* クイックソートを利用するときはこっち */
	/* qsort(shouhin, inputed_num, sizeof(record_data_t),compare_record_data_t); */

	/* print out result */
	for(i = 0; i  INPUT_LIMITS && i < inputed_num; i++){
		printf("%s %d\n", shouhin[i].name, shouhin[i].price);
	}
	return 0;
}

関数ポインタについて大急ぎで補足します。
変数に型があるのはC/C++erの常識ですが、この型の役割は何でしょうか?
ずばり、メモリー上にどのようにデータを置くか、ということを示しています。
関数も変数と同じように型が存在します。どういうことでしょう?
関数は呼び出す際にreturn値を書き込む場所、引数をスタックに積みます。そうです、どのように積むかが関数の型に当たるわけです。
例えば'compare_record_data_t'という関数の型は'int ()(void*, void*)'です(関数呼び出し規約についてはここでは無視します)。
で、これへのポインタ型なので'int (*)(void*, void*)'型となるわけです。

ただこれにもいくつか問題点があります。

swap関数が遅い
まあソートアルゴリズムバブルソートなので速度にこだわっても仕方ないですが、これは遅すぎます。
ソースコードにも書いていますがこれは構造体のコピー機能を利用しています。なので文字列もすべて精密にコピーされます。
お陰でシンプルにわかりやすくかけているのですが、メモリーアクセスが多すぎます。
compare関数が関数ポインタ経由呼び出し
関数ポインタ経由の呼び出しだとコンパイラーは関数をinline展開しにくくなり、コードが遅くなりがちです。
入力できるデーター数が固定(コンパイル時定数)
C99ならいざしらず、C89には可変長配列なんて物はありません。実行時に配列の大きさを決定するには動的確保する必要があります。
具体的には文字列は1文字ずつ読み込みreallocする処理を書くことになります
が、はっきりいって骨が折れます、心折設計とはまさにこのためにあるような言葉です。
ソートアルゴリズムが良くない
バブルソートはシンプルでわかりやすいのですが、あまり速くありません。
今回は学習用だろうと思いあえてそのままにしましたが、'stdlib.h'にあるqsort関数を使うべきです。(一応コメントでその方法を書いている)

C++14で書いてみる

ざっと以下の機能を使います。

  • クラス
  • コンストラクタの継承
  • コピーコンストラクタ
  • ムーブコンストラクタ
  • lvalue参照とrvalue参照
  • std::move
  • std::string
  • std::vector
  • std::cout, std::cerr
  • std::exception
  • std::runtime_error
  • Range-base for
  • 型推論(auto)
#include <iostream>
#include <string>
#include <vector>
#include <stdexcept>
#include <algorithm>
class record_data_t {
public:
	record_data_t() : name() {}
	record_data_t(const std::string& n, const int& p) : name(n) {//copy コンストラクタ
		this->price = p;
	}
	record_data_t& operator=(const record_data_t& r){
		this->name = r.name;
		this->price = r.price;
		return *this;
	}
	friend inline bool operator< (const record_data_t& l, const record_data_t& r);
	friend inline std::string to_string(const record_data_t&);
private:
	std::string name;
	int price;
};
inline bool operator< (const record_data_t& l, const record_data_t& r) {//ソートの基準となる、friend関数
	return (l.name < r.name) ? true : (l.name == r.name) ? l.price < r.price : false;
}
inline std::string to_string(const record_data_t& in) {//friend関数。operator<<をオーバーロードするのはめんdので逃げる。
	return (in.name + " " + std::to_string(in.price));
}
auto split(const std::string &str, char delim) {
	std::vector<std::string> res;
	size_t current = 0, found;
	while (std::string::npos != (found = str.find_first_of(delim, current))) {
		res.push_back(std::string(str, current, found - current));
		current = found + 1;
	}
	res.push_back(std::string(str, current, str.size() - current));
	return res;
}
auto convert_from_input(const std::string & line) {
	const auto vec = split(line, ' ');//空白文字で区切る
	if (2 != vec.size()) throw std::runtime_error("unknown input");
	return record_data_t(vec.at(0), std::stoi(vec.at(1)));//std::vectorからrecord_data_tに変換するためにコピーコンストラクタ(10行目)呼び出し
}
int main() {
	std::vector<record_data_t> shouhin;
	//input
	for (std::string buf; getline(std::cin, buf); ) {//一行を変数bufに読み込み
		try {
			shouhin.push_back(std::move(convert_from_input(buf)));//shouhinに追加。C++11:std::move,rvalue refarrence
		}
		catch (std::exception er) {//std::runtime_errorはstd::exceptionの派生型なのでこれでcatchできる
			std::cerr << er.what() << std::endl;
		}
	}
	//sort
	std::sort(shouhin.begin(), shouhin.end());

	//print data
	for (const auto& i : shouhin) {//Range-base for(C++11)
		std::cout << to_string(i) << std::endl;
	}
	return 0;
}