Go to Qiita Advent Calendar 2024 Top
LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@UFOnian

誰得遊び.平方採中法 on C++

Last updated at Posted at 2018-06-26

#readme1st
date:2018/6/26
この記事は2018/4月前までくらいに、誰も得しない個人的な遊びに書かれていた内容を、
分離し、単一記事にしたものです。

筆者はこの記事の最後（高速化のところ）を後に、
学校の授業再開等で忙しくしていたため、放置してました。
（興味を失ったわけではない）

で、その再開した授業で、Javaを習ったので、Javaでも書いてみたいなぁ...
と思った次第で、
記事をまた書き始める機会があるかもわからないが、
書くにしても、キリのいいとこまでやったらJavaに移行するかも。

#導入
date 18/03/21
ウィキペディアの疑似乱数のページの一番上で紹介されてた。
「一番上だし簡単じゃね？」って手を付けて半日潰したわけですが。
(っていうか「もっとも古い手法」ってちゃんと書いてあった。1946年だと。)

ウィキペディアさんを要約すると、ようは

  1. 初期値と、取り出すケタ数(take)を決める
  1. num = 初期値として以下を繰り返す
  • numを二乗する (tmp)
  • 真ん中の take ケタを取り出して、新たなnumとする
  • ただしこのとき、tmpをtake * 2 ケタとしてみなす。
  • 足りないケタ数は上位ケタに0をつける

    出力変換指定子風味に見せるなら%0(take*2)d 1

ただし、過去に出てきたのと同じ数字が現れると、それ以降は繰り返しとなるため、そこから先は乱数列に見えないよ。(疑似乱数ですらなくなるよ)

まあ読んでもらったほうが多くの場合はやいでしょう。
わかりやすい具体例も載ってますし。(具体例読んで理解したし)

##とりま作成
まず私が作ったのは、とりあえず上の演算で出てくる疑似乱数列を出力するもの。特に、ウィキペディアで紹介していた具体例の、4ケタを取り出すもの。これはそこまで難しくなかった。(アルゴリズムまんま書いてあったわけですし)

  • 前項を2乗したあとの下2ケタは不要なのでint型の変数(小数点以下切捨を利用)に100で割った数を記録させておく。仮称、a
  • 上2ケタを除去するために a を 10000で割った数をこれまたint型変数に入れた後、10000倍して上2ケタだけ抽出。仮称、b
  • a-bすると下4ケタ(つまり、前項の2乗の真ん中4ケタ)だけ取り出せる

最後の手順でb-aしたせいで負の数ばっかりでたり(2乗するせいで途中で変なことにならずに結果だけ負の数に...)っていう筆者の恥ずかしい失敗はさておき、これを関数に放り込んで繰り返しで実行すればrand()っぽくなる。実際に僕が書いたコードはこんなん

middle-square_prot

#include<stdio.h>

//初期値としてFSTを定義
#define FST 1763
int tmp = FST;

int nrand();

int main(){
	printf("FST= %d\n",FST);
	for(int i=0 ;i<5 ;i++)
		printf("%d\n",nrand());

	return 0;
}

int nrand() {
	int a = tmp*tmp /100;
	int b = a / 10000;
	b *= 10000;
	tmp = a - b;
	return tmp;
}

ぶっちゃけ今見ると、「前項の値を引数に与えると、次項こんな数になるでって戻って来る」感じでいいんじゃないかとか、これだとグローバル関数にtmpって名前が使えなくなるぜとか、いろいろ思うところがあるけど気にしない2（じゃあ書くなよ...）

ケタ数の指定がしたけりゃ100とか10000とかを10のn/2乗とかn乗とかで対処すればいいよねとか、そうする場合はケタ数多いとintじゃ足りなくなるかもねとかっていう発想も出てくるけどとりあえず満足して次に気になるところは、

繰り返しに入る瞬間である。

##繰り返しまで出力
最初僕は、一番最初にセットする初期値（上の例でいうならFST3）が再度出現するものと勝手に思い込んでかなり横道に逸れたのだが、

実際には「過去に既出の数が出ると繰り返しになる」である。
誰も初項とは言っていないのだよなぁ。

そうなると、過去に何が出現したか記録する必要がある。
知識不足の私はここで、「newで一個ずつ増やす...のはめんどい。bool型配列を10000個で用意して既出にチェック...はなんかキモい。」とかっていう遠回りを探って、
結局遠回りかもしれないけど、知識だけあったファイル入出力に頼ることにした。

ここから先のファイル操作とかについては、「苦しんで覚えるC言語」や「C言語関数辞典」からいろいろと知識を得たことを先に述べておく。

やりたいこと(ここで組みたいプログラムの順序)だけを先に述べると、

  • 上で作ったnrand()関数をfor文で繰り返す。
  • 出力される数値をファイルに書き込んで残す
  • ファイル中に、自分(nrandの戻り値)と同じ値があった場合は、繰り返し発生の旨を主張する

    (私が作ったものの場合、出力を停止する。)

以上である。

###ファイル制御に関するあーだこーだ（試行錯誤）

「ファイル制御系は完璧だし知ってること説かれてもなぁ」って人は読み飛ば推奨
「必要そうなファイルのあれこれを知ったところで実装」までジャンプジャンプ

自分が知っていたのは、

  • 外にあるテキストファイルから、数値をscanf(ファイルの場合fscanf)できるらしい
  • ファイルに書き出すの(fprintf)はやったことがある

ここまでである。具体的な方法についてはかなりうろ覚えだったので、9cguide^2を見返してなんとか思い出した。

ただし、
「やりたいこと」に書かれていることを実現するには、読み込みのために、ファイルの最初に戻る必要がある。(自分と同じ値が...の部分)

ファイルの任意位置のデータを読み取る...誰か使いたい人がいても全然おかしくないよなぁ
ってことでC言語関数辞典へ。
ヘッダーファイル別のページで「ファイル」をページ内検索すると、概要から拾える拾える。

###fseek関数
どうやら「fseek」関数を使うと

ファイル位置表示子を変更する
(C言語関数辞典より転載)

ことができる、らしい。
...なんだそのファイル位置表示子とやら

こことかも見て「ファイル(ストリーム)の何文字目かを示すものらしい」とか、「そもそもFILE型(だと思っていたもの)は構造体らしい」とか、いろいろと知った。
とりあえずは「カーソル位置」と認識することに。(しつこいようだが、この認識が正しいかどうか、筆者は全く保証しない)

fseek関数は、引数として

  • 位置表示子を変えたいファイル（ストリーム）
  • 相対位置（下で指定する「絶対位置」からの位置）
  • 絶対位置

の3つを要求される。

ファイルやストリームの指定には、FILE *で宣言したファイルポインタ型をそのまま渡す。FILE *fp = fopen("tst.txt","w+");とか宣言したならfpをそのまま突っ込む。
「ストリーム...まさか？」と思って、stdinを指定したらなんかいけたので報告しておく。
（後日覚えてたら記事にするかもしれないし、しないかもしれない）

絶対位置の指定には、あらかじめ用意されている位置表示情報を使える
SEEK_SET、SEEK_CUR、SEEK_END
の3通り。それぞれ
最初、今のカーソルの位置、最後

さらにそこに、相対位置分だけずらすことができる（？）。
相対位置の指定は、バイナリファイルのみらしいし、それはつまり、今回使わないということなので、詳しく見なかった。数値分のビット数（？）だけずれるんじゃないかな（ざつ）

例えばここで、fprintfとかして「カーソル」が最後まで行っているファイルのポインタ（fp）を持ってて、
「コイツの最初になんて数値入れたっけかfscanfで取り出してぇなぁ」ってなった場合、いちいち「fcloseしてもっかいfopenして...」みたいなことをせずに、ただfseek(fp,0,SEEK_SET);と書くことで、ファイルの最初に「カーソル」を持ってくることができる。ベンリ！

###rewind関数
その後もしばらくC言語関数辞典をうろちょろしてたら、rewind関数なるものがまた「ファイル位置表示子」を制御してくれそうだ。曰く、

ファイル位置表示子をそのファイルの始めに位置付ける
(C言語関数辞典より転載)

おお！これ使えばなんかSEEKなんたらとかすげーいらなそうな0とか書かなくてええやん！

と思ったけど、一応fseekで書くときとの違いとして、「エラー表示子をクリアする」っていうのがあるらしい。エラー表示子についても一応チラッと知ってはおいたけど、ここではやっぱり使わないつもりなので記事にはしない。

上で書いた例なら、rewind(fp);で済む。ラクチン！

##必要そうなファイルのあれこれを知ったところで実装
実際に書いてみた。

until_repeat

#include<stdio.h>

#define FST=1763
int tmp=FST;
int prev=-1;

FILE *memo;	//ファイル操作のためのポインタ


int nrand(){/*以前書いたのと同じなので省略*/}
bool lpck();

int main() {
	memo = fopen("mstmp.txt", "w+");
	fprintf(memo, "%d\n", tmp);

	printf("FST= %4d\n", tmp);

	for (int i = 0; /*break out*/ ; i++) {

		prev=tmp;	//直前の値を保持。実際にはnrand関数に含ませた
		nrand();
		printf("%7d | %04d\n", i,tmp);

		if (lpck())break;
	}

	fclose(memo);

	return 0;
}

bool lpck() {
//ファイルの最後にtmpを書き込み
	fseek(memo, 0, SEEK_END);
	fprintf(memo, "%4d\n", tmp);

	if (prev == tmp) return true;	//直前と同じなら繰り返し発生

/*ファイルの冒頭から直前と同じ値までを調べ、tmpと同じ値があれば繰り返し発生
「直前と同じ値」は、ここまで確実にlpckによってファイル中に重複がないことが保証されている限り、
「ファイルの最後のデータのひとつ上」まで出現しないことが保証される。 */
	rewind(memo);	//ファイルの冒頭から

	int t;
	do {
		fscanf(memo, "%d", &t);
		if (t == tmp) return true;	//繰り返し発生
	} while (t != prev);	//直前(prev)と同じ値まで

	return false;
}

追加されたのは主に

  • 直前の値を記憶する変数 prev
  • ファイル制御のためのいくつかの変更（FILEポインタ memo、実際の入出力先ファイルmstmp.txt、 関数 fopen、fclose等）
  • lpck(LooPChecK)関数。tmp、prev、ファイルの情報から、繰り返し発生を判定する。

今見るとやっぱり、

  • ファイル制御は基本的にlpck関数内だから、使うときだけlpck内で呼び出せばいいのでは？とか、
  • そしたらfseekのSEEK_END書かなくていいのでは（a+モードでファイル開けば）とか、
  • でもそうするとfopenとfcloseの回数増えて、（想定しないとはいえ）実行中に外からファイル開いたらデッドロックするのかなーとか、

思うところはある。（気にしない。じゃあ書くな2←ここまでテンプレ）

あと、fopenの戻り値がNULL4かどうか気にしてif(fopen(filename,"w+")==NULL)とかかいてエラー出力する書き方があるらしいけど、その辺全く考慮しない書き方なのでご了承（めんどいだけ）

さて、次に気になったのは、
##この方法で、ループするまでが最も長い4ケタの数は...?
0とか1000とか、0が絡み始める数や、下2ケタが「00」の数はすぐに繰り返しを始めるのは、実際に実行して繰り返し始めた数（1763の例なら4100とか）から想像はできる。できるが、

逆にループしだすまでが長いのはどんな数なのよってのは想像しにくいし、長いほうが乱数列としての"寿命"が長いと言えるだろう。

というわけで、寿命が長い初期値（当記事でいうところのFST3）を探るプログラムを作るゾ！
つってもコンピュータにさせる仕事なんで、0から10000まで虱潰してもらうだけなんですけどね

変更計画は以下の通り

  • 上で書いた具体例「until_repeat」のmain関数を改造して

    「FST(初期値)を引数として受け取り、ループ突入までの項目数（カウント）を戻り値として返す」関数にする

    具体的には、until_repeatのmain内のiを戻り値にする
  • main関数は新たに作成して、FST(0～9999)を上記の関数に渡して

    戻り値と暫定的な最大カウント数(max)とを比べて最大カウント数を更新していく。

この変更も大して難しくはなかったので、いきなりコードをはっつける。

max_until_repeat

#include<stdio.h>

FILE *memo;

int tmp;
int prev;

int nrand();
int dotry(int trynum);
bool lpck() {/*同一内容のため省略*/}

int main() {
	int max = 0;  //カウント最大値
	int maxn;     //最大値のときのFST
	
	for (int i = 0; i < 10000; i++) {  //FST

		int cnt=dotry(i);

		if (cnt > max) {
			max = cnt;
			maxn = i;
		}
	}

	printf("maxn : %d -> cnt : %d\n\n", maxn, max);

//	dotry(maxn);  最後にmaxnでdotryすれば、mstmp.txtに、ループまで一番長い時のデータを保持させられる。

	return 0;
}

int dotry(int trynum) {  //until_repeatでのmain関数・改
	tmp = trynum;

	memo = fopen("mstmp.txt", "w+");
	fprintf(memo, "%4d\n", tmp);

	printf(" %4d\n", trynum);

	int i;  //カウント変数
	for ( i = 0; /*break out*/ ; i++) {

		nrand();

//		printf("%7d | %04d\n", i,tmp); 出力処理減らし
	
		if (lpck())break;
	}

	fclose(memo);
	return i;
}

int nrand() {
	prev = tmp;  //prev更新をnrand内に記述
	int a = tmp*tmp/100;
	int b = a / 10000;
	b *= 10000;
	tmp = a - b;
	return tmp;
}

dotryとかtrynumとか、ひやひやする名前（doとかtryって予約語なのに）使っちゃって書きながら変な汗かいた。
っていうか、tmpグローバルで宣言してるし、main内でtmp更新してdotry呼びだせばtrynumとかいう変数いらなかったよね。（気にしな以下略2）

「寿命の終わりこれでいいんか？」って疑問の人は下の折り畳みへ

乱数列の寿命の終点位置についてのあーだこーだ ちなみに、上記のソースコードでは、ループし始めてから**最初のループが終わる瞬間**を終点としてカウントしている。 　（しかもカウント数はdotry関数中のfor文のiをあてているので、実際には相対値でしかない。 　　　基準の0は、FSTを第1項として、第2項がFSTと一致したときである。） ループ開始時点(最初のループの開始時点)を寿命とする見方もあるだろうし、そっちのがより乱数列としては"キレイ"だろうなぁと予測はつくが、今回は上記仕様で最後までやり通した。 ふたつの終点位置を両方保持、mstmp.txtとはまた別のファイルにcsv形式で保存して、表計算ソフトで表とかグラフで比較するのも面白いかもしれない。

実際にはもっといろいろと遠回りしたけれど、最終的にはこんな感じに落ち着いた。
実行すると0から9999までの数字を一行ずつ表示(処理中のFST。進行状況見たくて保持させた)したあと
maxn : 6239 -> cnt : 110を出力して停止する。

すなわち6239のときの寿命が最長らしい。
カウント数の110はちょっと信用しにくい（上記「終点位置」についての折り畳みに詳しい）ので、
dotry(6239)してmstmp.txt(入出力ファイル)を覗く5と、
108項目で出現した「4100」が、112項目で再出現してループとなるようだ。
この場合、6239は上限指定(もちろん10000未満。サイコロとか)の乱数、111回までなら乱数列として採用できなくもないと言える。

##ひとくぎり
とりあえず、この日(18/3/21)の僕の遊びはここまで。

思いつくのは、記事の途中でちょっと触れてた、取り出すケタ数の拡張の話。
4ケタではたったの110回そこらで寿命が尽きるが、取り出しケタ数を増やせばループ回数も増えるだろう。

ただし、上記max_until_repeatを実行した人ならわかると思うが、この方法はいささか時間がかかる。

##高速処理のための工夫
時間がかかる原因は、寿命が長い時特に顕著に表れる「一時ファイル(今回ならmemo(mstmp.txt))へのアクセス回数の増加」だと推理。
根拠...というか直観だが、寿命が長いということは、新しい項目が既存の項目と一致するか検証するとき、既存の項目数分ファイルからfscanfする。
寿命(ループまでの項目数)をnとするとき、fscanfが呼び出される回数は、
1+2+3+ ... +n 回、すなわちおおよそ n*n /2 回6
この場合、nが増えたときの回数増加はわりと無視できない。
実際、上記max_until_repeat時のfscanf回数を数えさせてみたところ、13,094,042回　(約1309万回)呼び出されていた。
うっひょえ。俺数えさせ方間違えたかな...

そんなわけで、fscanf回数を減らす方法を考えてみた。
具体的に思い浮かんだのは以下。

  • 「過去old_FSTでdotryしたとき、nrand列中に出てきた数」をFSTとしてdotryした場合、

    old_FSTのときよりも短い寿命しか持ちえない7

    　>よって、「過去のFSTでFST数列中に出てきた数値」をストレージする"何か"を用意し、それに一致するFSTは省くことで、ファイル読み込み回数を減らせる...かもしれない

とりあえず今(18/03/22-24時前後)時点で思いつくのはこれだけだ。

ちょっと面白そうなので、明日はこの「処理時間短縮」課題をクリアしていきたいと思う。
さんざ遊んだらまた続き書く（かも）

晩飯まだ食ってねぇ...(@date==18/03/22-24時)

###バイナリファイル
とその前に、バイナリファイルについてちょっとかじる。
私の発想では、上記の「FST数列中に既出の数」を記録するのに、やっぱり10000個の配列用意して1,0で既出かどうか記録するしか...
と思ったのだが、「1,0だけ保存するならバイナリファイルが向いてるんじゃね」とかいう誤解まっしぐらな発想でバイナリファイルに手を付けようとした。

きちんと調べたうえでの解釈↓
「コンピュータに保存してるファイルって言ったら本質的には全部バイナリファイルで、文字列を（文字列と思って）保存してるものを特にテキストファイルと呼ぶ」ってのが正しい認識なのかな？「バイナリファイル⊃テキストファイル」的な。

んで、c言語におけるバイナリファイルの扱いは、「1項目のデータサイズ（単位）を決めて、その単位毎に読み書きを行うファイル」ってところだろうか？
fwrite関数とかfread関数とか見た (C言語関数辞典にて)感じ、単位は途中で変わってもいいようだが。
（そのように扱う場合は仕様をギチギチに決めねばならないのだろうなぁ。ヒトが扱おうと思った場合はデータベース扱う時みたく列数決めて行数が変動とかそういう扱いじゃないと処理しにくそうだなぁ。とか思ってみたり。）

ともかく、なんかCSVファイルちっくに扱えて、調べたところ何やら処理も早いのがバイナリファイルの利点だとか。

早速バイナリエディタ（ビュアーで十分だけど）とか揃えていろいろ実験してわかったこと。
どうやら、int型のデータを保存するのに、処理する形式が、
テキストファイルとしてだと、1文字につき1バイト使っていた（文字列、つまりchar型の集まりとして保存していた）のが、
バイナリファイルとしてだと、1数値につき固定で4バイト使う（int型の直接保存）ことになる。

また、バイナリファイルの場合は直接数値をブチ込んでいるが、テキストファイルのほうは文字として数字を記録しているので、文字→数値の変換作業が間に挟まる分なんかめんどいことしてるんすねたぶん。8

そういうことなら、テキストファイルとして処理してた上のmemo(mstmp.txt)もバイナリにしたほうが早いに違いない！
早かろう良かろうなのだ！、というわけで、mstmp.txtまわりをバイナリ仕様にするための書き換えもするのであった。
ほとんどコード変わらない(rewindとかは相変わらず使える。fprintfやfscanfが、それぞれfwriteとfreadに置き換わって、増えた引数を補う作業になるだろう。引数いちいち書くのめんどそーだし関数化したけど。）が、変更部分を掲載する。

バイナリファイルでの読み書きへの改訂

txt2dat

template <class T>
void myfw(FILE* fp, T t) {
	T k = t;
	fwrite(&k,sizeof(T),1,fp);
}

template <class K>
void myfr(FILE* fp, K *t) {
	fread(t, sizeof(K), 1, fp);
}


int dotry(int trynum) {
	tmp = trynum;

	memo = fopen("mstmp.txt", "wb+"); //バイナリモードでfopen

//	fprintf(memo, "%4d\n", tmp);  fwriteへ改訂
	myfw(memo, tmp);

	printf(" %4d\n", trynum);
	int i;
	for (i = 0; /*break out*/; i++) {
		nrand();
		if (lpck())break;
	}
	fclose(memo);
	return i;
}

int nrand() {/*省略*/}

bool lpck() {
	fseek(memo, 0, SEEK_END);
//	fprintf(memo, "%4d\n", tmp);
	myfw(memo, tmp);
	
	if (prev == tmp) return true;
	rewind(memo);

	int t;
	do {
//		fscanf(memo, "%d", &t); freadへ改訂
		myfr(memo, &t);

		if (t == tmp) return true;
	} while (t != prev);

	return false;
}

int main() {/*省略*/}

正直に言うと上で宣言しているmyfwとmyfrの宣言の仕方は私は全くわかってない。

ぶっちゃけfreadもfwriteも引数が多いのである。しかもsizeofとか使うのキモい。（バイト数覚えりゃいらんけども）
配列との間で制御できるようにしたのはたぶん、一時ファイルとしてdatにぶち込んだ複数データ群を、使うときに配列（つまりメモリ）に必要なだけ読み込ませてどうの、ってつもりなのだろうし、そのほうが高速なのだろうけれども、ちょっとnewとか配列とかを組み合わせるのがめんどそう（思いつかないでもないが、できるか不安）なので、今回は一個ずつ取り出したい。（配列に読み込む方法もそのうち考えようとは思うが）
ので、項目数は1に固定させてもらう。

sizeof()の部分も省略したいけどintと、（あとで使う予定の）boolとで関数を分けるのは面倒くさい。

そこで、引数の型を指定しない関数を作れないか検索してみた。
C++ジェネリックプログラミング入門によると、template <class T/*(変動型名？)*/>のように書くと、Tという名前の変動型（？のようなもの）を宣言できる。後ろに戻り値の型 関数名(T x , ??...)と書いて、この関数を呼び出すときに、xの部分にint 型を入れるとその時にはint型として、bool型を入れるとその時にはbool型として処理される。またこのTは、上の関数の戻り値の型としても使える（上記記事ではそういう使い方をされていた）

実際の記述はこう。

テンプレートとは、 C++の言語機能の一つで、型を差し替え可能なクラスや関数を作成するための仕組み である。
（上記記事より引用）

上にも書いた通りというか、上で書いたような解釈の仕方しかしていない。この解釈が正しいかはちょっとわからないが...
動いたからそれでよいのだ！（オイ）
上記引用文の言ってる意味は分かるが、前提知識がなにぶんたりない。C言語では必須っぽいvectorと呼ばれるものが何であるのかすら把握していないのである。（調べて少し読んだけどむずそうで興味が霧散した。おのれいつか必ず読破してくれるわ...）

まあそんな知識を得た経緯とかは個人的な経験なのでいいとして、

上記myfw('myfw'rite),myfr('myfr'ead)は、変動型（仮）を宣言して、オリジナルの関数で用意されているfwriteやfreadで必要とされる引数のうち、「一項目のデータサイズ（私の言い方でいう「単位」）」と、「項目数(1で固定させる)」とを省略させるために、データサイズをsizeof(T)として、Tは引数の型に応じて変化するようにしている。

すなわち、上記コードの上数行の記述となる。

###ファイル読み取り回数を減らす
ファイルの読み取り回数を減らすための工夫として、これまでに検査されたFSTから始まる乱数列に含まれる数の検査を省略するものというものを考えた。

また、これをファイルへの入出力によって実現することにした。

実際にはもっと賢い方法があるようで、コメントにて指摘してくれたかたがいるので、そのうちそちらの書き方でもやってみたい。
（std::setやste::bitset）

（ある程度）具体的な変更点は以下。

  • mstmp.datとは別に、既出数を記録するためのファイル(old_FST.dat)を用意
  • dotryする前に、old_FST.datを参照し、今のFSTが過去のFSTの乱数列上に出現していなかったかを確認する。
  • old_FST.datの初期値をfalse(0x00)として初期化させる。
  • dotry中、nrandの戻り値として出現した数かどうかをold_FST.datの該当箇所で管理するため、出現した場合にtrue(0x01)に書き換える。

適用したコードが以下。

skip_read

#include<stdio.h>
#include<Windows.h>

FILE *memo;
FILE *old;

int nrand();

#define per 1000
int lef = 10000 / per;

int tmp;
int prev;

int glb_cnt = 0;


int dotry(int trynum);
bool lpck();

//fwriteの要素数を1で固定。書き込むモノに合わせてデータサイズ単位を自動指定。
template <class T>
void myfw(FILE* fp, T t);

//freadの要素数を1で固定。読み込ませるデータ先に合わせてデータサイズ単位を自動指定。
template <class K>
void myfr(FILE* fp, K *t);

//freadで読み込んだデータを返す。tはデータ型指定用
template <class Y>
Y myfrout(FILE* fp, Y t);

int main() {

	old = fopen("old_FST.dat", "wb+");

	int max = 0;
	int maxn = 0;

	for (int i = 0; i < 10000; i++) myfw(old, false);

	for (int i = 0; i < 10000; i++) {
//	for (int i = 9999; i >= 0; i--) {　//後ろからやったほうが早いかもという試みの名残

		fseek(old, i, SEEK_SET);	//iで正常動作することを確認する（本当にi番目か）
		if (myfrout(old,false)) continue;
		
		int cnt = dotry(i);

		if (cnt > max) {
			max = cnt;
			maxn = i;
		}

	}
	
	printf("maxn : %d -> cnt : %d\n\n", maxn, max);
	
	dotry(maxn);

	printf("glb_cnt > %d\n\n", glb_cnt);
	fclose(old);

	system("pause");
	return 0;
}



int dotry(int trynum) {
	int s=0;
	tmp = trynum;

	memo = fopen("mstmp.dat", "wb+");
	myfw(memo, tmp);

	printf(" %4d\t", trynum);
	//進行状況バー
	int blk = trynum / per + 1;
	int j;
	for (j = 0; j < blk; j++)	printf("■");
	for (; j < lef; j++)			printf("□");
	printf("\n");

	int i;
	int trand;
	//
	for ( i = 0; /*break out*/ ; i++) {

		trand = nrand();
//		printf("%10d | %04d\n", i,tmp);

		fseek(old, trand, SEEK_SET);	//相対位置キーがtrandで正常に動作するか確認する。
		myfw(old, true);

		if (lpck())break;
		
	}

	fclose(memo);


	return i;
}

int nrand() {
	prev = tmp;
	int a = tmp*tmp/100;
	int b = a / 10000;
	b *= 10000;
	tmp = a - b;
	return tmp;
}

bool lpck() {
	fseek(memo, 0, SEEK_END);
//	fprintf(memo, "%4d\n", tmp);
	myfw(memo, tmp);

	if (prev == tmp) return true;

	rewind(memo);

	int t;
	do {
//		fscanf(memo, "%d", &t);
		myfr(memo, &t);
		if (t == tmp) return true;
	} while (t != prev);

	return false;
}


template <class T>
void myfw(FILE* fp, T t) {
	T k = t;
	fwrite(&k, sizeof(T), 1, fp);
}

template <class K>
void myfr(FILE* fp, K *t) {
	fread(t, sizeof(K), 1, fp);
	glb_cnt++;
}

template <class Y>
Y myfrout(FILE* fp, Y t) {
	Y k;
	fread(&k, sizeof(Y), 1, fp);
	return k;
}

old_FST.datを読み取るためのファイル読み取りを含めて、読み取り回数は6,907,784回（訳691万回）まで減らせた。それでも半分か...

尚、上記コードは、久々（実に3カ月ぶり）にコードを見るのが面倒で、
とりあえず動くことと、ここにふさわしい動作をすることとを確認して、
コメント行とかほぼそのままにペーストしたものである。（やっつけ仕事万歳）

可読性のためのコメントの重要性とか、もちっときれいに整理しないかねぇとか感じた。

ひとくぎり#2

コメントでもらっていたdatasetについて（元記事のコメ欄参照のこと）
datasetの扱い方とかのテキストを、たぶん今（18/06/26）の私（クラスとか習った）なら不安なく読めそうなので、そちらでの実装を考えていきたい。
（が、おそらく次に手を出すのはJavaでのコーディングである。）

mof

#参考資料
各資料毎に個人的な感傷・感想をだーだー書いたが、見にくすぎて「なんじゃこりゃ」ってなったんで折りたたんだ。
読みたい人は▶をたたくと長文が開く。（やましいことは書いてない... 書いてないったら！）

[**苦しんで覚えるＣ言語**](http://9cguide.appspot.com/) 私がC言語について全く知らない状態から、「プログラマになるゾ」と思いついたときに、 とりあえずC言語、いっとかない？感覚でC言語を学習しようとwebサイトをあさって見つけたサイト。 「書籍化もしている」とのことから信頼して読み漁り、対話なしではちょっとついていけないポインタの話くらいまでここで学習した。 「苦しんで」という割に、全然知らない人でもきちんと読めば、とりあえず理解できるように説明されている印象を受ける素敵なサイト。（主に苦しんだの筆者じゃないかしらん） 「苦C」だの「9cguide」だの表記にブレがあって申し訳ない。 アドレスバーに「9」と入れると即ここが候補に挙がる程度にはアクセスしてる。というか、困ったら見てる。
[**C言語関数辞典**](http://www.c-tipsref.com/) C言語やってて「解説書に乗ってる関数全部覚えた」とかじゃなければ一度はアクセスするんじゃなかろうかっていうネーミングのサイト。 関数の引数・戻り値・機能のざっくりした説明に、サンプルコードも載ってて、関数以外にもマクロで定義されてるような定数の説明とか、専門用語で「聞いただけじゃわからないよ」って感じの単語の説明も載ってる、丁寧なサイト。 概要説明のある関数一覧のページで、欲しい機能に関連する単語（ファイル操作の関数なら「ファイル」とか）でページ内検索すれば概要に引っかかって探せちゃったりするので便利。ある種のチートシートとして利用している。
[**一週間で学べるシリーズ**](http://sevendays-study.com/index.html) シフトシステム株式会社さんが作ったプログラミング言語の解説ページ群 C++のページの、特にクラスに関する話にてお世話になった。 私はクラスについてはまださっぱり知らない初心者であるし(18年3月現在)、きちんと人（先生）との対話の中で勉強したいので、参考程度にチラリと見ただけだが。

  • Qiitaの投稿より
[**C++ジェネリックプログラミング入門**](https://qiita.com/MasayaMizuhara/items/f43085f309b9163de436) 引数の型を指定しない関数の作成がしたかったのでブラウジングしてた結果たどり着いた。 `template `と関数の前に書くことで、「何かしらの型"T"」みたいな扱いができるようだ。

eof

  1. この書き方は正確でない ↩

  2. 「気にしない気にしない」って書いてるけど、実際に書いてるコードはもっともっとぐちゃぐちゃなんだなんて口が裂けても言えない。 ↩ ↩2 ↩3

  3. ところでこのネーミングは「FirST」からくる。実にてきとう ↩ ↩2

  4. fopen関数は、ファイルオープン（書き込みのためのファイル確保。セマフォのどーたら（？）） に失敗するとNULLポインタが返る。if文でNULLが来たら、「ファイルオープンに失敗したよん」って画面に表示させることができる。このとき、上でチラッと触れたエラー表示子を使うことで、エラーコードを出力することもできる（？） ↩

  5. 一行目からFSTを出力して、ループの原因になる数値までを出力するので、ループ開始地点とかも見つけやすいし、行数が表示されるエディタであれば、その値が何項目かまでわかる。(行数も出力する仕様にしようと思えばできるハズだが) ↩

  6. こんなことは中学数学とか中学受験とか、ガウス先生っていう偉人なら小学3年生の頭脳で即興で(wikipediaリンク)、知るようなことだが、1からnまでの自然数の総和は(1+n)*n/2で求まる。
    今回はちっちゃいほうで取っても十分に大きくなると判断できるし、知らない人のために説明するのはめんどかったりで簡単に書いた。...ほんとに知らない人は「ここ」。
    ほんとはn^2 /2 って書きたいんだけど、xのn乗を x^n って書かない言語もある（ってかC言語がそう）なので避けた。 ↩

  7. かなりざっくりと直感的な証明(もどき)
    old_FST数列（仮称:old_FSTを初期値として、平方採中法に基づく数列で、ループ開始地点を最終項とする）は、途中からFST数列となる。
    ループを開始する数を共有しているうえに、そこにたどり着くまでの項目数はFST数列のほうが短いので、FST数列のほうが寿命が短いことがわかる ↩

  8. 具体的には、Unicodeベースの文字コードセットは、半角数字を、例えば5なら0x35(16進数表示。十進数なら53。2進数なら0011_0101)として保存する。数値データにするためには、16進数表示でいう上の一桁、二進数なら上4ケタの0011を取り除く処理をする。4ビット左にシフト演算してどうの...とか。さらに、10進数として記録して、ケタとして別れたそれを10倍して足して...みたいなこともしなければならない。記録するときにはこの逆が行われているハズだから、そっちも含めて時間を食ってるに違いない（という推測） ↩

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?