yamicha.com's Blog - Presented by yamicha.com
Blog yamicha.com's Blog - 2018/08 の記事
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31]

yamicha.com's Blog
 諸事情により、現在更新休止中。ご了承ください。もし今後ブログを再開することがあるとすれば、その際にはこのブログスクリプトではなく、新しく開発したものによるかもしれません。
 当ブログ管理者についてはこちらをご参照。
開発魔法(737)
社会問題(733)
お知らせ(11)
質問・バトン回答(15)
ゲスト出演(8)
経済・知的財産(150)
ゲーム開発(182)
[Ada] 勝手に補足
- Note
- 金配りの次の一手


- Endless Ultimate Diary
- 銃世界

漢字バトン
- うるる雑記帳
- 漢字接力棒

ツキアイゲノムバトン
- ブログ@うにうに画像倉庫
- あぶ内閣

縺イ縺セ縺、縺カ縺励ヰ繝医Φ
- 月夜のボヤキ
- 騎士サーラバトン
パスワードを使う
名無し (2012/02/27)


開発者解放裁判
yamicha.com (2010/03/14)
Winnyに関しては、私も「純白」とまでは考えておりませんし、使用し..

開発者解放裁判
通りすがり (2010/03/08)
winnyに関しては「ダウンロードソフト板」なんてところを拠点に開発..

新型インフルエンザの恐怖
いげ太 (2009/11/03)
> C#などの「int Some(int , int)」は、F#では「(int * int) ->..

時効に関する思考
yamicha.com (2009/08/31)
>いげ太さんコメントありがとうございます。手元にドキュメントが少..
Homepage
Blog Top
Normal View
List View
Search
Calendar
Comment List
Trackback List
Blog RSS
Send Trackback
Phone Mode
Administrator
yamicha.com
Blog
るううるる。
Source
法令データ提供システム
FindLaw
Development
Java2 Platform SE 6
Java EE 6 API
MySQL Developer Zone
PHP Reference
MSDN Library
Ada Reference Manual
Objective Caml
Python Documentation
Erlang
Prolog Documents
 垂オ訳ございませんが、現在このブログではトラックバックを受け入れていません。

 この記事に対してリンクされる場合には、こちらのURLをご利用ください。
http://void.yamicha.com/blog/blog.cgi?mode=view&number=368
 上記URLをトリプルクリックされますと、簡単にURL全体の選択が行えます。

※以下の記事がトラックバックされます。
日本赤十字軍
2006/05/11(Thu)06:12:00
 何やら物騒な「引きこもり支援施設」と称する施設の死亡事件。事の起こりは、被害者の母親が施設に電話をしたということになっていますが、施設側は下見の際に「カギ部屋」と呼ばれる監禁部屋に案内しなかったとか。まあ、するわけがありませんが。
 加害者は逮捕され、今後は罰則が下されることでしょう。それから、「被害者の家族にも落ち度があった」と指摘するのは簡単ですが、おそらく打ちひしがれているであろう遺族にそういう言葉を投げかけるのは、救う会、万引き少年を警察に渡した店主、またはイラクで殺害された香田さんサイドを批判するなどと同等の行為ですから、こちらは据え置きます。
 しかし、何よりの問題はこの施設がテレビで紹介されて連絡先が表示されたという点に他なりません。テレビというのは公共性の高いものであり、ゆえに放送には免許が必要ですし、外国人は放送会社の議決権を20%以上持てないようになっています。また、オウム冤罪事件のように、テレビなどが無罪の人間を犯罪者に仕立て上げることもあります。
 それだけ影響力のあるメディアが、監禁や虐待など何でもありで、結局は命が失われる結末となった施設を紹介したというのはとんでもない話です。犯罪に手を貸しているも同じではありませんか。読売新聞はこの前、佐々氏や海陽学園を美化して取り上げていたりしましたが、このテレビでもトンデモなものが美化して取り上げられていたのでしょう。
 公共メディアで情報を流すからには検証が欠かせません。そして、この施設もしっかり検証さえすれば実態が明るみに出た可能性があります。こんなのは退所者などに話を聞いていけば分かることですし、通常は取材過程で「おや」という点があるはずです。事実、入所者や職員の間では「カギ部屋」なる通称が定着していたといいます。
 テレビ番組がきっかけとなり、その施設で命が失われました。これ、下手すると犯罪なのでは。何より悔しいのは、メディア・スクラムの場合もそうですが、これを問題にする法律がないことです。倫理的には限りなくクロに近いはずの人間が、ぬけぬけとしていられるのですから。
 実際、私としてはいい加減に法整備を行うべきと考えるのですが、敵もさるものです。「報道の自由の侵害だ」とだけ称すれば、政府が手出しできなくなることを十分承知しています。病原体を根絶するのには、患者の治療(今回の場合は施設の摘発)と周囲への感染防止(同施設を報道しない、あるいは実態の報道)を同時に行わねばならないのと同じというのに。
 あと、これは結果論ですから無理な話とは分かっていますが、公共メディアで施設が公にされたからには、関係機関が動けなかったものでしょうか。最近は殺人事件が頻発し、感覚が失われかねませんが、殺人や致死事件は本来これほど重いことなのでは。

 その他、面白い記事が載っていました。若者に献血について聞いてみたところ、「興味はある」と答えたのが5割にもかかわらず、嫌な理由として「痛そう」「怖い」が存在し、しかも提案として「麻酔で痛みを和らげては」などがあるとか。
 それは確かに痛いでしょう。痛いですとも。ただし、開発者はいつでも「痛い」人間ですから(何のことやら)、割と大したことありません。とりあえず、針は派手に太いのですが、見た目ほど痛くはありません。こんなのに麻酔をかけたら余計痛いでしょう。麻酔薬が血に混ざってしまうのもまずいでしょうし。
 で、初めて訪れたらそれは怖いですとも。これはもう、実際にアタックして体験するしかありません。人によっては「2度とイヤだ」という人もいるでしょうが、案外平気なものです。1度体験してみれば、次からはそう怖がる必要はありません。
 ただ、緊張耐性が極めて高いはずの私も、今でもよく脈が高くなってしまうのですが。今年の成人の日の前日に行って、心拍数で撃沈し(自宅で測定しても120/secでした。体調が悪かったようです。翌日には回復)、それっきりです。たまには行かねば、と言いつつも、今の体調ではどうでしょう。ブログ書くのもままならないほど弱っているというのに。そのうち体調を回復してまた行きましょう。
 それでは私からも(半ばおふざけですが)提案を。献血の問診役には男性も女性もいますが、私が見たところ採血を行うなどするのは全員女性です(ただし、若い人ばかりではなくベテランもいます)。ということで、ここはハンサムな男性を仕入れて指名できるようにすれば。いや、これでは指名ホストではありませんか。

 先に扱ったソートアルゴリズムですが、いくらかチューニングしてみました。また、ヒープソートに関しては、やはり私が失敗していたようです。参考文献が分かりづらかったのと、私の理解が浅かったようで。それでは新しく作ったアルゴリズムを。一連のアルゴリズムでは開始点と終了点を設定できますから、実装は少々複雑になっています。
 なお、以前に作ったものに関してはこちらをご参照。
// 修正版ヒープソート
public void heapSort(int sort[] , int start , int end){
	int first = start;
	int last = end;

	// ヒープ構造を作成
	for(last = first; last <= end; last++){
		int r = last;
		while(r != first){
			int p = (r - first + 1) / 2 - 1 + first;
			if(sort[r] > sort[p]){
				int t = sort[p];
				sort[p] = sort[r];
				sort[r] = t;
				r = p;
			}else
				break;
		}
	}
	last --;

	while(first != last){
		// 根ヒープを除外
		int t = sort[last];
		sort[last] = sort[first];
		sort[first] = t;

		last --;

		// 下位ツリーへソート
		int r = 0;
		int top = 0;
		while((top = (r + 1) * 2 - 1 + first) <= last){
			int my = r + first;
			int f = 0;
			if(top + 1 <= last && sort[top] < sort[top + 1])
				f = 1;
			if(sort[my] > sort[top + f])
				break;
			int d = sort[top + f];
			sort[top + f] = sort[my];
			sort[my] = d;

			r = top + f - first;
		}
	}
}
// メモリ確保のオーバーヘッド回避型マージソート
public void refMergeSort(int sort[] , int start , int end){
	refMergeSort(sort , new int[end - start + 1] , start , end);
}
public void refMergeSort(int sort[] , int s[] , int start , int end){
	if(start >= end)
		return;
	int len = end - start + 1;

	// 分解
	int sv[] = new int[2];
	sv[0] = len / 2;
	sv[1] = len - sv[0];

	// 再帰的ソート
	refMergeSort(sort , s , start , start + sv[0] - 1);
	refMergeSort(sort , s , start + sv[0] , end);

	for(int i = start; i <= end; i++)
		s[i - start] = sort[i];

	// 並び替え
	int pos[] = new int[2];
	pos[0] = 0;
	pos[1] = sv[0];

	for(int i = start; i <= end; i++){
		int copy = 0;
		// インデックスの範囲内かチェック
		if(pos[0] >= sv[0]){
			copy = 1;
		}else if(pos[1] >= len){
			copy = 0;
		}else{	// 範囲内なら
			if(s[pos[0]] < s[pos[1]])
				copy = 0;
			else
				copy = 1;
		}
		sort[i] = s[pos[copy]];
		pos[copy] ++;
	}
}
// メモリ確保のオーバーヘッド回避型基数ソート
public void refRadixSort(int sort[] , int start , int end){
	int bv = 4;
	int max = 8;

	int bit = 1;	// ビット深度
	for(int i = 0; i < bv; i++)	// 累乗(bit = 2^bv)
		bit *= 2;

	// 必要なメモリをここで全部確保し、後はそれを使いまわし
	int s[] = new int[end - start + 1];
	for(int b = 0; b < max; b++){
		// バケット必要数を計算
		int use[] = new int[bit];
		// 個数を出す
		for(int i = start; i <= end; i++){
			int d = (sort[i] & ((bit - 1) << (bv * b))) >> (bv * b);
			if(d < use.length - 1)
				use[d + 1] ++;
		}
		for(int i = 1; i < use.length; i++)
			use[i] += use[i - 1];

		// バケット分別
		for(int i = start; i <= end; i++){
			int d = (sort[i] & ((bit - 1) << (bv * b))) >> (bv * b);
			s[use[d]] = sort[i];
			use[d] ++;
		}
		int index = 0;
		for(int i = start; i <= end; i++){
			sort[i] = s[index];
			index ++;
		}
	}
}
 これを実験した結果は以下の通りになりました。実行結果は一例ですが、何度繰り返しても大体この通りになります。今回は200,000個の配列をソートしました。
アルゴリズム時間(ms)
クイック1161
基数(前・通常)4257
基数(前・メモリ節約版)621
基数(新・メモリ節約版)551
ヒープ(新)781
マージ(前)2984
マージ(新)1172
 この通り。何とクイックソートがとんでもなく落ちているではありませんか。前回に作った、メモリを節約しない基数ソートとなると、もう話になりません。配列長のメモリを4ビット(4^2 = 16)分も確保するのですから。ここまでになると、カウントしてメモリを確保した方がオーバーヘッドを避けられます。
 しかし、これでもメモリを毎回確保するオーバーヘッドはバカになりませんから、そこで作成したのが今回のソートです。これは最初にデータ長のメモリ(バケットソートでは必ずデータ長分のメモリが必要)を確保しておいて、それを最後まで使いまわします。そうすると、200,000個の配列を8度作っていたのが1度でよくなり、性能が向上します。
 新しいヒープソートはさすがに速いです。基数ソートに少々劣りますが、基数ソートは制限が多い(例えばユーザー定義のソートに使うことは非常に困難)であることを考えれば、データ量が多いなら実質ヒープソートが最善の選択でしょう。
 そしてマージソートが意外に健闘しています。クイックソートとほぼ同等とは。バブルソートは省きましたが、さすがにこれでバブルソートを動かす勇気はありませんでした。相当な時間がかかる可能性がありますから。

 ついでに作ってみた素早さ実験アプレットがこちら。ただし、これはFFのようなATBではありません。あくまで擬似的にメーターを出しているのであって、すでに全員の順番は決定しています(順番は「ACT」をチェックしてください)。ただし、(このアプレットには素早さの変更処理などは実装されていませんが)途中でキャラのAGIが増減しても大丈夫なように設計してあります。
 これの目新しいところは、何といってもどれほど素早さが高くても、差があっても大丈夫な点に他なりません。相対的に評価しているため、たとえ素早さが1億であっても全くオーバーヘッドなしに動作します。そういうシステムですから。ただ、システムとして洗練されていない(というより実装に迷っている)部分はあります。
 しかし、魔道士イリアスが素早いのは当然として、問題はシェリーさん。騎士サーラが40回行動する間にようやく1回行動できる速度です。

 SQL.36。一応言っておきますが、ネタのストック帳にネタをためたりはしていません。ストックできるほどネタが出たらどれだけ助かるやら。即席でひねり出しては話の構成を作っているので、時としてクエリが破綻したり。

 本日も難題を抱えた魔道士イリアス。側近のサーラに相談します。

騎士サーラ「・・・とすれば、この計算の結果、正味資産は・・・」
魔道士イリアス「サーラ、ちょっと相談・・・って、何かまた難しいことを考え中らしいわね。じゃあ、後にするわ」
騎士サーラ「いえ、構いません。何かありましたら、寝ている時でもご遠慮なくどうぞ」
魔道士イリアス「そう?悪いわね。それで本題だけど・・・」
剣聖ハードゥン「うむ。あの会食を提案してきた国だが、汚職が発覚してボロボロらしい」
騎士サーラ「これまた痛いタイミングですね・・・」
魔道士イリアス「そうなのよ。もう国民が大怒りで一触即発。でも、この政府をどうするかは国民が決めることだけど、ここで私たちが相手国と関係を築いておけば、もし政権がひっくり返ってもある程度は有効だから、今のところ中断の選択肢はないわ」
騎士サーラ「しかし、なおさら治安が悪いのではありませんか?」
魔道士イリアス「だから困ってるのよ。全く、どうしてこのタイミングで、オショクジケンでシュウマイなのよ!」
剣聖ハードゥン「イリアス君、それシャレか?」
騎士サーラ「・・・・・・」
魔道士イリアス「・・・とにかく、話の続きだけど、これじゃなおさらシェリーをガッチリ警護しなきゃいけないわ。その上、非公式に会談の要請まで来ててね」
騎士サーラ「非公式に?」
魔道士イリアス「何か表ざたになると困る話でもするんじゃない?しかも条件付きで、出席者は双方ともに護衛込みで3名だって」
騎士サーラ「・・・3名とは・・・。厳しいですね・・・」
魔道士イリアス「そうなのよ。そこで、以下の条件からメンバーを絞り込んで欲しいのね」
1.メンバーは3名
2.魔道士イリアスには護衛が1名以上必要
3.イリスのシェリーには護衛が2名以上必要
4.これは会談であるため、実務者が最低1人は必要
5.補佐役も最低1人必要。ただし、これは実務者とは別人であること
6.護衛と実務または補佐を兼任することは構わない
7.これは組み合わせの問題であり、順番は関係ない。したがって
例:「イリアス,サーラ」「サーラ,イリアス」この2つは同一である

・メンバー(カッコ内は行える能力)
イリアス(補佐)
サーラ(実務,補佐,護衛)
ハードゥン(実務,護衛)
シェイン(護衛)
シェリー(実務)
アマンダ(補佐)
騎士サーラ「これの組み合わせの数量を求めるのですね?」
魔道士イリアス「そういうこと。やってみて」

 さあ、適切なメンバー構成は見つかるのでありましょうか。

模範解答
 見ての通り、今回のは結構複雑です。実務と補佐が兼任できるようなら、普通に足し算で何とかなるのですが、さすがに補佐役、つまり「アドバイザー」とか「書記」とかを実務者が兼任するなど無理な話です。護衛は単に「もしもの時に戦う」ことが目的ですから、兼任できるのでしょう。
 無論、クエリの実装方法は十人十色、最終的にスマートに答えが出れば構わないのですが、ここでは「実務・補佐がそれぞれ1人ずつは必要」である点に着目します。つまり、実務者枠と補佐枠は事実上「固定」されているのであり、この性質を生かせば比較的容易に検討が行えるでしょう。ではまずテーブルより。
 左から順に、通し番号、名前、こなせる役職(ビット演算。1:実務、2:補佐、4:護衛)、その人に必要となる護衛人数としました。
CREATE TABLE mem(number INT , name VARCHAR(32) , title INT , def INT) ENGINE=HEAP;
INSERT INTO mem VALUES(1 << 0 , 'ilias' , 2 , 1) , 
(1 << 1 , 'sara' , 1 | 2 | 4 , 0) , (1 << 2 , 'harden' , 1 | 4 , 0) , 
(1 << 3 , 'shein' , 4 , 0) , (1 << 4 , 'shelley' , 1 , 2) , 
(1 << 5 , 'amanda' , 2 , 0);
 さて、本題はここからです。実務と補佐は兼任できないのですから、実務者を1つ目のエイリアス、補佐役を2つ目に固定してしまいます。つまり、3つ目には護衛など誰を置いても良いことになります。また、これで自動的に、実務または補佐のない組み合わせは排除されます。
SELECT COUNT(*) FROM 
(SELECT b.name AS 'business' , a.name AS 'assistant' , o.name AS 'other' 
FROM mem b , mem a , mem o 
WHERE b.title & 1 AND a.title & 2 AND 
BIT_COUNT(b.number | a.number | o.number) = 3 
GROUP BY b.number + a.number + o.number) m;

// Result
18
 実務者と補佐役を固定し、重複を排除するだけで18項目まで絞ることができました。しかし、これではシェリーさんが危険ですから、護衛を設定することにします。
SELECT b.name AS 'b' , a.name AS 'a' , o.name AS 'o' 
FROM mem b , mem a , mem o 
WHERE b.title & 1 AND a.title & 2 AND 
(b.title & 4 = 4) + (a.title & 4 = 4) + (o.title & 4 = 4) >= 
GREATEST(b.def , a.def , o.def) AND 
BIT_COUNT(b.number | a.number | o.number) = 3 
GROUP BY b.number + a.number + o.number;

// Result
b	a	o
harden	sara	ilias
sara	ilias	shein
harden	ilias	shein
harden	sara	shein
shelley	sara	harden
shelley	sara	shein
sara	amanda	ilias
harden	amanda	ilias
harden	amanda	sara
sara	amanda	shein
harden	amanda	shein
 すなわち、この11個が組み合わせであることになります。

騎士サーラ「では、メンバーはどうされますか?」
魔道士イリアス「そうねぇ・・・。もし私が入るなら、サーラは欲しいわね」
騎士サーラ「はっ」
魔道士イリアス「サーラがいれば頼もしいけど、サーラだけで護衛から何からするのは大変だから、シェリーも入れたいわね」
騎士サーラ「はい。シェリーさんですね」
魔道士イリアス「でも、いくらサーラが強いからって、もしもの時に護衛が1人じゃ不安だし・・・。老練なハードゥンも入れたいわね。補佐にアマンダも欲しいし。シェインにも警護してもらえるとありがたいわ」
騎士サーラ「・・・イリアスさん、結局全員ではありませんか」
魔道士イリアス「まあ、そうだけど・・・。もうこうなったら占いで決めるわよ。シェリー、タロットはアルカナ?」
イリスのシェリー「イリアスさん、そのシャレ2度目ですよ・・・」
魔道士イリアス「タロットはダメっていうのね。仕方ないわね・・・。こう見えて私はダイスが大好きなのよ。ってことでシェリー、サイを取ってください」
イリスのシェリー「・・・はい、どうぞ。こちらがサイコロジカルラインの資料になっております」
魔道士イリアス「そんなもの渡されたって分からないわよ!」

 このように、SQLは非公式会談にも欠かせない逸品なのです。
カテゴリ [開発魔法][社会問題][ゲーム開発] [トラックバック 0][コメント 0]
<- 前の記事を参照 次の記事を参照 ->

- Blog by yamicha.com -