Entries

HSPでも再帰がしたい!

○概要
 再帰。プログラミングの教本にはチラッとだけ触れられて終わるのが通例ですが、まったくとんでもない話です。真面目にプログラミングしだすと避けては通れないと思うのですが、大抵の教本には階乗の計算でしか出てきません。あれでは、教本を読んだ初心者が、「ハッ、再帰っつても大したことないんだな、ループで十分じゃん」などという誤解を……いや、むしろ正しい?
 と、ともかく、再帰は面倒な処理を簡単に書くためには必要不可欠なものなのです。……が。
 ことHSPではそれがとにかく面倒だったという話。


○まずは定番の階乗計算をば
 C言語ではこんな感じに書くコードが、

int fact(int n){
if(n == 0)
return 1;
return fact(n - 1) * n;
}

HSPではこんな感じに書けます。まあこれぐらいは、教本でおなじみですよね?

#defcfunc fact int n
if n=0 :return 1
return fact(n-1)*n



○次に探索を……あれ?
 再帰と言えば探索。というわけで、POJのLake Counting問題を解かせてみます。要するに池の領域の数が分かればいいので、深さ優先探索(DFS)でガリガリ探索すれば解けます。
 まずはC++。蟻本丸写しでごめんなさい。

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

#define MAX_N 100
#define MAX_M 100

// 入力
int N,M;
char field[MAX_N][MAX_M + 1]; //庭

// 現在位置(x,y)
void dfs(int x, int y) {
// 今いるところを.に置き換える
field[x][y] = '.';

// 移動する8方向をループ
for (int dx = -1; dx <= 1; dx++) {
for (int dy = -1; dy <= 1; dy++) {
// x方向にdx y方向にdy 移動した場所を(nx, ny)とする
int nx = x + dx, ny = y + dy;

// nxとnyが庭の範囲内かをどうかとfield[nx][ny]が水溜りかどうかを判定
if (0 <= nx && nx < N && 0 <= ny && ny < M && field[nx][ny] == 'W') dfs(nx, ny);
}
}
return ;
}

void solve() {
int res = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (field[i][j] == 'W') {
// Wが残っているならそこからdfsをはじめる
dfs(i, j);
res++;
}
}
}
printf("%d\n", res);
}

int main() {
string tmp;

ifstream fin("map.txt");

// 入力サイズを表示
fin >> N >> M;

// マップデータを入力
for (int i = 0; i < N; i++) {
fin >> tmp;
for (int j = 0; j < M; j++) {
field[i][j] = tmp[j];
}
}

solve();
return 0;
}
 次にHSP。これも普通にDFSするコードを書けば解決なはず……ですが。

#module
#deffunc dfs int x,int y
field@(x,y)="."
for dx,-1,2
for dy,-1,2
nx=x+dx :ny=y+dy
if (limit(nx,0,N@-1)=nx)&(limit(ny,0,M@-1)=ny) {
if field@(nx,ny)="W" :dfs nx,ny
}
next
next
return
#global

notesel buf :noteload "map_.txt"

noteget tmp,0
split tmp," ",tmp_
N=int(tmp_.0) :M=int(tmp_.1)

sdim field,N,M
for i,0,N
noteget tmp,i+1
for j,0,M
field(i,j)=strmid(tmp,j,1)
next
next

res=0
for i,0,N
for j,0,M
if field(i,j)="W" {
dfs i,j
res+
}
next
next
mes res
stop
 ……実は、このままではダメです。具体的には、以下のデータを食わせると、「1」ではなく「3」と返します。

3 3
W.W
.W.
W.W


 どう考えてもどこか間違えているわけなのですがそれはどこか?
 すぐに分かった人は、きっと一度は自分で書いてみて試行錯誤したことがあるのでしょう。
 分からない人は、以下の文章をしっかり読んでおきましょう。


○なぜこんなことが起きるのか?
 一言で言うと、HSPにおけるモジュール機能のカスな仕様のせいです。

 ……具体的に説明しましょう。C言語などの普通の手続き型言語における関数の場合、関数内で同じ関数を呼び出しても、内部で宣言した変数が勝手に書き換わる、なんていう超常現象は起きません(static宣言されていない限り)。これは、各々の変数がスタックで管理されているからです。関数が一旦returnされる度に内部の変数が破棄され、スタックが戻されることにより、呼び出す前の変数の内容は維持されます。
 上のコードで言えば、「dx = 1, dy = -1」の状態の時に、(内部で「dx」「dy」という変数をいじる)dfs関数を呼び出したとしても、呼び出しから帰ってきた時に「dx」と「dy」の内容は維持されています。
(もちろん「dx」や「dy」がstatic変数 or グローバル変数なら話は別なのですが)

 一方HSPの場合、本質的に全ての変数がグローバル変数です。
 ……なに? 「モジュール機能があるじゃないか」って? ご冗談を。
 あれはモジュールごとに名前空間を用意して分けているだけです。
 この辺りにはヘルプ(hspprog.htm)にも長々と書かれていますが、要約するとこういうことです。↓

通常の変数→「test」または「test@」
モジュール内の変数→「test@モジュール名」
通常命令・関数→「command」と「command@hsp」(前者は後者のマクロによるdefine名)
モジュール命令・関数→「command@モジュール名」

 ここで重要なのは、モジュール内の変数は、スタックを積む実装ではないということです。ただ単に、「@モジュール名」という尾ひれが付いた変数を宣言しているだけです。この状態で再帰呼び出しをすると、内部変数が再帰毎に書き換わる愉快な現象が起きます。
 上のコードで言えば、

for dx,-1,2
for dy,-1,2

における「dx」「dy」は実は「dx@モジュール名」「dy@モジュール名」で、グローバル変数扱いだから再帰の度に上書きされてしまうということになります。「そんなオカルトありえません?
   俺が言いたいよ!!!


 ……話を戻します。さすがにおにたまさんも鬼(アホ)じゃないのか、変数をreturn時に破棄させるようにする(=ローカル変数)方法も用意してくれました。具体的には、関数or命令宣言部分で、ローカル変数にしたいものを「local 変数名」と書くだけです(ヘルプにもちゃんと書いています)。
 上のコードで言えば、「#deffunc dfs int x,int y」の後に「,local dx,local dy」と付け足せば大丈夫です。
 ただし、おにたまさん曰く、

ローカル変数を多用する ことは、実行効率や速度を求める場面では、初期化のためのオーバーヘッドが あることを留意してください。

だそうです☆ミ
 …………なんでローカル変数がオプション扱いなんだよアホンダレ! 当然配列とかは自力でスタックを実装する必要があるよ! ……ダルい。


○「てか、ゲームに再帰とかあんまし使わなくね?」
 ……使いますよ? 何を言っているんですか?

ミニマックス法やアルファベータ法など
⇒将棋や囲碁、オセロなどのプログラムでおなじみ。再帰だとかなり簡単に書けます。
・経路探索
⇒盤面・マップなどで、道のりや移動範囲を計算したりするのに必須。
ダイクストラ法? あれの元ネタは幅優先探索(BFS)なんだぜ?
・特定の条件を満たしかつ隣接する領域を調べる
⇒要するに、絵における塗りつぶしとかパズルゲーにおける連鎖判定とか。
・パズルゲーにおける探索
⇒前述したミニマックス法とかに近いかも。「8クイーン」とか「15パズル」とかが有名
・ハノイの塔

などなど、いわゆる「思考ルーチン」(AI)部分を作るのに大活躍します。それなのに、どうしてその辺がおざなりになってしまったのか……。慢心、環境の違い。


○補足
 これ以上憤っても仕方がないので、以下、おまけ。
 今回の記事タイトルは、当然某中二病アニメからもじったものです。諸事情によりまだアニメは観ていないのですが、なんとなくピッタリだと思ったので。と言うか前から思っていたのですが、
プログラミング(に限らずコンピュータ系のあれこれ)って"中二"っぽくね?
 ハイパースレッディングテクノロジーヘテロジニアスマルチコアなどのハードウェア系から、ウォーターフォールモデル分割統治法などのソフトウェア系ゼロデイアタックディレクトリトラバーサルなどのネットワーク系など、中二病患者が夢見がちなハッカー像は数知れず。(映画などで)画面に大量のコマンドがずらーーーっと並ぶ表示がカッコいいと一度でも思わなかった男子はいません!

 そうでなくても、WindowsのAPIとか(特にGUI関係)、boost::spiritとか、実に複雑怪奇な代物がゴロゴロしているのがこの世界。某百科事典で「闇の言語」とか言われているアレの場合、

#include <iostream>

template<char O, bool =O == 'h'? '-' :O == 'w'? '=' :0>class _;

template<char O>std::ostream&operator<<(std::ostream&lhs,_<O,0>*) {
return lhs << O;
}

template<char O>std::ostream&operator<<(std::ostream&lhs, _<(O), 'o'>*) {
return lhs<<(char)(O - '!' + '.' - '-' );
}

template<> std::ostream&operator<<<'~'>(std::ostream& m9,_<'~', 'o'>*) {
return m9<<('m');
}

int main(int orz=3) {
std::cout<<(_<'h'>*)0<<(_<'e'>*)0<<(_<'l'>*)0<<(_<'l'>*)0<<(_<'o'>*)0<<(_<'w',0>*)0<<(_<' '>*)0<<(_<'w'>*)0<<(_<'o'>*)0<<(_<'r'>*)0<<(_<'l'>*)0<<(_<'d'>*)0<<(_<'!'>*)0<<std::endl;
return 0;
}
なんていうキテレツなコードが普通に実行できたりするのだ(アンサイクロペディアより引用)。

 色々な意味で中二、かつ実用的。六花ちゃんにはぜひプログラミングの道を歩んでもらいたいものである(おい)


2013/07/21追記:
一部記述を修正。
関連記事
スポンサーサイト
この記事にトラックバックする(FC2ブログユーザー)
http://ysrken.blog.fc2.com/tb.php/50-9939a31c

トラックバック

コメント

[C54]

スタック領域を使用しない引数はぜひサブルーチンの方に欲しかったですね。
というよりかは、deffuncがグローバル空間で使いにくすぎるのでなんとかなってほしいです。
なんで関数定義をすり抜けて内部を実行してしまうのか…
  • 2013-06-28 11:19
  • ht.ask
  • URL
  • 編集

[C55] Re:

> deffuncがグローバル空間で使いにくすぎる
「全変数がグローバル空間」というのはどう考えてもトラップですよね……。
#moduleに入れても全く安心できないところがまた酷いw
  • 2013-06-29 02:18
  • YSR
  • URL
  • 編集

[C56]

HSPの変数は基本的に「グローバル」というより静的/staticなんですよね
#module の中の変数はグローバル変数ではなく、「静的なローカル変数」とよぶべきものです

>初期化のためのオーバーヘッド
というのは、具体的には「local 指定の変数を作るためのコスト」を指しているので、
(静的変数だったら最初にしか作らなくていいのでかからない)
その多寡はともかく、他の言語でも必然的にかかっているはずのコストです

[C57]

>静的なローカル変数
C言語的な意味でなら……まあstaticと言えますね。
HSPの場合、どちらかと言えばnamespaceで区切っているような気がしますが。
>他の言語でも必然的にかかっているはずのコストです
まあそれはそうでしょうね。使い勝手が糞なものを直すのに更に計算コストがかかるという事実に苛立っていたんでしょうw 修正しておきます。
  • 2013-07-21 14:11
  • YSR
  • URL
  • 編集

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

Appendix

プロフィール

YSR

Author:YSR
「YSR」「YSRKEN」「◆YSRKENkO6Y(~2013/08/25)」「◆YSRKEN.ceVZZ(2013/08/26~)」として活動しています。
プログラミングと艦これが趣味です。
プロフ画像はCrystalDiskInfoの水晶雫ちゃんです。
主な創作物についてはhttp://ysrken.blog.fc2.com/blog-entry-76.htmlをご覧ください。

カレンダー(月別)

08 ≪│2017/09│≫ 10
- - - - - 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

全記事表示リンク

全ての記事を表示する

QRコード

QR

総アクセス数

アクセス数

現在の閲覧者数: