スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

深夜テンションで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;
}
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

PDFを編集する1





昔の記事なので一部情報が古いですが、いまでも設定ファイル使えます。


さて、前回は、AdobeReader X(テンと読みます)を、紹介しましたが、今度はきっと編集したくなるはず。

AdobeReader Xにも、一応編集機能はあるものの、「マーカー」「コメント」の機能しかない。そこで、このソフトを紹介します。

PDF-XChange Viewer 

ダウンロード | 13.5MB

1.上のリンクをクリックして、「DOWNLOD」をクリック。

キャプチャ 

2.保存先を聞かれるので適当なところを指定。

3.DLすると、こんなファイルが現れるので、
キャプチャ2
必ず、ウィルススキャンをする。
キャプチャ3
(フリーソフトをいれる上で、鉄則。必ずやろう)

4.アイコンを、ダブルクリック。
キャプチャ4
5.実行
キャプチャ5
6.はい
キャプチャ6
7.OK

キャプチャ7

8.次へ

キャプチャ8

9.次へ

キャプチャ9
9 .同意して次へ

キャプチャ10

10.次へ

キャプチャ11

11.次へ

キャプチャ12

12. デスクトップにアイコンを置く場合は一番上をチェック、
   PDFファイルをダブルクリックしたときに、このソフトで開く場合は、真ん中にチェック、
   Web上で、PDFを見るときに、PDFを、ブラウザーの中で表示するならば、一番下をチェック
そして、次へ

キャプチャ13

13.I accept the terms of the Ask のチェックを外す。次へ

キャプチャ15

14.インストール

キャプチャ16 キャプチャ17 
15.完了


続いていちいち設定をするのが、めんどい人のみコチラへ.

キャプチャ18

1.ダウンロード。適当なところに。

キャプチャ19

2.ソフトを立ち上げて、図のようにクリック

キャプチャ20

3.さっきDLしたファイルを選択

キャプチャ21

4.はい





キャプチャ22

ソフトの使い方は、次回。

テーマ : フリーソフト
ジャンル : コンピュータ

1年目:教師を目指しての自己成長の課題(備忘録)

教職概論の時間で教師に求められるものを学ぶ中で、「わかりやすい授業づくり」や「指導力」が求められていると教わった。しかし、わかりやすい授業をすることがどれほど大変か、ということを改めて痛感させられている。

私は神楽坂一丁目通信局というサークルでプログラミングをしている。このサークルでは伝統として2年生が1年生にプログラミングの講習会を開いていて、私はその教科書作成主筆と講習会講師を務めることになった。しかし、わかりやすく物を伝えるというのはたとえ自分がそのことについて完全に理解していても難しく、例えば変数とはなにか、といったごくごく初歩的なことすら十分に伝わらない。

教師になるということは当然その教科について完全な理解が求められるのはもちろん、それをわかりやすく伝えられなければならない。自分は化学について十分に理解できているとは思っていない。十分に理解できていることですら伝わらないのに、どうして不十分な理解でものを説明できようか。

私はわかりやすく伝える技術の向上と教科に関する理解をより深めることを目標に、大学2年目を過ごしたい。

無意味だとしても私はPGOビルドをする

PGOビルドとは

まあざっというとif文の条件分岐予測とか関数のinline展開を適切にするとか関数の配置を最適化するとかして気持ち実行速度を上げる方法です。で、大雑把な手順は

  1. ふつーにビルド(若干コンパイルオプションをいじる)
  2. 空のプロファイルを作る
  3. テスト実行。あんまりたくさんはやらない
  4. プロファイルを元にリビルド

なかんじ。で、Visual Studioでのやり方を調べたんだけど、MSDNの解説がさっぱりわからない。
ガイド付き最適化のプロファイル | MSDN
https://msdn.microsoft.com/ja-jp/library/e7k32f4k.aspx
チュートリアル : Profile-Guided Optimizations の使用 | MSDN
https://msdn.microsoft.com/ja-jp/library/xct6db7f%28v=vs.90%29.aspx
そこで調べていたら昔わけわかめで投げ出したrigayaさんの解説に行き着いた。

rigayaの日記兼メモ帳 x265 ビルド ~ Visual Studio PGOビルド
http://rigaya34589.blog135.fc2.com/blog-entry-540.html

抜粋しつつMSDNみつつで結論がわかったので実際の手順を書いてみる。

手順 on Visual Studio 2015 RC Community

  1. Visual Studio上でフツーにReleaseビルドする。/GLコマンドオプションが必要だけど、Win32コンソールアプリケーションを選んでプロジェクト作ってればデフォでついてるっぽい。
  2. 「ツール」->「Visual Studio コマンドプロンプト」
  3. cd [.slnファイルがあるフォルダーのフルパス]
    MSBuild /p:Configuration=Release;WholeProgramOptimization=PGInstrument [ソリューション名.sln]
  4. テスト実行する。
  5. MSBuild /p:Configuration=Release;WholeProgramOptimization=PGOptimize [ソリューション名.sln]

以上!簡単でいいね。

効果の程は?

もともとコンパイラーが優秀だからそこまで速くなるわけではない。
std::threadを使いつつ調和数を求める | CodeGarage
http://codegarage.edisonthk.com/_p/snippet/245
で試したら普通のReleaseビルドが76秒に対しPGOビルドは70.964秒。うん微妙。
まあでもほとんど手間がかからず少しでも高速化できるなら文句はないよね。やって損はない。なんてrigayaさんとおなじありきたりな結論が出たところでこの記事を終えようと思います。

検索フォーム
デジタル・コルクマ3
コルクマワールド
東京 での時間:
更新履歴


総記事数:
Calendar 1.1
<
>
- - - - - - -
- - - - 1 23
4 5 6 7 8 910
11 12 13 14 15 1617
18 19 20 21 22 2324
25 26 27 28 29 3031
- - - - - - -

全記事

Designed by 石津 花

最新記事
カテゴリ
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
ブロとも申請フォーム

この人とブロともになる

QRコード
QR
プロフィール

yumetodo

Author:yumetodo
FC2ブログへようこそ!

Powered By FC2ブログ

今すぐブログを作ろう!

Powered By FC2ブログ

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。