アカウント名:
パスワード:
これ、ループじゃないですよね。
状態 k を関数 f(k) と評価して、関数の返り値 kintermediate を 相手の出方の予想関数に g(f(k)) と与えると 状態 k1 が得られて、f(k) - g(f(k)) が心地よく小さくなるまでこれを n 回にわたって再帰的に呼ぶと理想の状態に達するわけですよね? でも、この状態 kn って常に kn-1 との差分方程式の形でしか表現できないので、状態 k0 から kn までのすべての状態を保持しないといけなくないですか?
純粋なループなら g(f(k)) の一般項なので、kn-1 を捨てながらイテレーションを続ければ平衡状態まで思考を続けられるはず。ところがこれは再帰なので、"計算"を続けるといずれかの地点でスタック領域が埋まって、関数の最終行で例外が飛び、思考が打ち切られて行動を決定せざるを得なくなるんじゃないでしょうか。
で、リンク先を読むと一般人は n = 0~1 でそれが発生するよ、と書いてありますね。なるほど。
相手が取る手は最終的に一つだから、この手を取ってくる(から対応する手を取ろう)と考えた時点で破棄してOK。knやkn-1は常に確定している。ただf(k)やg(f(k))には再帰が含まれているかもしれないし、一般人はf(k)やg(f(k))をn=0~1ぐらいしか計算しない。で最適化としてせいぜいnを2~3に設定すれば充分だろうということになるんじゃない?メモリは破棄できても計算時間(やそのリソース)はかかるんだから。
ゲーム木の探索と似たようなもんじゃないのか単純なループにはなかなかならないと思うんだけど
そこはfだのgだのでしょ。
再帰だから=>差分方程式のでしか表現できないから => 状態 k0 から kn までのすべての状態を保持しないといけない、
のロジックがよくわからない。
多分、末尾再帰で書けるよね(ループにできる)。
>ロジックがよくわからない。
このように人間のロジックとは支離滅裂なので、相手の思考を読もうとしても意味がないという実例を示しているのでしょう。
定式化の方針次第じゃないかな。
1. 自分がグーチョキパーをそれぞれ1/3の確率で出すとする(数値をとりあえず適当に決める)2. 相手がそれぞれの手を読んだとすると、自分が出すべき手は…3. 2を何かしらの収束を迎えるまで繰り返す
ならループになる。
1. 自分がグーチョキパーを出す確率をp1, p2, p3とする2. 相手が自分の手を読んでる確率を…
からスタートすると、繰り返し毎に数式が複雑になって行く。
> これ、ループじゃないですよね。
ループと再帰が可換であることは理解してますか?
状態 k0 から kn の列 {k_i | i=0...n } をパラメータとして,fという関数が f({k_i}) を評価すると考えればループとなります
もう少しプログラマの人にもわかるように説明すると- {k_j | j=0...(i-1) } の情報をスタックに持たせて,サブルーチン f に k_iだけ引数で与えれば再帰処理- サブルーチン f に {k_i | i=0...n }を全部与えるなら,ループ処理となります
つまり両者は,計算機上での処理の実行方法の違いでしかありません.実装方法の違いとも言えます.そしてやってる計算・処理は同じです.
つまり「ループじゃなくて再帰」と言う指摘は「ループ処理は再帰でも処理できる(実装できる)」という言ってるに過ぎません.
そりゃそうです.可換ですから.
なんとなーく昔そんなことを聞いたかなとは思ってました。ただ、実際には「相手がこう出てくるはずだから、それに対して……」処理は人の頭ではループ処理にはなってなくて、常に途中の状態も評価しながら最終行でオブジェクトが増えていっていると思うんですよね。その辺が「ループじゃなくて再帰」の含意でした。
人の頭にはメモリがないからオブジェクトを参照する度にコンストラクタも走るし渡されたオブジェクトのコンストラクタも走る、だから計算量が爆発する、みたいな考え方の方が正確だったかな。
> 人の頭にはメモリがないからオブジェクトを参照する度にコンストラクタも走るし渡されたオブジェクトのコンストラクタも走る、だから計算量が爆発する、みたいな考え方の方が正確だったかな。
神経細胞の巨大なネットワークである脳の中で「コンストラクタが走る」みたいな考え方のどこが正確なんですか?
>ループと再帰が可換であることは理解してますか?
全く同じことを思って、このコメントがあって安心したんだけど、モデレーションおかしくない?スラド民は情報科学の学部レベルの知識もないのかな。。。
無い人が多いでしょうね。ここ日本では、学歴不問でソフトウェアエンジニアとかITエンジニアになれるから。
学歴なくてもループと再帰が相互変換可能ってのはすぐ思いつくと思うんだけども…
https://ja.wikipedia.org/wiki/%E6%9C%AB%E5%B0%BE%E5%86%8D%E5%B8%B0 [wikipedia.org]末尾呼出し最適化されたんじゃ...
gccで-O2オプションを付けると末尾再帰がループに変換される。つまりループと再帰は同じものなんだよ。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
にわかな奴ほど語りたがる -- あるハッカー
ループじゃなくて再帰 (スコア:5, 興味深い)
これ、ループじゃないですよね。
状態 k を関数 f(k) と評価して、関数の返り値 kintermediate を 相手の出方の予想関数に g(f(k)) と与えると 状態 k1 が得られて、f(k) - g(f(k)) が心地よく小さくなるまでこれを n 回にわたって再帰的に呼ぶと理想の状態に達するわけですよね? でも、この状態 kn って常に kn-1 との差分方程式の形でしか表現できないので、状態 k0 から kn までのすべての状態を保持しないといけなくないですか?
純粋なループなら g(f(k)) の一般項なので、kn-1 を捨てながらイテレーションを続ければ平衡状態まで思考を続けられるはず。ところがこれは再帰なので、"計算"を続けるといずれかの地点でスタック領域が埋まって、関数の最終行で例外が飛び、思考が打ち切られて行動を決定せざるを得なくなるんじゃないでしょうか。
で、リンク先を読むと一般人は n = 0~1 でそれが発生するよ、と書いてありますね。なるほど。
Re: (スコア:0)
相手が取る手は最終的に一つだから、この手を取ってくる(から対応する手を取ろう)と考えた時点で破棄してOK。
knやkn-1は常に確定している。
ただf(k)やg(f(k))には再帰が含まれているかもしれないし、一般人はf(k)やg(f(k))をn=0~1ぐらいしか計算しない。
で最適化としてせいぜいnを2~3に設定すれば充分だろうということになるんじゃない?
メモリは破棄できても計算時間(やそのリソース)はかかるんだから。
Re: (スコア:0)
ゲーム木の探索と似たようなもんじゃないのか
単純なループにはなかなかならないと思うんだけど
Re: (スコア:0)
そこはfだのgだのでしょ。
Re: (スコア:0)
再帰だから=>差分方程式のでしか表現できないから => 状態 k0 から kn までのすべての状態を保持しないといけない、
のロジックがよくわからない。
Re:ループじゃなくて再帰 (スコア:1)
多分、末尾再帰で書けるよね(ループにできる)。
Re: (スコア:0)
>ロジックがよくわからない。
このように人間のロジックとは支離滅裂なので、相手の思考を読もうとしても意味がないという実例を示しているのでしょう。
Re: (スコア:0)
定式化の方針次第じゃないかな。
1. 自分がグーチョキパーをそれぞれ1/3の確率で出すとする(数値をとりあえず適当に決める)
2. 相手がそれぞれの手を読んだとすると、自分が出すべき手は…
3. 2を何かしらの収束を迎えるまで繰り返す
ならループになる。
1. 自分がグーチョキパーを出す確率をp1, p2, p3とする
2. 相手が自分の手を読んでる確率を…
からスタートすると、繰り返し毎に数式が複雑になって行く。
Re: (スコア:0)
> これ、ループじゃないですよね。
ループと再帰が可換であることは理解してますか?
状態 k0 から kn の列 {k_i | i=0...n } をパラメータとして,fという関数が f({k_i}) を評価すると考えればループとなります
もう少しプログラマの人にもわかるように説明すると
- {k_j | j=0...(i-1) } の情報をスタックに持たせて,サブルーチン f に k_iだけ引数で与えれば再帰処理
- サブルーチン f に {k_i | i=0...n }を全部与えるなら,ループ処理
となります
つまり両者は,計算機上での処理の実行方法の違いでしかありません.実装方法の違いとも言えます.
そしてやってる計算・処理は同じです.
つまり「ループじゃなくて再帰」と言う指摘は
「ループ処理は再帰でも処理できる(実装できる)」という言ってるに過ぎません.
そりゃそうです.可換ですから.
Re:ループじゃなくて再帰 (スコア:2)
ループと再帰が可換であることは理解してますか?
なんとなーく昔そんなことを聞いたかなとは思ってました。ただ、実際には「相手がこう出てくるはずだから、それに対して……」処理は人の頭ではループ処理にはなってなくて、常に途中の状態も評価しながら最終行でオブジェクトが増えていっていると思うんですよね。その辺が「ループじゃなくて再帰」の含意でした。
人の頭にはメモリがないからオブジェクトを参照する度にコンストラクタも走るし渡されたオブジェクトのコンストラクタも走る、だから計算量が爆発する、みたいな考え方の方が正確だったかな。
Re: (スコア:0)
> 人の頭にはメモリがないからオブジェクトを参照する度にコンストラクタも走るし渡されたオブジェクトのコンストラクタも走る、だから計算量が爆発する、みたいな考え方の方が正確だったかな。
神経細胞の巨大なネットワークである脳の中で「コンストラクタが走る」みたいな考え方のどこが正確なんですか?
Re: (スコア:0)
>ループと再帰が可換であることは理解してますか?
全く同じことを思って、このコメントがあって安心したんだけど、モデレーションおかしくない?
スラド民は情報科学の学部レベルの知識もないのかな。。。
Re:ループじゃなくて再帰 (スコア:1)
無い人が多いでしょうね。
ここ日本では、学歴不問でソフトウェアエンジニアとかITエンジニアになれるから。
Re: (スコア:0)
学歴なくてもループと再帰が相互変換可能ってのはすぐ思いつくと思うんだけども…
Re: (スコア:0)
https://ja.wikipedia.org/wiki/%E6%9C%AB%E5%B0%BE%E5%86%8D%E5%B8%B0 [wikipedia.org]
末尾呼出し最適化されたんじゃ...
Re: (スコア:0)
gccで-O2オプションを付けると末尾再帰がループに変換される。
つまりループと再帰は同じものなんだよ。