なあ、再帰関数好きな人いる？パート3 [転載禁止]©2ch.net

なあ、再帰関数好きな人いる？パート3 [転載禁止]©2ch.net (914ﾚｽ)
上下前次1-新
抽出解除必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞あぼーん

364(2): 2015/12/27(日)09:33 ID:Zmrinoji(1/40) AAS
分かったことは
・再帰をただ単にループに直すと却って遅くなる
・最適化を施せばループのほうが速くなるが、10000倍速くなるなんてことはない
の2点でおっけい？

367: 2015/12/27(日)10:24 ID:Zmrinoji(2/40) AAS
>>366
昨日から昨晩に掛けてのやり取りを知らないのか？
俺はそのやり取りから、>>364が分かった事の全てであるって発言しただけなんだけど。

371(1): 2015/12/27(日)11:22 ID:Zmrinoji(3/40) AAS
>>368
お前の中ではそうなんだろうな。そんな事より現実を見ろよ。

大本の彼らの主張は「クイックソートをお題にした場合に於いて再帰はループに比べて何万倍も差がでる(>>219)」
俺らの主張は「そんなに差がでることは理論的にありえない(>>286)」
であって、
ループのほうが再帰より「僅かでも」速いかどうか(>>352-353)なんざ元々議論していない。

クイックソートをやる上で比較にならないほど再帰のほうが遅くなるというならソースを出せや

373(2): 2015/12/27(日)11:23 ID:Zmrinoji(4/40) AAS
>>370
>>325

375(1): 2015/12/27(日)11:32 ID:Zmrinoji(5/40) AAS
>>374
>>260

定数オーダーの空間計算量で計算が出来ないなら、原理的に余分なメモリ操作は避けられない。
それはループでも一緒。

380(1): 2015/12/27(日)12:27 ID:Zmrinoji(6/40) AAS
>>377
ほい、最適化しなければループのほうが遅い証拠。
画像ﾘﾝｸ[php]:www.fastpic.jp

382(1): 2015/12/27(日)12:35 ID:Zmrinoji(7/40) AAS
>>378
Pen4のデータシートの値を元にするなら
ループのコストと再帰のコストは約2.5〜3clockくらいの差になると思う。

今時のCPUならもっと差は縮まるだろうし、実際に測った訳じゃないけど
だいたいそのくらいになる筈。

383: 2015/12/27(日)12:38 ID:Zmrinoji(8/40) AAS
>>381
最適化が無くてもループの方が「僅かでも」速いって言い張るお前に
そうじゃない場合もあるって言ったのが>>373
で、それに対しお前はネイティブコードで比較しろっつーから
「最適化無しのネイティブコードで」比較したんだが。

一体お前は何を求めてるんだ？

385(1): 2015/12/27(日)12:42 ID:Zmrinoji(9/40) AAS
>>384
ループ以外の本質的な処理に100clock掛かるとすれば、
数％の差だけどループより再帰のが遅くなるって意見は正しいねって話さね

381については了解

402(2): 2015/12/27(日)17:01 ID:Zmrinoji(10/40) AAS
>>399
ねぇねぇ
そのループで実装されてる>>398のコードでも
自前でスタック管理してる訳じゃ無い。
とすると、>>379に対する突っ込みとしては>>388変じゃない？

405(2): 2015/12/27(日)17:04 ID:Zmrinoji(11/40) AAS
>>403
ほう、つまり君はただのループをスタック管理と解釈する訳だね？

407: 2015/12/27(日)17:07 ID:Zmrinoji(12/40) AAS
>>406
確かに。
>>256から数えて、1日半で150も伸びてる。

411(1): 2015/12/27(日)17:26 ID:Zmrinoji(13/40) AAS
>>408
ふーむ。

複雑な再帰構造を持つ場合、例えば再帰下降構文解析器みたいに複雑な相互再帰をする場合には
クイックソートの時のように簡単に再帰をループで置き換えることは出来ない。
そして一般に再帰をループで置き換えるならスタックが必要で、
込み入った再帰をスタックを使ってでもループに置き換える奴は居ないだろう。
現に赤黒木をスタック管理をしてでも強引にループで書き直すようなアホは居ないんじゃないの？
というのが>>379に関するこっちの解釈。
それに対し、いやいや赤黒木はループで実装してるんだぜ！ってのが>>388の俺の解釈。
話が噛み合って無くね？ってのが>>402
省1

413(1): 2015/12/27(日)17:29 ID:Zmrinoji(14/40) AAS
>>410
そもそもクイックソートは分割統治法の典型例だからなぁ。
自分を2度呼び出す時点で末尾再帰的じゃないし
ループらしい書き方をするとクイックソートとは呼べないシロモノになると思う

414: 2015/12/27(日)17:30 ID:Zmrinoji(15/40) AAS
あ、勿論クイックソートをもっと単純なループで書き直せるってんなら歓迎するよ！

416(1): 2015/12/27(日)17:33 ID:Zmrinoji(16/40) AAS
>>412
複数の解釈の仕方がありうるなら、
オレオレ解釈を元に相手をこき下ろす前にやることがあるだろうと

417(1): 2015/12/27(日)17:34 ID:Zmrinoji(17/40) AAS
>>415
・・・・・・それは依然として再帰関数と呼ぶのでは？

420(1): 2015/12/27(日)17:42 ID:Zmrinoji(18/40) AAS
>>418
いや、君が>>403で言ったのは「スタック管理」の解釈の違いだろ？
「赤黒木が再帰で書かれてる」等とは一言も言ってない>>379を読んだ君が>>408みたいな解釈をして、
人のことをテロリスト呼ばわりするのってどうなの？

421(1): 2015/12/27(日)17:43 ID:Zmrinoji(19/40) AAS
>>419
外部ﾘﾝｸ:ja.wikipedia.org
「再帰とは、あるものについて記述する際に、記述しているものそれ自身への参照が、その記述中にあらわれることをいう。」

ループを含む関数は再帰関数にはなれないの？
そんなことはないと思うんだけど。

424(1): 2015/12/27(日)17:54 ID:Zmrinoji(20/40) AAS
>>422
より正確には、「再帰全てをノーコストで末尾再帰にできるわけではなく」かな。
関数がファーストクラスならCPSに変換すれば末尾再帰の形にはなる。
・・・・・・ヒープガリゴリ使うし、スタックを自前で持つのと変わらんけど。

428(1): 2015/12/27(日)18:01 ID:Zmrinoji(21/40) AAS
>>425
確率が1を超えてるとか、幼稚園に迷い込んだ気分だよ。

「赤黒木の操作を自前でスタック管理するアホはいない」と言っている以上、
赤黒木の操作は、スタックなんてものをそもそも自分で触らないようなやり方、
つまり再帰か、又は上手なループで実装されているって話だろ？
フィボナッチ数を計算する関数をスタックを使わずに書いたって言った時、君は再帰の方しか思い浮かべられないのかい？
もしかして自閉症患者かい？

429(4): 2015/12/27(日)18:04 ID:Zmrinoji(22/40) AAS
>>427
それじゃぁ各ノードに可変個の子要素を持つ多分木を列挙するコードは
どうやって書くつもり？
for (auto it : children) {
　if (it->is_leaf()) {
printf("%d ", it->value);
} else {
it->print_values();
}
}

432(1): 2015/12/27(日)18:18 ID:Zmrinoji(23/40) AAS
>>430
日本語って難しいよね。分かる分かる。
>>389の解釈は、
再帰でも書けるところをループで書いたんだ。へぇ。バグってなくて良かったね。ご苦労さん。
じゃないの？
>>379が再帰を仮定しているかどうかとは別問題。

俺も自閉症患者だけどね。自分に謝るのって変な感じがするよ。

433: 2015/12/27(日)18:18 ID:Zmrinoji(24/40) AAS
>>431
どっちでも良いけど、どっちかしか「使ってはならない」というローカルルールの元ではどう書くの？

434(1): 2015/12/27(日)18:47 ID:Zmrinoji(25/40) AAS
>>431
まだ出来ないの？
>>429に7行で書いたような、こんなコードが走ります的な切れ端で十分伝わるんだよ？

437(1): 2015/12/27(日)19:08 ID:Zmrinoji(26/40) AAS
>>435
残念。

>>436
ループを含む関数が再帰関数になれないのであれば、
>>429のような書き方は認めないって事だよね？
君ならどう書くの？って聞いただけなのになんでそんな反応になるのかね？

441(1): 2015/12/27(日)19:14 ID:Zmrinoji(27/40) AAS
>>438
大本の論旨としては、人のことをテロリスト呼ばわりするのってどうなん？って事なんだけど。

ループと再帰の優劣をつけるなんてどこから出てきた？

447(1): 2015/12/27(日)19:40 ID:Zmrinoji(28/40) AAS
どうでも良いけど、再帰がテロ行為になるなんて初耳だなぁ

# 今日の夕飯はすき焼きでした

449: 2015/12/27(日)19:49 ID:Zmrinoji(29/40) AAS
>>448
誰がそこまで特殊でオンボロな例を挙げろと

ちなみにテロリストの定義はテロリズムを奉ずる人で、
テロリズムの定義は
外部ﾘﾝｸ[88]:ja.wikipedia.org
「住民を威嚇する、または政府や国際組織を強制する、あるいは行動を自制させる目的で、
市民や非戦闘員に対して殺害または重大な身体的危害を引き起こす事を意図したあらゆる行動」
だそうですよ。

あと自動車の場合、バシバシ轢き殺すなんて事態にはならず、単にエンストするだけだと思うの。
フェイルセーフって知ってるよね？

450(2): 2015/12/27(日)19:55 ID:Zmrinoji(30/40) AAS
>>440
> 俺は畑を耕していただけなんだ。そしたら ID:Zmrinoji こいつが
> 機関銃もって脅してきたんだ。おらはイモが食いたいだけだ。再帰使うやつはテロリストだ。
俺の知ってる事実と違うね。

俺は今日は364から話を始めた。そこにID:9aquywWvが388から割り込んできて、
人のことをやれテロリストだやれ機関銃をもって脅してきただ喚いてるの。

453: 2015/12/27(日)20:07 ID:Zmrinoji(31/40) AAS
そうやって正義の為にループを仕込むんだね？
よく分かったよ！

ちなみにバッファオーバーフローの攻撃手法としては再帰は下の下だからな。
getsなんかを使った方がよっぽど手っ取り早い上に任意コード実行まで出来る。

455(1): 2015/12/27(日)20:10 ID:Zmrinoji(32/40) AAS
>>454
知ってるよ？
でも再帰使うやつはテロリスト発言で敵を増やしてないかい？

457(2): 2015/12/27(日)20:15 ID:Zmrinoji(33/40) AAS
>>456
文脈をよく読もう。
364から始まる再帰とループに関する話に混ざった379に君が割り込んでるね？

462: 2015/12/27(日)20:18 ID:Zmrinoji(34/40) AAS
>>458
そうだね、偉大だね。
スプンタ・マンユに祈りを！(宗教ちげぇ)

463(1): 2015/12/27(日)20:25 ID:Zmrinoji(35/40) AAS
>>460
いわゆる暇人という奴では。

>>461
木構造って知ってる？

あと、俺はそのレス(>>379)にその返し(>>388)って変じゃね？って言っただけで、
それに対して君が「スタックの管理とは」なんて話を始めるから(>>403)
そのコード(>>398)の何処にスタックなんて使われてるんですか―って訊いて(>>405)
それに対してまだ答えが返ってきてないんだけど。
君はあれかな、都合の悪い質問は見なかったことにする人なのかな。

465(1): 2015/12/27(日)20:29 ID:Zmrinoji(36/40) AAS
>>464
暇潰しに最適なので大好きです

467(1): 2015/12/27(日)20:32 ID:Zmrinoji(37/40) AAS
>>466
それで、人のことをテロリスト呼ばわりするのってどうなん？

469(2): 2015/12/27(日)20:34 ID:Zmrinoji(38/40) AAS
>>469
必死乙

471(1): 2015/12/27(日)20:37 ID:Zmrinoji(39/40) AAS
>>470
つまり、>>469で示したように再帰を使う俺はどっち？

473: 2015/12/27(日)20:40 ID:Zmrinoji(40/40) AAS
>>472
笑ったから良いやｗｗ

上下前次1-新書関写板覧索設栞歴

ｽﾚ情報赤ﾚｽ抽出画像ﾚｽ抽出歴の未読ｽﾚ AAｻﾑﾈｲﾙ

ぬこの手ぬこTOP 1.101s*