15/11/28 18:51:38.86 Rc2MJzM/.net
なあ、再帰関数好きな人いる？
2:デフォルトの名無しさん
15/11/28 18:55:04.46 SbMJmhTc.net
わくわく
3:デフォルトの名無しさん
15/11/28 19:23:33.42 mf/sQ31/.net
嫌いな奴なんて見たことない
4:デフォルトの名無しさん
15/11/28 19:30:25.39 R0seH/nX.net
ループで書けるものはループで書く。
再帰使うのは仕方ない場合だけ。
5:デフォルトの名無しさん
15/11/28 19:53:36.58 R0seH/nX.net
スタック的なメモリ確保が必要かどうかがループと再帰を使い分ける分岐点じゃね。
末尾再帰最適化とかは本末転倒なイメージ。
6:デフォルトの名無しさん
15/11/28 20:05:09.47 N2qWmI2+.net
前スレ
なあ、再帰関数好きな人いる？ パート2
ｽﾚﾘﾝｸ(tech板)
7:デフォルトの名無しさん
15/11/28 20:30:33.91 Tq6BVuZs.net
>>5
ループ実装を隠せるのは大きいよ
抽象化はプログラミング言語の進化のベクトルと一致するからね
8:デフォルトの名無しさん
15/11/28 20:39:12.74 R0seH/nX.net
ループより再帰のほうが抽象度が高いと言っている？
そこは俺にはよくわからん。
俺的にはプログラムには必要最小限の機能を使うべきで、
本質的にループより再帰のほうが強力なのだから
可能な限りループを使うべきと思ってる。
もちろん再帰をループにするためにスタックを自前で用意するといったことでは本末転倒だが。
9:デフォルトの名無しさん
15/11/28 20:41:49.23 R0seH/nX.net
ツリーの巡回は再帰を使ったほうがいいだろう。
リストの巡回はループでいいんじゃね？
10:デフォルトの名無しさん
15/11/28 20:48:22.48 Tq6BVuZs.net
>>8
> 俺的にはプログラムには必要最小限の機能を使うべき
そういうのはコンパイラなりインタプリタなりが頑張るべきところだと思うね
人間はより抽象化された対象を扱うようにするのがモダンなプログラミング言語の方向だし
11:デフォルトの名無しさん
15/11/28 20:52:46.74 fFSPKhVt.net
抽象的なスレだな
12:デフォルトの名無しさん
15/11/28 20:58:39.47 R0seH/nX.net
うーん。必要な抽象化は歓迎するが無駄な抽象化は歓迎しないというか。
この例は再帰とは関係ないけどJavaのファイル入出力なんかは
結構複雑な作りになってて無駄な抽象化なんじゃねーのとか思ってしまう。
まあ、俺個人の感想だが。
13:デフォルトの名無しさん
15/11/28 21:12:02.73 M/Wigktg.net
アルゴリズムが再帰なら普通に再帰で書く
スタックサイズ制限とかあるなら別だけど
14:デフォルトの名無しさん
15/11/28 21:30:44.25 10sD81C/.net
アルゴリズムが再帰であってもクイックソートなど
再帰のままじゃあ使い物にならんものがいくらでも。
15:デフォルトの名無しさん
15/11/28 21:32:52.35 R0seH/nX.net
スマンｗ クイックソートは再帰で書くわｗ
16:デフォルトの名無しさん
15/11/28 21:34:06.03 fFSPKhVt.net
書いたことないくせにｗ
17:デフォルトの名無しさん
15/11/28 21:52:35.40 R0seH/nX.net
書いたことはあるけど１０年以上昔の話だな。
これは拾い物だけどクイックソートなんてこれだけのことだろ。
qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
18:デフォルトの名無しさん
15/11/28 22:09:37.77 fFSPKhVt.net
リストの巡回はループでいいんじゃないんかｗ
19:デフォルトの名無しさん
15/11/28 22:13:01.33 R0seH/nX.net
クイックソートは単純な巡回とは違うだろ。
だからスタック的なメモリを必要とするかどうかだよ。
20:デフォルトの名無しさん
15/11/28 22:21:22.26 fFSPKhVt.net
ｆｉｌｔｅｒはリストの巡回とちゃうんかｗ
21:デフォルトの名無しさん
15/11/28 22:25:38.46 R0seH/nX.net
filterの実装がどうなってるかまでは知らんがな。
22:デフォルトの名無しさん
15/11/28 22:32:42.45 fFSPKhVt.net
知らんなら最初からそう言えやｗ
23:デフォルトの名無しさん
15/11/28 22:39:27.55 R0seH/nX.net
なんか変なテンションだなぁ
俺がC++とかでfilter相当の関数書かにゃならんくなったらループで書くよ。
24:デフォルトの名無しさん
15/11/28 22:44:37.77 fFSPKhVt.net
クイックソートはhaskellでfilterはc++なんか？
なんか変な奴だなぁニヤニヤ
25:デフォルトの名無しさん
15/11/28 22:49:36.42 R0seH/nX.net
何が変か、わからん。
まあ関数型言語なんかは再帰推奨らしいがあんまり好きになれん。
26:デフォルトの名無しさん
15/11/28 22:59:20.81 fFSPKhVt.net
推奨なんて生易しいもんじゃないで。
理論に囚われすぎて原理主義に陥いった餓鬼共やｗ
27:デフォルトの名無しさん
15/11/28 23:05:01.58 R0seH/nX.net
まあ参照透過性とかは原理主義か？という気はする。
28:デフォルトの名無しさん
15/11/28 23:29:11.93 W0C1+0hV.net
やっぱハノイの塔は再帰
有能
29:デフォルトの名無しさん
15/11/28 23:38:40.71 SyBhAT0R.net
お遊びに使うためのものだね。
再帰なんて。
30:デフォルトの名無しさん
15/11/28 23:40:05.61 1kauGQoG.net
>>8
ループでquicksort書いてみてくれ
上のコードと比較で見るだろ
言語は好きに選んでいい
31:デフォルトの名無しさん
15/11/28 23:45:06.21 R0seH/nX.net
ループでクイックソート書こうとするとスタック的なものを自前で用意せにゃならんのじゃないか。
めんどくさすぎ。
32:デフォルトの名無しさん
15/11/28 23:51:19.94 oWRhnwkW.net
なんかやたらと再帰がお遊びだと連呼する奴がいるが、どういう意図で言っているのか分からん。
お遊び感覚で動くものが作れるのだから、苦労しなくていい分優れているってこと？
33:デフォルトの名無しさん
15/11/29 00:02:43.51 aMnBRPWz.net
>>25
関数型言語は変数再代入禁止（のものが多い）から、そもそもループは書けないんだよね
34:デフォルトの名無しさん
15/11/29 00:04:00.34 BjpFnvXY.net
再帰がお遊びだ
再帰がお遊びだ
再帰がお遊びだ
>>32が可哀想だから連呼してあげたよ
35:デフォルトの名無しさん
15/11/29 00:06:31.94 BjpFnvXY.net
あ、意味は「お遊び感覚で動くものを作るな」という事です。
36:デフォルトの名無しさん
15/11/29 00:10:17.71 aMnBRPWz.net
動くんならいいんじゃないの？
37:デフォルトの名無しさん
15/11/29 00:20:09.59 iZIE7tB6.net
ま～た関数型コンプレックスのアホが暴れてるのか
38:デフォルトの名無しさん
15/11/29 00:24:10.72 aMnBRPWz.net
関数型は関数脳にならないと書けないからねー
手続き脳がしみついてると貶す対象にしかならないよね
39:デフォルトの名無しさん
15/11/29 00:29:56.09 BjpFnvXY.net
お前ら俺を笑い死にさせる気かｗ
40:デフォルトの名無しさん
15/11/29 03:56:07.52 1KywF+Vz.net
初めて知った時すごいと思いました
41:uy ◆Qawu9.2l1E
15/11/29 04:26:32.10 RQPUWZLH.net
せっかく埋め立てたのに何またスレ立ててんのゴミクズ
42:デフォルトの名無しさん
15/11/29 06:56:51.27 GeZFA4k5.net
ぼくたん初心者なのでわからんけど僕が今作ってる
関数から値を求める計算プログラムで再起型関数が大活躍してるお
たぶん今僕がやってる書き方が一番きれいだと思うんだけどなー
43:デフォルトの名無しさん
15/11/29 15:21:16.51 +8PPW4GA.net
> たぶん今僕がやってる書き方が一番きれいだと思うんだけどなー
いろんな方法で書いてみないと比較できないんじゃね？
44:デフォルトの名無しさん
15/11/29 15:49:46.72 BHpn4xqB.net
クイックソートで再帰なんてありえんと
さんざん言われ続けているのに、まだバカが湧いとるんだな。
ライブラリのループ版を使えば何の手間もかからず高速処理ができるのに
わざわざ問題ありまくりの再帰で書くなんてテロ同然の暴挙。
45:デフォルトの名無しさん
15/11/29 16:17:12.78 1uX74bCE.net
>>44
それって結局真の再帰を見たことがないからそう思い込んでるだけだよね。
見せてやるよ、真の再帰ってやつをな。
URLﾘﾝｸ(ideone.com)
46:デフォルトの名無しさん
15/11/29 16:52:01.83 +8PPW4GA.net
もうソーティングの話は良いよ、仕事で使う大抵の言語ではライブラリとして用意されてるんだから。
47:デフォルトの名無しさん
15/11/29 17:09:26.93 BHpn4xqB.net
>>45
再帰じゃあ、１０件程度のソートに控えるという事なんだよな。
48:デフォルトの名無しさん
15/11/29 17:29:39.96 +8PPW4GA.net
10件程度のソートならソーティングネットワークによるソーティングが一番速いから
十分少ない要素数に対してはそいつを呼び出して終わりだろ。
書いてないだけだろうけど。
49:デフォルトの名無しさん
15/11/29 20:46:37.54 ILoya83o.net
>>9
俺の見解では、ツリートラバースに再帰を必要とするのはデータ構造に問題があると思うんだよな。
イテレータの実装を考えると再帰はちょっと無理があるんじゃないかと思う。
もちろん出来ないわけではないのだが。
ノードが子ノードを保持するような原始的なデータ構造は良くないのではないか。
50:デフォルトの名無しさん
15/11/29 20:56:36.78 ILoya83o.net
代表的なツリーの一つとしてHTMLがある。
HTMLのフラグメントを切り出し、別のノードの子として加えるような操作を考えるとき、
これはやはりループに軍配が上がると思う。
もちろん、ノードに子ノードを保持するような原始的なデータ構造ではかなりメンドクサイ。
というのもHTMLの一部を切り出す時、ノードの種類によって、ノードの分割や併合が起こる。
再帰と原始的なデータ構造では非常にめんどくさい。
私はこの用途のために直列化ツリー構造というデータ構造を考案した。
（おそらくすでに一般的に使われているとは思うのだが。）
51:デフォルトの名無しさん
15/11/29 21:13:17.76 TqJ6Jff5.net
ループは再帰の特別なケースに過ぎない
ループの方が無駄がなく見える事もあるだろう
だが結局はその程度の話だ
52:デフォルトの名無しさん
15/11/29 21:25:34.60 +8PPW4GA.net
>>49
> イテレータの実装を考えると再帰はちょっと無理があるんじゃないかと思う。
問題はデータ構造の方じゃなくて言語の方だと思う。
というのも、yieldを持つ言語なら再帰を使ったやり方が最も簡潔に書けるから。
-- language:lua
function traverse(node)
if node then
traverse(node.left)
coroutine.yield(node.value)
traverse(node.right)
end
end
co = coroutine.create(traverse)
not_end, value = coroutine.resume(co, node)
53:デフォルトの名無しさん
15/11/29 21:52:31.69 ILoya83o.net
>>52
ちょっとそのやり方で、HTMLの一部をコピペするコード書いてみて。
54:デフォルトの名無しさん
15/11/29 22:12:36.39 +8PPW4GA.net
>>53
一部ってのはどういう風に探すのん？
特定の属性を持ってるタグを探す感じ？
55:デフォルトの名無しさん
15/11/29 22:23:46.56 euqwPPlR.net
どういう風に探すか後から指定できる感じで。
56:デフォルトの名無しさん
15/11/29 23:04:51.51 ILoya83o.net
>>54
HTMLのコピペがいつ起こるかというと、ユーザーがその操作をした時なので、
そういう前提で設計してはどうでしょうか。
57:デフォルトの名無しさん
15/11/29 23:13:29.23 ILoya83o.net
HTMLをユーザーの直観に適合する形で操作するのは意外と難しいですよ。
HTMLフラグメントの移動なんてどうですかね。
面白い題材だと思うのですが。
58:デフォルトの名無しさん
15/11/29 23:27:31.14 euqwPPlR.net
直列化ツリー構造kwsk
59:デフォルトの名無しさん
15/11/30 00:13:02.74 vNB8BIt6.net
>>53
書いてはみたけどウェブプログラミング初心者でごめんよ
URLﾘﾝｸ(ideone.com)
60:デフォルトの名無しさん
15/11/30 11:10:04.73 lmaKmArc.net
>>59 乙
61:デフォルトの名無しさん
15/11/30 14:51:10.36 +Ls/PK0X.net
>>52>>53を繰り返しで書ける人はいないみたいだね。
62:デフォルトの名無しさん
15/11/30 20:27:21.92 lmaKmArc.net
そういやC++のstd::mapのイテレータとかってどうなってんるのん？
63:デフォルトの名無しさん
15/11/30 21:11:57.14 9VRs5I4S.net
>>62
ノードオブジェクトに親を指すポインターもあって愚直に辿ってる。
赤黒木使ってるのが殆どだから、
レスしてる奴もコード読めない奴の方が多いんじゃないかw
64:デフォルトの名無しさん
15/12/01 00:02:40.17 M545w8lo.net
赤黒木って難しいよね、結構。
65:デフォルトの名無しさん
15/12/01 13:24:08.38 wfTLHpyu.net
データを吐き出す方法として前方イテレートしかしないの前提ならB+木がループでトラバース出来る上に高速なんだけど
挿入と削除を頻繁にするなら、そしてデータがキャッシュに乗り切らない程度に沢山あるなら赤黒木が高速になる
全部キャッシュに乗る程度の小さなデータ数ならAVL木が高速で
更に小さいならベクタ上にヒープ木でも作ればって話になる。
どの構造でも再帰で列挙出来るけど、ループでAVL木や赤黒木のデータを列挙するのは骨だな
66:uy ◆Qawu9.2l1E
15/12/01 15:00:00.16 p3g6QuXB.net
再帰・ループの相互変換が難しいとかさあ
アルゴリズムの根本的なところ理解してないだけ
恥ずかしすぎるこのスレ
67:デフォルトの名無しさん
15/12/01 16:04:55.52 M545w8lo.net
f(0,b)=b+1
f(a,0)=f(a-1,1)
f(a,b)=f(a-1,f(a,b-1))
68:デフォルトの名無しさん
15/12/01 16:39:12.55 wfTLHpyu.net
>>66
>>67をループに変換するのは難しくないんだね？
ちょっとやってみせてよ。
69:uy ◆Qawu9.2l1E
15/12/01 17:10:17.46 p3g6QuXB.net
rubyで書いてくれないとちょっと。
70:デフォルトの名無しさん
15/12/01 17:22:48.32 wfTLHpyu.net
>>69
rubyで書いたぞ
URLﾘﾝｸ(ideone.com)
71:デフォルトの名無しさん
15/12/01 17:26:42.78 alJpKlDN.net
再帰・ループの相互変換が難しいとかさあ
アルゴリズムの根本的なところ理解してないだけ
無能の>>68 は、勉強しろ。
72:デフォルトの名無しさん
15/12/01 17:26:51.00 UT6gApH3.net
uyって式も読めないのかな
73: ◆tAo.kQ2STk
15/12/01 17:33:25.45 wfTLHpyu.net
>>71
無能でーすチッスチッス
インターン先はGoogle(技術職8週間、コンパイラを改良するお仕事)でしたが何か？
今The Art of Computer Programmingの英語版の2巻読んでるんだけど
次に読むべき本は何？
>>72
数式から雰囲気掴むことも出来ない重度のアスペだから仕方ない。
74:デフォルトの名無しさん
15/12/01 17:39:29.54 UT6gApH3.net
>>73
uyの残した名言
何で出来ているか？というのは愚問過ぎる
例えばそれを「uy」としましょう
「uy」から派性したＡやＢといった概念から「uy」を辿る事は出来る
例えばこの世界にある「オブジェクト指向」という概念や「量子ビット」といった概念から
「uy」を辿る事が可能なので、
それらで世界が出来ているといった勘違いが可能なのです
でもそれは、一体いくつ「uy」から継承がネストしていて、プログラム等でいえばメソッドが追加されてしまった純粋性のない概念なのでしょうか？
それを知っているのは「uy」だけです
この世界にあるすべての概念は「uy」へと通じているので、
料理人は料理を通じて世界を知り、スポーツ選手はスポーツを通じて世界を知ります
誰も「uy」からは逃げられないんだよ
75:konisi ◆tAo.kQ2STk
15/12/01 17:44:25.62 wfTLHpyu.net
>>74
酉とIDくらい見なさいな
# どうでもいいけど最近障害者3級取ったわ
76: ◆tAo.kQ2STk
15/12/01 17:49:32.14 wfTLHpyu.net
あぁ、俺がuyと同一人物だと勘違いされたのではなく、
uyって人がそういう名言を残したって話か
ごめんごめん
77:デフォルトの名無しさん
15/12/01 18:38:14.45 UT6gApH3.net
誰も uy なんかに価値を求めてないのにね
78:デフォルトの名無しさん
15/12/01 18:56:25.56 wfTLHpyu.net
でかでかと引用した奴が言うと説得力があるね。
79:デフォルトの名無しさん
15/12/01 19:16:25.46 UT6gApH3.net
んでuyちゃんのループ問題はまだ解決しないのかしら
80:デフォルトの名無しさん
15/12/01 19:43:22.28 M545w8lo.net
まさにuyがアルゴリズムの根本的なところを理解しているかどうか問われているなｗ
81:デフォルトの名無しさん
15/12/01 19:54:09.54 UT6gApH3.net
それな、今までC++スレ読んでてこいつ頭おかしいなとは思ってたけど実力が問われるよな
82:デフォルトの名無しさん
15/12/01 19:58:37.14 wfTLHpyu.net
はてさてuyの実力は如何。
# 俺自身の実力はさておき。
83:デフォルトの名無しさん
15/12/01 20:19:08.98 UT6gApH3.net
おせぇな uy
84:デフォルトの名無しさん
15/12/01 20:49:22.02 M545w8lo.net
uy自力で頑張ってんのか？
なかなか根性あるじゃないか。
俺ならググって解答見てしまうがｗ
85: ◆tAo.kQ2STk
15/12/02 00:55:46.45 SG5bn8pD.net
再帰で書かれた超有名な関数をループにするだけの簡単なお仕事なのに
何ですぐに出来ないんだろうね？
# 全然簡単じゃないからです
86:デフォルトの名無しさん
15/12/02 02:08:55.48 sE+ivAhG.net
末尾再帰に書き換えてから蓄積引数を中に押し込んでループにするんだよ。
やり方を書いたのだからきっとuyにもできるはず！
87:デフォルトの名無しさん
15/12/02 06:47:05.05 UkYZlpUx.net
>>85
普通に悩んだけど再帰なら一瞬でとけんのに
ループじゃまず何のデータ構造を使っていいかわからん。
88:デフォルトの名無しさん
15/12/02 08:22:03.59 73uUfhWJ.net
スタックだろ。
再帰とループ＋スタックは等価。
理屈ではそうだが実際やるのは結構難しいんじゃね。
89:uy ◆Qawu9.2l1E
15/12/02 08:50:25.92 znqtbEKc.net
>>70
URLﾘﾝｸ(ideone.com)
「この程度」が難しいとか言われても
は？ としか思えない
再帰というのは単なるスタック付きのループであって
君たちがどこら辺で躓いているのか理解できないんです
やっぱわからない所がわからない状態なんだろうけど、
つうかＳＴＡＣＫＵって知っていますか？
90:uy ◆Qawu9.2l1E
15/12/02 09:14:47.18 znqtbEKc.net
ちなみにここ一週間のuyの生活は、朝起きて、ネトゲして朝寝る です。
ちょうどいま、起きたところではなく24時間起き続けていたので今から寝る前でした
とあるゲームであと１００戦程の対戦をこなし、誰よりも速く称号を獲得しようとしてる最中です
2chのム板なんて頻繁に開いてる暇とかないし結構忙しいんですわ
91:デフォルトの名無しさん
15/12/02 09:18:01.80 UkYZlpUx.net
>>89
お見事です。申し訳ありませんでした。
92:デフォルトの名無しさん
15/12/02 09:19:02.13 UkYZlpUx.net
自分には分からなかったわ
じゃあ質問なんだけど、再帰は全てスタック+ループで書き換えられるの？
93:デフォルトの名無しさん
15/12/02 09:34:55.30 UkYZlpUx.net
連投だけど分かったかも、
再帰で帰ってくるべき値をスタックしておくってことでループ+スタック=再帰なのね
94: ◆tAo.kQ2STk
15/12/02 09:39:29.64 SG5bn8pD.net
>>89
問題のすり替えはいけないな。
俺は「難しくないならやってみて？」って言っただけで
そもそも「再帰のほうがループより圧倒的に簡潔に書けるよね？」って文脈だろ。
君が「難しいから出来るもんならやってみろ」って捉えたかどうかなんざ知らんがおつかれさん
うんうん、言いたいことは分かった。
それで、そのコードのどこら辺が綺麗なの？
ちなみに機械的に変換したのがこちら(rubyじゃなくてごめんよ)
URLﾘﾝｸ(ideone.com)
fとhは機械的に変換したという意味では等価だし君のコードとほぼ同じ事をしてるのだけど、
h関数をパッと見て>>69式と等しいって言うのは凄く度胸が居るよね？
>>92
そもそも再帰をどうやってソフトウェア実装してるかというとコールスタック+ジャンプ≒スタック+ループな訳で
# ちなみにスタックの正しいスペルはstack。stackuなんて子は知りませんね。
95: ◆tAo.kQ2STk
15/12/02 09:48:27.56 SG5bn8pD.net
s/69/67/
96:デフォルトの名無しさん
15/12/02 10:13:14.24 amR8vvu9.net
>>92
数学的に証明されてる。
97:デフォルトの名無しさん
15/12/02 10:15:05.34 UkYZlpUx.net
>>96
そうなのか、、、
ならできるようにならなきゃだな
98:デフォルトの名無しさん
15/12/02 11:13:43.91 sE+ivAhG.net
>>92
再帰は機械的にCPSに書き換えることで末尾再帰にできて
そうしたらそれをループに書き換えられる
両方証明されてる
99: ◆tAo.kQ2STk
15/12/02 11:28:01.97 SG5bn8pD.net
>>97
アセンブリ言語によくあるcall系命令の挙動を正確に言えるようになれば
どんな再帰もスタックとループで書けるようになるよ
何しろスタックとループで再帰を表現してるのがcall系命令だからね。
それをそのまま書くとこんな具合に超汚くなるけど。
URLﾘﾝｸ(ideone.com)
100:デフォルトの名無しさん
15/12/02 12:52:27.49 UkYZlpUx.net
ありがとうございます
101:デフォルトの名無しさん
15/12/02 18:34:40.93 73uUfhWJ.net
uyなかなかやるな。
ググって解答見た可能性もあるが、ググれるのも実力のうちだからな。
102:.パンティーガァル
15/12/02 20:57:19.51 V8iEgN6C.net
>>90
> ちなみにここ一週間のuyの生活は、朝起きて、ネトゲして朝寝る です。
悲観することはない（してないかもしれないがｗ）
それも一つの生き方だ
人間の人生などそんなものだ
103:デフォルトの名無しさん
15/12/02 22:54:08.11 73uUfhWJ.net
URLﾘﾝｸ(ideone.com)
アッカーマン関数の展開の様子を書いてみた。
メモリリークあるけど気にしない。
もっとスマートにかけそうな気もするが言語が悪いのかな？
104:デフォルトの名無しさん
15/12/03 13:20:12.94 lU1L6vf0.net
誰かループ版と再帰版でベンチマークしてみなよ
105: ◆tAo.kQ2STk
15/12/03 13:56:10.07 cYXsvyZR.net
>>103
俺も書いてみたけど
確かにどう書いてももうちょっとスマートに書ける気がする。
URLﾘﾝｸ(ideone.com)
106:デフォルトの名無しさん
15/12/03 17:06:18.36 Sp77D/ez.net
>>105
メンドクサイやつだなお前ｗ
107:デフォルトの名無しさん
15/12/03 17:30:30.61 Sp77D/ez.net
>>104
ack(3,10)を100回計算させたところ
ループ 3.99秒
再帰 4.50秒
だった。微妙にループが速い。
言語はg++ 最適化あり
108: ◆tAo.kQ2STk
15/12/03 17:54:16.46 cYXsvyZR.net
>>106
でも115行目以降は>>103に比べてスマートじゃない？
アッカーマン関数をより素直に表現している(ように見える)というか。
テンプレートその他がひじょーに面倒臭い事になってるのは認めるよｗｗ
109:デフォルトの名無しさん
15/12/03 18:28:15.45 Sp77D/ez.net
>>108
まあそうかも。
言語によってはめちゃくちゃ簡潔に書けたりするのかな、気になる。
110: ◆tAo.kQ2STk
15/12/03 19:58:47.04 cYXsvyZR.net
>>109
ちなみに扱ってるのがアッカーマン関数だけだということとか考慮しつつ短く書くとこうなる。
URLﾘﾝｸ(ideone.com)
111:デフォルトの名無しさん
15/12/03 20:19:17.43 Sp77D/ez.net
>>110
だいぶスッキリした。
でも入れ子構造がなくなっちゃってるのはちょっと寂しいかな。
112:デフォルトの名無しさん
15/12/03 22:49:14.77 Sp77D/ez.net
URLﾘﾝｸ(ideone.com)
んんん、haskell 気持ちいい！
113:デフォルトの名無しさん
15/12/04 18:59:19.58 abMxFNxB.net
きっしょ
114:デフォルトの名無しさん
15/12/04 20:33:45.20 tAWNVevx.net
んぎもちいいいいいいいいいい
115:デフォルトの名無しさん
15/12/05 12:06:08.66 kPO9yvRD.net
気持ち悪い生き物だなこいつは
116:デフォルトの名無しさん
15/12/05 12:08:54.94 75VGJDuj.net
再起関数難しくて苦手だわ
117:デフォルトの名無しさん
15/12/05 12:38:44.60 vOhmiziG.net
おいらも苦手だわ
118:デフォルトの名無しさん
15/12/05 12:50:09.98 fWHJ2v3J.net
アッカーマンを知ったばかりで嬉しくてしょうがないんだろうな
俺くらいになるとどうでもよくなるけど
119:デフォルトの名無しさん
15/12/05 14:22:16.61 3X0n/q/1.net
さぁ次は竹内関数(たらい回し関数)だ！
120:デフォルトの名無しさん
15/12/05 14:24:24.30 FIUesRuL.net
>>118
アッカーマン関数が原始帰納関数でない証明を頼む。
定義がシンプルかつ一般帰納関数になるように
アッカーマンさんが構成したらしいが。
121:デフォルトの名無しさん
15/12/05 16:27:08.57 fWHJ2v3J.net
その問題が解けて嬉しかったんだろうな
122:デフォルトの名無しさん
15/12/05 22:53:23.45 Ij5oOkBB.net
たらいのループ化と展開の様子誰か頼む
123:デフォルトの名無しさん
15/12/07 01:05:16.16 OW/BWl2V.net
なんで自分でやらない？
再帰関数が好きなんだろ？
124:ネトuy ◆Qawu9.2l1E
15/12/07 02:12:06.27 IGEuV37f.net
ｗ
125:デフォルトの名無しさん
15/12/07 19:27:26.73 NCOmGjcr.net
URLﾘﾝｸ(ideone.com)
たらいの展開の様子
haskell気持ちEー！
ループ化は誰か頼むわ
126:デフォルトの名無しさん
15/12/08 10:04:03.24 HiEYAt85.net
きも
127:デフォルトの名無しさん
15/12/10 22:01:50.93 ZuWvmJPo.net
たらいのループ化どうやるかわからん。
128:デフォルトの名無しさん
15/12/10 23:27:19.50 ZuWvmJPo.net
んーなんかプログラムカウンタに相当するものをスタックに積まなきゃいけない感じ？
129:デフォルトの名無しさん
15/12/11 02:06:03.72 6gh0GR4/.net
URLﾘﾝｸ(ideone.com)
んーできたっぽい？
コンパイラの吐いたアセンブラとか見ながら書いたからチートしてるけど。
130:デフォルトの名無しさん
15/12/11 13:42:03.51 Z+QL5bbx.net
再帰厨はcall命令とjmp命令の違いが分かってから布教してほしい
131:デフォルトの名無しさん
15/12/11 18:14:40.60 H0NYZxX+.net
>>130
何言ってるんだ。。
ループで書けば早い、自分でスタック作れば、って言ってるループキチガイに、
命令にもこういうのがあるよ、必要だからあるんだよ。
と教えてあげてはどうだ？
132:デフォルトの名無しさん
15/12/11 18:27:07.72 FXKTAEC3.net
＞命令にもこういうのがあるよ、必要だからあるんだよ。
だからどうしたとしか。
基地外宗教を布教するなら、自分でするんだね。
133:デフォルトの名無しさん
15/12/11 19:01:03.96 DIOiIqvd.net
callとjumpの中間の命令もあるよな。
call使わない奴はいないのか?
134:デフォルトの名無しさん
15/12/11 19:02:56.29 6gh0GR4/.net
中間の命令ってなんだよ？
135:デフォルトの名無しさん
15/12/11 19:40:32.13 DIOiIqvd.net
>>134
MIPSのjalとjrとか。
callとretに相当。
jal相当すらなくてpcのレジスタ保存命令しかないのもあった。
136:デフォルトの名無しさん
15/12/13 22:44:03.31 1ET048aA.net
ツリーのイテレータってどう書くの
誰か頼む
137:uy ◆Qawu9.2l1E
15/12/14 05:58:59.61 0uboKikK.net
まずはこの手のアルゴリズム抽象化でC++使うのをやめろ
効率悪すぎ
138:uy ◆Qawu9.2l1E
15/12/14 06:02:04.72 WJU5GahL.net
ツリーのイテレータっつうか
ゲームプログラミング的にいえばツリー構造のタスクシステム
ゲームプログラミングしてれば普通に書いてるような低レベルの話
139: ◆tAo.kQ2STk
15/12/14 11:28:00.80 v4oN6dOD.net
>>136
ツリーのイテレータの書き方は大きく分けて3種類ある。
一つ目はイテレータ自身に「どのノードを辿ってきたか」って情報を覚えさせておいてそれを用いる方法
イテレータの空間効率がO(log n)になる代わりにサクセッサの時間効率が平均でO(1)になる。
二つ目はイテレータ自身にキーを覚えさせておいて、一旦そのキーを手繰ってから次のノードを手繰り直す方法
イテレータの空間効率がO(1)になる代わりにサクセッサの時間効率がO(log n)になる。
三つ目は木構造の各葉っぱに次の葉っぱへのポインタを書いておく方法
イテレータの空間効率がO(1)、サクセッサの時間効率がO(1)になる代わりに葉要素のサイズがO(1)増える。
140:名無しさん＠そうだ選挙に行こう
15/12/14 11:57:14.44 S7hw1GZs.net
イテレータってそんなにたくさん使うもんじゃないし、一つ目がいいかな、俺的に。
141:uy ◆Qawu9.2l1E
15/12/14 15:02:59.78 WIf5dtaV.net
それ種類じゃなくて、全部組み合わせて実装したほうが汎用的じゃねーの
class A
attr_accessor :up , :key , :list , :data
end
最低でも１と３のup listは無ければ木構造にならないだろ
君の考えは prev(up) と next(list) になってる
142:名無しさん＠そうだ選挙に行こう
15/12/14 16:34:38.86 S7hw1GZs.net
全部組み合わせたほうが汎用的？
何を言ってるかよくわからん
143:uy ◆Qawu9.2l1E
15/12/14 21:12:22.29 WIf5dtaV.net
まず、ツリーにしたらそれはイテレータとは呼ばないから
ただのツリーを走査する為の関数に過ぎない
「イテレータ」にしか使用できないツリーじゃなくて
一通りの事に使用できるツリークラス作れば？って話
144:デフォルトの名無しさん
15/12/14 21:30:28.83 lwFUcSQC.net
function NodeIterator(node, childNodesName) {
this._stack = [node];
this._name = childNodesName;
}
NodeIterator.prototype.hasNext = function() {
return this._stack.length > 0;
}
NodeIterator.prototype.next = function() {
var node = this._stack.pop();
if (node) {
for (var i = node[this._name].length -1; i > -1; --i) {
this._stack.push(node[this._name][i]);
}
}
return node;
}
ノードの親や深さも欲しい時は、スタックに積むノードをオブジェクトでラップして親の参照や深さを持たせればいいかも
145:デフォルトの名無しさん
15/12/14 22:23:44.30 S7hw1GZs.net
uyのイテレータの定義がさっぱりわからん。
俺はC++STLのイテレータを想像しているんだが。
uyの言ってるイテレータはなんのイテレータなんだ？
146:デフォルトの名無しさん
15/12/14 23:47:42.33 S7hw1GZs.net
uyが言ってるのはツリーで実装されたイテレータということかな？
俺が言いたいのはツリーを巡回するイテレータなんだが？
147:デフォルトの名無しさん
15/12/15 02:12:24.45 1v1TladX.net
コレクションを操作するのがイタレータ
148:uy ◆Qawu9.2l1E
15/12/15 02:28:13.41 hKbS74r3.net
センスないと無理
149:デフォルトの名無しさん
15/12/15 02:42:41.61 1v1TladX.net
>>147
それを言うなら走査だろと自分で突っ込んどく
150:uy ◆Qawu9.2l1E
15/12/15 02:44:41.16 xpC/Gts5.net
例えば
[1,2,3,4] ← これをイテレートするのがイテレータだろ？
ツリーは
[1,2,[3,4,[5,6]]] ← これをイテレートしたいのが作りたいイテレータだろ？
下のはイテレータと表現するまでもなくプログラム中でツリー構造が必要になって、
「ツリークラス」ってのを定義した事あれば、そんなのは標準実装しているレベルのものだから、わざわざツリーのイテレータなんていう半端なものは誰も作らない
作る順序的にまずはイテレータのツリー化じゃなくて、ツリークラスの定義
考えが追いつかないなら好きな順序で作れば良いけど
151:デフォルトの名無しさん
15/12/15 07:32:58.54 1zInVUKk.net
ツリーオブジェクトにtoArray()メソッドを用意すれば
すべて解決すると思うの。
152:デフォルトの名無しさん
15/12/15 10:44:59.05 kfL23r5/.net
大富豪プログラミングだなtoArray()
ツリーなんかはサイズが非常にデカくなることがしばしばあるぞ。
153:デフォルトの名無しさん
15/12/15 18:13:10.16 kfL23r5/.net
tAo.kQ2STk ってテレンスタオから取ってんの？
154:デフォルトの名無しさん
15/12/15 18:56:51.85 kfL23r5/.net
>>150
汎用的なツリークラス作れって言ってんのか？
javascriptみたいになるんじゃね？
155: ◆tAo.kQ2STk
15/12/15 19:28:58.56 1tm7yObV.net
>>153
違うよ。人間が読める某文字列をキーにしたらその酉が作れる。
ところでさ、どうでも良いんだけど
今話題にしてるのは木構造
>>141が示したデータ構造は無向グラフ
・・・・・・だよね？
156:デフォルトの名無しさん
15/12/15 22:38:36.35 WpFCIHcQ.net
ツリーじゃね
157:デフォルトの名無しさん
15/12/15 22:42:50.33 kfL23r5/.net
参照が木構造になってるかグラフになってるかなんて実行時に決まることじゃないのか？
158:デフォルトの名無しさん
15/12/16 03:41:52.77 L2apS2Qu.net
何だこの池沼ｗ
159:デフォルトの名無しさん
15/12/16 09:38:17.31 VSvjkteq.net
ごめん
160:デフォルトの名無しさん
15/12/16 21:37:56.27 OpCUYLL/.net
いいってことよ
161:デフォルトの名無しさん
15/12/17 17:19:47.96 Szn4FINI.net
Elixir再帰おもろい
URLﾘﾝｸ(confreaks.tv)
162:デフォルトの名無しさん
15/12/18 23:27:00.37 95zCi6v5.net
プログラマはMacを使ってるってマジ？
ｽﾚﾘﾝｸ(news板)
163:デフォルトの名無しさん
15/12/19 15:12:57.98 iG82T79N.net
メモメモ
URLﾘﾝｸ(izumi-math.jp)
URLﾘﾝｸ(examist.jp)
URLﾘﾝｸ(mathtrain.jp)
164:デフォルトの名無しさん
15/12/19 16:17:36.19 qhiLE2sk.net
制御では、実行時間が読めないアルゴリズムは使いにくい。
165:デフォルトの名無しさん
15/12/19 16:48:17.67 mZAnd63z.net
再帰と繰り返しは相互に変換可能なんだから、再帰で実行時間が読めないならば、繰り返しでも読めない。
こんなじょうしきも知らないの?
166:デフォルトの名無しさん
15/12/19 20:02:11.53 owy4KRbC.net
ごめん
167:デフォルトの名無しさん
15/12/19 20:16:05.69 hx9j/3Ds.net
再帰はシステムダウンの危険がある。
処理速度もはるかに遅くなる。
再帰の場合には、こうした実行時間が読めない特有の問題点がある。
168:デフォルトの名無しさん
15/12/19 22:02:48.92 EjHtX5K0.net
> 再帰はシステムダウンの危険がある。
そう言う環境ならば、システムダウンの可能性は繰り返しでもある。
> 処理速度もはるかに遅くなる。
ヘボが作った繰り返しは再帰よりはるかに遅い。
169:デフォルトの名無しさん
15/12/19 22:20:57.65 ZeO9ImyW.net
>>168
繰り返しと再帰はいっしょなんだろ？
170:デフォルトの名無しさん
15/12/19 22:22:37.57 EjHtX5K0.net
>>169
お前、バカなんだろ。
171:デフォルトの名無しさん
15/12/19 23:26:42.72 25MZJC6Y.net
末尾再帰に対応した言語が少ないからなぁ
172:デフォルトの名無しさん
15/12/19 23:29:13.06 srVmyYNw.net
普通の言語は対応してる
変な言語は使うもんじゃない
173:uy ◆Qawu9.2l1E
15/12/20 01:30:16.73 cCXQYS6+.net
# 1
def f
if 条件
処理
else
f()
end
end
# 2
def f
if 条件
f()
end
end
# 3
def f
case 条件
when LABEL
f()
end
end
末尾再帰されるパターンわからない奴ｗｗｗｗｗｗｗｗｗｗｗｗっうぃる？
174:デフォルトの名無しさん
15/12/20 01:48:28.93 XCzWC+ME.net
>>172
Java「…」
175:デフォルトの名無しさん
15/12/20 12:14:12.80 8RLYRFXT.net
>>175
漸化式
176:デフォルトの名無しさん
15/12/20 12:15:13.29 37nsyMmy.net
それは、無限再帰
177:デフォルトの名無しさん
15/12/20 14:49:43.30 zNzoBoA2.net
ID:EjHtX5K0のような白痴ばかりだから
再帰厨だと馬鹿にされることになる。
再帰を愛して使うんだったら、
ループ版にはない深刻なデメリットがある事ぐらいちゃんと注意した上で、
効率や安全性を無視したプログラミングを楽しむべき。
178:デフォルトの名無しさん
15/12/20 17:18:50.85 37nsyMmy.net
繰り返しの唯一の利点は回数の制御が再帰よりも容易であること。
これ以外の利点はない。
バカにはそれが理解できないらしいが。
179:デフォルトの名無しさん
15/12/20 17:26:49.52 8RLYRFXT.net
馬鹿には出来ませんね
180:デフォルトの名無しさん
15/12/20 18:23:24.49 /qKlyz5E.net
ごめん
181:デフォルトの名無しさん
15/12/20 19:26:33.84 37nsyMmy.net
再帰はID:zNzoBoA2のように低知能には理解不能という弱点があるけど
ID:zNzoBoA2のような低知能の出現率は低いので全然問題無い
むしろ低知能者を検出試験としてのメリットの方が大きい
182:デフォルトの名無しさん
15/12/20 22:01:31.82 ywvYIxL3.net
再帰苦手だから何でもかんでもループ使ってすまん
183:デフォルトの名無しさん
15/12/20 22:05:01.79 A/4Tj+iv.net
flattenとか難しいよね
184:デフォルトの名無しさん
15/12/20 22:51:10.83 zNzoBoA2.net
もし再帰が理解出来たつもりなら、ちゃんとループに直せるぐらいのプログラミング技術は備えなくちゃ。
最低でもそれくらいの技術や知能が無ければ
再帰を楽しむことはできないよ。
185:デフォルトの名無しさん
15/12/21 02:17:48.47 EKnooMo4.net
「再帰には深刻なデメリットがある」キリッ
なんて発言する低知能人は再帰を理解してるはずが無い、理解不能なものを怖れている。未開人と同じ。
186:デフォルトの名無しさん
15/12/21 09:54:25.69 S8kWm1db.net
ループを恐れるのは、ループにするだけの知識・経験を欠いているから。
その程度じゃあプログラミングの世界からすぐに消えるだけの存在。
再帰厨は、現実で満たされないのでスレで妄想を垂れ流すことしかできないクズ。
187:デフォルトの名無しさん
15/12/21 10:52:48.60 zel3cCjW.net
関数内にjmpも好き勝手にやるタイプだからどうとも言わんけど、
再帰否定派はまさか単一のアーキテクチャの話してないよな？
アルゴリズムとして再帰がイケてないって話だよな？
188:デフォルトの名無しさん
15/12/21 14:23:04.48 MyhUNItP.net
そうなのか？
189:デフォルトの名無しさん
15/12/21 14:51:29.83 EKnooMo4.net
>>186
必死で再帰を否定しているバカを弄っているだけで、繰り返しを否定しているわけでは無い
やっぱり低知能なんだな。
190:デフォルトの名無しさん
15/12/21 18:43:17.30 u4st+H+L.net
みなさん、これが「弄ってるって言いたいバカ」ですｗ
191:デフォルトの名無しさん
15/12/22 08:48:59.73 kujr6tD9.net
迷信を信じ込んで再帰を否定してるバカが
深刻なデメリット(爆笑)、例えば
> 処理速度もはるかに遅くなる。
を、実証すればスレ終了するのに。
192:デフォルトの名無しさん
15/12/22 11:16:51.41 4uBr+2Cy.net
>>191
そういう超基本的なプログラミング知識が無いのに
なんでプログラム板にいるの？
そもそもプログラミング経験無いだろ、お前。
193: ◆tAo.kQ2STk
15/12/22 12:54:32.04 S5fGjlFA.net
異様に伸びてると思ったら深刻な問題祭りかい
いくらでも例外は挙げられるけど
再帰で書こうがループで書こうが計算時間や空間計算量はそんなに変わらんから
書きやすく、読みやすい方で書いたほうが良いんじゃない？
そんなに変わらないって言うのは十分大きな入力に対して精々2〜3倍以下に納まるって意味だからね。
1時間掛かる処理を20マイクロ秒速くする為にごちゃごちゃ書き換えるのは結構な事だけど。
194:デフォルトの名無しさん
15/12/22 14:08:14.84 dkSLpih8.net
はるかと言っても所詮定数倍でしょ。
しかも一桁違うケースは
関数呼び出しがやや高価なスクリプト系の言語でもほとんどないでしょ。
195:デフォルトの名無しさん
15/12/22 17:31:14.37 qPz15M1W.net
>>193
いやね，絶対的に再帰でないと書けない，いや非常に書きにくいものはあるのは確かで．
たとえば代数式の解析を非再帰的で記述しろといわれると「はたして出来るのか？？」と逡巡してしまう．
こういう話題があまり発展しないのはどうしたわけですかね
関係ないけどquick-sort を三項演算子とコンマ演算子で書く話題，誰か‥私は挫折した‥
196:uy ◆Qawu9.2l1E
15/12/22 18:25:40.50 /7VurpfC.net
再帰の深刻なデメリットと言えば、コンパイラ設計者が甘えてる事によってバグを触ったり
異常に速度遅くなるパターンが放置されてたりする事
なんの言語とは言わないけど
197:デフォルトの名無しさん
15/12/22 19:03:19.84 8Du/ashj.net
それは再帰のデメリットではなくそういうクソコンパイラしかない言語のデメリット
198:デフォルトの名無しさん
15/12/22 22:57:38.64 kujr6tD9.net
>>192
能書きはいいからとっとと実証しろ。超基本的な知識なんだろ。
「はるかに遅い」とか言ってるバカ仲間のサイトでも良いぞ。
199:uy ◆Qawu9.2l1E
15/12/22 23:43:59.28 qcwFiUkP.net
>>197
なんか食パン裏返してこっちが表だとか必死に言ってるようなレスだな
200:デフォルトの名無しさん
15/12/22 23:48:59.13 8Du/ashj.net
>>199
食パン裏返してんのはお前のほうだよw
201:デフォルトの名無しさん
15/12/22 23:51:52.68 2TsBrERG.net
>>198
へい。再帰が130倍時間がかかるエビデンス。
URLﾘﾝｸ(www.fastpic.jp)
202:デフォルトの名無しさん
15/12/23 01:07:26.60 xKy7nhKt.net
食パンの裏はどっち側だよ
203:デフォルトの名無しさん
15/12/23 01:25:49.85 zjRNfIWb.net
>>201
こうするとなかなか興味深いことになるね。
本当に興味深いと思ってるだけで他意は無いよ。
fun_rec(){
if [ $1 -gt 5000 ] ; then
time fun_for
return
fi
fun_rec $(( $1 + 1 ))
}
204:デフォルトの名無しさん
15/12/23 02:04:18.65 3NYqkGXc.net
>>203
たしかにおもしろい。
再帰の深さに比例して時間がかかる。
再帰が深くなると処理に時間がかかるようになるのか、
別の時間を測ってしまっているのか。わからん。これはわからん。
205:デフォルトの名無しさん
15/12/23 07:21:41.71 fM9ORKUP.net
>>201
必死で再帰否定してるバカは知能が低いというエビデンス乙
シェル関数は呼び出しのたびに名前解決するのでペナルティが大きい
206:デフォルトの名無しさん
15/12/23 07:28:38.71 fM9ORKUP.net
Cの場合は入った時にフレーム作成と出る時にフレーム復元
c86なら、レジスタ操作4ステップ(複合命令なら2ステップ)だ。
名前解決なんかリンク時に終わってる。
207:デフォルトの名無しさん
15/12/23 08:47:35.90 2F8TsTF+.net
最近の関数呼び出しは引数をスタックに積まずにレジスタ渡しみたいだから
再帰で何段ネストしちゃっててもレジスタに収まってる限りは爆速なんじゃね
208:デフォルトの名無しさん
15/12/23 08:59:40.61 r+tlUph/.net
名前解決まで計算時間に含めるなら
もう再帰云々じゃなくて長大な再帰なしの一つの関数で全部こなせって話になるんだがな
>>207
いや、そうはならない。
レジスタの退避が必要になるから、自己再帰するならどっちにしても同じだけpush/popは必要になる。
最適化が掛かったらその限りじゃないけど。
209:デフォルトの名無しさん
15/12/23 09:02:09.80 QhR+qVh6.net
>>205
呼び出しだけじゃなく参照もね、iの。
localでもスタックフレームなめてるのかな?
210:デフォルトの名無しさん
15/12/23 09:10:56.81 2F8TsTF+.net
>レジスタの退避が必要になるから
そうかなー
211:デフォルトの名無しさん
15/12/23 09:15:53.17 fM9ORKUP.net
>>209
スタッフフレームは再帰に必要なステップだから、再帰のペナルティとしてあえて受け入れた。
シェルスクリプトを持ち出した時点で「スタックは容量制限が厳しい(場合もある)リソース」
を自分で否定しちゃうところが再帰否定してるバカが低知能であるもう一つのエビデンス(笑)
(場合もある)を知らないのか、教わってないのか知らないが、全ての場合だと思い込んでるところもバカの、特徴だね。
212:デフォルトの名無しさん
15/12/23 09:50:24.66 r+tlUph/.net
>>210
再帰で書いた何の変哲もないフィボナッチ関数をビルドしたケースを示すよ
URLﾘﾝｸ(gist.github.com)
gccではr12を、clangではraxを、rbp/rbxの他に退避してるのが分かる。
213:デフォルトの名無しさん
15/12/23 11:20:43.15 2F8TsTF+.net
対比先もレジスタにすればいいのにね
214:デフォルトの名無しさん
15/12/23 11:25:42.60 r+tlUph/.net
そんな事をすると
既に退避させてある値を別なレジスタに退避させてから、退避させたい値を退避するコードを吐く羽目になるけど
レジスタが最低でも加算無限個無いと出来ないからね。仕方ないね。
215:デフォルトの名無しさん
15/12/23 11:53:11.24 /Snk+v/P.net
externしていないstatic関数とかならレジスタ渡しもふつうにある。
もちろんCランタイム・コンパイラによる
216:デフォルトの名無しさん
15/12/23 12:07:45.20 r+tlUph/.net
>>215
いつの時代の話をしてるのか分からんのだけど、所謂Intel系の64bit環境(amd64)だとレジスタ渡しがデフォルトだよ。
URLﾘﾝｸ(en.wikipedia.org)
217:デフォルトの名無しさん
15/12/23 12:46:44.21 2bKYe5U2.net
>>204
bashはダイナミックスコープだから再帰の深いところでは
変数の参照に時間がかかるのかな。いまはその辺を疑ってる。
218:uy ◆Qawu9.2l1E
15/12/23 13:07:16.81 cGrC7qed.net
>>197
ｗ
219:デフォルトの名無しさん
15/12/23 16:35:42.36 u0B3Sjd8.net
だいたい再帰で問題が無いなんて
クイックソートで再帰が役に立たない事すら知らないってことか？
処理件数が増えたら速度の差なんて、何万倍どころじゃないし。
220:デフォルトの名無しさん
15/12/23 16:37:36.04 xKy7nhKt.net
>>219
何が言いたいのかわからん…
221:uy ◆Qawu9.2l1E
15/12/23 16:45:18.40 uhnrlQdn.net
>>219
ファーｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
222:デフォルトの名無しさん
15/12/23 17:05:56.20 fM9ORKUP.net
>>219
じゃ、これを10000倍高速化して実証してよ。
URLﾘﾝｸ(svnweb.freebsd.org)
223:デフォルトの名無しさん
15/12/23 17:15:03.86 2bKYe5U2.net
>>222
きったねえソースだな。どこの糞コード持ってきてんだ。
見せてやるよ、本気のクイックソートってやつをな。
void qsort(int a[], int left, int right)
{
int i, last;
if (left >= right)
return;
swap(a, left, (left + right) / 2);
last = left;
for (i = left + 1; i <= right; i++)
if(a[i] < a[left])
swap(a, ++last, i);
swap(a, left, last);
qsort(a, left, last - 1);
qsort(a, last + 1, right);
}
224:デフォルトの名無しさん
15/12/23 17:27:00.65 fM9ORKUP.net
>>223
10000倍高速化の比較対象はそれでも良いぞ。
225:デフォルトの名無しさん
15/12/23 17:56:16.45 ZCUCTd42.net
一万倍とかｗｗｗｗ
どこをどうやったら一万倍差がつくんだ
226:デフォルトの名無しさん
15/12/23 18:11:01.01 2bKYe5U2.net
>>225
クイックソートの最悪の時間計算量はn^2なので
データによってはとても大変なんよ。
227:uy ◆Qawu9.2l1E
15/12/23 18:27:35.24 PjxVSF2U.net
アルゴリズムの抽象化に静的言語使うチンパンとか話にならないから(´・ω・｀)
def qsort a , left , right
return if left >= right
swap a , left , (left + right) / 2
last = left
(left + 1).step(right) do |i|
if a[i] < a[left]
swap a , last+=1 , i
end
end
swap a , left , last
qsort a , left , last - 1
qsort a , last + 1, right
end
228:デフォルトの名無しさん
15/12/23 18:50:34.28 fM9ORKUP.net
>>225
最低10000倍ね。笑
>>219
>処理件数が増えたら速度の差なんて、何万倍どころじゃないし。
あ、小学生のように0.0001万倍とか言い逃れるかも。爆笑
229:デフォルトの名無しさん
15/12/23 21:36:40.93 L95mHKNc.net
>>227
URLﾘﾝｸ(hissi.org)
230:デフォルトの名無しさん
15/12/23 21:47:18.77 ZCUCTd42.net
万倍高速化はよｗｗｗ
231:デフォルトの名無しさん
15/12/23 22:10:25.42 fM9ORKUP.net
ID:u0B3Sjd8
10000倍の高速化まだ? 常識的で簡単そうな口ぶりだったけど。
232:デフォルトの名無しさん
15/12/23 22:12:02.95 fM9ORKUP.net
万は間違いだったとしても、最低でも倍速は楽勝なんだろ。
233:デフォルトの名無しさん
15/12/23 22:29:26.28 zjRNfIWb.net
>>232
速度以前に >>223 は簡単にスタックオーバーフローするよ。
それを防ぐ方法を教えてやってよ。
234:デフォルトの名無しさん
15/12/23 22:33:54.64 QhR+qVh6.net
>>233
繰り返し版が明示的スタックに使うヒープと同サイズに
マシンスタックの上限を変更すればOK
235:デフォルトの名無しさん
15/12/23 22:55:30.83 zjRNfIWb.net
いや、君に言ったわけじゃないし、最適化を教えてやれってことなんだけど。
236:デフォルトの名無しさん
15/12/23 23:35:43.46 fM9ORKUP.net
>>233
バカなの? >>222読めないの?
10000倍の高速化まってんだから、くだらねー横槍入れないように。
お前が10000万倍高速化するならかまってやんよ。
237:デフォルトの名無しさん
15/12/23 23:43:11.94 QhR+qVh6.net
>>226
繰り返しか再帰かに関係ないがな。
pivotの選び方次第だろ。
それは明示的にスタック使う繰り返し版クイックソートでも同じ。
238:デフォルトの名無しさん
15/12/23 23:58:42.12 2bKYe5U2.net
>>237
あたりまえ
239:デフォルトの名無しさん
15/12/24 01:02:26.01 aanAAc0G.net
>>238
>>225に対するレスとして
>>226はおかしいだろ。
気にならんのか?
240:デフォルトの名無しさん
15/12/24 01:08:56.14 VDgCwlJn.net
>>239
何を言っているのか意味がわからない…
241:デフォルトの名無しさん
15/12/24 06:51:58.79 2ShnOfV/.net
>>240
最悪パターンでもよいから、10000倍高速化しろよ。
242:uy ◆Qawu9.2l1E
15/12/24 08:02:14.94 Ecjqx/Av.net
スキルない人間をいくら叩いても何も出てこないのに
ここは動物園かよ
243:デフォルトの名無しさん
15/12/24 08:55:59.49 Q6U3kr4L.net
黒魔術師は再帰関数が大好き
244:デフォルトの名無しさん
15/12/24 09:09:51.37 Zs2o0pyD.net
黒魔術師はマクロを生成するマクロも大好き
245:デフォルトの名無しさん
15/12/24 11:57:48.07 2ShnOfV/.net
再帰を必死に否定しているバカの主張
1 スタックが制限の厳しいリソースである環境が全てだと思い込み、再帰の致命的なペナルティだと主張する
2 シェル関数呼び出しをエビデンスとして、再帰が130倍遅いと主張する
3 再帰版のqsortは数万倍遅いと主張するが、数万倍速いはずの非再帰版を示さない
4 知能が低く再帰を理解できない。それをもって再帰は難解と主張する。
246:デフォルトの名無しさん
15/12/24 14:54:05.30 QIUsopJK.net
>>245
そうやって執拗に絡むのもはっきりいって馬鹿丸出しだよ。
せっかく相手がクイックソートのコードを書いてくれたんだから
そのコードの問題点を指摘する方が賢そうに見えると思ったんだけどね。
247:デフォルトの名無しさん
15/12/24 16:38:25.55 2ShnOfV/.net
>>246
さらなる意味不明なバカが出てきたな。
コード出したのは再帰を必死で否定してるバカじゃないぞ。
248:デフォルトの名無しさん
15/12/24 17:26:51.73 ri4CJahT.net
最初期は再帰をサポートしてなかった計算言語があるらしい
249:デフォルトの名無しさん
15/12/24 18:44:44.88 W/SZtGXt.net
今はハードウェアレベルで再帰が実装されてるからな。
それを思えばいかに再帰が本質的にプログラミングに必要とされてるかってことだな。
250:デフォルトの名無しさん
15/12/24 20:04:26.21 aanAAc0G.net
計算可能性を探求する試みにおいて最初に出たのが、
エルブラン・ゲーデルの一般帰納関数だからね。
次がラムダ計算。
その次がノイマン型計算機直系の先祖であるチューリングマシン。
251:デフォルトの名無しさん
15/12/24 20:37:54.33 Hny3MC9I.net
10000倍だっておとなしいぐらい。
再帰だと落ちまくるから∞倍だって当たり前だろ。
252:デフォルトの名無しさん
15/12/24 20:46:14.21 W/SZtGXt.net
メモリ足りないなら動かないのは再帰もループも変わらんだろ。
ループのほうが本質的にメモリ使用量少なくなるとかなら話は変わってくるが。
253:デフォルトの名無しさん
15/12/24 20:58:31.47 2ShnOfV/.net
これだね。本当に知能が低い。
> 1 スタックが制限の厳しいリソースである環境が全てだと思い込み、再帰の致命的なペナルティだと主張する
254:デフォルトの名無しさん
15/12/25 18:57:10.38 IqCVGu/8.net
＞再帰もループも変わらんだろ。
なんで試してみないんだ？
再帰とループでクイックソート
ループ方式なら、データが何千万件あろうと無問題
255:デフォルトの名無しさん
15/12/25 19:44:32.39 TZMq+uAI.net
>>254
ループのソース晒してみろや
256:uy ◆Qawu9.2l1E
15/12/26 05:53:41.97 QzXIU7/C.net
覚えたての知識を使ってレスバトルするだけのスレなんていらねーから
257:デフォルトの名無しさん
15/12/26 08:33:15.25 oIXuKyHb.net
いらないスレを使って自分の意見を垂れ流すとか有効活用乙としか
258:デフォルトの名無しさん
15/12/26 10:19:35.68 EXUTS9i+.net
そういう初心者の遊び場もあっていいと思うけどなあ
259:デフォルトの名無しさん
15/12/26 12:54:13.38 KD7gR2Cz.net
>>252
再帰の方は、関数呼び出し大量に発生するから、リターンアドレス待避とレジスタ待避に、メモリーが喰われる。
260:デフォルトの名無しさん
15/12/26 13:36:54.41 oIXuKyHb.net
>>259
ループの方は今どの範囲についてソートしているのかという情報が大量に発生するから同じ議論が成り立つ訳だが。
261:デフォルトの名無しさん
15/12/26 13:40:32.70 6n5NtJkM.net
>>260
ループはヒープ、再帰はスタック
つまり、ヒープとスタックがぼくらを助けてくれるんだ！
262:sage
15/12/26 15:02:23.21 Igcba1qr.net
>>254
>>222(再帰版qsort)で5000万件ソートしてみた。楽勝で終了する。
必死で再帰を否定しているバカが低知能だという事がまた証明されてしまった。
頭が悪いって本当にかわいそう。
263:デフォルトの名無しさん
15/12/26 16:45:09.37 YV12MLKo.net
>>262
再帰版でうまくいくのだったら非再帰版ではもっとうまくいく，という発想はないのかね？
264:デフォルトの名無しさん
15/12/26 16:59:02.38 oIXuKyHb.net
>>263
うまくいくって言ったって高々定数倍速くなるだけだろ？
非再帰版を書いたり保守したりするコストより新しい速いマシンを買ったほうが安く上がるって発想は無いのかね？
265:デフォルトの名無しさん
15/12/26 17:27:47.02 Igcba1qr.net
>>263
知能障害者って本当にかわいそう。
5000万件でソート出来てるってことは、「再帰はスタックあふれる」という迷信が嘘だという発想には至らないのかね。
クイックソートの深さの制御はすでに研究し尽くされてて、全然問題ないんだよ。
266:デフォルトの名無しさん
15/12/26 17:37:15.54 Igcba1qr.net
あっ、繰り返し版は10000倍速いんだっけ? (爆笑)
早く実装コードみたいなあ。
267:デフォルトの名無しさん
15/12/26 18:11:47.33 6n5NtJkM.net
>>266
そんなに実装したいのなら教えてしんぜよう。
5000万件で >>201 を実行してみたまえ。
再帰呼出しというのは効率が悪いとても頭の悪いやり方なんだよ。
268:デフォルトの名無しさん
15/12/26 18:13:42.40 EXUTS9i+.net
シェルスクリプトを証拠として使うのは笑ってしまうからやめろ
269:デフォルトの名無しさん
15/12/26 18:16:50.75 6n5NtJkM.net
>>268
反論できないのな？じゃあお前の負けってことで。
270:デフォルトの名無しさん
15/12/26 18:22:25.08 EXUTS9i+.net
野次飛ばしてる観客相手に勝利宣言も笑うからやめろ
おまえはプロレスのヒール役か
271:デフォルトの名無しさん
15/12/26 18:26:32.21 gy7QXsCA.net
＞高々定数倍
そんな安全なもんじゃあねぇ。
データが増えれば差も増大。
272:デフォルトの名無しさん
15/12/26 18:38:59.41 Igcba1qr.net
>>267
ぷぷぷぷ
知能障害者は>>201をクイックソートと呼ぶのか?
273:デフォルトの名無しさん
15/12/26 18:41:57.44 Igcba1qr.net
>>271
ミジメすぎるぞ。クイックソートのスタック消費量はlog nに抑える事が可能。
こんな基本的な事を知らないから数千万件はソート出来ない。キリッ
とか、赤面な発言しちゃうんだよ。
274:デフォルトの名無しさん
15/12/26 18:47:36.31 Igcba1qr.net
ちなみにglibcのqsort(これは非再帰)も同じ手法で自前スタックを管理してる
知能が低いって本当にかわいそう。
URLﾘﾝｸ(sourceware.org)
/* The next 4 #defines implement a very fast in-line stack abstraction. */
/* The stack needs log (total_elements) entries (we could even subtract
log(MAX_THRESH)). Since total_elements has type size_t, we get as
upper bound for log (total_elements):
bits per byte (CHAR_BIT) * sizeof(size_t). */
275:デフォルトの名無しさん
15/12/26 19:02:41.83 6n5NtJkM.net
>>272
バカかお前は。ボウフラサイズの脳ミソしか搭載してないのか？
ただの繰り返しでさえ130倍の差があるのだから
クイックソートを実装したらそれ以上の開きがあるのは自明だろうが。
276:デフォルトの名無しさん
15/12/26 19:08:33.46 YV12MLKo.net
>>273
log n は発散するんだが‥
277:デフォルトの名無しさん
15/12/26 19:09:07.52 oIXuKyHb.net
>>275
バカはお前だ。シェルスクリプトでクイックソートを実装するなんて誰がするか。
sortプログラムを使え。
ちなみにシェルスクリプトの場合、関数呼び出しはそれ自体がスタックの深さをnとしてO(n^2)くらいの計算時間を持つっぽい。
278:デフォルトの名無しさん
15/12/26 19:09:41.46 Igcba1qr.net
>>275
ぷぷぷ。知能障害は本当にかわいそう。
qsortの繰り返し版は関数呼び出しの代わりに自前でスタック管理しなきゃならないんだよ。
10000倍高速化の実証コードはよ。
279:デフォルトの名無しさん
15/12/26 19:10:23.62 oIXuKyHb.net
>>276
確かに、うん、確かに、非常にゆるやかに発散するね。
n=2^64としてもlog nは64だけどね。
定数と変わんないレベルだよね。
280:デフォルトの名無しさん
15/12/26 19:11:25.60 6n5NtJkM.net
>>277
実装できないのな？無理なのな？はい論破。
281:デフォルトの名無しさん
15/12/26 19:14:27.33 6n5NtJkM.net
>>278
>>201 がすべてを物語っている。
これが何よりの証拠。再帰がとてつもなく効率が悪いことを
つまびらかにしてみせた。ここに来て見てみぬふりは通用しない。
エビデンスもきちんと示されている。もはや知らぬ存ぜぬでは済まされない。
282:デフォルトの名無しさん
15/12/26 19:14:30.05 Igcba1qr.net
>>280
何万倍も高速だっ。キリッ。
って主張してる奴に実証責任があるんだが
ガイジにはわからないの?
283:デフォルトの名無しさん
15/12/26 19:16:21.04 oIXuKyHb.net
>>280
練習のためなら兎も角、シェルスクリプト「だけ」でソーティングなんてやる意味が無い。
ループだろうと再帰だろうとね。
理由は遅いから。
ループで組んだとしても、非常に遅いから、実装するだけの意味が無い。
sortを呼べばCで書かれた非常に高速でスケーラブルなソーティングが出来るから、普通はそっちを使う。
さぁ君は一体何を論破したというのだい？
284:デフォルトの名無しさん
15/12/26 19:16:31.66 Igcba1qr.net
>>281
障害児くん
10000倍と130倍って、どっちがどれだけ大きいかわかる?
285:デフォルトの名無しさん
15/12/26 19:17:31.65 6n5NtJkM.net
>>282
>>201 で完全に証明してみせた。
反証する責任がお前にあるとは俺は思わないよ。
俺は自分の都合の良いように他人に責任を押し付けるなんて
卑劣な真似はできない。俺はただの真実の探求者。
286:デフォルトの名無しさん
15/12/26 19:21:05.64 oIXuKyHb.net
>>281
ちょっと試せば分かることなんだけど、シェルスクリプトに於いて再帰の実行速度は
呼び出し深さnに対してO(n^2)くらい掛かる。
で、クイックソートの呼び出しの深さは要素数mについてO(log m)なので
O(log^2 m)の計算時間が再帰だけで掛かることになる。
つまり全体の計算量はO(m log^2 m)だ。
一方でループの場合にはO(m log m)掛かるから、その差はO(log m)だ。
この値はm=5000万、底2として約25だ。
つまり、理論上は再帰とループで25倍の差が開きうる。
そして君は10000倍違うと言う。
残り400倍はどうやって稼ぐんだい？
287:デフォルトの名無しさん
15/12/26 19:21:48.42 6n5NtJkM.net
>>284
ボウフラ並みの脳ミソをメダカにでも食われたのかお前。
頭悪いにも程があるだろうが。こんな鶏頭野郎の
相手する俺の身にもなれ。なんていいやつなんだ俺。
聖人君子としか言いようがないわ。>>201 は5000回の繰り返しだ。
5000回の繰り返しでさえ130倍の開きがあるのだから回数が
増えれば差は開く一方だ。だから、>>267 で5000万と言ったのだよ。
288:デフォルトの名無しさん
15/12/26 19:23:23.36 PvF8tuZ2.net
霊がいるのかいないのかは判りませんが
人間の目が無いものを見ることがあるのは事実です
289:デフォルトの名無しさん
15/12/26 19:23:40.75 EXUTS9i+.net
差は開くだろうけど比も開くのか？
290:デフォルトの名無しさん
15/12/26 19:23:44.50 oIXuKyHb.net
>>287
5000回の再帰で130倍の差が開いた訳じゃなくて、
深さ5000の関数呼び出しで130倍の差が開いたって事を理解してる？
5000万要素のクイックソートなら最良のケースで深さ25の再帰だからね？
130倍どころか2倍にもならないからね？
291:デフォルトの名無しさん
15/12/26 19:23:54.44 6n5NtJkM.net
>>286
クイックソートを実装して試したのか？あ？
だれが実装するかと言っていたのと矛盾するだろうが。
つまり、君は嘘をついている。ゆえに俺が言ってることの方が正しい。はい論破。
292:デフォルトの名無しさん
15/12/26 19:26:45.13 6n5NtJkM.net
>>289
当たり前だろ。小さな町の町長が東京の都知事になって
仕事をこなせると思うか？数が増えるほどにコストは増大するんだ。劇的にな。劇的にだ！
293:デフォルトの名無しさん
15/12/26 19:29:40.16 Igcba1qr.net
障害児発作を発症中
294:デフォルトの名無しさん
15/12/26 19:31:02.17 EXUTS9i+.net
>>292
すまん、その例えどこまで信用していいか分からないからそういうの語るときは式でお願い
295:デフォルトの名無しさん
15/12/26 19:31:21.63 6n5NtJkM.net
>>290
ヤってみたのか？ヤったのか？ヤってから言えや！
さっさとクイックソートのコード提示しろよ！
いつまでグズグズ言ってりゃ気が済むんだ
俺はお前がクイックソートをシェルで実装するのをあとどれだけ待てばいいわけ？
296:デフォルトの名無しさん
15/12/26 19:32:53.62 Igcba1qr.net
>>295
再帰は数万倍遅いといったお前が実証しろよ
297:デフォルトの名無しさん
15/12/26 19:33:00.02 6n5NtJkM.net
>>294
log2・5000 : log2・5000 ? 30 ⇒ log2・50000000 : 10^4 ? A
QED.
298:デフォルトの名無しさん
15/12/26 19:34:26.18 Igcba1qr.net
1万倍高速なクイックソートはよ
299:デフォルトの名無しさん
15/12/26 19:34:37.78 6n5NtJkM.net
>>296
俺は >>201 で示したし、それで十分に満足の行く結果を得た。
>>201 に不満だというのならそれを超えるものをお前が書け。自分でやれ。
他人にやらせるっていうのは俺の常識からは考えられない。
300:デフォルトの名無しさん
15/12/26 19:35:10.69 6n5NtJkM.net
>>298
お前がやるんだ。お前が言い出したことだろうが。
301:デフォルトの名無しさん
15/12/26 19:35:32.98 oIXuKyHb.net
>>295
どうして俺が実装しなきゃならないわけ？
数万倍遅いって言い出した奴が実証のためにコードを提供するのが筋だろ？
302:デフォルトの名無しさん
15/12/26 19:42:36.24 6n5NtJkM.net
>>301
そんな筋は通らない。実証コードが欲しいといいだしたのは
お前なのだからお前が自分で書け。言い出しっぺの法則は
プログラマを始め科学的論証に関わる人間すべてに通じる基本原則だ。
どうやればそれを確認できるかという手順も道筋も結論も示した。
自分の満足のいくものが欲しいのなら自分で行動しろ。
他人の足にしがみつくな、気持ち悪い。
303:デフォルトの名無しさん
15/12/26 19:44:38.98 6n5NtJkM.net
１万倍の実証コードとか言い出しといて書かないってどういうことよ？
他人に頼りっきりってどういうことよ？
夢があるのなら自分で叶えろよ
親の足かじってんじゃねえぞニート野郎
304:デフォルトの名無しさん
15/12/26 19:50:48.20 oIXuKyHb.net
>>302
IDをよく見ろ。俺は実証コードが欲しいだなんて一言も言ってない。
305:デフォルトの名無しさん
15/12/26 19:51:36.37 EXUTS9i+.net
>>297
何この記法初めて見た
もしかして情報界隈では常識なのか？
306:デフォルトの名無しさん
15/12/26 19:51:49.58 Igcba1qr.net
>>219
親のスネかじってんじゃねーぞニート野郎
とっとと数万倍速いクイックソートの実証しろよ
307:デフォルトの名無しさん
15/12/26 19:54:34.25 Igcba1qr.net
ID:6n5NtJkMは発狂して「再帰は数万倍遅い」発言をウヤムヤにしたい模様
でも、まだ300レス。先は長いぞ。頑張れ。
308:デフォルトの名無しさん
15/12/26 19:56:25.26 oIXuKyHb.net
>>305
俺も見たこと無い。
一瞬、三項演算子にも見えるけど順序がおかしいし。
309:デフォルトの名無しさん
15/12/26 19:57:11.33 6n5NtJkM.net
>>304
言ったかどうかは問題じゃない！
お前はクイックソートで1万倍の差があるのか確認したい、
それを確認する手段としてシェルでクイックソートを実装すればわかる
ということを俺は示したんだよ。それだけわかってればいいよもう！
310:デフォルトの名無しさん
15/12/26 20:00:13.46 6n5NtJkM.net
>>308
?はただの文字化けだぞ。
数理式計算量証明の理想解近似法を大学で習ってたらわかるだろ。
情報科学の基礎中の基礎だし。
311:デフォルトの名無しさん
15/12/26 20:02:01.94 oIXuKyHb.net
>>309
いいや、そもそもそんな事は望んでない。よく読め。
俺が言いたいのは、1万倍もの差が出るなんて事は理論上ありえないって事だ。
それでも尚、実際に1万倍の差が出ると言い張るのであれば
それを実証するコードを君が示すべきだよね？
312:デフォルトの名無しさん
15/12/26 20:03:37.49 EXUTS9i+.net
>>310
すまん、その文字化けしてるところ元は何だったのか教えてくれ
O?
313:デフォルトの名無しさん
15/12/26 20:05:55.80 6n5NtJkM.net
>>311
だから、俺は示したって言ってるだろうが！
>>201 でくっきりはっきりと証明してみせただろうが。
それで満足できないというのであれば、満足の行くコードを見たいというのであれば
お前がそれを書くべきだ！それが論理的検証というものだ。科学的な姿勢というものだ。
他人の論文に満足できないと言ってるばかりじゃ学会では一切評価されないよ。
それを超える論文を自分で書いてこれでどうだと魅せつけるべきだ。
君はシェルでクイックソートを書くべきなんだ！！
314:デフォルトの名無しさん
15/12/26 20:06:59.46 6n5NtJkM.net
>>312
掛け算の掛けるだ。
右側では1万倍になってるのがわかっていただけると思う。
315:デフォルトの名無しさん
15/12/26 20:09:01.51 YV12MLKo.net
>>281
>>205
316:デフォルトの名無しさん
15/12/26 20:09:33.38 YV12MLKo.net
>>285
>>205
317:デフォルトの名無しさん
15/12/26 20:13:31.65 oIXuKyHb.net
>>313
いいかい？
君は「示した」と何度もはっきり発言してはいるけど、実のところ何も示しちゃいないんだ。
318:デフォルトの名無しさん
15/12/26 20:22:57.69 6n5NtJkM.net
>>315
バカかお前は。大脳半球が全損して産まれて来たのか？
名前解決に時間がかかるとするならば、名前解決まで含めて再帰呼出しだ。
外務省はシリアへの渡航を自粛するよう日本国民に通告しているが、そんな不安な情勢の中、
「シリアが危険なんじゃないテロリストが危険なんだ」と言って
意気揚々とシリアに出かけていく頭の中お花畑野郎と同じだろうが。
お前が言ってるのはそれと全く同じこと。
シリアという地域でテロの被害に遭う確率が高いから外務省は渡航を自粛するように
必死に呼びかけているんだ。少しでも日本の国民がテロの被害に遭わないよう骨身を削って
頑張っているんだ。再帰呼出しでプログラム事故に遭う確率が高いから俺は再帰を自粛するよう
呼びかけているんだ。外交官としての俺の立場に立って再考してみろ。お前がどれだけ
愚かなことを言っているか今一度ようく考えてみることだな。
319:デフォルトの名無しさん
15/12/26 20:24:31.77 EXUTS9i+.net
やべえ記号わかってもなお式の意味わかんねえw
320:デフォルトの名無しさん
15/12/26 20:25:46.83 Igcba1qr.net
障害児は
シェル関数呼び出しはwhileより130倍遅い
と
再帰版のクイックソートは何万倍も遅い
が等価らしい
必死で再帰を否定しているバカが低知能であることのエビデンスがまた一つ明らかになってしまった
321:デフォルトの名無しさん
15/12/26 20:27:35.19 6n5NtJkM.net
>>317
>>201 の画像が見えないのか？俺はエビデンスをしっかりちゃっかりくっきりまるっきり示したぞ。
お前はアイマスク付けて前が見えないと言ってるだけのただのうつけ者。話にならない。
322:デフォルトの名無しさん
15/12/26 20:30:11.96 EXUTS9i+.net
もしかしてだけどさ、もししてだけどさ、>>201で示されてることってシェル関数呼び出しがシェルwhileより130倍遅いことだけじゃね？
323:デフォルトの名無しさん
15/12/26 20:35:37.94 6n5NtJkM.net
>>322
おいおいいい加減にしろよナメクジ野郎。
自らの関数を呼び出すことを再帰と言うのだろうが。
関数の呼び出しが遅い、すなわち再帰の効率がとてもよろしくないということだ。
テロリストが民間人を殺害するのならば、テロがはびこっているシリアには行くべきじゃないということだ。
お前、後藤さんのご家族の前で後藤さんが悪いって言えるのか？後藤さんは悪いよ。
とても危険なところと知りつつシリアに言ったんだから。だけど、それをご家族の前で言う意味がないよね。
324:デフォルトの名無しさん
15/12/26 20:38:45.39 6n5NtJkM.net
再帰を使うっていうのはテロリストの前に自らの首を差し出すことと同義。
何があっても文句言うな。そして周囲の人間をその愚行に巻き込むな。
悲しませるな。俺はお前らが再帰を使うと悲しいよ。
325:デフォルトの名無しさん
15/12/26 21:07:17.88 oIXuKyHb.net
純粋にシェルスクリプトだけでクイックソートを組むのは骨が折れたぞっと
URLﾘﾝｸ(www.fastpic.jp)
ループのほうが遅いです本当にどうもありがとうございました
326:デフォルトの名無しさん
15/12/26 21:10:42.27 oIXuKyHb.net
コードが見たけりゃどうぞ。
URLﾘﾝｸ(ideone.com)
327:デフォルトの名無しさん
15/12/26 21:21:55.47 6n5NtJkM.net
＿＿＿_
／ ＼
／ ─ ─ ＼
／ （●） （●） ＼
| （__人__） |
＼ ｀⌒´ ,／
／ ー‐ ＼
328:デフォルトの名無しさん
15/12/26 21:22:21.55 EXUTS9i+.net
なんだやっぱり再帰の方がいいのか
329:デフォルトの名無しさん
15/12/26 21:26:26.06 hFLlv/LI.net
ぐうの音も出ないなこれは
330:デフォルトの名無しさん
15/12/26 21:31:21.64 6n5NtJkM.net
シリアとか言わなきゃよかった
後藤さんのくだりとか意味わかんないし
331:デフォルトの名無しさん
15/12/26 21:40:05.38 hFLlv/LI.net
フィボナッチとかはループと再帰で指数倍の差が出るんだっけ？
332:デフォルトの名無しさん
15/12/26 22:10:31.84 oIXuKyHb.net
メモ化しないコードだとそうなるね
333:デフォルトの名無しさん
15/12/26 22:19:22.17 hFLlv/LI.net
メモ化とか線形のメモリ食うじゃね？
334:デフォルトの名無しさん
15/12/26 22:46:18.19 JxygBNoz.net
>>333
直近2つを記憶するだけだから定数
335:デフォルトの名無しさん
15/12/26 23:20:10.16 YV12MLKo.net
>>334
それは再帰的定義を使う方では？
フィボナッチ数列の第n項を直接nの式で表せるはずだが
336:デフォルトの名無しさん
15/12/26 23:36:55.55 JxygBNoz.net
>>335
文脈読もうな。
メモ化に必要な記憶領域が線形ではないか、と言ってる奴がいたから定数だ、と答えただけ。
337:デフォルトの名無しさん
15/12/26 23:44:58.30 jxcpNE9M.net
まだアーキ依存どころか言語依存の話してるの？
338:デフォルトの名無しさん
15/12/27 00:05:08.34 TlhMnrM9.net
再帰メモ化定数メモリフィボナッチってどんなソースになるの？
339:デフォルトの名無しさん
15/12/27 00:35:22.25 nuYFrBF7.net
fibonacci = fib (0,1)
fib (m1,m2) 0 = m2
fib (m1,m2) n = fib (m2, m1+m2) (n-1)
340:デフォルトの名無しさん
15/12/27 00:38:15.78 nuYFrBF7.net
タプルの代わりに木かハッシュを使えば値を全部保持する
普通のメモ化にできるがフィボナッチの計算にはもちろん不要
341:デフォルトの名無しさん
15/12/27 00:54:47.63 Y7IK7QLW.net
>>325
bashを使うのであれば
if [ $i -ge $j ]; then
の代わりに
if (( $i < $j )); then と書ける。
また(( )) の中で単体の変数は$を省略できる
if (( i < j )); then
一行で書くこともできる。
(( i >= $ )) && break
342:デフォルトの名無しさん
15/12/27 01:09:36.05 Y7IK7QLW.net
stack=("${stack[@]:0:((${#stack[@]}-2))}")
これは、こう書ける。
stack=("${stack[@]::${#stack[@]}-2}")
ついでに、""をつける方が正しいのではあるが、
値にスペースが無ければ、"" は省略可能。
343:デフォルトの名無しさん
15/12/27 01:15:06.76 Y7IK7QLW.net
p=$(( $((${array2[$i]}+${array2[$j]}))/2 ))
$((・・・)) の中では普通に () が使用可能
p=$(( (${array2[$i]} + ${array2[$j]}) / 2 ))
344:デフォルトの名無しさん
15/12/27 01:21:25.37 Y7IK7QLW.net
for i in `seq 1 1 1000`; do
`` は基本的に $() と同等。新しい$()の使用が推奨されている。
for i in $(seq 1 1 1000); do
また、これは以下のように書ける
for i in {1..1000}; do
345:デフォルトの名無しさん
15/12/27 01:32:25.91 Y7IK7QLW.net
lintツールとして、shellcheckコマンドがある。
qsort_rec $left $((i-1))
^-- SC2086: Double quote to prevent globbing and word splitting.
qsort_rec $((j+1)) $right
^-- SC2086: Double quote to prevent globbing and word splitting.
$leftと$rightにスペースが入ってる場合に問題になるから""をつけろと警告される。
これは冒頭で
left=$(($1))
right=$(($2))
のようにして数値であると保証してあげれば消える。
変数 pair が未使用
その他の警告は、上の指摘を修正すれば消えるはず
346:デフォルトの名無しさん
15/12/27 01:46:16.35 Y7IK7QLW.net
ループ版で時間がかかってるのはこの部分な気がするな。
配列をコピーしているわけだし。
stack=(${stack[@]::${#stack[@]}-2})
URLﾘﾝｸ(www.drk7.jp)
さて、ここの非再帰版を見ると、どうも配列のコピーはしてないようだ。
ループ版は高速化の余地がありそうだ。
やってみるかね？ うまく実装できるかな？
347:デフォルトの名無しさん
15/12/27 02:00:40.37 qGJmRem2.net
ループの途中でコマンドを呼び出すようにすればもう少し遅くできるんじゃないかな。
348:デフォルトの名無しさん
15/12/27 02:20:49.37 Y7IK7QLW.net
さーて、コードをほとんど読まずに、Perl版をそのまま置き換えてみたが
きちんと動かんぞとｗ 面倒くさいな。
速度的には再帰版より速くなりそうな感じはしてるが、処理間違ってるからなｗ
349:デフォルトの名無しさん
15/12/27 02:32:42.88 Y7IK7QLW.net
あ、できたっぽい？ 参考にしたコードに二箇所バグが有るようだな。
> &qsort_array($array2,0,$size);
> $right_stack[0] = $right;
$sizeが$rightに入るが、正しくは$size-1
> if ($i - $left < $right - i) {
↓
> if ( ($i - $left) < ($right - i) ) {
Perlの優先順位は、下のように解釈されるんだっけ？
そんなの変えないよな。
今コードを見直してる。
350:デフォルトの名無しさん
15/12/27 02:34:29.15 Y7IK7QLW.net
ごめん嘘だったｗ 。あれぇ～？
351:デフォルトの名無しさん
15/12/27 02:58:09.23 Y7IK7QLW.net
Perl版実行してみたがもともとのコードからして動いてないｗ
352:デフォルトの名無しさん
15/12/27 03:31:06.37 Y7IK7QLW.net
マジめんどくさかったわｗ 参考にしたコードが悪すぎた。
他のコードと比べてよくわからん比較条件とか処理が多かったので
結局諦めてこっちを参考にした。
URLﾘﾝｸ(gauc.no-ip.org)
結論。やっぱりループのほうが速かったねｗ
URLﾘﾝｸ(ideone.com)
recursive
real 0m0.550s
user 0m0.548s
sys 0m0.000s
loop
real 0m0.439s
user 0m0.436s
sys 0m0.000s
なお再帰版も>>326よりも速くなっているのは、
上で指摘した点をリファクタリングしたため。
>>326のコード
> recursive
> real 0m0.637s
> user 0m0.636s
> sys 0m0.000s
>
> loop
> real 0m0.723s
> user 0m0.720s
> sys 0m0.000s
353:デフォルトの名無しさん
15/12/27 03:35:18.72 Y7IK7QLW.net
ループの方が速かったので訂正よろｗ
328 名前：デフォルトの名無しさん[] 投稿日：2015/12/26(土) 21:22:21.55 ID:EXUTS9i+ [10/10]
なんだやっぱり再帰の方がいいのか
329 名前：デフォルトの名無しさん[sage] 投稿日：2015/12/26(土) 21:26:26.06 ID:hFLlv/LI [1/3]
ぐうの音も出ないなこれは
354:デフォルトの名無しさん
15/12/27 03:56:54.62 nuYFrBF7.net
定数の差とかどうでもいい
355:デフォルトの名無しさん
15/12/27 07:31:06.68 hwv/tSGM.net
>>353
10000倍高速化してから言いなさい
356:デフォルトの名無しさん
15/12/27 07:39:49.49 Y7IK7QLW.net
>>355
いいだしっぺどうぞｗ
357:デフォルトの名無しさん
15/12/27 07:50:22.72 hwv/tSGM.net
>>356
>>219の主張を受け継いで高速化したお前が言い出しっぺ
358:デフォルトの名無しさん
15/12/27 07:55:16.56 Y7IK7QLW.net
言い出しっぺの定義を変えるなよｗ
本当に往生際が悪いｗ
359:デフォルトの名無しさん
15/12/27 08:00:41.71 hwv/tSGM.net
>>353でお前が訂正を求めたレスはID:6n5NtJkMの
「再帰は1万倍遅い」に対するレス。
なので、訂正を求めるには10000倍高速化する必要がある
知能障害児には理解不能かな?
360:デフォルトの名無しさん
15/12/27 08:06:42.55 Y7IK7QLW.net
と言われてもなぁｗ
俺は1万倍速いなんて言ってないし。
ループのほうが速いという証拠も出したからどうでもいいかなｗ
361:デフォルトの名無しさん
15/12/27 08:16:44.55 hwv/tSGM.net
じゃ、求めた訂正を取り消しなさい。
362:デフォルトの名無しさん
15/12/27 08:18:08.68 Y7IK7QLW.net
>>361
これでいいのかい？ｗ
ループの方が速かったよｗｗｗ
328 名前：デフォルトの名無しさん[] 投稿日：2015/12/26(土) 21:22:21.55 ID:EXUTS9i+ [10/10]
なんだやっぱり再帰の方がいいのか
329 名前：デフォルトの名無しさん[sage] 投稿日：2015/12/26(土) 21:26:26.06 ID:hFLlv/LI [1/3]
ぐうの音も出ないなこれは
363:デフォルトの名無しさん
15/12/27 09:08:43.20 hwv/tSGM.net
少し速いと10000倍速いの区別がつかないおバカさんとうエビデンス(笑)
364:デフォルトの名無しさん
15/12/27 09:33:20.24 Zmrinoji.net
分かったことは
・再帰をただ単にループに直すと却って遅くなる
・最適化を施せばループのほうが速くなるが、10000倍速くなるなんてことはない
の2点でおっけい？
365:デフォルトの名無しさん
15/12/27 09:55:25.37 TQTcd7lL.net
そうだな。シリアがどうとか言い始めるほどループの方が優秀な訳では無さそうだな
366:デフォルトの名無しさん
15/12/27 10:12:22.58 dpCOQ+Jx.net
∞倍だね。
再帰なんってのと比較すること自体おかしい。
却って遅くなるなんて書いてる恥知らずは、プログラミング技術が無さ過ぎ。
367:デフォルトの名無しさん
15/12/27 10:24:13.63 Zmrinoji.net
>>366
昨日から昨晩に掛けてのやり取りを知らないのか？
俺はそのやり取りから、>>364が分かった事の全てであるって発言しただけなんだけど。
368:デフォルトの名無しさん
15/12/27 10:36:38.52 dpCOQ+Jx.net
やり取りからだって？
２ｃｈの妄想だけじゃなくて現実を見ろよ。
369:デフォルトの名無しさん
15/12/27 10:40:01.29 hwv/tSGM.net
∞倍 ｗｗｗｗｗ
無限大を憶えたての小学生かよ
quick sort 再帰/quick sort 非再帰 = ∞, すなわちquick sort 非再帰が0って事だな。
再帰を必死に否定しているバカの主張
1 スタックが制限の厳しいリソースである環境が全てだと思い込み、再帰の致命的なペナルティだと主張する
2 シェル関数呼び出しをエビデンスとして、再帰が130倍遅いと主張する
3 再帰版のqsortは数万倍遅いと主張するが、数万倍速いはずの非再帰版を示さない
4 知能が低く再帰を理解できない。それをもって再帰は難解と主張する。
5 非再帰版qsortの実行時間はゼロ
本当に知能が低い
370:デフォルトの名無しさん
15/12/27 11:19:02.84 BwztOoZh.net
>>364
最適化なくてもループのが速いでしょ
10000倍は無いがw
371:デフォルトの名無しさん
15/12/27 11:22:49.99 Zmrinoji.net
>>368
お前の中ではそうなんだろうな。そんな事より現実を見ろよ。
大本の彼らの主張は「クイックソートをお題にした場合に於いて再帰はループに比べて何万倍も差がでる(>>219)」
俺らの主張は「そんなに差がでることは理論的にありえない(>>286)」
であって、
ループのほうが再帰より「僅かでも」速いかどうか(>>352-353)なんざ元々議論していない。
クイックソートをやる上で比較にならないほど再帰のほうが遅くなるというならソースを出せや
372:デフォルトの名無しさん
15/12/27 11:23:28.75 yWds0j/q.net
繰り返しの方が再帰より速い！
(ただしシェルスクリプトに限る)
373:デフォルトの名無しさん
15/12/27 11:23:33.41 Zmrinoji.net
>>370
>>325
374:デフォルトの名無しさん
15/12/27 11:29:16.92 nlFV9EHx.net
>>371
引数受け渡しとかレジスタ待避とかで、余分なメモリー操作が発生する。
375:デフォルトの名無しさん
15/12/27 11:32:56.76 Zmrinoji.net
>>374
>>260
定数オーダーの空間計算量で計算が出来ないなら、原理的に余分なメモリ操作は避けられない。
それはループでも一緒。
376:デフォルトの名無しさん
15/12/27 11:43:09.26 yWds0j/q.net
>>374
明示的なスタック操作と大差ないのでは?
377:デフォルトの名無しさん
15/12/27 11:52:39.31 BwztOoZh.net
>>373
純粋に処理速度の話してんならネイティヴコード化したものでないとさ
378:デフォルトの名無しさん
15/12/27 12:07:38.28 BwztOoZh.net
>>375
横ですが、再帰呼出だとcallのオーバーがある分遅くなるで良いのかな？
まあ数パーセント程度だと思うけど
379:デフォルトの名無しさん
15/12/27 12:20:57.14 nuYFrBF7.net
クイックソートだからなんとかなってるだけで
たとえば赤黒木の操作を自前でスタック管理するアホはいないわけ
380:デフォルトの名無しさん
15/12/27 12:27:15.41 Zmrinoji.net
>>377
ほい、最適化しなければループのほうが遅い証拠。
URLﾘﾝｸ(www.fastpic.jp)
381:デフォルトの名無しさん
15/12/27 12:33:24.41 BwztOoZh.net
>>380
ああ分かってない人ねwww
382:デフォルトの名無しさん
15/12/27 12:35:34.85 Zmrinoji.net
>>378
Pen4のデータシートの値を元にするなら
ループのコストと再帰のコストは約2.5～3clockくらいの差になると思う。
今時のCPUならもっと差は縮まるだろうし、実際に測った訳じゃないけど
だいたいそのくらいになる筈。
383:デフォルトの名無しさん
15/12/27 12:38:44.94 Zmrinoji.net
>>381
最適化が無くてもループの方が「僅かでも」速いって言い張るお前に
そうじゃない場合もあるって言ったのが>>373
で、それに対しお前はネイティブコードで比較しろっつーから
「最適化無しのネイティブコードで」比較したんだが。
一体お前は何を求めてるんだ？
384:デフォルトの名無しさん
15/12/27 12:38:57.92 BwztOoZh.net
>>382
そこまで解説できる人ならネイティヴコードだと逆転するのわかるでしょ
アセンブリで書けとは言わんけどさ
>>381はすまん
385:デフォルトの名無しさん
15/12/27 12:42:13.97 Zmrinoji.net
>>384
ループ以外の本質的な処理に100clock掛かるとすれば、
数％の差だけどループより再帰のが遅くなるって意見は正しいねって話さね
381については了解
386:デフォルトの名無しさん
15/12/27 12:46:31.99 BwztOoZh.net
>>385
thx
387:デフォルトの名無しさん
15/12/27 13:08:45.42 yWds0j/q.net
>>378
tail callを繰り返しに変換できるようなケースだと
関数呼び出しはコスト高かも知れないが、
ループ版では明示的スタック操作をしなければならない場合、
call,ret相当のことをjpと組み合わせて明示的にやらないといけない。
通常、関数呼び出し後のスタックフレームの確保はcalleeが明示的にやるからループ版と変わらないが、
スタックフレームの開放はretが自動的にやる。
だからコスト的には大差なく、
関数呼び出しの方が有利なケースだってあるはず。
繰り返しの明示的なスタック操作が圧倒的有利にあるのは、
FILOじゃなくてFIFOにしたり戦略が建てられること。
388:デフォルトの名無しさん
15/12/27 13:36:27.64 9aquywWv.net
>>379
お前は何を言っているんだ。
FreeBSDもLinuxも.NETもJavaも赤黒木はループで実装してるぞ。
再帰はプログラムの中に時限爆弾仕込むようなもの。再帰使うやつはテロリスト。
389:デフォルトの名無しさん
15/12/27 13:46:00.90 nuYFrBF7.net
頑張ってバグ入れずに済んでよかったね、としか。
しかもそれで得られる速度の向上も微々たるもの。
390:デフォルトの名無しさん
15/12/27 14:00:50.68 9aquywWv.net
>>389
再帰にしたらバグが減るってものでもないしなあ。
不変オブジェクトを使うから再帰がやりやすいのであって
可変オブジェクトでの再帰はループよりもややこしいところがあるよ。
391:デフォルトの名無しさん
15/12/27 14:27:20.76 +491JRRx.net
>>388
＞赤黒木はループで実装してる
本当か？やればできるものなのか？証拠をみせてみろ
平衡ニ分木であるからスタックもむやみに深くならないし，
正直なところ，可能だとしてループ化するメリットがあるのかね
392:デフォルトの名無しさん
15/12/27 14:37:53.35 9aquywWv.net
>>391
freebsd red black tree source
とかで検索すれば出てくるよ
393:デフォルトの名無しさん
15/12/27 14:44:37.25 BwztOoZh.net
>>390
バグ云々ではなくて、コード数や可読性だと思うが
そもそも再帰呼出を理解出来ない人は論外だが
394:デフォルトの名無しさん
15/12/27 14:47:35.86 kNkpHWWg.net
知らないうちにコードが再帰化してハマりました
のほうが多そう
395:デフォルトの名無しさん
15/12/27 15:00:09.33 9aquywWv.net
>>393
主語がわからん
396:デフォルトの名無しさん
15/12/27 15:03:49.95 BwztOoZh.net
>>395
バグが増える要因はプログラミングソースのステップ数や可読性に左右されるのであって、アルゴリズムは特に関係ないということ
397:デフォルトの名無しさん
15/12/27 15:06:51.61 9aquywWv.net
>>396
アルゴリズムによってステップ数や可読性は変わるよ
398:デフォルトの名無しさん
15/12/27 16:29:32.45 hwv/tSGM.net
>>388
LinuxもFreeBSDも木全体に対して何らかの操作を行うインターフェースを実装してないからあたりまえ。
どっかで見たことある気がしたので探してみたらunbound
URLﾘﾝｸ(code.metager.de)
また一つ、再帰否定バカが無知のエビデンス(笑)を積み重ねていく
399:デフォルトの名無しさん
15/12/27 16:32:53.51 9aquywWv.net
>>398
知らない人がいたから言っただけだよ。
ループで実装されてるんだよーって。
インターフェースを実装してないからとか理屈付けする意味あるのかな。
バカはお前。
400:デフォルトの名無しさん
15/12/27 16:47:04.16 9aquywWv.net
インターフェース？
再帰と関係あるのかな？
わからん。この世はわからんことだらけだ。
401:デフォルトの名無しさん
15/12/27 17:00:20.74 GUkoCLfr.net
> LinuxもFreeBSDも木全体に対して何らかの操作を行うインターフェースを実装してない
？
OSが…インタフェースを…実装？
402:デフォルトの名無しさん
15/12/27 17:01:14.29 Zmrinoji.net
>>399
ねぇねぇ
そのループで実装されてる>>398のコードでも
自前でスタック管理してる訳じゃ無い。
とすると、>>379に対する突っ込みとしては>>388変じゃない？
403:デフォルトの名無しさん
15/12/27 17:03:04.29 9aquywWv.net
>>402
スタック管理の解釈次第だね。>>388が変だと結論できる解釈もありだね。
404:デフォルトの名無しさん
15/12/27 17:03:49.11 9aquywWv.net
>>401
わけわからんよね。
405:デフォルトの名無しさん
15/12/27 17:04:55.68 Zmrinoji.net
>>403
ほう、つまり君はただのループをスタック管理と解釈する訳だね？
406:デフォルトの名無しさん
15/12/27 17:05:12.17 X/TfzIFq.net
最近、書き込みが多くなって
このスレの勢いがすごい
407:デフォルトの名無しさん
15/12/27 17:07:35.61 Zmrinoji.net
>>406
確かに。
>>256から数えて、1日半で150も伸びてる。
408:デフォルトの名無しさん
15/12/27 17:18:58.89 9aquywWv.net
>>405
再帰をループに置き換えるときには
再帰で暗黙的に管理されるスタック上の情報を
明示的に管理する必要がある。それをやるのは面倒だから
赤黒木は再帰で実装されているはずだというのが>>379に関する俺の解釈。
面倒なことないよ、現に赤黒木はループで実装されることが多いよっていうのが>>388
409:デフォルトの名無しさん
15/12/27 17:21:03.25 9aquywWv.net
語句の解釈に文句つけるのはあまり建設的じゃないような・・・。
その先には何もないような・・・。
410:デフォルトの名無しさん
15/12/27 17:24:39.80 9aquywWv.net
クイックソートについても再帰のスタックをそのまま
ループで再現するっていうのはどうかと思うなあ。
末尾再帰は単純なループに変換できる。ループで書くならループらしい書き方をするべき。
411:デフォルトの名無しさん
15/12/27 17:26:57.17 Zmrinoji.net
>>408
ふーむ。
複雑な再帰構造を持つ場合、例えば再帰下降構文解析器みたいに複雑な相互再帰をする場合には
クイックソートの時のように簡単に再帰をループで置き換えることは出来ない。
そして一般に再帰をループで置き換えるならスタックが必要で、
込み入った再帰をスタックを使ってでもループに置き換える奴は居ないだろう。
現に赤黒木をスタック管理をしてでも強引にループで書き直すようなアホは居ないんじゃないの？
というのが>>379に関するこっちの解釈。
それに対し、いやいや赤黒木はループで実装してるんだぜ！ってのが>>388の俺の解釈。
話が噛み合って無くね？ってのが>>402
日本語の問題な気も
412:デフォルトの名無しさん
15/12/27 17:28:09.10 9aquywWv.net
>>411
解釈が違うのなら話が噛み合わないことについては筋が通るかと。
413:デフォルトの名無しさん
15/12/27 17:29:32.88 Zmrinoji.net
>>410
そもそもクイックソートは分割統治法の典型例だからなぁ。
自分を2度呼び出す時点で末尾再帰的じゃないし
ループらしい書き方をするとクイックソートとは呼べないシロモノになると思う
414:デフォルトの名無しさん
15/12/27 17:30:37.18 Zmrinoji.net
あ、勿論クイックソートをもっと単純なループで書き直せるってんなら歓迎するよ！
415:デフォルトの名無しさん
15/12/27 17:33:05.31 9aquywWv.net
>>413
一方の再帰呼び出しは末尾再帰になるっしょ。ループに置換できる。
416:デフォルトの名無しさん
15/12/27 17:33:09.23 Zmrinoji.net
>>412
複数の解釈の仕方がありうるなら、
オレオレ解釈を元に相手をこき下ろす前にやることがあるだろうと