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

レス数が900を超えています。1000を超えると表示できなくなるよ。
1デフォルトの名無しさん
垢版 |
2015/11/28(土) 18:51:38.86ID:Rc2MJzM/
なあ、再帰関数好きな人いる？
2015/11/28(土) 18:55:04.46ID:SbMJmhTc
わくわく
2015/11/28(土) 19:23:33.42ID:mf/sQ31/
嫌いな奴なんて見たことない
2015/11/28(土) 19:30:25.39ID:R0seH/nX
ループで書けるものはループで書く。
再帰使うのは仕方ない場合だけ。
2015/11/28(土) 19:53:36.58ID:R0seH/nX
スタック的なメモリ確保が必要かどうかがループと再帰を使い分ける分岐点じゃね。
末尾再帰最適化とかは本末転倒なイメージ。
2015/11/28(土) 20:05:09.47ID:N2qWmI2+
前スレ
なあ、再帰関数好きな人いる？ パート2
http://peace.2ch.net/test/read.cgi/tech/1441528549/
2015/11/28(土) 20:30:33.91ID:Tq6BVuZs
>>5
ループ実装を隠せるのは大きいよ
抽象化はプログラミング言語の進化のベクトルと一致するからね
2015/11/28(土) 20:39:12.74ID:R0seH/nX
ループより再帰のほうが抽象度が高いと言っている？
そこは俺にはよくわからん。

俺的にはプログラムには必要最小限の機能を使うべきで、
本質的にループより再帰のほうが強力なのだから
可能な限りループを使うべきと思ってる。

もちろん再帰をループにするためにスタックを自前で用意するといったことでは本末転倒だが。
2015/11/28(土) 20:41:49.23ID:R0seH/nX
ツリーの巡回は再帰を使ったほうがいいだろう。
リストの巡回はループでいいんじゃね？
2015/11/28(土) 20:48:22.48ID:Tq6BVuZs
>>8
> 俺的にはプログラムには必要最小限の機能を使うべき
そういうのはコンパイラなりインタプリタなりが頑張るべきところだと思うね
人間はより抽象化された対象を扱うようにするのがモダンなプログラミング言語の方向だし
11デフォルトの名無しさん
垢版 |
2015/11/28(土) 20:52:46.74ID:fFSPKhVt
抽象的なスレだな
2015/11/28(土) 20:58:39.47ID:R0seH/nX
うーん。必要な抽象化は歓迎するが無駄な抽象化は歓迎しないというか。

この例は再帰とは関係ないけどJavaのファイル入出力なんかは
結構複雑な作りになってて無駄な抽象化なんじゃねーのとか思ってしまう。
まあ、俺個人の感想だが。
2015/11/28(土) 21:12:02.73ID:M/Wigktg
アルゴリズムが再帰なら普通に再帰で書く
スタックサイズ制限とかあるなら別だけど
2015/11/28(土) 21:30:44.25ID:10sD81C/
アルゴリズムが再帰であってもクイックソートなど
再帰のままじゃあ使い物にならんものがいくらでも。
2015/11/28(土) 21:32:52.35ID:R0seH/nX
スマンｗ　クイックソートは再帰で書くわｗ
16デフォルトの名無しさん
垢版 |
2015/11/28(土) 21:34:06.03ID:fFSPKhVt
書いたことないくせにｗ
2015/11/28(土) 21:52:35.40ID:R0seH/nX
書いたことはあるけど１０年以上昔の話だな。
これは拾い物だけどクイックソートなんてこれだけのことだろ。

qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
18デフォルトの名無しさん
垢版 |
2015/11/28(土) 22:09:37.77ID:fFSPKhVt
リストの巡回はループでいいんじゃないんかｗ
2015/11/28(土) 22:13:01.33ID:R0seH/nX
クイックソートは単純な巡回とは違うだろ。
だからスタック的なメモリを必要とするかどうかだよ。
20デフォルトの名無しさん
垢版 |
2015/11/28(土) 22:21:22.26ID:fFSPKhVt
ｆｉｌｔｅｒはリストの巡回とちゃうんかｗ
2015/11/28(土) 22:25:38.46ID:R0seH/nX
filterの実装がどうなってるかまでは知らんがな。
22デフォルトの名無しさん
垢版 |
2015/11/28(土) 22:32:42.45ID:fFSPKhVt
知らんなら最初からそう言えやｗ
2015/11/28(土) 22:39:27.55ID:R0seH/nX
なんか変なテンションだなぁ
俺がC++とかでfilter相当の関数書かにゃならんくなったらループで書くよ。
24デフォルトの名無しさん
垢版 |
2015/11/28(土) 22:44:37.77ID:fFSPKhVt
クイックソートはhaskellでfilterはc++なんか？
なんか変な奴だなぁニヤニヤ
2015/11/28(土) 22:49:36.42ID:R0seH/nX
何が変か、わからん。
まあ関数型言語なんかは再帰推奨らしいがあんまり好きになれん。
26デフォルトの名無しさん
垢版 |
2015/11/28(土) 22:59:20.81ID:fFSPKhVt
推奨なんて生易しいもんじゃないで。
理論に囚われすぎて原理主義に陥いった餓鬼共やｗ
2015/11/28(土) 23:05:01.58ID:R0seH/nX
まあ参照透過性とかは原理主義か？という気はする。
2015/11/28(土) 23:29:11.93ID:W0C1+0hV
やっぱハノイの塔は再帰
有能
2015/11/28(土) 23:38:40.71ID:SyBhAT0R
お遊びに使うためのものだね。
再帰なんて。
2015/11/28(土) 23:40:05.61ID:1kauGQoG
>>8
ループでquicksort書いてみてくれ
上のコードと比較で見るだろ
言語は好きに選んでいい
2015/11/28(土) 23:45:06.21ID:R0seH/nX
ループでクイックソート書こうとするとスタック的なものを自前で用意せにゃならんのじゃないか。
めんどくさすぎ。
2015/11/28(土) 23:51:19.94ID:oWRhnwkW
なんかやたらと再帰がお遊びだと連呼する奴がいるが、どういう意図で言っているのか分からん。
お遊び感覚で動くものが作れるのだから、苦労しなくていい分優れているってこと？
2015/11/29(日) 00:02:43.51ID:aMnBRPWz
>>25
関数型言語は変数再代入禁止（のものが多い）から、そもそもループは書けないんだよね
34デフォルトの名無しさん
垢版 |
2015/11/29(日) 00:04:00.34ID:BjpFnvXY
再帰がお遊びだ
再帰がお遊びだ
再帰がお遊びだ

>>32が可哀想だから連呼してあげたよ
35デフォルトの名無しさん
垢版 |
2015/11/29(日) 00:06:31.94ID:BjpFnvXY
あ、意味は「お遊び感覚で動くものを作るな」という事です。
2015/11/29(日) 00:10:17.71ID:aMnBRPWz
動くんならいいんじゃないの？
2015/11/29(日) 00:20:09.59ID:iZIE7tB6
ま〜た関数型コンプレックスのアホが暴れてるのか
2015/11/29(日) 00:24:10.72ID:aMnBRPWz
関数型は関数脳にならないと書けないからねー
手続き脳がしみついてると貶す対象にしかならないよね
39デフォルトの名無しさん
垢版 |
2015/11/29(日) 00:29:56.09ID:BjpFnvXY
お前ら俺を笑い死にさせる気かｗ
2015/11/29(日) 03:56:07.52ID:1KywF+Vz
初めて知った時すごいと思いました
2015/11/29(日) 04:26:32.10ID:RQPUWZLH
せっかく埋め立てたのに何またスレ立ててんのゴミクズ
2015/11/29(日) 06:56:51.27ID:GeZFA4k5
ぼくたん初心者なのでわからんけど僕が今作ってる
関数から値を求める計算プログラムで再起型関数が大活躍してるお
たぶん今僕がやってる書き方が一番きれいだと思うんだけどなー
2015/11/29(日) 15:21:16.51ID:+8PPW4GA
> たぶん今僕がやってる書き方が一番きれいだと思うんだけどなー
いろんな方法で書いてみないと比較できないんじゃね？
2015/11/29(日) 15:49:46.72ID:BHpn4xqB
クイックソートで再帰なんてありえんと
さんざん言われ続けているのに、まだバカが湧いとるんだな。

ライブラリのループ版を使えば何の手間もかからず高速処理ができるのに
わざわざ問題ありまくりの再帰で書くなんてテロ同然の暴挙。
45デフォルトの名無しさん
垢版 |
2015/11/29(日) 16:17:12.78ID:1uX74bCE
>>44
それって結局真の再帰を見たことがないからそう思い込んでるだけだよね。
見せてやるよ、真の再帰ってやつをな。
https://ideone.com/EDtRIH
2015/11/29(日) 16:52:01.83ID:+8PPW4GA
もうソーティングの話は良いよ、仕事で使う大抵の言語ではライブラリとして用意されてるんだから。
2015/11/29(日) 17:09:26.93ID:BHpn4xqB
>>45
再帰じゃあ、１０件程度のソートに控えるという事なんだよな。
2015/11/29(日) 17:29:39.96ID:+8PPW4GA
10件程度のソートならソーティングネットワークによるソーティングが一番速いから
十分少ない要素数に対してはそいつを呼び出して終わりだろ。

書いてないだけだろうけど。
49デフォルトの名無しさん
垢版 |
2015/11/29(日) 20:46:37.54ID:ILoya83o
>>9
俺の見解では、ツリートラバースに再帰を必要とするのはデータ構造に問題があると思うんだよな。
イテレータの実装を考えると再帰はちょっと無理があるんじゃないかと思う。
もちろん出来ないわけではないのだが。
ノードが子ノードを保持するような原始的なデータ構造は良くないのではないか。
50デフォルトの名無しさん
垢版 |
2015/11/29(日) 20:56:36.78ID:ILoya83o
代表的なツリーの一つとしてHTMLがある。
HTMLのフラグメントを切り出し、別のノードの子として加えるような操作を考えるとき、
これはやはりループに軍配が上がると思う。
もちろん、ノードに子ノードを保持するような原始的なデータ構造ではかなりメンドクサイ。
というのもHTMLの一部を切り出す時、ノードの種類によって、ノードの分割や併合が起こる。
再帰と原始的なデータ構造では非常にめんどくさい。
私はこの用途のために直列化ツリー構造というデータ構造を考案した。
（おそらくすでに一般的に使われているとは思うのだが。）
2015/11/29(日) 21:13:17.76ID:TqJ6Jff5
ループは再帰の特別なケースに過ぎない
ループの方が無駄がなく見える事もあるだろう
だが結局はその程度の話だ
2015/11/29(日) 21:25:34.60ID:+8PPW4GA
>>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デフォルトの名無しさん
垢版 |
2015/11/29(日) 21:52:31.69ID:ILoya83o
>>52
ちょっとそのやり方で、HTMLの一部をコピペするコード書いてみて。
2015/11/29(日) 22:12:36.39ID:+8PPW4GA
>>53
一部ってのはどういう風に探すのん？
特定の属性を持ってるタグを探す感じ？
2015/11/29(日) 22:23:46.56ID:euqwPPlR
どういう風に探すか後から指定できる感じで。
56デフォルトの名無しさん
垢版 |
2015/11/29(日) 23:04:51.51ID:ILoya83o
>>54
HTMLのコピペがいつ起こるかというと、ユーザーがその操作をした時なので、
そういう前提で設計してはどうでしょうか。
57デフォルトの名無しさん
垢版 |
2015/11/29(日) 23:13:29.23ID:ILoya83o
HTMLをユーザーの直観に適合する形で操作するのは意外と難しいですよ。
HTMLフラグメントの移動なんてどうですかね。
面白い題材だと思うのですが。
2015/11/29(日) 23:27:31.14ID:euqwPPlR
直列化ツリー構造kwsk
2015/11/30(月) 00:13:02.74ID:vNB8BIt6
>>53
書いてはみたけどウェブプログラミング初心者でごめんよ
https://ideone.com/KO4rFy
2015/11/30(月) 11:10:04.73ID:lmaKmArc
>>59 乙
2015/11/30(月) 14:51:10.36ID:+Ls/PK0X
>>52>>53を繰り返しで書ける人はいないみたいだね。
2015/11/30(月) 20:27:21.92ID:lmaKmArc
そういやC++のstd::mapのイテレータとかってどうなってんるのん？
2015/11/30(月) 21:11:57.14ID:9VRs5I4S
>>62
ノードオブジェクトに親を指すポインターもあって愚直に辿ってる。
赤黒木使ってるのが殆どだから、
レスしてる奴もコード読めない奴の方が多いんじゃないかw
2015/12/01(火) 00:02:40.17ID:M545w8lo
赤黒木って難しいよね、結構。
2015/12/01(火) 13:24:08.38ID:wfTLHpyu
データを吐き出す方法として前方イテレートしかしないの前提ならB+木がループでトラバース出来る上に高速なんだけど
挿入と削除を頻繁にするなら、そしてデータがキャッシュに乗り切らない程度に沢山あるなら赤黒木が高速になる
全部キャッシュに乗る程度の小さなデータ数ならAVL木が高速で
更に小さいならベクタ上にヒープ木でも作ればって話になる。
どの構造でも再帰で列挙出来るけど、ループでAVL木や赤黒木のデータを列挙するのは骨だな
2015/12/01(火) 15:00:00.16ID:p3g6QuXB
再帰・ループの相互変換が難しいとかさあ
アルゴリズムの根本的なところ理解してないだけ

恥ずかしすぎるこのスレ
2015/12/01(火) 16:04:55.52ID:M545w8lo
f(0,b)=b+1
f(a,0)=f(a-1,1)
f(a,b)=f(a-1,f(a,b-1))
2015/12/01(火) 16:39:12.55ID:wfTLHpyu
>>66
>>67をループに変換するのは難しくないんだね？
ちょっとやってみせてよ。
2015/12/01(火) 17:10:17.46ID:p3g6QuXB
rubyで書いてくれないとちょっと。
2015/12/01(火) 17:22:48.32ID:wfTLHpyu
>>69
rubyで書いたぞ
http://ideone.com/B1bDnp
2015/12/01(火) 17:26:42.78ID:alJpKlDN
再帰・ループの相互変換が難しいとかさあ
アルゴリズムの根本的なところ理解してないだけ

無能の>>68 は、勉強しろ。
2015/12/01(火) 17:26:51.00ID:UT6gApH3
uyって式も読めないのかな
2015/12/01(火) 17:33:25.45ID:wfTLHpyu
>>71
無能でーすチッスチッス
インターン先はGoogle(技術職8週間、コンパイラを改良するお仕事)でしたが何か？
今The Art of Computer Programmingの英語版の2巻読んでるんだけど
次に読むべき本は何？

>>72
数式から雰囲気掴むことも出来ない重度のアスペだから仕方ない。
2015/12/01(火) 17:39:29.54ID:UT6gApH3
>>73
uyの残した名言

何で出来ているか？というのは愚問過ぎる

例えばそれを「uy」としましょう
「uy」から派性したＡやＢといった概念から「uy」を辿る事は出来る

例えばこの世界にある「オブジェクト指向」という概念や「量子ビット」といった概念から
「uy」を辿る事が可能なので、
それらで世界が出来ているといった勘違いが可能なのです
でもそれは、一体いくつ「uy」から継承がネストしていて、プログラム等でいえばメソッドが追加されてしまった純粋性のない概念なのでしょうか？
それを知っているのは「uy」だけです

この世界にあるすべての概念は「uy」へと通じているので、
料理人は料理を通じて世界を知り、スポーツ選手はスポーツを通じて世界を知ります

誰も「uy」からは逃げられないんだよ
2015/12/01(火) 17:44:25.62ID:wfTLHpyu
>>74
酉とIDくらい見なさいな

# どうでもいいけど最近障害者3級取ったわ
2015/12/01(火) 17:49:32.14ID:wfTLHpyu
あぁ、俺がuyと同一人物だと勘違いされたのではなく、
uyって人がそういう名言を残したって話か
ごめんごめん
2015/12/01(火) 18:38:14.45ID:UT6gApH3
誰も uy なんかに価値を求めてないのにね
2015/12/01(火) 18:56:25.56ID:wfTLHpyu
でかでかと引用した奴が言うと説得力があるね。
2015/12/01(火) 19:16:25.46ID:UT6gApH3
んでuyちゃんのループ問題はまだ解決しないのかしら
2015/12/01(火) 19:43:22.28ID:M545w8lo
まさにuyがアルゴリズムの根本的なところを理解しているかどうか問われているなｗ
2015/12/01(火) 19:54:09.54ID:UT6gApH3
それな、今までC++スレ読んでてこいつ頭おかしいなとは思ってたけど実力が問われるよな
2015/12/01(火) 19:58:37.14ID:wfTLHpyu
はてさてuyの実力は如何。

# 俺自身の実力はさておき。
2015/12/01(火) 20:19:08.98ID:UT6gApH3
おせぇな uy
2015/12/01(火) 20:49:22.02ID:M545w8lo
uy自力で頑張ってんのか？
なかなか根性あるじゃないか。
俺ならググって解答見てしまうがｗ
2015/12/02(水) 00:55:46.45ID:SG5bn8pD
再帰で書かれた超有名な関数をループにするだけの簡単なお仕事なのに
何ですぐに出来ないんだろうね？

# 全然簡単じゃないからです
2015/12/02(水) 02:08:55.48ID:sE+ivAhG
末尾再帰に書き換えてから蓄積引数を中に押し込んでループにするんだよ。
やり方を書いたのだからきっとuyにもできるはず！
2015/12/02(水) 06:47:05.05ID:UkYZlpUx
>>85
普通に悩んだけど再帰なら一瞬でとけんのに
ループじゃまず何のデータ構造を使っていいかわからん。
2015/12/02(水) 08:22:03.59ID:73uUfhWJ
スタックだろ。
再帰とループ＋スタックは等価。
理屈ではそうだが実際やるのは結構難しいんじゃね。
2015/12/02(水) 08:50:25.92ID:znqtbEKc
>>70
http://ideone.com/KDSDTc

「この程度」が難しいとか言われても
は？　としか思えない

再帰というのは単なるスタック付きのループであって
君たちがどこら辺で躓いているのか理解できないんです
やっぱわからない所がわからない状態なんだろうけど、

つうかＳＴＡＣＫＵって知っていますか？
2015/12/02(水) 09:14:47.18ID:znqtbEKc
ちなみにここ一週間のuyの生活は、朝起きて、ネトゲして朝寝る　です。

ちょうどいま、起きたところではなく24時間起き続けていたので今から寝る前でした

とあるゲームであと１００戦程の対戦をこなし、誰よりも速く称号を獲得しようとしてる最中です
2chのム板なんて頻繁に開いてる暇とかないし結構忙しいんですわ
2015/12/02(水) 09:18:01.80ID:UkYZlpUx
>>89
お見事です。申し訳ありませんでした。
2015/12/02(水) 09:19:02.13ID:UkYZlpUx
自分には分からなかったわ

じゃあ質問なんだけど、再帰は全てスタック+ループで書き換えられるの？
2015/12/02(水) 09:34:55.30ID:UkYZlpUx
連投だけど分かったかも、
再帰で帰ってくるべき値をスタックしておくってことでループ+スタック=再帰なのね
2015/12/02(水) 09:39:29.64ID:SG5bn8pD
>>89
問題のすり替えはいけないな。
俺は「難しくないならやってみて？」って言っただけで
そもそも「再帰のほうがループより圧倒的に簡潔に書けるよね？」って文脈だろ。
君が「難しいから出来るもんならやってみろ」って捉えたかどうかなんざ知らんがおつかれさん
うんうん、言いたいことは分かった。
それで、そのコードのどこら辺が綺麗なの？

ちなみに機械的に変換したのがこちら(rubyじゃなくてごめんよ)
https://ideone.com/XsZh4c
fとhは機械的に変換したという意味では等価だし君のコードとほぼ同じ事をしてるのだけど、
h関数をパッと見て>>69式と等しいって言うのは凄く度胸が居るよね？

>>92
そもそも再帰をどうやってソフトウェア実装してるかというとコールスタック+ジャンプ≒スタック+ループな訳で

# ちなみにスタックの正しいスペルはstack。stackuなんて子は知りませんね。
2015/12/02(水) 09:48:27.56ID:SG5bn8pD
s/69/67/
2015/12/02(水) 10:13:14.24ID:amR8vvu9
>>92
数学的に証明されてる。
2015/12/02(水) 10:15:05.34ID:UkYZlpUx
>>96
そうなのか、、、
ならできるようにならなきゃだな
2015/12/02(水) 11:13:43.91ID:sE+ivAhG
>>92
再帰は機械的にCPSに書き換えることで末尾再帰にできて
そうしたらそれをループに書き換えられる
両方証明されてる
2015/12/02(水) 11:28:01.97ID:SG5bn8pD
>>97
アセンブリ言語によくあるcall系命令の挙動を正確に言えるようになれば
どんな再帰もスタックとループで書けるようになるよ
何しろスタックとループで再帰を表現してるのがcall系命令だからね。

それをそのまま書くとこんな具合に超汚くなるけど。
https://ideone.com/0QXd8O
2015/12/02(水) 12:52:27.49ID:UkYZlpUx
ありがとうございます
2015/12/02(水) 18:34:40.93ID:73uUfhWJ
uyなかなかやるな。
ググって解答見た可能性もあるが、ググれるのも実力のうちだからな。
2015/12/02(水) 20:57:19.51ID:V8iEgN6C
>>90
> ちなみにここ一週間のuyの生活は、朝起きて、ネトゲして朝寝る　です。
悲観することはない（してないかもしれないがｗ）
それも一つの生き方だ
人間の人生などそんなものだ
2015/12/02(水) 22:54:08.11ID:73uUfhWJ
https://ideone.com/upRuBk
アッカーマン関数の展開の様子を書いてみた。
メモリリークあるけど気にしない。
もっとスマートにかけそうな気もするが言語が悪いのかな？
2015/12/03(木) 13:20:12.94ID:lU1L6vf0
誰かループ版と再帰版でベンチマークしてみなよ
2015/12/03(木) 13:56:10.07ID:cYXsvyZR
>>103
俺も書いてみたけど
確かにどう書いてももうちょっとスマートに書ける気がする。
https://ideone.com/BFP2wh
2015/12/03(木) 17:06:18.36ID:Sp77D/ez
>>105
メンドクサイやつだなお前ｗ
2015/12/03(木) 17:30:30.61ID:Sp77D/ez
>>104
ack(3,10)を100回計算させたところ

ループ 3.99秒
再帰 4.50秒

だった。微妙にループが速い。
言語はg++ 最適化あり
2015/12/03(木) 17:54:16.46ID:cYXsvyZR
>>106
でも115行目以降は>>103に比べてスマートじゃない？
アッカーマン関数をより素直に表現している(ように見える)というか。

テンプレートその他がひじょーに面倒臭い事になってるのは認めるよｗｗ
2015/12/03(木) 18:28:15.45ID:Sp77D/ez
>>108
まあそうかも。
言語によってはめちゃくちゃ簡潔に書けたりするのかな、気になる。
2015/12/03(木) 19:58:47.04ID:cYXsvyZR
>>109
ちなみに扱ってるのがアッカーマン関数だけだということとか考慮しつつ短く書くとこうなる。
https://ideone.com/ILFKf2
2015/12/03(木) 20:19:17.43ID:Sp77D/ez
>>110
だいぶスッキリした。
でも入れ子構造がなくなっちゃってるのはちょっと寂しいかな。
2015/12/03(木) 22:49:14.77ID:Sp77D/ez
https://ideone.com/hlWWly
んんん、haskell　気持ちいい！
2015/12/04(金) 18:59:19.58ID:abMxFNxB
きっしょ
2015/12/04(金) 20:33:45.20ID:tAWNVevx
んぎもちいいいいいいいいいい
2015/12/05(土) 12:06:08.66ID:kPO9yvRD
気持ち悪い生き物だなこいつは
116デフォルトの名無しさん
垢版 |
2015/12/05(土) 12:08:54.94ID:75VGJDuj
再起関数難しくて苦手だわ
117デフォルトの名無しさん
垢版 |
2015/12/05(土) 12:38:44.60ID:vOhmiziG
おいらも苦手だわ
2015/12/05(土) 12:50:09.98ID:fWHJ2v3J
アッカーマンを知ったばかりで嬉しくてしょうがないんだろうな
俺くらいになるとどうでもよくなるけど
2015/12/05(土) 14:22:16.61ID:3X0n/q/1
さぁ次は竹内関数(たらい回し関数)だ！
2015/12/05(土) 14:24:24.30ID:FIUesRuL
>>118
アッカーマン関数が原始帰納関数でない証明を頼む。
定義がシンプルかつ一般帰納関数になるように
アッカーマンさんが構成したらしいが。
2015/12/05(土) 16:27:08.57ID:fWHJ2v3J
その問題が解けて嬉しかったんだろうな
2015/12/05(土) 22:53:23.45ID:Ij5oOkBB
たらいのループ化と展開の様子誰か頼む
2015/12/07(月) 01:05:16.16ID:OW/BWl2V
なんで自分でやらない？

再帰関数が好きなんだろ？
2015/12/07(月) 02:12:06.27ID:IGEuV37f
ｗ
2015/12/07(月) 19:27:26.73ID:NCOmGjcr
https://ideone.com/63bZSE

たらいの展開の様子

haskell気持ちEー！

ループ化は誰か頼むわ
2015/12/08(火) 10:04:03.24ID:HiEYAt85
きも
2015/12/10(木) 22:01:50.93ID:ZuWvmJPo
たらいのループ化どうやるかわからん。
2015/12/10(木) 23:27:19.50ID:ZuWvmJPo
んーなんかプログラムカウンタに相当するものをスタックに積まなきゃいけない感じ？
2015/12/11(金) 02:06:03.72ID:6gh0GR4/
https://ideone.com/rO18tw
んーできたっぽい？
コンパイラの吐いたアセンブラとか見ながら書いたからチートしてるけど。
2015/12/11(金) 13:42:03.51ID:Z+QL5bbx
再帰厨はcall命令とjmp命令の違いが分かってから布教してほしい
2015/12/11(金) 18:14:40.60ID:H0NYZxX+
>>130
何言ってるんだ。。
ループで書けば早い、自分でスタック作れば、って言ってるループキチガイに、
命令にもこういうのがあるよ、必要だからあるんだよ。
と教えてあげてはどうだ？
2015/12/11(金) 18:27:07.72ID:FXKTAEC3
＞命令にもこういうのがあるよ、必要だからあるんだよ。

だからどうしたとしか。
基地外宗教を布教するなら、自分でするんだね。
2015/12/11(金) 19:01:03.96ID:DIOiIqvd
callとjumpの中間の命令もあるよな。
call使わない奴はいないのか?
2015/12/11(金) 19:02:56.29ID:6gh0GR4/
中間の命令ってなんだよ？
2015/12/11(金) 19:40:32.13ID:DIOiIqvd
>>134
MIPSのjalとjrとか。
callとretに相当。
jal相当すらなくてpcのレジスタ保存命令しかないのもあった。
2015/12/13(日) 22:44:03.31ID:1ET048aA
ツリーのイテレータってどう書くの
誰か頼む
137uy ◆Qawu9.2l1E
垢版 |
2015/12/14(月) 05:58:59.61ID:0uboKikK
まずはこの手のアルゴリズム抽象化でC++使うのをやめろ
効率悪すぎ
138uy ◆Qawu9.2l1E
垢版 |
2015/12/14(月) 06:02:04.72ID:WJU5GahL
ツリーのイテレータっつうか
ゲームプログラミング的にいえばツリー構造のタスクシステム
ゲームプログラミングしてれば普通に書いてるような低レベルの話
2015/12/14(月) 11:28:00.80ID:v4oN6dOD
>>136
ツリーのイテレータの書き方は大きく分けて3種類ある。
一つ目はイテレータ自身に「どのノードを辿ってきたか」って情報を覚えさせておいてそれを用いる方法
イテレータの空間効率がO(log n)になる代わりにサクセッサの時間効率が平均でO(1)になる。
二つ目はイテレータ自身にキーを覚えさせておいて、一旦そのキーを手繰ってから次のノードを手繰り直す方法
イテレータの空間効率がO(1)になる代わりにサクセッサの時間効率がO(log n)になる。
三つ目は木構造の各葉っぱに次の葉っぱへのポインタを書いておく方法
イテレータの空間効率がO(1)、サクセッサの時間効率がO(1)になる代わりに葉要素のサイズがO(1)増える。
2015/12/14(月) 11:57:14.44ID:S7hw1GZs
イテレータってそんなにたくさん使うもんじゃないし、一つ目がいいかな、俺的に。
141uy ◆Qawu9.2l1E
垢版 |
2015/12/14(月) 15:02:59.78ID:WIf5dtaV
それ種類じゃなくて、全部組み合わせて実装したほうが汎用的じゃねーの

class A
  attr_accessor :up , :key , :list , :data
end

最低でも１と３のup listは無ければ木構造にならないだろ
君の考えは prev(up) と next(list) になってる
2015/12/14(月) 16:34:38.86ID:S7hw1GZs
全部組み合わせたほうが汎用的？
何を言ってるかよくわからん
143uy ◆Qawu9.2l1E
垢版 |
2015/12/14(月) 21:12:22.29ID:WIf5dtaV
まず、ツリーにしたらそれはイテレータとは呼ばないから
ただのツリーを走査する為の関数に過ぎない

「イテレータ」にしか使用できないツリーじゃなくて
一通りの事に使用できるツリークラス作れば？って話
2015/12/14(月) 21:30:28.83ID:lwFUcSQC
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;
}

ノードの親や深さも欲しい時は、スタックに積むノードをオブジェクトでラップして親の参照や深さを持たせればいいかも
2015/12/14(月) 22:23:44.30ID:S7hw1GZs
uyのイテレータの定義がさっぱりわからん。
俺はC++STLのイテレータを想像しているんだが。
uyの言ってるイテレータはなんのイテレータなんだ？
2015/12/14(月) 23:47:42.33ID:S7hw1GZs
uyが言ってるのはツリーで実装されたイテレータということかな？
俺が言いたいのはツリーを巡回するイテレータなんだが？
2015/12/15(火) 02:12:24.45ID:1v1TladX
コレクションを操作するのがイタレータ
148uy ◆Qawu9.2l1E
垢版 |
2015/12/15(火) 02:28:13.41ID:hKbS74r3
センスないと無理
2015/12/15(火) 02:42:41.61ID:1v1TladX
>>147
それを言うなら走査だろと自分で突っ込んどく
150uy ◆Qawu9.2l1E
垢版 |
2015/12/15(火) 02:44:41.16ID:xpC/Gts5
例えば
[1,2,3,4]　←　これをイテレートするのがイテレータだろ？

ツリーは
[1,2,[3,4,[5,6]]]　←　これをイテレートしたいのが作りたいイテレータだろ？


下のはイテレータと表現するまでもなくプログラム中でツリー構造が必要になって、
「ツリークラス」ってのを定義した事あれば、そんなのは標準実装しているレベルのものだから、わざわざツリーのイテレータなんていう半端なものは誰も作らない

作る順序的にまずはイテレータのツリー化じゃなくて、ツリークラスの定義
考えが追いつかないなら好きな順序で作れば良いけど
151デフォルトの名無しさん
垢版 |
2015/12/15(火) 07:32:58.54ID:1zInVUKk
ツリーオブジェクトにtoArray()メソッドを用意すれば
すべて解決すると思うの。
2015/12/15(火) 10:44:59.05ID:kfL23r5/
大富豪プログラミングだなtoArray()
ツリーなんかはサイズが非常にデカくなることがしばしばあるぞ。
2015/12/15(火) 18:13:10.16ID:kfL23r5/
tAo.kQ2STk　ってテレンスタオから取ってんの？
2015/12/15(火) 18:56:51.85ID:kfL23r5/
>>150
汎用的なツリークラス作れって言ってんのか？
javascriptみたいになるんじゃね？
2015/12/15(火) 19:28:58.56ID:1tm7yObV
>>153
違うよ。人間が読める某文字列をキーにしたらその酉が作れる。

ところでさ、どうでも良いんだけど
今話題にしてるのは木構造
>>141が示したデータ構造は無向グラフ
・・・・・・だよね？
156デフォルトの名無しさん
垢版 |
2015/12/15(火) 22:38:36.35ID:WpFCIHcQ
ツリーじゃね
2015/12/15(火) 22:42:50.33ID:kfL23r5/
参照が木構造になってるかグラフになってるかなんて実行時に決まることじゃないのか？
158デフォルトの名無しさん
垢版 |
2015/12/16(水) 03:41:52.77ID:L2apS2Qu
何だこの池沼ｗ
159デフォルトの名無しさん
垢版 |
2015/12/16(水) 09:38:17.31ID:VSvjkteq
ごめん
2015/12/16(水) 21:37:56.27ID:OpCUYLL/
いいってことよ
161デフォルトの名無しさん
垢版 |
2015/12/17(木) 17:19:47.96ID:Szn4FINI
Elixir再帰おもろい
http://confreaks.tv/videos/elixirconf2014-introduction-to-elixir-for-rubyists
162デフォルトの名無しさん
垢版 |
2015/12/18(金) 23:27:00.37ID:95zCi6v5
プログラマはMacを使ってるってマジ？
http://hayabusa3.2ch.net/test/read.cgi/news/1450395043/
163デフォルトの名無しさん
垢版 |
2015/12/19(土) 15:12:57.98ID:iG82T79N
メモメモ
http://izumi-math.jp/M_Harada/kinou_o/kinou_o.pdf
http://examist.jp/mathematics/recurrence-formula/suitei/
http://mathtrain.jp/fibonacci
2015/12/19(土) 16:17:36.19ID:qhiLE2sk
制御では、実行時間が読めないアルゴリズムは使いにくい。
2015/12/19(土) 16:48:17.67ID:mZAnd63z
再帰と繰り返しは相互に変換可能なんだから、再帰で実行時間が読めないならば、繰り返しでも読めない。
こんなじょうしきも知らないの?
166デフォルトの名無しさん
垢版 |
2015/12/19(土) 20:02:11.53ID:owy4KRbC
ごめん
2015/12/19(土) 20:16:05.69ID:hx9j/3Ds
再帰はシステムダウンの危険がある。
処理速度もはるかに遅くなる。

再帰の場合には、こうした実行時間が読めない特有の問題点がある。
2015/12/19(土) 22:02:48.92ID:EjHtX5K0
> 再帰はシステムダウンの危険がある。
そう言う環境ならば、システムダウンの可能性は繰り返しでもある。

> 処理速度もはるかに遅くなる。
ヘボが作った繰り返しは再帰よりはるかに遅い。
2015/12/19(土) 22:20:57.65ID:ZeO9ImyW
>>168
繰り返しと再帰はいっしょなんだろ？
2015/12/19(土) 22:22:37.57ID:EjHtX5K0
>>169
お前、バカなんだろ。
2015/12/19(土) 23:26:42.72ID:25MZJC6Y
末尾再帰に対応した言語が少ないからなぁ
2015/12/19(土) 23:29:13.06ID:srVmyYNw
普通の言語は対応してる
変な言語は使うもんじゃない
173uy ◆Qawu9.2l1E
垢版 |
2015/12/20(日) 01:30:16.73ID:cCXQYS6+
# 1
def f
　if 条件
　　処理
　else
　　f()
　end
end

# 2
def f
　if 条件
　　f()
　end
end


# 3
def f
　case 条件
　when LABEL
　　f()
　end
end


末尾再帰されるパターンわからない奴ｗｗｗｗｗｗｗｗｗｗｗｗっうぃる？　
2015/12/20(日) 01:48:28.93ID:XCzWC+ME
>>172
Java「…」
175デフォルトの名無しさん
垢版 |
2015/12/20(日) 12:14:12.80ID:8RLYRFXT
>>175
漸化式
2015/12/20(日) 12:15:13.29ID:37nsyMmy
それは、無限再帰
2015/12/20(日) 14:49:43.30ID:zNzoBoA2
ID:EjHtX5K0のような白痴ばかりだから
再帰厨だと馬鹿にされることになる。

再帰を愛して使うんだったら、
ループ版にはない深刻なデメリットがある事ぐらいちゃんと注意した上で、
効率や安全性を無視したプログラミングを楽しむべき。
2015/12/20(日) 17:18:50.85ID:37nsyMmy
繰り返しの唯一の利点は回数の制御が再帰よりも容易であること。
これ以外の利点はない。

バカにはそれが理解できないらしいが。
2015/12/20(日) 17:26:49.52ID:8RLYRFXT
馬鹿には出来ませんね
180デフォルトの名無しさん
垢版 |
2015/12/20(日) 18:23:24.49ID:/qKlyz5E
ごめん
2015/12/20(日) 19:26:33.84ID:37nsyMmy
再帰はID:zNzoBoA2のように低知能には理解不能という弱点があるけど
ID:zNzoBoA2のような低知能の出現率は低いので全然問題無い
むしろ低知能者を検出試験としてのメリットの方が大きい
182デフォルトの名無しさん
垢版 |
2015/12/20(日) 22:01:31.82ID:ywvYIxL3
再帰苦手だから何でもかんでもループ使ってすまん
2015/12/20(日) 22:05:01.79ID:A/4Tj+iv
flattenとか難しいよね
2015/12/20(日) 22:51:10.83ID:zNzoBoA2
もし再帰が理解出来たつもりなら、ちゃんとループに直せるぐらいのプログラミング技術は備えなくちゃ。

最低でもそれくらいの技術や知能が無ければ
再帰を楽しむことはできないよ。
2015/12/21(月) 02:17:48.47ID:EKnooMo4
「再帰には深刻なデメリットがある」キリッ
なんて発言する低知能人は再帰を理解してるはずが無い、理解不能なものを怖れている。未開人と同じ。
2015/12/21(月) 09:54:25.69ID:S8kWm1db
ループを恐れるのは、ループにするだけの知識・経験を欠いているから。

その程度じゃあプログラミングの世界からすぐに消えるだけの存在。
再帰厨は、現実で満たされないのでスレで妄想を垂れ流すことしかできないクズ。
2015/12/21(月) 10:52:48.60ID:zel3cCjW
関数内にjmpも好き勝手にやるタイプだからどうとも言わんけど、
再帰否定派はまさか単一のアーキテクチャの話してないよな？
アルゴリズムとして再帰がイケてないって話だよな？
188デフォルトの名無しさん
垢版 |
2015/12/21(月) 14:23:04.48ID:MyhUNItP
そうなのか？
189デフォルトの名無しさん
垢版 |
2015/12/21(月) 14:51:29.83ID:EKnooMo4
>>186
必死で再帰を否定しているバカを弄っているだけで、繰り返しを否定しているわけでは無い

やっぱり低知能なんだな。
190デフォルトの名無しさん
垢版 |
2015/12/21(月) 18:43:17.30ID:u4st+H+L
みなさん、これが「弄ってるって言いたいバカ」ですｗ
191デフォルトの名無しさん
垢版 |
2015/12/22(火) 08:48:59.73ID:kujr6tD9
迷信を信じ込んで再帰を否定してるバカが
深刻なデメリット(爆笑)、例えば
> 処理速度もはるかに遅くなる。
を、実証すればスレ終了するのに。
2015/12/22(火) 11:16:51.41ID:4uBr+2Cy
>>191
そういう超基本的なプログラミング知識が無いのに
なんでプログラム板にいるの？

そもそもプログラミング経験無いだろ、お前。
2015/12/22(火) 12:54:32.04ID:S5fGjlFA
異様に伸びてると思ったら深刻な問題祭りかい

いくらでも例外は挙げられるけど
再帰で書こうがループで書こうが計算時間や空間計算量はそんなに変わらんから
書きやすく、読みやすい方で書いたほうが良いんじゃない？

そんなに変わらないって言うのは十分大きな入力に対して精々2〜3倍以下に納まるって意味だからね。
1時間掛かる処理を20マイクロ秒速くする為にごちゃごちゃ書き換えるのは結構な事だけど。
2015/12/22(火) 14:08:14.84ID:dkSLpih8
はるかと言っても所詮定数倍でしょ。
しかも一桁違うケースは
関数呼び出しがやや高価なスクリプト系の言語でもほとんどないでしょ。
2015/12/22(火) 17:31:14.37ID:qPz15M1W
>>193
いやね，絶対的に再帰でないと書けない，いや非常に書きにくいものはあるのは確かで．
たとえば代数式の解析を非再帰的で記述しろといわれると「はたして出来るのか？？」と逡巡してしまう．
こういう話題があまり発展しないのはどうしたわけですかね

関係ないけどquick-sort を三項演算子とコンマ演算子で書く話題，誰か‥私は挫折した‥
2015/12/22(火) 18:25:40.50ID:/7VurpfC
再帰の深刻なデメリットと言えば、コンパイラ設計者が甘えてる事によってバグを触ったり
異常に速度遅くなるパターンが放置されてたりする事

なんの言語とは言わないけど
2015/12/22(火) 19:03:19.84ID:8Du/ashj
それは再帰のデメリットではなくそういうクソコンパイラしかない言語のデメリット
198デフォルトの名無しさん
垢版 |
2015/12/22(火) 22:57:38.64ID:kujr6tD9
>>192
能書きはいいからとっとと実証しろ。超基本的な知識なんだろ。

「はるかに遅い」とか言ってるバカ仲間のサイトでも良いぞ。
2015/12/22(火) 23:43:59.28ID:qcwFiUkP
>>197
なんか食パン裏返してこっちが表だとか必死に言ってるようなレスだな
2015/12/22(火) 23:48:59.13ID:8Du/ashj
>>199
食パン裏返してんのはお前のほうだよw
201デフォルトの名無しさん
垢版 |
2015/12/22(火) 23:51:52.68ID:2TsBrERG
>>198
へい。再帰が130倍時間がかかるエビデンス。
http://www.fastpic.jp/images.php?file=1406113032.png
2015/12/23(水) 01:07:26.60ID:xKy7nhKt
食パンの裏はどっち側だよ
203デフォルトの名無しさん
垢版 |
2015/12/23(水) 01:25:49.85ID:zjRNfIWb
>>201
こうするとなかなか興味深いことになるね。
本当に興味深いと思ってるだけで他意は無いよ。

fun_rec(){
if [ $1 -gt 5000 ] ; then
time fun_for
return
fi
fun_rec $(( $1 + 1 ))
}
204デフォルトの名無しさん
垢版 |
2015/12/23(水) 02:04:18.65ID:3NYqkGXc
>>203
たしかにおもしろい。
再帰の深さに比例して時間がかかる。
再帰が深くなると処理に時間がかかるようになるのか、
別の時間を測ってしまっているのか。わからん。これはわからん。
205デフォルトの名無しさん
垢版 |
2015/12/23(水) 07:21:41.71ID:fM9ORKUP
>>201
必死で再帰否定してるバカは知能が低いというエビデンス乙

シェル関数は呼び出しのたびに名前解決するのでペナルティが大きい
206デフォルトの名無しさん
垢版 |
2015/12/23(水) 07:28:38.71ID:fM9ORKUP
Cの場合は入った時にフレーム作成と出る時にフレーム復元
c86なら、レジスタ操作4ステップ(複合命令なら2ステップ)だ。
名前解決なんかリンク時に終わってる。
2015/12/23(水) 08:47:35.90ID:2F8TsTF+
最近の関数呼び出しは引数をスタックに積まずにレジスタ渡しみたいだから
再帰で何段ネストしちゃっててもレジスタに収まってる限りは爆速なんじゃね
2015/12/23(水) 08:59:40.61ID:r+tlUph/
名前解決まで計算時間に含めるなら
もう再帰云々じゃなくて長大な再帰なしの一つの関数で全部こなせって話になるんだがな

>>207
いや、そうはならない。
レジスタの退避が必要になるから、自己再帰するならどっちにしても同じだけpush/popは必要になる。
最適化が掛かったらその限りじゃないけど。
2015/12/23(水) 09:02:09.80ID:QhR+qVh6
>>205
呼び出しだけじゃなく参照もね、iの。
localでもスタックフレームなめてるのかな?
2015/12/23(水) 09:10:56.81ID:2F8TsTF+
>レジスタの退避が必要になるから

そうかなー
211デフォルトの名無しさん
垢版 |
2015/12/23(水) 09:15:53.17ID:fM9ORKUP
>>209
スタッフフレームは再帰に必要なステップだから、再帰のペナルティとしてあえて受け入れた。

シェルスクリプトを持ち出した時点で「スタックは容量制限が厳しい(場合もある)リソース」
を自分で否定しちゃうところが再帰否定してるバカが低知能であるもう一つのエビデンス(笑)

(場合もある)を知らないのか、教わってないのか知らないが、全ての場合だと思い込んでるところもバカの、特徴だね。
2015/12/23(水) 09:50:24.66ID:r+tlUph/
>>210
再帰で書いた何の変哲もないフィボナッチ関数をビルドしたケースを示すよ
https://gist.github.com/pixie-grasper/ba2d0ade523b8599c182
gccではr12を、clangではraxを、rbp/rbxの他に退避してるのが分かる。
2015/12/23(水) 11:20:43.15ID:2F8TsTF+
対比先もレジスタにすればいいのにね
2015/12/23(水) 11:25:42.60ID:r+tlUph/
そんな事をすると
既に退避させてある値を別なレジスタに退避させてから、退避させたい値を退避するコードを吐く羽目になるけど
レジスタが最低でも加算無限個無いと出来ないからね。仕方ないね。
2015/12/23(水) 11:53:11.24ID:/Snk+v/P
externしていないstatic関数とかならレジスタ渡しもふつうにある。
もちろんCランタイム・コンパイラによる
2015/12/23(水) 12:07:45.20ID:r+tlUph/
>>215
いつの時代の話をしてるのか分からんのだけど、所謂Intel系の64bit環境(amd64)だとレジスタ渡しがデフォルトだよ。
https://en.wikipedia.org/wiki/X86_calling_conventions#List_of_x86_calling_conventions
217デフォルトの名無しさん
垢版 |
2015/12/23(水) 12:46:44.21ID:2bKYe5U2
>>204
bashはダイナミックスコープだから再帰の深いところでは
変数の参照に時間がかかるのかな。いまはその辺を疑ってる。
2015/12/23(水) 13:07:16.81ID:cGrC7qed
>>197
ｗ
2015/12/23(水) 16:35:42.36ID:u0B3Sjd8
だいたい再帰で問題が無いなんて
クイックソートで再帰が役に立たない事すら知らないってことか？

処理件数が増えたら速度の差なんて、何万倍どころじゃないし。
2015/12/23(水) 16:37:36.04ID:xKy7nhKt
>>219
何が言いたいのかわからん…
2015/12/23(水) 16:45:18.40ID:uhnrlQdn
>>219
ファーｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
222デフォルトの名無しさん
垢版 |
2015/12/23(水) 17:05:56.20ID:fM9ORKUP
>>219
じゃ、これを10000倍高速化して実証してよ。
http://svnweb.freebsd.org/base/stable/10/lib/libc/stdlib/qsort.c?revision=256281&;view=markup
223デフォルトの名無しさん
垢版 |
2015/12/23(水) 17:15:03.86ID:2bKYe5U2
>>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デフォルトの名無しさん
垢版 |
2015/12/23(水) 17:27:00.65ID:fM9ORKUP
>>223
10000倍高速化の比較対象はそれでも良いぞ。
2015/12/23(水) 17:56:16.45ID:ZCUCTd42
一万倍とかｗｗｗｗ
どこをどうやったら一万倍差がつくんだ
226デフォルトの名無しさん
垢版 |
2015/12/23(水) 18:11:01.01ID:2bKYe5U2
>>225
クイックソートの最悪の時間計算量はn^2なので
データによってはとても大変なんよ。
2015/12/23(水) 18:27:35.24ID:PjxVSF2U
アルゴリズムの抽象化に静的言語使うチンパンとか話にならないから(´・ω・｀)


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デフォルトの名無しさん
垢版 |
2015/12/23(水) 18:50:34.28ID:fM9ORKUP
>>225
最低10000倍ね。笑

>>219
>処理件数が増えたら速度の差なんて、何万倍どころじゃないし。

あ、小学生のように0.0001万倍とか言い逃れるかも。爆笑
2015/12/23(水) 21:36:40.93ID:L95mHKNc
>>227
http://hissi.org/read.php/tech/20151223/UGp4VlNGMlU.html
2015/12/23(水) 21:47:18.77ID:ZCUCTd42
万倍高速化はよｗｗｗ
231デフォルトの名無しさん
垢版 |
2015/12/23(水) 22:10:25.42ID:fM9ORKUP
ID:u0B3Sjd8
10000倍の高速化まだ? 常識的で簡単そうな口ぶりだったけど。
232デフォルトの名無しさん
垢版 |
2015/12/23(水) 22:12:02.95ID:fM9ORKUP
万は間違いだったとしても、最低でも倍速は楽勝なんだろ。
233デフォルトの名無しさん
垢版 |
2015/12/23(水) 22:29:26.28ID:zjRNfIWb
>>232
速度以前に >>223 は簡単にスタックオーバーフローするよ。
それを防ぐ方法を教えてやってよ。
2015/12/23(水) 22:33:54.64ID:QhR+qVh6
>>233
繰り返し版が明示的スタックに使うヒープと同サイズに
マシンスタックの上限を変更すればOK
235デフォルトの名無しさん
垢版 |
2015/12/23(水) 22:55:30.83ID:zjRNfIWb
いや、君に言ったわけじゃないし、最適化を教えてやれってことなんだけど。
236デフォルトの名無しさん
垢版 |
2015/12/23(水) 23:35:43.46ID:fM9ORKUP
>>233
バカなの? >>222読めないの?
10000倍の高速化まってんだから、くだらねー横槍入れないように。
お前が10000万倍高速化するならかまってやんよ。
2015/12/23(水) 23:43:11.94ID:QhR+qVh6
>>226
繰り返しか再帰かに関係ないがな。
pivotの選び方次第だろ。
それは明示的にスタック使う繰り返し版クイックソートでも同じ。
238デフォルトの名無しさん
垢版 |
2015/12/23(水) 23:58:42.12ID:2bKYe5U2
>>237
あたりまえ
2015/12/24(木) 01:02:26.01ID:aanAAc0G
>>238
>>225に対するレスとして
>>226はおかしいだろ。
気にならんのか?
2015/12/24(木) 01:08:56.14ID:VDgCwlJn
>>239
何を言っているのか意味がわからない…
2015/12/24(木) 06:51:58.79ID:2ShnOfV/
>>240
最悪パターンでもよいから、10000倍高速化しろよ。
2015/12/24(木) 08:02:14.94ID:Ecjqx/Av
スキルない人間をいくら叩いても何も出てこないのに
ここは動物園かよ
243デフォルトの名無しさん
垢版 |
2015/12/24(木) 08:55:59.49ID:Q6U3kr4L
黒魔術師は再帰関数が大好き
2015/12/24(木) 09:09:51.37ID:Zs2o0pyD
黒魔術師はマクロを生成するマクロも大好き
245デフォルトの名無しさん
垢版 |
2015/12/24(木) 11:57:48.07ID:2ShnOfV/
再帰を必死に否定しているバカの主張

1 スタックが制限の厳しいリソースである環境が全てだと思い込み、再帰の致命的なペナルティだと主張する
2 シェル関数呼び出しをエビデンスとして、再帰が130倍遅いと主張する
3 再帰版のqsortは数万倍遅いと主張するが、数万倍速いはずの非再帰版を示さない
4 知能が低く再帰を理解できない。それをもって再帰は難解と主張する。
246デフォルトの名無しさん
垢版 |
2015/12/24(木) 14:54:05.30ID:QIUsopJK
>>245
そうやって執拗に絡むのもはっきりいって馬鹿丸出しだよ。
せっかく相手がクイックソートのコードを書いてくれたんだから
そのコードの問題点を指摘する方が賢そうに見えると思ったんだけどね。
2015/12/24(木) 16:38:25.55ID:2ShnOfV/
>>246
さらなる意味不明なバカが出てきたな。
コード出したのは再帰を必死で否定してるバカじゃないぞ。
248デフォルトの名無しさん
垢版 |
2015/12/24(木) 17:26:51.73ID:ri4CJahT
最初期は再帰をサポートしてなかった計算言語があるらしい
2015/12/24(木) 18:44:44.88ID:W/SZtGXt
今はハードウェアレベルで再帰が実装されてるからな。
それを思えばいかに再帰が本質的にプログラミングに必要とされてるかってことだな。
2015/12/24(木) 20:04:26.21ID:aanAAc0G
計算可能性を探求する試みにおいて最初に出たのが、
エルブラン・ゲーデルの一般帰納関数だからね。
次がラムダ計算。
その次がノイマン型計算機直系の先祖であるチューリングマシン。
2015/12/24(木) 20:37:54.33ID:Hny3MC9I
10000倍だっておとなしいぐらい。

再帰だと落ちまくるから∞倍だって当たり前だろ。
2015/12/24(木) 20:46:14.21ID:W/SZtGXt
メモリ足りないなら動かないのは再帰もループも変わらんだろ。
ループのほうが本質的にメモリ使用量少なくなるとかなら話は変わってくるが。
2015/12/24(木) 20:58:31.47ID:2ShnOfV/
これだね。本当に知能が低い。
> 1 スタックが制限の厳しいリソースである環境が全てだと思い込み、再帰の致命的なペナルティだと主張する
2015/12/25(金) 18:57:10.38ID:IqCVGu/8
＞再帰もループも変わらんだろ。

なんで試してみないんだ？
再帰とループでクイックソート

ループ方式なら、データが何千万件あろうと無問題
2015/12/25(金) 19:44:32.39ID:TZMq+uAI
>>254
ループのソース晒してみろや
2015/12/26(土) 05:53:41.97ID:QzXIU7/C
覚えたての知識を使ってレスバトルするだけのスレなんていらねーから
2015/12/26(土) 08:33:15.25ID:oIXuKyHb
いらないスレを使って自分の意見を垂れ流すとか有効活用乙としか
258デフォルトの名無しさん
垢版 |
2015/12/26(土) 10:19:35.68ID:EXUTS9i+
そういう初心者の遊び場もあっていいと思うけどなあ
2015/12/26(土) 12:54:13.38ID:KD7gR2Cz
>>252
再帰の方は、関数呼び出し大量に発生するから、リターンアドレス待避とレジスタ待避に、メモリーが喰われる。
2015/12/26(土) 13:36:54.41ID:oIXuKyHb
>>259
ループの方は今どの範囲についてソートしているのかという情報が大量に発生するから同じ議論が成り立つ訳だが。
261デフォルトの名無しさん
垢版 |
2015/12/26(土) 13:40:32.70ID:6n5NtJkM
>>260
ループはヒープ、再帰はスタック
つまり、ヒープとスタックがぼくらを助けてくれるんだ！
262sage
垢版 |
2015/12/26(土) 15:02:23.21ID:Igcba1qr
>>254
>>222(再帰版qsort)で5000万件ソートしてみた。楽勝で終了する。
必死で再帰を否定しているバカが低知能だという事がまた証明されてしまった。
頭が悪いって本当にかわいそう。
2015/12/26(土) 16:45:09.37ID:YV12MLKo
>>262
再帰版でうまくいくのだったら非再帰版ではもっとうまくいく，という発想はないのかね？
2015/12/26(土) 16:59:02.38ID:oIXuKyHb
>>263
うまくいくって言ったって高々定数倍速くなるだけだろ？
非再帰版を書いたり保守したりするコストより新しい速いマシンを買ったほうが安く上がるって発想は無いのかね？
265デフォルトの名無しさん
垢版 |
2015/12/26(土) 17:27:47.02ID:Igcba1qr
>>263
知能障害者って本当にかわいそう。
5000万件でソート出来てるってことは、「再帰はスタックあふれる」という迷信が嘘だという発想には至らないのかね。
クイックソートの深さの制御はすでに研究し尽くされてて、全然問題ないんだよ。
266デフォルトの名無しさん
垢版 |
2015/12/26(土) 17:37:15.54ID:Igcba1qr
あっ、繰り返し版は10000倍速いんだっけ? (爆笑)
早く実装コードみたいなあ。
267デフォルトの名無しさん
垢版 |
2015/12/26(土) 18:11:47.33ID:6n5NtJkM
>>266
そんなに実装したいのなら教えてしんぜよう。
5000万件で >>201 を実行してみたまえ。
再帰呼出しというのは効率が悪いとても頭の悪いやり方なんだよ。
268デフォルトの名無しさん
垢版 |
2015/12/26(土) 18:13:42.40ID:EXUTS9i+
シェルスクリプトを証拠として使うのは笑ってしまうからやめろ
269デフォルトの名無しさん
垢版 |
2015/12/26(土) 18:16:50.75ID:6n5NtJkM
>>268
反論できないのな？じゃあお前の負けってことで。
270デフォルトの名無しさん
垢版 |
2015/12/26(土) 18:22:25.08ID:EXUTS9i+
野次飛ばしてる観客相手に勝利宣言も笑うからやめろ
おまえはプロレスのヒール役か
2015/12/26(土) 18:26:32.21ID:gy7QXsCA
＞高々定数倍

そんな安全なもんじゃあねぇ。
データが増えれば差も増大。
272デフォルトの名無しさん
垢版 |
2015/12/26(土) 18:38:59.41ID:Igcba1qr
>>267
ぷぷぷぷ
知能障害者は>>201をクイックソートと呼ぶのか?
273デフォルトの名無しさん
垢版 |
2015/12/26(土) 18:41:57.44ID:Igcba1qr
>>271
ミジメすぎるぞ。クイックソートのスタック消費量はlog nに抑える事が可能。
こんな基本的な事を知らないから数千万件はソート出来ない。キリッ

とか、赤面な発言しちゃうんだよ。
274デフォルトの名無しさん
垢版 |
2015/12/26(土) 18:47:36.31ID:Igcba1qr
ちなみにglibcのqsort(これは非再帰)も同じ手法で自前スタックを管理してる
知能が低いって本当にかわいそう。

https://sourceware.org/git/?p=glibc.git;a=blob_plain;f=stdlib/qsort.c;h=04c25b984f74a8f738233cc6da8a738b6437833c;hb=b8079dd0d360648e4e8de48656c5c38972621072

/* 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デフォルトの名無しさん
垢版 |
2015/12/26(土) 19:02:41.83ID:6n5NtJkM
>>272
バカかお前は。ボウフラサイズの脳ミソしか搭載してないのか？
ただの繰り返しでさえ130倍の差があるのだから
クイックソートを実装したらそれ以上の開きがあるのは自明だろうが。
2015/12/26(土) 19:08:33.46ID:YV12MLKo
>>273
log n は発散するんだが‥
2015/12/26(土) 19:09:07.52ID:oIXuKyHb
>>275
バカはお前だ。シェルスクリプトでクイックソートを実装するなんて誰がするか。
sortプログラムを使え。

ちなみにシェルスクリプトの場合、関数呼び出しはそれ自体がスタックの深さをnとしてO(n^2)くらいの計算時間を持つっぽい。
278デフォルトの名無しさん
垢版 |
2015/12/26(土) 19:09:41.46ID:Igcba1qr
>>275
ぷぷぷ。知能障害は本当にかわいそう。
qsortの繰り返し版は関数呼び出しの代わりに自前でスタック管理しなきゃならないんだよ。
10000倍高速化の実証コードはよ。
2015/12/26(土) 19:10:23.62ID:oIXuKyHb
>>276
確かに、うん、確かに、非常にゆるやかに発散するね。

n=2^64としてもlog nは64だけどね。
定数と変わんないレベルだよね。
280デフォルトの名無しさん
垢版 |
2015/12/26(土) 19:11:25.60ID:6n5NtJkM
>>277
実装できないのな？無理なのな？はい論破。
281デフォルトの名無しさん
垢版 |
2015/12/26(土) 19:14:27.33ID:6n5NtJkM
>>278
>>201 がすべてを物語っている。
これが何よりの証拠。再帰がとてつもなく効率が悪いことを
つまびらかにしてみせた。ここに来て見てみぬふりは通用しない。
エビデンスもきちんと示されている。もはや知らぬ存ぜぬでは済まされない。
282デフォルトの名無しさん
垢版 |
2015/12/26(土) 19:14:30.05ID:Igcba1qr
>>280
何万倍も高速だっ。キリッ。
って主張してる奴に実証責任があるんだが

ガイジにはわからないの?
2015/12/26(土) 19:16:21.04ID:oIXuKyHb
>>280
練習のためなら兎も角、シェルスクリプト「だけ」でソーティングなんてやる意味が無い。
ループだろうと再帰だろうとね。
理由は遅いから。
ループで組んだとしても、非常に遅いから、実装するだけの意味が無い。
sortを呼べばCで書かれた非常に高速でスケーラブルなソーティングが出来るから、普通はそっちを使う。

さぁ君は一体何を論破したというのだい？
284デフォルトの名無しさん
垢版 |
2015/12/26(土) 19:16:31.66ID:Igcba1qr
>>281
障害児くん
10000倍と130倍って、どっちがどれだけ大きいかわかる?
285デフォルトの名無しさん
垢版 |
2015/12/26(土) 19:17:31.65ID:6n5NtJkM
>>282
>>201 で完全に証明してみせた。
反証する責任がお前にあるとは俺は思わないよ。
俺は自分の都合の良いように他人に責任を押し付けるなんて
卑劣な真似はできない。俺はただの真実の探求者。
2015/12/26(土) 19:21:05.64ID:oIXuKyHb
>>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デフォルトの名無しさん
垢版 |
2015/12/26(土) 19:21:48.42ID:6n5NtJkM
>>284
ボウフラ並みの脳ミソをメダカにでも食われたのかお前。
頭悪いにも程があるだろうが。こんな鶏頭野郎の
相手する俺の身にもなれ。なんていいやつなんだ俺。
聖人君子としか言いようがないわ。>>201 は5000回の繰り返しだ。
5000回の繰り返しでさえ130倍の開きがあるのだから回数が
増えれば差は開く一方だ。だから、>>267 で5000万と言ったのだよ。
2015/12/26(土) 19:23:23.36ID:PvF8tuZ2
霊がいるのかいないのかは判りませんが
人間の目が無いものを見ることがあるのは事実です
289デフォルトの名無しさん
垢版 |
2015/12/26(土) 19:23:40.75ID:EXUTS9i+
差は開くだろうけど比も開くのか？
2015/12/26(土) 19:23:44.50ID:oIXuKyHb
>>287
5000回の再帰で130倍の差が開いた訳じゃなくて、
深さ5000の関数呼び出しで130倍の差が開いたって事を理解してる？

5000万要素のクイックソートなら最良のケースで深さ25の再帰だからね？
130倍どころか2倍にもならないからね？
291デフォルトの名無しさん
垢版 |
2015/12/26(土) 19:23:54.44ID:6n5NtJkM
>>286
クイックソートを実装して試したのか？あ？
だれが実装するかと言っていたのと矛盾するだろうが。
つまり、君は嘘をついている。ゆえに俺が言ってることの方が正しい。はい論破。
292デフォルトの名無しさん
垢版 |
2015/12/26(土) 19:26:45.13ID:6n5NtJkM
>>289
当たり前だろ。小さな町の町長が東京の都知事になって
仕事をこなせると思うか？数が増えるほどにコストは増大するんだ。劇的にな。劇的にだ！
293デフォルトの名無しさん
垢版 |
2015/12/26(土) 19:29:40.16ID:Igcba1qr
障害児発作を発症中
294デフォルトの名無しさん
垢版 |
2015/12/26(土) 19:31:02.17ID:EXUTS9i+
>>292
すまん、その例えどこまで信用していいか分からないからそういうの語るときは式でお願い
295デフォルトの名無しさん
垢版 |
2015/12/26(土) 19:31:21.63ID:6n5NtJkM
>>290
ヤってみたのか？ヤったのか？ヤってから言えや！
さっさとクイックソートのコード提示しろよ！
いつまでグズグズ言ってりゃ気が済むんだ
俺はお前がクイックソートをシェルで実装するのをあとどれだけ待てばいいわけ？
296デフォルトの名無しさん
垢版 |
2015/12/26(土) 19:32:53.62ID:Igcba1qr
>>295
再帰は数万倍遅いといったお前が実証しろよ
297デフォルトの名無しさん
垢版 |
2015/12/26(土) 19:33:00.02ID:6n5NtJkM
>>294
log2・5000 : log2・5000 ? 30 ⇒ log2・50000000 : 10^4 ? A
QED.
298デフォルトの名無しさん
垢版 |
2015/12/26(土) 19:34:26.18ID:Igcba1qr
1万倍高速なクイックソートはよ
299デフォルトの名無しさん
垢版 |
2015/12/26(土) 19:34:37.78ID:6n5NtJkM
>>296
俺は >>201 で示したし、それで十分に満足の行く結果を得た。
>>201 に不満だというのならそれを超えるものをお前が書け。自分でやれ。
他人にやらせるっていうのは俺の常識からは考えられない。
300デフォルトの名無しさん
垢版 |
2015/12/26(土) 19:35:10.69ID:6n5NtJkM
>>298
お前がやるんだ。お前が言い出したことだろうが。
2015/12/26(土) 19:35:32.98ID:oIXuKyHb
>>295
どうして俺が実装しなきゃならないわけ？
数万倍遅いって言い出した奴が実証のためにコードを提供するのが筋だろ？
302デフォルトの名無しさん
垢版 |
2015/12/26(土) 19:42:36.24ID:6n5NtJkM
>>301
そんな筋は通らない。実証コードが欲しいといいだしたのは
お前なのだからお前が自分で書け。言い出しっぺの法則は
プログラマを始め科学的論証に関わる人間すべてに通じる基本原則だ。
どうやればそれを確認できるかという手順も道筋も結論も示した。
自分の満足のいくものが欲しいのなら自分で行動しろ。
他人の足にしがみつくな、気持ち悪い。
303デフォルトの名無しさん
垢版 |
2015/12/26(土) 19:44:38.98ID:6n5NtJkM
１万倍の実証コードとか言い出しといて書かないってどういうことよ？
他人に頼りっきりってどういうことよ？
夢があるのなら自分で叶えろよ
親の足かじってんじゃねえぞニート野郎
2015/12/26(土) 19:50:48.20ID:oIXuKyHb
>>302
IDをよく見ろ。俺は実証コードが欲しいだなんて一言も言ってない。
305デフォルトの名無しさん
垢版 |
2015/12/26(土) 19:51:36.37ID:EXUTS9i+
>>297
何この記法初めて見た
もしかして情報界隈では常識なのか？
306デフォルトの名無しさん
垢版 |
2015/12/26(土) 19:51:49.58ID:Igcba1qr
>>219
親のスネかじってんじゃねーぞニート野郎
とっとと数万倍速いクイックソートの実証しろよ
307デフォルトの名無しさん
垢版 |
2015/12/26(土) 19:54:34.25ID:Igcba1qr
ID:6n5NtJkMは発狂して「再帰は数万倍遅い」発言をウヤムヤにしたい模様
でも、まだ300レス。先は長いぞ。頑張れ。
2015/12/26(土) 19:56:25.26ID:oIXuKyHb
>>305
俺も見たこと無い。
一瞬、三項演算子にも見えるけど順序がおかしいし。
309デフォルトの名無しさん
垢版 |
2015/12/26(土) 19:57:11.33ID:6n5NtJkM
>>304
言ったかどうかは問題じゃない！
お前はクイックソートで1万倍の差があるのか確認したい、
それを確認する手段としてシェルでクイックソートを実装すればわかる
ということを俺は示したんだよ。それだけわかってればいいよもう！
310デフォルトの名無しさん
垢版 |
2015/12/26(土) 20:00:13.46ID:6n5NtJkM
>>308
?はただの文字化けだぞ。
数理式計算量証明の理想解近似法を大学で習ってたらわかるだろ。
情報科学の基礎中の基礎だし。
2015/12/26(土) 20:02:01.94ID:oIXuKyHb
>>309
いいや、そもそもそんな事は望んでない。よく読め。
俺が言いたいのは、1万倍もの差が出るなんて事は理論上ありえないって事だ。

それでも尚、実際に1万倍の差が出ると言い張るのであれば
それを実証するコードを君が示すべきだよね？
312デフォルトの名無しさん
垢版 |
2015/12/26(土) 20:03:37.49ID:EXUTS9i+
>>310
すまん、その文字化けしてるところ元は何だったのか教えてくれ
O?
313デフォルトの名無しさん
垢版 |
2015/12/26(土) 20:05:55.80ID:6n5NtJkM
>>311
だから、俺は示したって言ってるだろうが！
>>201 でくっきりはっきりと証明してみせただろうが。
それで満足できないというのであれば、満足の行くコードを見たいというのであれば
お前がそれを書くべきだ！それが論理的検証というものだ。科学的な姿勢というものだ。
他人の論文に満足できないと言ってるばかりじゃ学会では一切評価されないよ。
それを超える論文を自分で書いてこれでどうだと魅せつけるべきだ。
君はシェルでクイックソートを書くべきなんだ！！
314デフォルトの名無しさん
垢版 |
2015/12/26(土) 20:06:59.46ID:6n5NtJkM
>>312
掛け算の掛けるだ。
右側では1万倍になってるのがわかっていただけると思う。
2015/12/26(土) 20:09:01.51ID:YV12MLKo
>>281
>>205
2015/12/26(土) 20:09:33.38ID:YV12MLKo
>>285
>>205
2015/12/26(土) 20:13:31.65ID:oIXuKyHb
>>313
いいかい？
君は「示した」と何度もはっきり発言してはいるけど、実のところ何も示しちゃいないんだ。
318デフォルトの名無しさん
垢版 |
2015/12/26(土) 20:22:57.69ID:6n5NtJkM
>>315
バカかお前は。大脳半球が全損して産まれて来たのか？
名前解決に時間がかかるとするならば、名前解決まで含めて再帰呼出しだ。
外務省はシリアへの渡航を自粛するよう日本国民に通告しているが、そんな不安な情勢の中、
「シリアが危険なんじゃないテロリストが危険なんだ」と言って
意気揚々とシリアに出かけていく頭の中お花畑野郎と同じだろうが。
お前が言ってるのはそれと全く同じこと。
シリアという地域でテロの被害に遭う確率が高いから外務省は渡航を自粛するように
必死に呼びかけているんだ。少しでも日本の国民がテロの被害に遭わないよう骨身を削って
頑張っているんだ。再帰呼出しでプログラム事故に遭う確率が高いから俺は再帰を自粛するよう
呼びかけているんだ。外交官としての俺の立場に立って再考してみろ。お前がどれだけ
愚かなことを言っているか今一度ようく考えてみることだな。
319デフォルトの名無しさん
垢版 |
2015/12/26(土) 20:24:31.77ID:EXUTS9i+
やべえ記号わかってもなお式の意味わかんねえw
320デフォルトの名無しさん
垢版 |
2015/12/26(土) 20:25:46.83ID:Igcba1qr
障害児は
シェル関数呼び出しはwhileより130倍遅い
と
再帰版のクイックソートは何万倍も遅い
が等価らしい

必死で再帰を否定しているバカが低知能であることのエビデンスがまた一つ明らかになってしまった
321デフォルトの名無しさん
垢版 |
2015/12/26(土) 20:27:35.19ID:6n5NtJkM
>>317
>>201 の画像が見えないのか？俺はエビデンスをしっかりちゃっかりくっきりまるっきり示したぞ。
お前はアイマスク付けて前が見えないと言ってるだけのただのうつけ者。話にならない。
322デフォルトの名無しさん
垢版 |
2015/12/26(土) 20:30:11.96ID:EXUTS9i+
もしかしてだけどさ、もししてだけどさ、>>201で示されてることってシェル関数呼び出しがシェルwhileより130倍遅いことだけじゃね？
323デフォルトの名無しさん
垢版 |
2015/12/26(土) 20:35:37.94ID:6n5NtJkM
>>322
おいおいいい加減にしろよナメクジ野郎。
自らの関数を呼び出すことを再帰と言うのだろうが。
関数の呼び出しが遅い、すなわち再帰の効率がとてもよろしくないということだ。
テロリストが民間人を殺害するのならば、テロがはびこっているシリアには行くべきじゃないということだ。
お前、後藤さんのご家族の前で後藤さんが悪いって言えるのか？後藤さんは悪いよ。
とても危険なところと知りつつシリアに言ったんだから。だけど、それをご家族の前で言う意味がないよね。
324デフォルトの名無しさん
垢版 |
2015/12/26(土) 20:38:45.39ID:6n5NtJkM
再帰を使うっていうのはテロリストの前に自らの首を差し出すことと同義。
何があっても文句言うな。そして周囲の人間をその愚行に巻き込むな。
悲しませるな。俺はお前らが再帰を使うと悲しいよ。
325デフォルトの名無しさん
垢版 |
2015/12/26(土) 21:07:17.88ID:oIXuKyHb
純粋にシェルスクリプトだけでクイックソートを組むのは骨が折れたぞっと
http://www.fastpic.jp/images.php?file=2429159438.png

ループのほうが遅いです本当にどうもありがとうございました
2015/12/26(土) 21:10:42.27ID:oIXuKyHb
コードが見たけりゃどうぞ。
https://ideone.com/b9DfXr
327デフォルトの名無しさん
垢版 |
2015/12/26(土) 21:21:55.47ID:6n5NtJkM
　 　 　 ＿＿＿_
　 　 ／　　 　 　＼
　 ／　─　 　 ─　＼
／ 　 （●） 　（●） 　＼
|　 　 　 （__人__）　　 　 |
＼　 　　 ｀⌒´ 　　　,／
／　　　 　ー‐　　　　＼
328デフォルトの名無しさん
垢版 |
2015/12/26(土) 21:22:21.55ID:EXUTS9i+
なんだやっぱり再帰の方がいいのか
2015/12/26(土) 21:26:26.06ID:hFLlv/LI
ぐうの音も出ないなこれは
330デフォルトの名無しさん
垢版 |
2015/12/26(土) 21:31:21.64ID:6n5NtJkM
シリアとか言わなきゃよかった
後藤さんのくだりとか意味わかんないし
2015/12/26(土) 21:40:05.38ID:hFLlv/LI
フィボナッチとかはループと再帰で指数倍の差が出るんだっけ？
2015/12/26(土) 22:10:31.84ID:oIXuKyHb
メモ化しないコードだとそうなるね
2015/12/26(土) 22:19:22.17ID:hFLlv/LI
メモ化とか線形のメモリ食うじゃね？
2015/12/26(土) 22:46:18.19ID:JxygBNoz
>>333
直近2つを記憶するだけだから定数
2015/12/26(土) 23:20:10.16ID:YV12MLKo
>>334
それは再帰的定義を使う方では？
フィボナッチ数列の第n項を直接nの式で表せるはずだが
2015/12/26(土) 23:36:55.55ID:JxygBNoz
>>335
文脈読もうな。
メモ化に必要な記憶領域が線形ではないか、と言ってる奴がいたから定数だ、と答えただけ。
2015/12/26(土) 23:44:58.30ID:jxcpNE9M
まだアーキ依存どころか言語依存の話してるの？
2015/12/27(日) 00:05:08.34ID:TlhMnrM9
再帰メモ化定数メモリフィボナッチってどんなソースになるの？
2015/12/27(日) 00:35:22.25ID:nuYFrBF7
fibonacci = fib (0,1)
fib (m1,m2) 0 = m2
fib (m1,m2) n = fib (m2, m1+m2) (n-1)
2015/12/27(日) 00:38:15.78ID:nuYFrBF7
タプルの代わりに木かハッシュを使えば値を全部保持する
普通のメモ化にできるがフィボナッチの計算にはもちろん不要
2015/12/27(日) 00:54:47.63ID:Y7IK7QLW
>>325
bashを使うのであれば

if [ $i -ge $j ]; then
の代わりに
if (( $i < $j )); then と書ける。

また(( )) の中で単体の変数は$を省略できる
if (( i < j )); then

一行で書くこともできる。
(( i >= $ )) && break
2015/12/27(日) 01:09:36.05ID:Y7IK7QLW
stack=("${stack[@]:0:((${#stack[@]}-2))}")

これは、こう書ける。

stack=("${stack[@]::${#stack[@]}-2}")

ついでに、""をつける方が正しいのではあるが、
値にスペースが無ければ、"" は省略可能。
2015/12/27(日) 01:15:06.76ID:Y7IK7QLW
p=$(( $((${array2[$i]}+${array2[$j]}))/2 ))


$((・・・)) の中では普通に () が使用可能

p=$(( (${array2[$i]} + ${array2[$j]}) / 2 ))
2015/12/27(日) 01:21:25.37ID:Y7IK7QLW
for i in `seq 1 1 1000`; do


`` は基本的に $() と同等。新しい$()の使用が推奨されている。

for i in $(seq 1 1 1000); do


また、これは以下のように書ける

for i in {1..1000}; do
2015/12/27(日) 01:32:25.91ID:Y7IK7QLW
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 が未使用

その他の警告は、上の指摘を修正すれば消えるはず
2015/12/27(日) 01:46:16.35ID:Y7IK7QLW
ループ版で時間がかかってるのはこの部分な気がするな。
配列をコピーしているわけだし。

stack=(${stack[@]::${#stack[@]}-2})

http://www.drk7.jp/MT/archives/000995.html
さて、ここの非再帰版を見ると、どうも配列のコピーはしてないようだ。
ループ版は高速化の余地がありそうだ。

やってみるかね？ うまく実装できるかな？
347デフォルトの名無しさん
垢版 |
2015/12/27(日) 02:00:40.37ID:qGJmRem2
ループの途中でコマンドを呼び出すようにすればもう少し遅くできるんじゃないかな。
2015/12/27(日) 02:20:49.37ID:Y7IK7QLW
さーて、コードをほとんど読まずに、Perl版をそのまま置き換えてみたが
きちんと動かんぞとｗ 面倒くさいな。
速度的には再帰版より速くなりそうな感じはしてるが、処理間違ってるからなｗ
2015/12/27(日) 02:32:42.88ID:Y7IK7QLW
あ、できたっぽい？ 参考にしたコードに二箇所バグが有るようだな。

> &qsort_array($array2,0,$size);
> $right_stack[0] = $right;

$sizeが$rightに入るが、正しくは$size-1

> if ($i - $left < $right - i) {
↓
> if ( ($i - $left) < ($right - i) ) {

Perlの優先順位は、下のように解釈されるんだっけ？
そんなの変えないよな。

今コードを見直してる。
2015/12/27(日) 02:34:29.15ID:Y7IK7QLW
ごめん嘘だったｗ 。あれぇ〜？
2015/12/27(日) 02:58:09.23ID:Y7IK7QLW
Perl版実行してみたがもともとのコードからして動いてないｗ
2015/12/27(日) 03:31:06.37ID:Y7IK7QLW
マジめんどくさかったわｗ 参考にしたコードが悪すぎた。

他のコードと比べてよくわからん比較条件とか処理が多かったので
結局諦めてこっちを参考にした。
http://gauc.no-ip.org/awk-users-jp/blis.cgi/DoukakuAWK_102

結論。やっぱりループのほうが速かったねｗ
https://ideone.com/KmmnH7
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
2015/12/27(日) 03:35:18.72ID:Y7IK7QLW
ループの方が速かったので訂正よろｗ

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]
ぐうの音も出ないなこれは
2015/12/27(日) 03:56:54.62ID:nuYFrBF7
定数の差とかどうでもいい
355デフォルトの名無しさん
垢版 |
2015/12/27(日) 07:31:06.68ID:hwv/tSGM
>>353
10000倍高速化してから言いなさい
2015/12/27(日) 07:39:49.49ID:Y7IK7QLW
>>355
いいだしっぺどうぞｗ
357デフォルトの名無しさん
垢版 |
2015/12/27(日) 07:50:22.72ID:hwv/tSGM
>>356
>>219の主張を受け継いで高速化したお前が言い出しっぺ
2015/12/27(日) 07:55:16.56ID:Y7IK7QLW
言い出しっぺの定義を変えるなよｗ
本当に往生際が悪いｗ
359デフォルトの名無しさん
垢版 |
2015/12/27(日) 08:00:41.71ID:hwv/tSGM
>>353でお前が訂正を求めたレスはID:6n5NtJkMの
「再帰は1万倍遅い」に対するレス。
なので、訂正を求めるには10000倍高速化する必要がある

知能障害児には理解不能かな?
2015/12/27(日) 08:06:42.55ID:Y7IK7QLW
と言われてもなぁｗ

俺は1万倍速いなんて言ってないし。
ループのほうが速いという証拠も出したからどうでもいいかなｗ
361デフォルトの名無しさん
垢版 |
2015/12/27(日) 08:16:44.55ID:hwv/tSGM
じゃ、求めた訂正を取り消しなさい。
2015/12/27(日) 08:18:08.68ID:Y7IK7QLW
>>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デフォルトの名無しさん
垢版 |
2015/12/27(日) 09:08:43.20ID:hwv/tSGM
少し速いと10000倍速いの区別がつかないおバカさんとうエビデンス(笑)
2015/12/27(日) 09:33:20.24ID:Zmrinoji
分かったことは
・再帰をただ単にループに直すと却って遅くなる
・最適化を施せばループのほうが速くなるが、10000倍速くなるなんてことはない
の2点でおっけい？
365デフォルトの名無しさん
垢版 |
2015/12/27(日) 09:55:25.37ID:TQTcd7lL
そうだな。シリアがどうとか言い始めるほどループの方が優秀な訳では無さそうだな
2015/12/27(日) 10:12:22.58ID:dpCOQ+Jx
∞倍だね。

再帰なんってのと比較すること自体おかしい。
却って遅くなるなんて書いてる恥知らずは、プログラミング技術が無さ過ぎ。
2015/12/27(日) 10:24:13.63ID:Zmrinoji
>>366
昨日から昨晩に掛けてのやり取りを知らないのか？
俺はそのやり取りから、>>364が分かった事の全てであるって発言しただけなんだけど。
2015/12/27(日) 10:36:38.52ID:dpCOQ+Jx
やり取りからだって？

２ｃｈの妄想だけじゃなくて現実を見ろよ。
369デフォルトの名無しさん
垢版 |
2015/12/27(日) 10:40:01.29ID:hwv/tSGM
∞倍 ｗｗｗｗｗ
無限大を憶えたての小学生かよ
quick sort 再帰/quick sort 非再帰 = ∞, すなわちquick sort 非再帰が0って事だな。

再帰を必死に否定しているバカの主張

1 スタックが制限の厳しいリソースである環境が全てだと思い込み、再帰の致命的なペナルティだと主張する
2 シェル関数呼び出しをエビデンスとして、再帰が130倍遅いと主張する
3 再帰版のqsortは数万倍遅いと主張するが、数万倍速いはずの非再帰版を示さない
4 知能が低く再帰を理解できない。それをもって再帰は難解と主張する。
5 非再帰版qsortの実行時間はゼロ

本当に知能が低い
2015/12/27(日) 11:19:02.84ID:BwztOoZh
>>364
最適化なくてもループのが速いでしょ
10000倍は無いがw
2015/12/27(日) 11:22:49.99ID:Zmrinoji
>>368
お前の中ではそうなんだろうな。そんな事より現実を見ろよ。

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

クイックソートをやる上で比較にならないほど再帰のほうが遅くなるというならソースを出せや
2015/12/27(日) 11:23:28.75ID:yWds0j/q
繰り返しの方が再帰より速い！
(ただしシェルスクリプトに限る)
2015/12/27(日) 11:23:33.41ID:Zmrinoji
>>370
>>325
2015/12/27(日) 11:29:16.92ID:nlFV9EHx
>>371
引数受け渡しとかレジスタ待避とかで、余分なメモリー操作が発生する。
2015/12/27(日) 11:32:56.76ID:Zmrinoji
>>374
>>260

定数オーダーの空間計算量で計算が出来ないなら、原理的に余分なメモリ操作は避けられない。
それはループでも一緒。
2015/12/27(日) 11:43:09.26ID:yWds0j/q
>>374
明示的なスタック操作と大差ないのでは?
2015/12/27(日) 11:52:39.31ID:BwztOoZh
>>373
純粋に処理速度の話してんならネイティヴコード化したものでないとさ
2015/12/27(日) 12:07:38.28ID:BwztOoZh
>>375
横ですが、再帰呼出だとcallのオーバーがある分遅くなるで良いのかな？
まあ数パーセント程度だと思うけど
2015/12/27(日) 12:20:57.14ID:nuYFrBF7
クイックソートだからなんとかなってるだけで
たとえば赤黒木の操作を自前でスタック管理するアホはいないわけ
380デフォルトの名無しさん
垢版 |
2015/12/27(日) 12:27:15.41ID:Zmrinoji
>>377
ほい、最適化しなければループのほうが遅い証拠。
http://www.fastpic.jp/images.php?file=8506909875.png
2015/12/27(日) 12:33:24.41ID:BwztOoZh
>>380
ああ分かってない人ねwww
2015/12/27(日) 12:35:34.85ID:Zmrinoji
>>378
Pen4のデータシートの値を元にするなら
ループのコストと再帰のコストは約2.5〜3clockくらいの差になると思う。

今時のCPUならもっと差は縮まるだろうし、実際に測った訳じゃないけど
だいたいそのくらいになる筈。
2015/12/27(日) 12:38:44.94ID:Zmrinoji
>>381
最適化が無くてもループの方が「僅かでも」速いって言い張るお前に
そうじゃない場合もあるって言ったのが>>373
で、それに対しお前はネイティブコードで比較しろっつーから
「最適化無しのネイティブコードで」比較したんだが。

一体お前は何を求めてるんだ？
2015/12/27(日) 12:38:57.92ID:BwztOoZh
>>382
そこまで解説できる人ならネイティヴコードだと逆転するのわかるでしょ
アセンブリで書けとは言わんけどさ

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

381については了解
2015/12/27(日) 12:46:31.99ID:BwztOoZh
>>385
thx
2015/12/27(日) 13:08:45.42ID:yWds0j/q
>>378
tail callを繰り返しに変換できるようなケースだと
関数呼び出しはコスト高かも知れないが、
ループ版では明示的スタック操作をしなければならない場合、
call,ret相当のことをjpと組み合わせて明示的にやらないといけない。
通常、関数呼び出し後のスタックフレームの確保はcalleeが明示的にやるからループ版と変わらないが、
スタックフレームの開放はretが自動的にやる。
だからコスト的には大差なく、
関数呼び出しの方が有利なケースだってあるはず。

繰り返しの明示的なスタック操作が圧倒的有利にあるのは、
FILOじゃなくてFIFOにしたり戦略が建てられること。
388デフォルトの名無しさん
垢版 |
2015/12/27(日) 13:36:27.64ID:9aquywWv
>>379
お前は何を言っているんだ。
FreeBSDもLinuxも.NETもJavaも赤黒木はループで実装してるぞ。
再帰はプログラムの中に時限爆弾仕込むようなもの。再帰使うやつはテロリスト。
2015/12/27(日) 13:46:00.90ID:nuYFrBF7
頑張ってバグ入れずに済んでよかったね、としか。
しかもそれで得られる速度の向上も微々たるもの。
390デフォルトの名無しさん
垢版 |
2015/12/27(日) 14:00:50.68ID:9aquywWv
>>389
再帰にしたらバグが減るってものでもないしなあ。
不変オブジェクトを使うから再帰がやりやすいのであって
可変オブジェクトでの再帰はループよりもややこしいところがあるよ。
2015/12/27(日) 14:27:20.76ID:+491JRRx
>>388
＞赤黒木はループで実装してる
本当か？やればできるものなのか？証拠をみせてみろ

平衡ニ分木であるからスタックもむやみに深くならないし，
正直なところ，可能だとしてループ化するメリットがあるのかね
392デフォルトの名無しさん
垢版 |
2015/12/27(日) 14:37:53.35ID:9aquywWv
>>391
freebsd red black tree source
とかで検索すれば出てくるよ
2015/12/27(日) 14:44:37.25ID:BwztOoZh
>>390
バグ云々ではなくて、コード数や可読性だと思うが
そもそも再帰呼出を理解出来ない人は論外だが
2015/12/27(日) 14:47:35.86ID:kNkpHWWg
知らないうちにコードが再帰化してハマりました
のほうが多そう
395デフォルトの名無しさん
垢版 |
2015/12/27(日) 15:00:09.33ID:9aquywWv
>>393
主語がわからん
2015/12/27(日) 15:03:49.95ID:BwztOoZh
>>395
バグが増える要因はプログラミングソースのステップ数や可読性に左右されるのであって、アルゴリズムは特に関係ないということ
397デフォルトの名無しさん
垢版 |
2015/12/27(日) 15:06:51.61ID:9aquywWv
>>396
アルゴリズムによってステップ数や可読性は変わるよ
398デフォルトの名無しさん
垢版 |
2015/12/27(日) 16:29:32.45ID:hwv/tSGM
>>388
LinuxもFreeBSDも木全体に対して何らかの操作を行うインターフェースを実装してないからあたりまえ。

どっかで見たことある気がしたので探してみたらunbound
http://code.metager.de/source/xref/freebsd/contrib/unbound/util/rbtree.c

また一つ、再帰否定バカが無知のエビデンス(笑)を積み重ねていく
399デフォルトの名無しさん
垢版 |
2015/12/27(日) 16:32:53.51ID:9aquywWv
>>398
知らない人がいたから言っただけだよ。
ループで実装されてるんだよーって。
インターフェースを実装してないからとか理屈付けする意味あるのかな。
バカはお前。
400デフォルトの名無しさん
垢版 |
2015/12/27(日) 16:47:04.16ID:9aquywWv
インターフェース？
再帰と関係あるのかな？
わからん。この世はわからんことだらけだ。
2015/12/27(日) 17:00:20.74ID:GUkoCLfr
> LinuxもFreeBSDも木全体に対して何らかの操作を行うインターフェースを実装してない

？
OSが…インタフェースを…実装？
2015/12/27(日) 17:01:14.29ID:Zmrinoji
>>399
ねぇねぇ
そのループで実装されてる>>398のコードでも
自前でスタック管理してる訳じゃ無い。
とすると、>>379に対する突っ込みとしては>>388変じゃない？
403デフォルトの名無しさん
垢版 |
2015/12/27(日) 17:03:04.29ID:9aquywWv
>>402
スタック管理の解釈次第だね。>>388が変だと結論できる解釈もありだね。
404デフォルトの名無しさん
垢版 |
2015/12/27(日) 17:03:49.11ID:9aquywWv
>>401
わけわからんよね。
2015/12/27(日) 17:04:55.68ID:Zmrinoji
>>403
ほう、つまり君はただのループをスタック管理と解釈する訳だね？
2015/12/27(日) 17:05:12.17ID:X/TfzIFq
最近、書き込みが多くなって
このスレの勢いがすごい
2015/12/27(日) 17:07:35.61ID:Zmrinoji
>>406
確かに。
>>256から数えて、1日半で150も伸びてる。
408デフォルトの名無しさん
垢版 |
2015/12/27(日) 17:18:58.89ID:9aquywWv
>>405
再帰をループに置き換えるときには
再帰で暗黙的に管理されるスタック上の情報を
明示的に管理する必要がある。それをやるのは面倒だから
赤黒木は再帰で実装されているはずだというのが>>379に関する俺の解釈。
面倒なことないよ、現に赤黒木はループで実装されることが多いよっていうのが>>388
409デフォルトの名無しさん
垢版 |
2015/12/27(日) 17:21:03.25ID:9aquywWv
語句の解釈に文句つけるのはあまり建設的じゃないような・・・。
その先には何もないような・・・。
410デフォルトの名無しさん
垢版 |
2015/12/27(日) 17:24:39.80ID:9aquywWv
クイックソートについても再帰のスタックをそのまま
ループで再現するっていうのはどうかと思うなあ。
末尾再帰は単純なループに変換できる。ループで書くならループらしい書き方をするべき。
2015/12/27(日) 17:26:57.17ID:Zmrinoji
>>408
ふーむ。

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

日本語の問題な気も
412デフォルトの名無しさん
垢版 |
2015/12/27(日) 17:28:09.10ID:9aquywWv
>>411
解釈が違うのなら話が噛み合わないことについては筋が通るかと。
2015/12/27(日) 17:29:32.88ID:Zmrinoji
>>410
そもそもクイックソートは分割統治法の典型例だからなぁ。
自分を2度呼び出す時点で末尾再帰的じゃないし
ループらしい書き方をするとクイックソートとは呼べないシロモノになると思う
2015/12/27(日) 17:30:37.18ID:Zmrinoji
あ、勿論クイックソートをもっと単純なループで書き直せるってんなら歓迎するよ！
415デフォルトの名無しさん
垢版 |
2015/12/27(日) 17:33:05.31ID:9aquywWv
>>413
一方の再帰呼び出しは末尾再帰になるっしょ。ループに置換できる。
2015/12/27(日) 17:33:09.23ID:Zmrinoji
>>412
複数の解釈の仕方がありうるなら、
オレオレ解釈を元に相手をこき下ろす前にやることがあるだろうと
2015/12/27(日) 17:34:13.75ID:Zmrinoji
>>415
・・・・・・それは依然として再帰関数と呼ぶのでは？
418デフォルトの名無しさん
垢版 |
2015/12/27(日) 17:37:56.44ID:9aquywWv
>>416
僕とー君とーは解釈が違うよねってことだよ。
こき下ろすべきじゃないと思うのは君の勝手ー。
こき下ろすのも僕の勝手ー。
ヒューマニズム振りかざす人大嫌いー。←これ僕
419デフォルトの名無しさん
垢版 |
2015/12/27(日) 17:39:20.40ID:9aquywWv
>>417
ループを書く場合、一方の再帰呼び出しは末尾再帰だから
単純なループに置き換えられるよねってことだから、もはや再帰関数とは呼ばないよ。
2015/12/27(日) 17:42:10.80ID:Zmrinoji
>>418
いや、君が>>403で言ったのは「スタック管理」の解釈の違いだろ？
「赤黒木が再帰で書かれてる」等とは一言も言ってない>>379を読んだ君が>>408みたいな解釈をして、
人のことをテロリスト呼ばわりするのってどうなの？
2015/12/27(日) 17:43:59.16ID:Zmrinoji
>>419
https://ja.wikipedia.org/wiki/%E5%86%8D%E5%B8%B0
「再帰とは、あるものについて記述する際に、記述しているものそれ自身への参照が、その記述中にあらわれることをいう。」

ループを含む関数は再帰関数にはなれないの？
そんなことはないと思うんだけど。
2015/12/27(日) 17:46:46.63ID:YWwZOVBb
末尾再帰を勘違いしている人がいるので説明しておこう。

末尾再帰は「再帰を末尾再帰で書けば速くなる」というものではなくて
（単純な）ループを何らかの理由で再帰の形にしないといけない時、
末尾再帰の条件を満たすように、ループを再帰に変換すると
コンパイラが再帰をループに逆変換してくれる機能


なので、再帰を全て末尾再帰にできるわけではなく
（末尾再帰にできるのは、元が単純なループの場合のみ）
また、ループ ─(人間)→ 再帰 ─(コンパイラ) → ループ
というふうに、ループに戻しているだけなのでループより速くなることはない。
423デフォルトの名無しさん
垢版 |
2015/12/27(日) 17:47:27.00ID:hwv/tSGM
>>401,404
FreeBSDのrbtreeもLinuxのrbtreeもそういうインターフェースを実装していないって事だよ。
2015/12/27(日) 17:54:40.33ID:Zmrinoji
>>422
より正確には、「再帰全てをノーコストで末尾再帰にできるわけではなく」かな。
関数がファーストクラスならCPSに変換すれば末尾再帰の形にはなる。
・・・・・・ヒープガリゴリ使うし、スタックを自前で持つのと変わらんけど。
425デフォルトの名無しさん
垢版 |
2015/12/27(日) 17:56:45.58ID:9aquywWv
>>420
>>379は「赤黒木が再帰で書かれてる」とは一言も言ってないけれども、
「赤黒木の操作を自前でスタック管理するアホはいない」と言っているのだから
赤黒木の操作は、自前でスタック管理しないやり方、つまり再帰で実装される
と思っているという解釈は妥当だと思ってる。悪いけど、この解釈については譲歩するつもりはないよ。
120%君が間違っているし、再帰を使う人は120%テロリスト。それでいいね？
2015/12/27(日) 17:58:29.79ID:YWwZOVBb
>>424
速くするための末尾再帰なのに、
逆に遅くなったら本末転倒だよなｗ
427デフォルトの名無しさん
垢版 |
2015/12/27(日) 18:00:45.81ID:9aquywWv
>>421
無理。再帰を使うなら全部再帰で書くべき。
ループを使う処理では再帰を書かない。
再帰を使う処理ではループを書かない。
それで初めてループと再帰の決着がつけられる。
そしてループが勝利する。
2015/12/27(日) 18:01:48.21ID:Zmrinoji
>>425
確率が1を超えてるとか、幼稚園に迷い込んだ気分だよ。

「赤黒木の操作を自前でスタック管理するアホはいない」と言っている以上、
赤黒木の操作は、スタックなんてものをそもそも自分で触らないようなやり方、
つまり再帰か、又は上手なループで実装されているって話だろ？
フィボナッチ数を計算する関数をスタックを使わずに書いたって言った時、君は再帰の方しか思い浮かべられないのかい？
もしかして自閉症患者かい？
2015/12/27(日) 18:04:52.45ID:Zmrinoji
>>427
それじゃぁ各ノードに可変個の子要素を持つ多分木を列挙するコードは
どうやって書くつもり？
for (auto it : children) {
　if (it->is_leaf()) {
printf("%d ", it->value);
} else {
it->print_values();
}
}
430デフォルトの名無しさん
垢版 |
2015/12/27(日) 18:11:29.94ID:9aquywWv
>>428
>>389を見るに、そうじゃないと思うんだがなあ。
俺は自閉症患者だけれども、それとこれとは関係ない。
お前は全国の自閉症患者やそのご家族の方に謝罪するべき。
あとテロリストにも。
431デフォルトの名無しさん
垢版 |
2015/12/27(日) 18:15:49.41ID:9aquywWv
>>429
どうやってって何がだよ？
ループでか？再帰でか？
2015/12/27(日) 18:18:05.73ID:Zmrinoji
>>430
日本語って難しいよね。分かる分かる。
>>389の解釈は、
再帰でも書けるところをループで書いたんだ。へぇ。バグってなくて良かったね。ご苦労さん。
じゃないの？
>>379が再帰を仮定しているかどうかとは別問題。

俺も自閉症患者だけどね。自分に謝るのって変な感じがするよ。
2015/12/27(日) 18:18:46.64ID:Zmrinoji
>>431
どっちでも良いけど、どっちかしか「使ってはならない」というローカルルールの元ではどう書くの？
2015/12/27(日) 18:47:59.48ID:Zmrinoji
>>431
まだ出来ないの？
>>429に7行で書いたような、こんなコードが走ります的な切れ端で十分伝わるんだよ？
435デフォルトの名無しさん
垢版 |
2015/12/27(日) 18:53:56.10ID:9aquywWv
>>432
スタックで管理の解釈の違いだな。やっぱり噛み合わない。
436デフォルトの名無しさん
垢版 |
2015/12/27(日) 18:57:04.25ID:9aquywWv
>>434
あのさ、同意も取らずに強引に物事を進めようとするのってどうかと思うよ。
北風と太陽って話くらい知ってるでしょ？コンセンサスってとても大事。
お前コンセントしか知らないだろ。扇風機の線をぶち込んどけば何とかなるものと
しか思ってないだろ。それじゃないからな。
まずは、どういう理由で書いてほしいのかっていうところと
それによって何が成し遂げられるのかっていうところとどうして自分で
やらないのかって言うところを説明して、心からお願いしないと俺の不動の心は動かないよ。
2015/12/27(日) 19:08:44.13ID:Zmrinoji
>>435
残念。

>>436
ループを含む関数が再帰関数になれないのであれば、
>>429のような書き方は認めないって事だよね？
君ならどう書くの？って聞いただけなのになんでそんな反応になるのかね？
2015/12/27(日) 19:10:20.46ID:/NTMuKoN
横道にそれ過ぎずに、それぞれの論旨を書いてみろよ。
中傷合戦ひどくてわからん。
439デフォルトの名無しさん
垢版 |
2015/12/27(日) 19:12:29.31ID:9aquywWv
>>437
ループと再帰の優劣をつける場合、ループはループだけで
再帰は再帰だけで実装するべきだよねって話をしただけだよ。
お話の前提をすり替えてあたかもお話が続いているように
するのはよろしくないと思うんだよな。
440デフォルトの名無しさん
垢版 |
2015/12/27(日) 19:13:53.77ID:9aquywWv
>>438
俺は畑を耕していただけなんだ。そしたら ID:Zmrinoji こいつが
機関銃もって脅してきたんだ。おらはイモが食いたいだけだ。再帰使うやつはテロリストだ。
恐ろしいことだ。
2015/12/27(日) 19:14:42.52ID:Zmrinoji
>>438
大本の論旨としては、人のことをテロリスト呼ばわりするのってどうなん？って事なんだけど。

ループと再帰の優劣をつけるなんてどこから出てきた？
442デフォルトの名無しさん
垢版 |
2015/12/27(日) 19:19:02.12ID:9aquywWv
>>441
テロリストと呼ばれるのが嫌ならテロ行為やらなければいいだろ。
クイックソートでやってただろ。ループがいいか、再帰がいいかって。それのこと。
知らなかったの？じゃあ知って。今知って。
443デフォルトの名無しさん
垢版 |
2015/12/27(日) 19:19:34.89ID:Rer1VVak
バッファオーバーフロー攻撃を成功させるためには、再帰が最も都合よい。
444デフォルトの名無しさん
垢版 |
2015/12/27(日) 19:26:07.61ID:Rer1VVak
攻撃されるのと攻撃するのと、どちらが良いか？
当然、攻撃する方が良い。

つまりテロリストは勝ち組なのである。

当該スレにおいて再帰を推奨している人は勝ち組である。
なぜなら危険物を推奨するのは攻撃側だからである。
445デフォルトの名無しさん
垢版 |
2015/12/27(日) 19:30:06.01ID:9aquywWv
>>443
そういうことだな。昨今、関数型言語の流行に伴って再帰がすぐれたものであると
思い込んだニワカのペーペーどもがろくな知識も持たずに危険なコードを
書きまくって悦に入ってる姿を見ると暗い気持ちになる。再帰というのは
ループに大敗北した歴史を持つものだっていうのを知って欲しい。
for whileというのは再帰の進化形。メガ進化。
446デフォルトの名無しさん
垢版 |
2015/12/27(日) 19:33:08.96ID:Rer1VVak
お前ら逮捕されても知らんぞ。

公共の場所で再帰を勧めたりしてたら、そのうち警察が事情を聴きに来るぞ。
2015/12/27(日) 19:40:05.96ID:Zmrinoji
どうでも良いけど、再帰がテロ行為になるなんて初耳だなぁ

# 今日の夕飯はすき焼きでした
448デフォルトの名無しさん
垢版 |
2015/12/27(日) 19:43:06.97ID:Rer1VVak
>>447
自動車の256バイトしかないRAMで再帰したら、バシバシ轢き殺すぞ。
そこまでやってこそ本物のテロリストだろ。
2015/12/27(日) 19:49:26.35ID:Zmrinoji
>>448
誰がそこまで特殊でオンボロな例を挙げろと

ちなみにテロリストの定義はテロリズムを奉ずる人で、
テロリズムの定義は
https://ja.wikipedia.org/wiki/%E3%83%86%E3%83%AD%E3%83%AA%E3%82%BA%E3%83%A0#.E5.9B.BD.E9.9A.9B.E9.80.A3.E5.90.88
「住民を威嚇する、または政府や国際組織を強制する、あるいは行動を自制させる目的で、
市民や非戦闘員に対して殺害または重大な身体的危害を引き起こす事を意図したあらゆる行動」
だそうですよ。

あと自動車の場合、バシバシ轢き殺すなんて事態にはならず、単にエンストするだけだと思うの。
フェイルセーフって知ってるよね？
2015/12/27(日) 19:55:14.65ID:Zmrinoji
>>440
> 俺は畑を耕していただけなんだ。そしたら ID:Zmrinoji こいつが
> 機関銃もって脅してきたんだ。おらはイモが食いたいだけだ。再帰使うやつはテロリストだ。
俺の知ってる事実と違うね。

俺は今日は364から話を始めた。そこにID:9aquywWvが388から割り込んできて、
人のことをやれテロリストだやれ機関銃をもって脅してきただ喚いてるの。
451デフォルトの名無しさん
垢版 |
2015/12/27(日) 20:01:43.77ID:Rer1VVak
>>450
テロリストは自分のことをテロリストだと思っていないんだよな。
聖戦士だと思ってる。
正義のために再帰を仕込むんだよな。

まあでも、国民側から見ればテロリストなんだけどな。
452デフォルトの名無しさん
垢版 |
2015/12/27(日) 20:02:57.65ID:Rer1VVak
再帰なんてある意味爆弾みたいなものだしな。
テロリストが使う新型爆弾なんじゃねーかな。
2015/12/27(日) 20:07:24.21ID:Zmrinoji
そうやって正義の為にループを仕込むんだね？
よく分かったよ！

ちなみにバッファオーバーフローの攻撃手法としては再帰は下の下だからな。
getsなんかを使った方がよっぽど手っ取り早い上に任意コード実行まで出来る。
454デフォルトの名無しさん
垢版 |
2015/12/27(日) 20:08:29.75ID:9aquywWv
>>450
聞かれたから答えてたけど、>>388は君に対するレスじゃないよ。
2015/12/27(日) 20:10:16.23ID:Zmrinoji
>>454
知ってるよ？
でも再帰使うやつはテロリスト発言で敵を増やしてないかい？
456デフォルトの名無しさん
垢版 |
2015/12/27(日) 20:12:06.44ID:9aquywWv
>>455
割り込んでないよね。テロリストと糾弾されて君が勝手にファビョッただけだよね。
僕は畑耕してただけ。
2015/12/27(日) 20:15:26.35ID:Zmrinoji
>>456
文脈をよく読もう。
364から始まる再帰とループに関する話に混ざった379に君が割り込んでるね？
458デフォルトの名無しさん
垢版 |
2015/12/27(日) 20:17:05.55ID:Rer1VVak
>>457
アッラーアクバル。
459デフォルトの名無しさん
垢版 |
2015/12/27(日) 20:17:12.93ID:TQTcd7lL
テロリスト（笑）
アホかな？
2015/12/27(日) 20:17:29.15ID:TlhMnrM9
お前らなんでそんな盛り上がってんだ？
461デフォルトの名無しさん
垢版 |
2015/12/27(日) 20:17:55.10ID:9aquywWv
>>457
割り込んでないね。僕は>>379に話しかけただけだね。
君が>>379とお話したかったのなら>>379に話しかけるべきだね。
2015/12/27(日) 20:18:53.79ID:Zmrinoji
>>458
そうだね、偉大だね。
スプンタ・マンユに祈りを！(宗教ちげぇ)
2015/12/27(日) 20:25:14.94ID:Zmrinoji
>>460
いわゆる暇人という奴では。

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

あと、俺はそのレス(>>379)にその返し(>>388)って変じゃね？って言っただけで、
それに対して君が「スタックの管理とは」なんて話を始めるから(>>403)
そのコード(>>398)の何処にスタックなんて使われてるんですか―って訊いて(>>405)
それに対してまだ答えが返ってきてないんだけど。
君はあれかな、都合の悪い質問は見なかったことにする人なのかな。
464デフォルトの名無しさん
垢版 |
2015/12/27(日) 20:29:09.10ID:9aquywWv
>>463
なんで僕にレスしてくるの？
自分が話したいことがあるならそれを話せばいいじゃん。

僕は僕で自分の話したい話を話したい人とするから。
たまたま>>379だったってだけで君が>>379と話したいなら
僕はそれを否定しないよ。割り込まれたとも思わない。

ほら話しかけろよ。>>379も絶対お前のこと好きだって。
言っちゃえよ。好きだって言っちゃえよ！
2015/12/27(日) 20:29:57.74ID:Zmrinoji
>>464
暇潰しに最適なので大好きです
466デフォルトの名無しさん
垢版 |
2015/12/27(日) 20:31:26.39ID:9aquywWv
>>465
僕もだよ
2015/12/27(日) 20:32:45.93ID:Zmrinoji
>>466
それで、人のことをテロリスト呼ばわりするのってどうなん？
2015/12/27(日) 20:33:29.47ID:5UZSmdOE
ID:Zmrinoji必死だなｗ
2015/12/27(日) 20:34:10.68ID:Zmrinoji
>>469
必死乙
470デフォルトの名無しさん
垢版 |
2015/12/27(日) 20:36:11.58ID:9aquywWv
>>467
違うんだ、待ってくれ、君のことをテロリストと言ったんじゃない。
再帰を使う人はテロリストなんだ。君じゃない。
2015/12/27(日) 20:37:37.99ID:Zmrinoji
>>470
つまり、>>469で示したように再帰を使う俺はどっち？
472デフォルトの名無しさん
垢版 |
2015/12/27(日) 20:39:37.16ID:9aquywWv
>>471
では準構成員ということでここはひとつ
2015/12/27(日) 20:40:19.12ID:Zmrinoji
>>472
笑ったから良いやｗｗ
2015/12/27(日) 23:12:05.90ID:P4P/t2xP
お前ら仲良いな
2015/12/28(月) 00:41:11.60ID:cpjqbiy5
やっぱり再帰無しでループによるプログラミングが最高だね！
2015/12/28(月) 02:41:10.02ID:/Vjc/SbZ
しね
2015/12/28(月) 07:13:10.09ID:N+qRD9W4
uy
品が無さすぎ。
2015/12/28(月) 08:54:56.95ID:i05gjBFH
>>476
>>476
2015/12/28(月) 14:13:49.28ID:FI1ndW8l
私生活において自分ほど品性の高い奴はそうそういないよ
何をしていてもカリスマ性があふれ出してしまう
2015/12/28(月) 14:17:04.49ID:FI1ndW8l
「しね」というのは、実は奥の深い言葉なんだけど知っていましたか？
プログラム中でいえばNULLと似ている

人はなぜ生きるのか、なぜ死なないのか、
その真理を見つける事は誰も出来ていない
よって「死」とは恐怖かもしれないし、救いかもしれない
つまり正解でも不正解でも無い
それゆえに「しね」という言葉を発しても、敵と味方は最終的に五分にしかならない意味のない言葉なんです
だから頻繁に使っていくと良いよ
2015/12/28(月) 14:30:10.73ID:i05gjBFH
アスペが語りだしたと聞いて
482デフォルトの名無しさん
垢版 |
2015/12/28(月) 14:59:07.57ID:kIejf3VS
>>480
しね
2015/12/28(月) 17:06:38.81ID:6k5OwRcO
再帰じゃないと書いてらんない関数があるのも事実
2015/12/29(火) 05:12:44.62ID:GnldGbIR
>>419
アホはしね
2015/12/29(火) 05:14:17.23ID:GnldGbIR
>>422
tail callも知らんのかよw
2015/12/29(火) 05:16:02.68ID:GnldGbIR
>>423
インターフェースとか抽象データ型ってことを理解できてないから、
そう言っただけでは理解できないんだと思うよ。
487デフォルトの名無しさん
垢版 |
2015/12/29(火) 16:41:59.31ID:+ubDtqOv
>>429
でけたやでー
https://ideone.com/hykdXg
2015/12/29(火) 20:37:04.28ID:mZCjkrMY
>>485
お前のほうが分かっていないような気がするが‥
2015/12/29(火) 22:38:58.43ID:tgd/4Yaw
>>422の「なので、再帰を全て末尾再帰にできるわけではなく」とか恥ずかしいよなw
2015/12/30(水) 07:30:40.60ID:hgJXqSbV
>>489
>422 「再帰を全て末尾再帰にできるわけではな」いのは当然だが，どうしてはずかしいんだ？
491デフォルトの名無しさん
垢版 |
2015/12/30(水) 16:36:10.59ID:GbTfiPvb
> コンパイラが再帰をループに逆変換してくれる機能
恥ずかしい発言はこれだね。
2015/12/30(水) 17:06:15.23ID:JfqdTNxj
>>491
その理由を言わないとｗ
493デフォルトの名無しさん
垢版 |
2015/12/30(水) 17:07:27.17ID:WCUOMmTt
掲示板ではレベルのミスマッチがよくあるんだよな。

たとえば、アセンブリと機械語は一対一で対応していると純粋に信じてる人は世の中に結構多い。
そういう人たちとプロセッサのデザイナが掲示板で議論すると当然ミスマッチが起こる。
こういう場合、当然勢力の面でデザイナの方が分が悪くなるね。
世の中、知ったかぶりのバカの方が多いから。
2015/12/30(水) 17:08:24.47ID:JfqdTNxj
手動で末尾最適化をしてみればいいんだよ。

そうすれば、なるほど、
これが最適化されたコードなんだな！って
ループになったコードを目の当たりにすることになる。
2015/12/30(水) 17:28:38.17ID:hD2EQx+W
そういう周りくどい事やってるうちは三流
uyの領域に到達すると文章読むだけで理解する
2015/12/30(水) 17:39:40.10ID:hgJXqSbV
>>491
コンパイラが再帰をループにしてくれる機能はあるよ，恥ずかしいのはどちら？
497デフォルトの名無しさん
垢版 |
2015/12/30(水) 18:05:13.50ID:WCUOMmTt
再帰の方が有利なら、わざわざループに変換するなよ。
むしろ、ループを自動的に再帰に変換しろよ。
2015/12/30(水) 18:08:15.81ID:Y9esFwyM
>>492
逆変換が意味不明
単に変換なら同意するけど
499デフォルトの名無しさん
垢版 |
2015/12/30(水) 18:35:57.34ID:WCUOMmTt
テロリストは逮捕されろよ。
2015/12/30(水) 18:45:12.16ID:o3pJDHAa
再帰が実用的でなく
ループの方が有利だから
変換しないといけない。
2015/12/30(水) 18:47:59.10ID:hgJXqSbV
>>498
それは文脈による，よく逆電圧っていうが実は順電圧だったりすることはあるし
2015/12/30(水) 19:10:36.15ID:Y9esFwyM
>>501
> それは文脈による，

だからこの文脈だと意味不明って言ってるんだが

> よく逆電圧っていうが実は順電圧だったりすることはあるし

ますます意味不明
503デフォルトの名無しさん
垢版 |
2015/12/30(水) 19:20:03.93ID:pyiqU+eC
>>502
この分からず屋！！
2015/12/30(水) 21:43:44.03ID:c5JPL3VW
分かるように説明できないんじゃ周りは皆分からず屋に見えてしまうね
505デフォルトの名無しさん
垢版 |
2015/12/30(水) 21:56:06.02ID:WCUOMmTt
我々市民はテロリストを納得させるような言葉を持たない。
従って、テロリスト自ら変わらない限り、テロリストは永遠に市民の敵である。
506デフォルトの名無しさん
垢版 |
2015/12/31(木) 01:15:35.98ID:+JFM0ZYm
>>496
キミの方だとおもうよ。ぷぷぷ。
「末尾再帰は... コンパイラが再帰をループに変換してくれる機能」

> 末尾再帰は「再帰を末尾再帰で書けば速くなる」というものではなくて
> （単純な）ループを何らかの理由で再帰の形にしないといけない時、
> 末尾再帰の条件を満たすように、ループを再帰に変換すると
> コンパイラが再帰をループに逆変換してくれる機能
507デフォルトの名無しさん
垢版 |
2015/12/31(木) 01:18:23.37ID:+JFM0ZYm
>>496
それは、「末尾再帰最適化」というコンパイラの機能だね。
508デフォルトの名無しさん
垢版 |
2015/12/31(木) 01:21:18.07ID:+JFM0ZYm
「ループを再帰に変換すると、コンパイラが再帰をループに逆変換してくれる」
頭沸いてるだろ。ぷぷぷ。最初からループで書いとけよ。
509デフォルトの名無しさん
垢版 |
2015/12/31(木) 02:10:00.81ID:RPyreEna
そんなんじゃ小説なんか読めないだろう。
読解力なさすぎだよ。
510デフォルトの名無しさん
垢版 |
2015/12/31(木) 02:17:21.09ID:+JFM0ZYm
読解力が足りないとか言いだしたぞ。このバカ。

> ループを再帰に変換すると、コンパイラが再帰をループに逆変換してくれる機能
2015/12/31(木) 02:26:21.16ID:Rb2meO2K
>>490
再帰はすべて機械的に末尾再帰に変換できる。
そんな基本的なことも知らないのは恥ずかしいだろう？
512デフォルトの名無しさん
垢版 |
2015/12/31(木) 02:32:06.38ID:+JFM0ZYm
おー、すげー。天才現る。
これで、スタックオーバーフロー完全克服だ。
513デフォルトの名無しさん
垢版 |
2015/12/31(木) 02:52:07.07ID:cXVC2Dha
末尾再帰に変換できるとは言ったが,スタックオーバーフローを回避できるとは言ってない(ｷﾘｯ
514デフォルトの名無しさん
垢版 |
2015/12/31(木) 03:04:20.45ID:+JFM0ZYm
クイックソート10000倍高速化とか再帰→末尾再帰の自動変換とか、このスレには天才が多いな。
2015/12/31(木) 07:33:29.73ID:Rb2meO2K
CPS変換も知らんのか…
516デフォルトの名無しさん
垢版 |
2015/12/31(木) 09:52:41.50ID:tmojp+ig
>>510
俺は第三者だ。
俺は書き込んだ奴の言いたいことが容易に把握できている。
それがキミにはできないという。

再帰についてのスレで再帰について書かれているのだから、バックボーンの違いではないだろう。
知識ではなく読解力の問題だ。
こんなもん小学生でも意味をくみ取るぞ。
517デフォルトの名無しさん
垢版 |
2016/01/01(金) 00:50:07.33ID:PlqvFYu0
>>516
>>422を理解出来てるのか? こりゃすげーわ。
ループを再帰の形にするときに、ループを再帰に変換すると、再帰をループに逆変換してくれるコンパイラの機能が末尾再帰?

>>422が末尾再帰を理解してない事が読み取れるだけだ。
それをお前が読み取れるという事は、同一人物以外あり得ない。
518デフォルトの名無しさん
垢版 |
2016/01/01(金) 00:56:33.12ID:XLbYQ9mF
そんなんじゃ小説も読めないだろう。

末尾再帰とは、本来ループで書くべきものを再帰で書いた時にコンパイラが
自動でループに直す機能・・・という主張なのだろう。
519デフォルトの名無しさん
垢版 |
2016/01/01(金) 00:57:41.99ID:PlqvFYu0
>>515
よくいるんだわ。より難解な前提が必要なのに、出来るよって言い出す奴。
520デフォルトの名無しさん
垢版 |
2016/01/01(金) 00:57:43.20ID:XLbYQ9mF
逆変換という言葉は、そういった前提があって出てくる言葉だと思うぞ。
2016/01/01(金) 02:37:45.56ID:mIgzxpKK
コンパイラが最適化してくれるならコンパイラにやらせるのが普通の話だよね
2016/01/01(金) 08:22:45.99ID:xWjlSole
>>521
ループの方が最適化効きやすいしな。
523デフォルトの名無しさん
垢版 |
2016/01/01(金) 08:28:26.90ID:PlqvFYu0
>>520
末尾再帰の説明に「逆変換」を使うってどういう前提だよ www
524デフォルトの名無しさん
垢版 |
2016/01/01(金) 10:18:04.79ID:TPZeTHW+
>>523
本来ループであるべきものをプログラマが再帰に変換しているので、
コンパイラがループに逆変換するという主張なのだろう。

お前、本当にこの程度の文章が読めないの？
そんなんじゃ小説どころか論文も読めないだろう。

俺は元の文すら読んでいなく、引用されてるのを見てそこまで理解できてるぞ。
もう一度聞くけど、お前本当にこの程度の文が読めないの？
2016/01/01(金) 11:36:06.33ID:wTuRpENh
> インバータ（Inverter）とは、
> 直流電力から交流電力を電気的に生成する（逆変換する）電源回路、
> またはその回路を持つ電力変換装置のことである。
> 逆変換回路（ぎゃくへんかんかいろ）、逆変換装置（ぎゃくへんかんそうち）などとも呼ばれる。

逆変換ｗ
2016/01/01(金) 12:12:39.23ID:D046Nv8F
>>519
>よくいるんだわ。より難解な前提が必要なのに、出来るよって言い出す奴。

何言ってんだこいつ
527デフォルトの名無しさん
垢版 |
2016/01/01(金) 15:45:58.36ID:PlqvFYu0
>>524
おおー、スゲー
その調子で>>422を解説してくれや。
528デフォルトの名無しさん
垢版 |
2016/01/01(金) 15:48:40.55ID:PlqvFYu0
>>526
読解力が、足りない。

半端な知識を振り回す知ったかぶりが沢山いるという事だよ。
529デフォルトの名無しさん
垢版 |
2016/01/01(金) 16:18:10.88ID:TPZeTHW+
>>528
それは読解力関係ないだろう。
俺にも全く意味が分からなかった。
何言ってんだコイツ？というのが素直な感想。
2016/01/01(金) 19:46:32.52ID:FqzQpFZg
http://athos.hatenablog.com/entry/20110119/p1

ここまでこれの話題ないって相当終わったレベルの奴らしかこのスレにいないんだな

さっさと死ねよ
2016/01/01(金) 19:53:29.38ID:BqDq7bML
>>530
そりゃrubyだからさ
532デフォルトの名無しさん
垢版 |
2016/01/01(金) 20:37:19.16ID:KnWw4/o3
今年もrubyのオワコン芸ｗ
2016/01/02(土) 03:28:12.35ID:cdXNgg3P
>>531-532
本当に頭悪いカスだな
rubyに限定せず実装出来ると思うけど技量的に理解すら無理な感じ？
再帰とループの変換や末尾再帰の話題には触れてもここはTCOという単語が今まで一回も出てこないという事実

「知ってる側」からすると嘘をついてるのがすぐにわかってしまう
知ったかぶりのクズ
2016/01/02(土) 03:30:31.88ID:cqMsfgi2
>>531-532
さっさと死ねよ
2016/01/02(土) 09:53:52.00ID:QH+c5K8j
>>533
だって末尾再帰なんてlisp/schemeでは当たり前だもの，今はgccでも当たり前だし
いまさらrubyですかね‥
2016/01/02(土) 13:32:29.04ID:3O/U03ws
むしろ自分でやんないと末尾呼び最適化が利かない処理系って（ry
2016/01/02(土) 15:04:15.58ID:QH+c5K8j
なんだか遅れてるんだよねruby屋さんって
2016/01/02(土) 15:39:39.87ID:TZBdz3NA
rubyだからね。仕方ないね。
539デフォルトの名無しさん
垢版 |
2016/01/03(日) 22:30:43.03ID:F57MRPO3
>>533
何度も出てるし「末尾再帰」といった時点でジャンプへの変換という意味を持っていってるんだよ。
最適化が無ければ「末尾」と特別な扱いをする意味が無い。
runyって最近言い出したのか。30年遅れてるな。
2016/01/04(月) 03:42:45.74ID:XM/1Dr6r
理解度が低すぎる
このアルゴリズムはこのスレでは初出だと認識してるけど
読めなくてわけわかんない状態か

さっさと死ねゴミ
2016/01/04(月) 03:51:45.48ID:wtRTZBq6
妥協点でPythonだからね
それ以下の言語でアルゴリズム語ってるスレ見ると
そこで話してる内容とか読む前に
まずはスレ民を学習させる事から初めて
レベルを上げてやらないと話にならない
2016/01/04(月) 04:13:44.75ID:u97FRQbx
>>540
末尾再帰のループ最適化は >>5 や >>507 ですでに出てきているよ

>>541
最適化の話題なら python や ruby のようなインタプリタではなく
コンパイラで比較するのが適切だね，インタプリタ上で速くなっても
だれもうれしくない．C/C++一択だよ
ま，fortran でもいいが
2016/01/04(月) 04:55:36.62ID:WY8liDeA
再帰好きの人をサイキッカーと呼びたい
544デフォルトの名無しさん
垢版 |
2016/01/04(月) 10:03:14.86ID:hsfrcHKj
いいなそれ
545デフォルトの名無しさん
垢版 |
2016/01/04(月) 12:27:00.00ID:U406TFbL
再帰好きの人のを中二コーダーと呼びたい
2016/01/04(月) 15:06:50.79ID:KNqXLa56
>>542
理解力なさすぎだな
お前の学校の担任はさぞかし苦労したことだろう
2016/01/04(月) 16:24:41.19ID:u97FRQbx
>>546
どんな点をみて「理解力がない」と判断したのか？
説明できますかね，それとも吼えるだけ？
548NAS6 ◆n3AmnVhjwc
垢版 |
2016/01/04(月) 17:38:28.00ID:7uWOp/tU
つか、末尾再帰ってループそのまんまで再帰の利点ないし

recHoge1(a,n,arg...){
　dobefore()...
　if(a<n)recHoge1(a,n,arg...);
}
loopHoge1(a,n,arg...){
while(a<n){
　dobefore()...
　}
}
再帰は無意味、使う必要なし

recHoge2(a,n,arg...){
　dobefore()...
　recHoge2(a,n,arg...);
　doafter()...
}
loopHoge2(a,n,arg...){
　while(a<n){
　　pushargstack();
　　dobefore()...
　　popargstack();
　　doafter()...
　}
}
再帰で有意味、この場合使える
549NAS6 ◆n3AmnVhjwc
垢版 |
2016/01/04(月) 17:44:32.72ID:7uWOp/tU
pop,push逆だった
loopHoge2(a,n,arg...){
　while(a<n){
　　popargstack();
　　dobefore()...
　　pushargstack();
　　doafter()...
　}
}
550NAS6 ◆n3AmnVhjwc
垢版 |
2016/01/04(月) 18:00:09.14ID:7uWOp/tU
pushargstack();
popargstack();
ユーザー定義のこれらはめんどくさいから
再帰関数使ってコンパイラ任せにするよ
2016/01/04(月) 18:13:29.66ID:zTvWipKl
またゴミカス初心者が来たけど
また１から説明して教育しなきゃいけないの？
552NAS6 ◆n3AmnVhjwc
垢版 |
2016/01/04(月) 18:16:50.81ID:7uWOp/tU
recHoge1(term,arg...){
　dobefore()...
　if(term)recHoge1(term,arg...);
}
loopHoge1(term,arg...){
　while(term){
　　dobefore()...
　}
}
再帰は無意味、使う必要なし
recHoge2(term,arg...){
　dobefore()...
　if(term)recHoge2(term,arg...);
　doafter()...
}
loopHoge2(term,arg...){
　while(term){
　　popargstack();
　　dobefore()...
　　if(term)continue;
　　pushargstack();
　　doafter()...
　}
}
再帰で有意味、この場合使える
pushargstack(); popargstack();
ユーザー定義のこれらはめんどくさいから、再帰関数使ってコンパイラ任せにするよ
たったこれだけの内容
553NAS6 ◆n3AmnVhjwc
垢版 |
2016/01/04(月) 18:19:28.48ID:7uWOp/tU
>>551
>>552
以上のことの何があるか説明してみてよ
554NAS6 ◆n3AmnVhjwc
垢版 |
2016/01/04(月) 18:42:48.29ID:7uWOp/tU
ttp://nas6.main.jp/Maze.cpp

再帰、ループ、等価迷路
555NAS6 ◆n3AmnVhjwc
垢版 |
2016/01/04(月) 18:55:15.40ID:7uWOp/tU
recHoge1(term,arg...){
　dobefore()...
　if(term)recHoge1(term,arg...);
}
loopHoge1(term,arg...){
　while(term){
　　dobefore()...
　}
}
再帰は無意味、使う必要なし
recHoge2(term,arg...){
　dobefore()...
　if(term)recHoge2(term,arg...);
　doafter()...
}
loopHoge2(term,arg...){
　while(term){
　　pushargstack();
　　dobefore()...
　　if(term)continue;
　　popargstack();
　　doafter()...
　}
}
再帰で有意味、この場合使える
pushargstack(); popargstack();
ユーザー定義のこれらはめんどくさいから、再帰関数使ってコンパイラ任せにするよ
たったこれだけの内容 、勘違い訂正
556NAS6 ◆n3AmnVhjwc
垢版 |
2016/01/04(月) 19:03:49.25ID:7uWOp/tU
>>554で、
ループ実装が好きなやつはいないと思うんだけどな
2016/01/04(月) 21:13:17.67ID:KNqXLa56
RubyかPythonで書き直して
C++とかいうゴミいらねーから
558NAS6 ◆n3AmnVhjwc
垢版 |
2016/01/04(月) 21:51:32.16ID:7uWOp/tU
「｛Ｃ＋＋規則をかなり抑えてＣライク｝で書かれたソースコード」
のクロスランゲッジなんて、ほぼ、ライブラリの関数名を書き換えるだけだろ
559NAS6 ◆n3AmnVhjwc
垢版 |
2016/01/04(月) 21:54:46.92ID:7uWOp/tU
あ、あと制御構文もちゃっちゃっと書き換えれば出来上がり
2016/01/04(月) 22:07:47.26ID:mZvmD2Em
それをなぜ最初から簡潔な言語で書かないで
わざわざ冗長したC++・C言語といった言語でドヤァとソースコード貼りつけてくるのか、理解しがたいんだけど
カスレベルの初心者である事を数レスに渡る自己紹介でもしにきたのかね？
アルゴリズムの抽象化でC++とか使う奴はその時点で初心者だって一瞬で分かるって言ってるのに
自分が知恵遅れだと分かってないままの奴が続々現れるからこういう場所は話題がループする
2016/01/04(月) 22:08:20.17ID:HCl/OTCR
>>559
死ね
562デフォルトの名無しさん
垢版 |
2016/01/04(月) 22:23:59.40ID:JpzJLk3f
熱烈なC++アンチって速度要求される場面に出会ったことがないんだろな
もしくはフォートラン信者なんだろな
563デフォルトの名無しさん
垢版 |
2016/01/04(月) 22:31:14.13ID:OFaVtQHO
オッパイソンはベーシックみたいなもんで非プログラマが使うのに適してるけど、
プログラマが使うには色々しょぼすぎ。
ペイントショッププロのマクロにオッパイソンが採用されたときは、来るかと思ったけど、
それを機に没落していった。
イヌックスの呪いは有名だけど、オッパイソンの呪いもあるのかもしれん。
564デフォルトの名無しさん
垢版 |
2016/01/04(月) 22:35:24.75ID:OFaVtQHO
しかし、エクセルのマクロ使いはザラにいるのに、他のアプリはマクロ使いが
ほとんどいないんだよな。
イーマックソとか言うウンコは置いといて。
CADなんかマクロの使いであると思うのだが。
Autocadなんかウンコ使いが泣いて喜ぶLisp搭載してるのにな。
なんでだ。
2016/01/04(月) 22:55:58.31ID:8iRyCi7U
とりあえずuyがほんとになにもわかってないことだけわかった
566NAS6 ◆n3AmnVhjwc
垢版 |
2016/01/04(月) 23:00:49.51ID:7uWOp/tU
ruby知らんがこんな感じだろ

def recHoge2(term,arg...)
　　dobefore(arg...)
　　if term
　　　recHoge2(term,arg...)
　　end
　　doafter(arg...)
end
end

def loopHoge2(term,arg...)
　while term
　　pushargstack(arg...)
　　dobefore(arg...)
　　if term
　　　next
　　end
　　popargstack(arg...)
　　doafter(arg...)
end
end
567NAS6 ◆n3AmnVhjwc
垢版 |
2016/01/04(月) 23:01:55.35ID:7uWOp/tU
class stack
　def initialize
　　@ret = -1
　　@crnt = 0
　　@MAX_STACK = 32768
　　@stk[MAX_STACK]
　end
def pop_stk()
　　if -1 < crnt
　　　ret = stk[crnt]
　　　crnt = crnt - 1
　　end　
　end　
def push_stk(v)
　　if crnt < MAX_STACK - 1
　　　crnt = crnt + 1
　　　stk[crnt] = v
　　end
　end
end
stk = stack
def pushargstack(arg1...argn)
　stk.push_stk(arg1)
　...
　stk.push_stk(argn)
end
def popargstack(arg1...argn)
　argn = stk.pop_stk()
　...
　arg1 = stk.pop_stk()
end
568NAS6 ◆n3AmnVhjwc
垢版 |
2016/01/04(月) 23:07:46.09ID:7uWOp/tU
def recHoge2(term,arg...)
　dobefore(arg...)
　if term
　　recHoge2(term,arg...)
　end
　doafter(arg...)
end

で、こんだけで済むのに、
ループにしたいからって
スタックのユーザー定義なんて馬鹿だろう
569NAS6 ◆n3AmnVhjwc
垢版 |
2016/01/04(月) 23:22:49.68ID:7uWOp/tU
再帰をループにしたかったら
こういうのをいちいち作らなきゃだめだよ
class stack
　def initialize
　　@crnt = 0
　　@MAX_STACK = 32768
　　@stk[MAX_STACK]
　end
def pop_stk()
　　if -1 < crnt
　　　ret = stk[crnt]
　　　crnt = crnt - 1
　　　return ret
　　end　
　end　
def push_stk(v)
　　if crnt < MAX_STACK - 1
　　　crnt = crnt + 1
　　　stk[crnt] = v
　　end
　end
end
2016/01/05(火) 02:57:13.31ID:/kPL7pQm
プログラミング半年目くらいだろうかコイツは
多く見積もって1年半
それ以上なら今すぐPC捨てたほうが良いレベル
571デフォルトの名無しさん
垢版 |
2016/01/05(火) 02:58:35.02ID:3cj4CitF
>>569

http://www.rubylife.jp/ini/

http://www.tohoho-web.com/python/index.html

http://qiita.com/ozw_sei/items/b45e316fced8aec9a97e
572デフォルトの名無しさん
垢版 |
2016/01/05(火) 02:59:25.81ID:CnA8UQLB
　
　
　　
死ねカス
573NAS6 ◆n3AmnVhjwc
垢版 |
2016/01/05(火) 06:30:43.49ID:FnNfbNzM
Array.push()、Array.pop()があるんね
>>568で済む内容を、ループで書きたかったら↓しなければならない

def loopHoge2(term,arg...)
　while term
　　pushargstack(arg...)
　　dobefore(arg...)
　　if term
　　　next
　　end
　　popargstack(arg...)
　　doafter(arg...)
　end
end

stk = Array.new()

def pushargstack(arg1...argn)
　stk.push(arg1)
　...
　stk.push(argn)
end
def popargstack(arg1...argn)
　argn = stk.pop()
　...
　arg1 = stk.pop()
end
574NAS6 ◆n3AmnVhjwc
垢版 |
2016/01/05(火) 06:44:29.17ID:FnNfbNzM
def recHoge2(term,arg1...argn)
　dobefore(arg1...argn)
　if term
　　recHoge2(term,arg1...argn)
　end
　doafter(arg1...argn)
end
↑は、こう↓書き換えられる
def loopHoge2(term,arg1...argn)
　while term
　　pushargstack(arg1...argn)
　　dobefore(arg1...argn)
　　if term
　　　next
　　end
　　popargstack(arg1...argn)
　　doafter(arg1...argn)
end
end
stk = Array.new()
def pushargstack(arg1...argn)
　stk.push(arg1)
　...
　stk.push(argn)
end
def popargstack(arg1...argn)
　argn = stk.pop()
　...
　arg1 = stk.pop()
end
575NAS6 ◆n3AmnVhjwc
垢版 |
2016/01/05(火) 07:30:28.12ID:FnNfbNzM
#同色上書き塗りつぶし
def refill(dest,src,x,y,color,minx,miny,maxx,maxy)
　if (x < minx) || (maxx < x) ||(y < miny) || (maxy < y)
　　return
　end
　dest[y][x] = color
　#上
　if (src[y-1][x] == color) && (dest[y-1][x] != color)
　　refill(dest,src,x,y-1,color,minx,miny,maxx,maxy)
　end
　#左
　if (src[y][x-1] == color) && (dest[y][x-1] != color)
　　refill(dest,src,x-1,y,color,minx,miny,maxx,maxy)
　end
　#下
　if (src[y+1][x] == color) && (dest[y+1][x] != color)
　　refill(dest,src,x,y+1,color,minx,miny,maxx,maxy)
　end
　#右
　if (src[y][x+1] == color) && (dest[y][x+1] != color)
　　refill(dest,src,x+1,y,color,minx,miny,maxx,maxy)
　end
end

↑のループ等価が↓
576NAS6 ◆n3AmnVhjwc
垢版 |
2016/01/05(火) 07:31:25.96ID:FnNfbNzM
stk =Array.new()
#同色上書き塗りつぶし
def loop_refill(dest,src,x,y,color,minx,miny,maxx,maxy)
　term = 0
　while !((x < minx) || (maxx < x) ||(y < miny) || (maxy < y))
　　dest[y][x] = color
　　#上
　　if (term < 1) && (src[y-1][x] == color) && (dest[y-1][x] != color)
　　　term = 0
　　　stk.push(x)
　　　stk.push(y)
　　　stk.push(term)
　　　y = y - 1
　　　term = 0
　　　next
　　end
　　#左
　　if (term < 2) && (src[y][x-1] == color) && (dest[y][x-1] != color)
　　　term = 1
　　　stk.push(x)
　　　stk.push(y)
　　　stk.push(term)
　　　x = x - 1
　　　term = 0
　　　next
　　end
577NAS6 ◆n3AmnVhjwc
垢版 |
2016/01/05(火) 07:31:53.09ID:FnNfbNzM
　　#下
　　if (term < 3) && (src[y+1][x] == color) && (dest[y+1][x] != color)
　　　term = 2
　　　stk.push(x)
　　　stk.push(y)
　　　stk.push(term)
　　　y = y + 1
　　　term = 0
　　　next
　　end
　　#右
　　if (term < 4) && (src[y][x+1] == color) && (dest[y][x+1] != color)
　　　term = 3
　　　stk.push(x)
　　　stk.push(y)
　　　stk.push(term)
　　　x = x + 1
　　　term = 0
　　　next
　　end
　　term = stk.pop()
　　y = stk.pop()
　　x = stk.pop()
　end
end
578NAS6 ◆n3AmnVhjwc
垢版 |
2016/01/05(火) 07:34:06.45ID:FnNfbNzM
再帰関数を無理矢理ループで書くことが
正解だなんてとても思えないんだけど・・・
579NAS6 ◆n3AmnVhjwc
垢版 |
2016/01/05(火) 07:57:54.39ID:FnNfbNzM
>>575-577
はdestにcolorが最初から使われていると、それ以上塗れないバグがあるな
ま、いいか
580NAS6 ◆n3AmnVhjwc
垢版 |
2016/01/05(火) 08:01:46.66ID:FnNfbNzM
destはコピー先だからそういう条件でクリア済みってことで
581NAS6 ◆n3AmnVhjwc
垢版 |
2016/01/05(火) 08:14:57.62ID:FnNfbNzM
2色必要だった・・・
srcのx,yからcolor2の連続部分をdestにcolor1で塗りつぶし
#同色上書き塗りつぶし
def refill(dest,src,x,y,color1,color2,minx,miny,maxx,maxy)
　if (x < minx) || (maxx < x) ||(y < miny) || (maxy < y)
　　return
　end
　dest[y][x] = color1
　#上
　if (src[y-1][x] == color2) && (dest[y-1][x] != color1)
　　refill(dest,src,x,y-1,color1,color2,minx,miny,maxx,maxy)
　end
　#左
　if (src[y][x-1] == color2) && (dest[y][x-1] != color1)
　　refill(dest,src,x-1,y,color1,color2,minx,miny,maxx,maxy)
　end
　#下
　if (src[y+1][x] == color2) && (dest[y+1][x] != color1)
　　refill(dest,src,x,y+1,color1,color2,minx,miny,maxx,maxy)
　end
　#右
　if (src[y][x+1] == color2) && (dest[y][x+1] != color1)
　　refill(dest,src,x+1,y,color1,color2,minx,miny,maxx,maxy)
　end
end
582NAS6 ◆n3AmnVhjwc
垢版 |
2016/01/05(火) 08:16:57.10ID:FnNfbNzM
>>576-577
も同様に直してね
583NAS6 ◆n3AmnVhjwc
垢版 |
2016/01/05(火) 08:48:45.20ID:FnNfbNzM
recHoge2(term,arg1...argn){
　dobefore(arg1...argn);
　if(term)recHoge2(term,arg1...argn);
　doafter(arg1...argn);
}
この↑再帰関数を無理矢理
loopHoge2(term,arg1...argn){
　while(term){
　　pushargstack(arg1...argn);
　　dobefore(arg1...argn);
　　if(term){continue;}
　　popargstack(arg1...argn);
　　doafter(arg1...argn);
　}
}
ループで書くのはpushargstack()popargstack()書くのもだし
再帰関数でreturnされた時の箇所で
制御をdoafter()に飛ばすように考えるのもめんどくさい
つまり、再帰関数の構造化の部分までなんでわざわざ
コーディングする必要があるのか謎
2016/01/05(火) 23:45:47.40ID:zRwuHMxA
そうだね、グリーンだね。

任意の再帰はスタックを使えばループに書き直せるし、任意のループは末尾再帰で書き表せるけど
書きやすい方で書いたら良いんじゃない？
配列を舐めるだけのループをわざわざ再帰で書く必要はないし、
二分木を舐めるだけの再帰をわざわざループで書く必要はない。
勿論例外は幾つもあるけどね。
2016/01/06(水) 01:13:15.45ID:kZN9AhFE
死ね　→　NAS6 ◆n3AmnVhjw
2016/01/06(水) 01:26:34.40ID:2plodUsJ
>>585
語彙少なすぎだろ
2016/01/06(水) 05:38:10.76ID:NwAUbAKq
時間とフィンガーポイントを無駄にしたくない
2016/01/06(水) 11:44:51.16ID:Hrty1iRZ
ばいばい
2016/01/07(木) 03:29:43.72ID:VBUUQOGk
MPC
2016/01/07(木) 14:29:25.41ID:9s+XESwg
>>589
時間とフィンガーポイントを無駄にしない為に今すぐ2chから立ち去るんだ！
さぁ早く！
2016/01/07(木) 23:10:34.37ID:ceukK3gk
またuyが言い負かされてると聞いて
2016/01/08(金) 07:36:31.52ID:37pbuAYe
http://kakaku.com/item/K0000791258/
これを使ってるけど打ちにくい
隙間にゴミが入りにくいキーボードで何か探してくれれば長文レス出来るけど
ゲームもやるから同時押しが出来ないキーボードは使えないんだよ
バッファローのこのキーボード系列は
何故かゲーミングキーボードでもない癖にかなりの同時押しが出来る
お前らもこれくらい社会の役に立ってくれ
2016/01/08(金) 07:58:14.49ID:qSmN42Fw
長文レスなんざしなくていいから死ね
2016/01/08(金) 08:06:15.22ID:t0B3KsjR
ゲームなどという恥ずかしいご趣味をお持ちのようで
2016/01/08(金) 12:51:08.30ID:OGMciHiU
tail callはrecursive callと直行する概念だと理解してないのが何人かいるな
596デフォルトの名無しさん
垢版 |
2016/01/08(金) 12:54:36.23ID:qoujFuKs
直行てなんやねんｗてのが何人もいるな
2016/01/08(金) 13:19:39.58ID:39T3KdLp
読みやすい方で書いたらいいんちゃうの？
無理にループにしてソース長くしてテスト項目増やす奴の気がしれんわ
2016/01/08(金) 13:22:10.55ID:39T3KdLp
取り敢えずutがカスだってのは旗から見てわかった

補足しておくけどループで済むものを再起にしろと言ってるわけではないからな
2016/01/08(金) 14:05:20.20ID:qSmN42Fw
そりゃrecursiveじゃないtail callなんざ幾らでもあるわ
2016/01/08(金) 14:44:50.10ID:oo2zXXZh
流し
https://pbs.twimg.com/media/CL3nAldUYAEC9OE.jpg:large
2016/01/08(金) 19:53:25.00ID:XdIzL1DI
仮にもプログラマならHHK使ってます自慢くらいしろよっていう

そういう俺はreal forceだけど。
2016/01/08(金) 22:36:48.34ID:ktsgJ36p
>>595
まっすぐ行ってどうすんねん…
2016/01/08(金) 22:52:34.47ID:Ydps26p4
ワロタ
604デフォルトの名無しさん
垢版 |
2016/01/09(土) 19:28:51.30ID:j10t/SxZ
芸能界で生きていけるレベルの芸だな。
2016/01/13(水) 15:37:06.33ID:KvZEN8k1
自分はプログラマじゃないんだよ
目的を最高効率で達成する事を念頭に置いてるスクリプトキディだ

そして複数人でプログラムを組むときに必要なノウハウなんて持ってない
そもそも自分はそういう事をしなくて良いから、生きてく上で必要無い配慮だから
周りが読みにくいとか知った事ではないし

身分がちげーんだよカス
606デフォルトの名無しさん
垢版 |
2016/01/13(水) 16:53:37.49ID:QjeDGB/s
スクリプトキディの意味も知らないのな
2016/01/13(水) 16:58:20.95ID:4eNfFdO0
（他人の作った）スクリプトを使うしか能の無いお子様

正しく自分のこと理解してるということでいいのかもしれないですね。
608デフォルトの名無しさん
垢版 |
2016/01/13(水) 18:34:23.73ID:QjeDGB/s
正しく自分を理解していたら、あんなバカな生態を晒し続けるわけが無い

スクリプトキディとは、他人の作ったスクリプトでいたずらしてはしゃぐお子様の事だね
2016/01/13(水) 19:01:27.17ID:U6rexLyV
にちゃんに
2016/01/13(水) 19:03:20.75ID:U6rexLyV
誤送信

2ちゃんに書き込んでる地点で効率最悪といえる
2016/01/13(水) 21:24:04.62ID:VbVWsLR9
地点？
2016/01/13(水) 22:25:51.39ID:IMboGSkT
数学的な再帰定義関数は好き
プログラムの再帰定義は多少罪悪感が
2016/01/14(木) 05:26:27.60ID:uv3Ej0dB
身分は再起する
2016/01/15(金) 10:47:33.86ID:u0Mj97aD
>>605
読みやすさを考慮しなくていいとか言うなら、ソースあげんなksが
615デフォルトの名無しさん
垢版 |
2016/01/15(金) 20:31:31.62ID:POz82VxF
まともなプログラムは再帰使わないて
Javaじゃ標準でhashでもvisitorでも使ってるやん
初心者かな？
616デフォルトの名無しさん
垢版 |
2016/01/15(金) 20:52:05.45ID:DNDI2k7a
>>615
ウェブサイトがハッキングされるのはそのせいかもしれませんね。
617デフォルトの名無しさん
垢版 |
2016/01/15(金) 20:59:16.36ID:POz82VxF
ワロタ
何別人ぶってるんだコイツ
618デフォルトの名無しさん
垢版 |
2016/01/15(金) 21:40:58.93ID:bARE8Ecx
Javaがまともじゃないとか何様だよ
619デフォルトの名無しさん
垢版 |
2016/01/15(金) 22:51:22.58ID:DNDI2k7a
Haskellを知ればJavaなんぞ子供のおもちゃにも及ばない。
2016/01/15(金) 22:52:36.63ID:nz6sd5//
でも　cloujure が気になるのです‥
621デフォルトの名無しさん
垢版 |
2016/01/16(土) 20:53:37.66ID:mv0cs2FW
データベース扱いにくいゴミ
622デフォルトの名無しさん
垢版 |
2016/01/16(土) 22:18:41.95ID:8IHN4wdz
データベースは扱いにくいゴミだそうです。
2016/01/17(日) 15:36:45.95ID:LBaM8j14
いや、もしかしたら
データベースを扱うのに困難を伴うゴミ人間って意味かも
624デフォルトの名無しさん
垢版 |
2016/01/17(日) 18:00:23.51ID:UWpoaTz9
もしかして、もしかしてだけどさ、Haskelのこと言ってるんじゃね？
2016/01/18(月) 05:28:47.91ID:lC5RiWYz
Haskellほどデータベース扱いやすい言語も少ないからそれはない
626デフォルトの名無しさん
垢版 |
2016/01/18(月) 20:02:16.24ID:DTRfKFLk
世界一のデータベースを持つと言われるGoogleがHaskellで動いているくらいだからね。
2016/01/18(月) 20:42:43.12ID:1d5YkXP9
Haskellって実用で使われてんのかｗ
おもちゃかと思ってたわｗ
628デフォルトの名無しさん
垢版 |
2016/01/19(火) 15:31:29.42ID:py3nDmvs
おもちゃだよ
Googleのおもちゃ
2016/01/19(火) 21:26:53.35ID:C1tOs2Eu
この世はおもちゃで十分
2016/01/20(水) 12:31:10.14ID:K5mS7ftq
2ちゃんは漏れらのおもちゃ
631デフォルトの名無しさん
垢版 |
2016/01/20(水) 17:52:59.34ID:Evm4j3E4
漏れらとか使う香具師久しぶりに見たわ
2016/01/20(水) 19:02:11.21ID:aKBKow0I
イッテヨシとかギコはにゃーんとかもう死語なんだろうな。
ゴルァはまだありかな。
2016/01/21(木) 12:48:08.73ID:zpe1QHZ3
ヌルポにはガッっていうのはなぜだったのか理由がいまだに判らないので
香具師にどう反応すればいいのかも判らない
2016/01/21(木) 23:38:12.84ID:C4EemGup
>>633
ぬるぽにかぎらず、例外発生したら、ガッ！
2016/01/22(金) 01:18:00.03ID:G5rv7JJ3
>>633
NullPointerExceptionをぬるぽと呼ぶスレだかなんだかいうスレタイのスレが立った2分後に
2が1にガッしたから

だった筈
2016/01/22(金) 11:22:37.47ID:vIHZAGQE
ヌルポ
637デフォルトの名無しさん
垢版 |
2016/01/22(金) 17:22:39.92ID:AzZButyZ
たたき続けなさい
さすればヌルポは失せるでしょう
2016/01/23(土) 18:27:15.12ID:TOjqi36j
>>636
catch
2016/01/23(土) 18:56:26.79ID:0d2orZXz
>>638
ガッてキャッチのことだったの?
640デフォルトの名無しさん
垢版 |
2016/01/31(日) 18:53:58.36ID:N9Aq8poo
>>638
そしてスローせず
2016/01/31(日) 21:42:25.99ID:OzonL4m2
ガッはガッチャの略だろ。　ガッチャマンでお馴染みのガッチャはI have got you.の略で捕まえたとかの意味。
642デフォルトの名無しさん
垢版 |
2016/02/01(月) 01:42:44.99ID:IP+vl4xQ
でもアメリカのドラマ見てると了解するときにガッチャ！って言ってるよね。
特にチャーリーズエンジェルのカエル顔が（別のドラマでも）言ってるような気がする。
2016/02/19(金) 20:26:15.94ID:wEwKzS1i
再帰使うとエラーの予測が立てにくい
2016/02/19(金) 22:00:01.71ID:eeiEIdAh
それ再帰のせいじゃなくてもともと難しいアルゴリズムなんじゃ
2016/02/19(金) 22:04:28.48ID:jxx0XdOv
再帰の方が簡単に難しいアルゴリズムを作れる
2016/02/19(金) 22:41:27.96ID:wEwKzS1i
同じコードでも言語やバージョンの違いで即死する可能性があるのがネック。
可能ならwhileにするよ。
どうでもいいスクリプトなら木にしないけど。
べ、別に再帰関数苦手なわけじゃないんだからね！
2016/02/24(水) 00:10:47.14ID:i1Xglt1a
再帰否定する奴は局所変数も否定すんの？
648uy ◆Qawu9.2l1E
垢版 |
2016/02/25(木) 06:44:19.41ID:loCQbBq3
再帰否定派は生きるのがつらいんだよ
いつも周りのもの何もかも否定してるよ
2016/02/25(木) 12:35:19.93ID:tc7lGvfi
無限か有限かを判別するだけでも難しい再帰コールが簡単に作れるからな
2016/02/25(木) 22:13:06.90ID:OuMkr9Sq
ループなら無限か有限か簡単に判別できるとでも？
2016/02/26(金) 03:25:44.03ID:VdCPJ0Vc
再帰の方が簡単に作れる
2016/02/26(金) 03:33:16.76ID:VdCPJ0Vc
例えば再帰を使えばC++149文字で数学的に非常に判別が難しいコードが作れる
ステップ数がF_φ_ω(0) (n)のオーダー
再帰を使わないともっとずっと必要な文字数は増える
653デフォルトの名無しさん
垢版 |
2016/02/26(金) 12:24:24.63ID:x5+an1W2
つまり再帰を使うと簡単に分かりにくいコードが書けてしまうというアピール

アホなのこいつ？
2016/02/26(金) 12:55:19.99ID:V8jyQAYV
まともなプログラマーしかいなけりゃ問題ないよ
2016/02/26(金) 20:22:01.88ID:KBsVtPlI
適材適所

まぁ、ループは現代ではほとんど高階関数に置き換えられてはいるが
2016/02/26(金) 20:31:47.39ID:VdCPJ0Vc
そうか？
2016/02/27(土) 09:47:03.89ID:GGk6IaQQ
再帰、ループ、高階関数は互いに別カテゴリーの概念だけどな。
2016/02/27(土) 13:35:50.10ID:wN2C/qqy
>ループは現代ではほとんど高階関数に置き換えられてはいるが

mapとかfoldって言いたいの？
2016/02/29(月) 09:52:02.11ID:+UQXiICf
ファンクショナルのことだろ
2016/02/29(月) 12:09:46.90ID:gY4tu7UX
Yコンビネータの事かも
2016/03/05(土) 08:19:26.32ID:C1oJ0ySj
最近の言語は分かり易いから好んで使う人多いみたいだね。

俺はダメだわ。単純な再帰でもアセンブラ時代の間接修飾と再帰を混合で使ってたときのトラウマが・・・
2016/03/05(土) 13:03:33.56ID:4AspLwzf
スタック使うから組み込みでは禁則かな
2016/03/05(土) 16:01:56.83ID:Xc1YGBo+
末尾呼びにすればぁ？
2016/03/06(日) 13:58:13.11ID:9mzH85Ox
無理して使う物ではないのは、確か。
665デフォルトの名無しさん
垢版 |
2016/03/07(月) 19:41:03.81ID:0qoaCMqF
今更だけどアッカーマンの展開ループです
https://ideone.com/dKocyf

これループに直せません？
https://ideone.com/Ub1M86
2016/03/07(月) 20:15:13.20ID:X8YwrOCo
>>665
ループ，というよりは map によるメモ化を先にするべきかと思う
2016/03/07(月) 20:44:00.00ID:ouSCK2N5
アッカーマンメモ化はやめとけ
メモリ使用量がシャレにならん。
小さい引数ならいいけど。
2016/03/07(月) 23:04:02.15ID:ouSCK2N5
と思ったけどスタック消費量は逆に減る？
よくわからんくなってきた。
669デフォルトの名無しさん
垢版 |
2016/03/07(月) 23:55:21.18ID:DhnnCcYX
>>668
アッカーマンはメモ化意味ない
2016/03/08(火) 06:31:35.48ID:mBS7w7C0
しかしヤッターマンならきっとやってくれる
2016/03/09(水) 19:45:38.58ID:8kThrIH6
>>669
それはありえない．
アッカーマン関数にメモ化は有用な手段
http://echo.2ch.net/test/read.cgi/tech/1434079972/14
2016/03/15(火) 20:46:33.65ID:Ar6pzjDU
メモ化とかメモリリークしてるに等しい欠陥技術でしょ。
2016/03/15(火) 20:54:37.80ID:RIoPtDsj
>>672
fjの昔からの議論をここで蒸し返しますか？
2016/03/25(金) 20:10:31.18ID:ARWxn+lM
再帰というソフトにはスタックというハードがあるけどほかのソフトをハードで実装するのはどうなの？
ＧＣとかハードで実装してまったくフリーズなしに出来ないの？
2016/03/27(日) 16:40:13.75ID:WR+Y3fPV
int main(){return main();}
2016/03/31(木) 20:21:06.47ID:qF1fcJk9
とあるRubyスクリプトだけどこれと等価のＣ書けんの？

$f=lambda{
print "f";
return $g
}

$g=lambda{
print "g"
return $f
}

a=$f
10.times{a=a.call}
677デフォルトの名無しさん
垢版 |
2016/03/31(木) 20:26:53.36ID:+v8smRGz
rubyはcで書かれているんやで知らんかったやろ？
2016/03/31(木) 20:35:19.21ID:qF1fcJk9
そういう等価じゃなくて文法的にというか。
Cだと$fと$gの型をどうしていいかわからん。
2016/03/31(木) 21:08:44.15ID:qF1fcJk9
グローバル変数じゃなくてもこれでいけるっぽい

g=nil

f=lambda{
print "f";
return g
}

g=lambda{
print "g"
return f
}


a=f
10.times{a=a.call}
680デフォルトの名無しさん
垢版 |
2016/03/31(木) 21:11:44.63ID:+v8smRGz
typedef void *(*F)()でいいやんけ
2016/03/31(木) 21:15:14.22ID:qF1fcJk9
まじで
やってみる
2016/03/31(木) 21:20:03.99ID:qF1fcJk9
やりかたわからん。
コンパイル通るソースプリーズ
683デフォルトの名無しさん
垢版 |
2016/03/31(木) 21:36:59.68ID:+v8smRGz
これでいけるやろ
#include <stdio.h>
typedef void *(*F)();
void *f();
void *g();
void *f()
{
puts("f");
return g;
}
void *g()
{
puts("g");
return f;
}
int main()
{
int i;
F func;
func = f;
for (i = 0; i < 10; ++i)
func = func();
return 0;
}
2016/03/31(木) 21:42:19.47ID:qF1fcJk9
g++だとエラーになるんだが。
コンパイラは何で確認した？
685デフォルトの名無しさん
垢版 |
2016/03/31(木) 21:46:42.36ID:+v8smRGz
なんでいきなりg++やねんw
これ以上はcの質問スレでもいって聞けタコ
2016/03/31(木) 21:55:26.05ID:qF1fcJk9
なんだ、結局コンパイル通ってないのか
687デフォルトの名無しさん
垢版 |
2016/03/31(木) 22:06:32.37ID:+v8smRGz
通るわアホw
つーかそんなレベルでよくその質問出来るなお前
2016/03/31(木) 22:09:21.97ID:qF1fcJk9
だからコンパイラは何つかったんよ。
こっちでも確認するから教えれ。
有料コンパイラだったら諦めるけど。
2016/03/31(木) 22:22:46.20ID:qF1fcJk9
まあ、Ｃ質問スレにもマルチしてみるわ
2016/03/31(木) 22:23:23.28ID:X8/ytHGi
>>684
ここではうまくいく
http://codepad.org/vXykoc8I
2016/03/31(木) 22:34:22.91ID:qF1fcJk9
>>690
ふーむ確かに。
コンパイラがC++だといかんの？
2016/03/31(木) 22:49:44.78ID:qF1fcJk9
キャストすればいいのか
2016/03/31(木) 22:50:45.57ID:qF1fcJk9
しかしvoid * はなにか負けたような気分になるなｗ
2016/03/31(木) 23:19:06.00ID:rR3RT0GR
キャストが嫌ならちゃんと型定義すればいいじゃん
と思ったがちゃんとやるには自己参照型定義みたいなのが必要になるのか
Cでそれってできるのかな

関数型Fのポインタを返す関数型をFと定義
2016/03/31(木) 23:22:26.42ID:qF1fcJk9
>>694
そう、それ！
俺もそれで悩んだ。
696デフォルトの名無しさん
垢版 |
2016/04/01(金) 00:06:13.07ID:hr4pCajV
お前はその前に悩むべき問題が山程あるだろｗ
2016/04/01(金) 03:40:11.25ID:0hX+vVN6
voidにキャストがどうのって、rubyでコード書くような奴に言われてもなぁ。
2016/04/01(金) 22:07:22.21ID:8s2Zo6V8
>関数型Fのポインタを返す関数型をFと定義

これ定義できる静的型言語ってあるの？
それとも本質的論理的に矛盾した型であって、どうやっても定義できないの？
2016/04/06(水) 03:07:16.94ID:0S+muf67
Forループは正直見た目が汚らしい
場合にもよるんだろうけど、再帰で書けるならそっちのほうがコードが綺麗になる
700デフォルトの名無しさん
垢版 |
2016/04/06(水) 12:22:11.84ID:N51toXoc
いかにもルビイバカらしい考え方だな
2016/04/06(水) 19:04:18.80ID:H8hE7WlY
なんでルビイなんだ？
ハスケルバカならまだわかるが。
2016/04/06(水) 23:26:38.04ID:UScN8EXw
るびいもはすけるもよく知らないんでしょ
2016/04/14(木) 21:05:36.57ID:Lg/h7ZOX
Y = λf.(λx.f (x x)) (λx.f (x x))　
2016/04/14(木) 22:00:43.41ID:Lg/h7ZOX
#include<stdio.h>
char*s="#include<stdio.h>%cchar*s=%c%s%c;main(){printf(s,10,34,s,34);return 0;}";main(){printf(s,10,34,s,34);return 0;}
2016/04/23(土) 00:44:20.59ID:voC0Rj8b
ピクセルシェーダーで再帰関数使えるようになるのはいつだろうか
2016/04/24(日) 20:32:40.26ID:Y7E1SWkm
CPUがGPU化するのが先かGPUがCPU化するのが先か。
まあ超並列プログラムは憧れるけどね。
2016/04/26(火) 20:14:03.31ID:ymr+ysub
main = putStrLn $ q ++ show q where q = "main = putStrLn $ q ++ show q where q = "
2016/04/27(水) 01:24:44.62ID:Pvz0UkFG
超並列はどうしてもデータレースが怖いからハードウェアトランザクションは必須だな
2016/04/28(木) 20:33:07.32ID:B776VxzF
ツクツクボウシの鳴き声を一番正確に表せた奴が優勝 [無断転載禁止]©2ch.net

1 ：以下、無断転載禁止でVIPがお送りします：2016/04/28(木) 08:01:56.231 ID:EVnE4ji20
ツクツクボーシッ！！！！ツクツクボーシッ！！！！ツククツ、ツククククククク……！！！
ｱｯ　ヴィーナス！！！！　ヴィーナス！！！！ヴィヴィヴィヴィッ！！！！！

8 ：以下、無断転載禁止でVIPがお送りします：2016/04/28(木) 08:05:05.180 ID:rZ8gq0650
ツクツクホーシ！ツクツクホーシ！ッツクツク、ツクツクホーシ！
ッ！ツクツクヴィーヨー！ツクツクヴィーヨー！ツクツクツクツクアアアアｱﾞｱﾞｱﾞｱﾞｱﾞ…天

12 ：以下、無断転載禁止でVIPがお送りします：2016/04/28(木) 08:24:50.425 ID:SYCMGSQFa
ツクツクウィーヨーンｗｗｗｗｗｗツクツクウィーヨーンｗｗｗｗｗｗウィーヨーンｗｗｗｗｗｗウィーヨーンｗｗｗｗｗｗあああああああああああああああ あ！！！！！！！
710デフォルトの名無しさん
垢版 |
2016/04/30(土) 22:02:43.20ID:uVz81x78
GitHubで匿名通信（Tor、i2p等）ができるBitComet（トラッカーサイト不要でDHTだけで日本語検索可能）
みたいな、BitTorrentがオープンソースで開発されています
言語は何でも大丈夫だそうなので、P2P書きたい！って人居ませんか？
Covenantの作者（Lyrise）がそういう人と話したいそうなので、よろしければツイートお願いします
https://twitter.com/Lyrise_al

ちなみにオイラはCovenant(純粋P2Pのファイル共有ソフト)の完成が待ち遠しいプログラミングできないアスペルガーｗ
q
711デフォルトの名無しさん
垢版 |
2016/05/04(水) 10:34:46.82ID:PLBcNQ3k
匿名通信（Tor、i2p等）ができるファイル共有ソフトBitComet（ビットコメット）みたいな、
BitTorrent（Covenant）が活発な情報交換・交流コミュニティでオープンソース開発されています（プログラマー募集中）

言語は何でも大丈夫だそうなので、P2P書きたい！って人居ませんか？

Covenantの作者（Lyrise氏）がそういう人と話したいそうなので、よろしければツイートお願いします<(_ _)>
https://twitter.com/Lyrise_al

ちなみにオイラはCovenantの完成が待ち遠しいプログラミングできない情報発信好きアスペルガーｗ


The Covenant Project
概要

Covenantは、純粋P2Pのファイル共有ソフトです

目的

インターネットにおける権力による抑圧を排除することが最終的な目標です。 そのためにCovenantでは、中央に依存しない、高効率で検索能力の高いファイル共有の機能をユーザーに提供します

特徴

Covenant = Bittorrent + Abstract Network + DHT + (Search = WoT + PoW)

接続は抽象化されているので、I2P, Tor, TCP, Proxy, その他を利用可能です
DHTにはKademlia + コネクションプールを使用します
UPnPによってポートを解放することができますが、Port0でも利用可能です(接続数は少なくなります)
検索リクエスト、アップロード、ダウンロードなどのすべての通信はDHT的に分散され、特定のサーバーに依存しません
ｔ
712デフォルトの名無しさん
垢版 |
2016/05/05(木) 20:47:26.30ID:a3JwFvV1
眠い時にプログラム書いてたら1つの関数の中にこれでもかと再帰を詰め込んだモンスター関数を書いてしまって訳が分からなくなる
2016/05/09(月) 20:57:03.75ID:QYIZFGji
アッカーマン関数はただの再帰じゃないらしいけど、
再帰のパワーを究極まで高めたら何になるの？
2016/05/10(火) 14:12:08.45ID:zxnDb8j/
チューリングマシンになる

証明：以下より明らか
・再帰を用いて、スタックとループをそれぞれ構築できる
・スタック2つとループを用いて、チューリングマシンを模倣できる
・故に、再帰の能力はチューリングマシン以上である。
・一方で、チューリングマシンを用いて再帰を表現出来る
・よって、再帰はチューリングマシンと等価である。

# ツッコミ待ち
2016/05/10(火) 22:44:58.13ID:HO4tbZvB
突っ込み待ちというかそんなに間違ってなくない？
2016/05/11(水) 19:52:51.98ID:+rpbSEWz
なんで再帰がどうこうで喧嘩してるんだこいつらw
2016/05/11(水) 20:12:13.79ID:LnJQmy5e
グッドスタイン数列というのがペアノ算術の限界を超えた再帰という話があるらしいのだが、詳しいことはよくわからない。
でもロマンを感じる。
718デフォルトの名無しさん
垢版 |
2016/05/19(木) 19:24:04.68ID:eYV7veAj
女性限定、恋愛相談サイトオープン。
4000名のイケメンカウンセラーが在籍中♪

自己紹介動画はいつでも見放題です！

メンガ　って検索してください
※本当のサイト名は英字です
719デフォルトの名無しさん
垢版 |
2016/06/19(日) 18:09:53.79ID:SmadYZ7Z
最近再帰好きだわ
2016/06/19(日) 20:03:06.77ID:d2BELKj/
ダジャレ？
2016/06/19(日) 20:41:14.58ID:N0SKT7vZ
>>719
そう言う時期が俺にもあったな...（遠い目）
2016/06/19(日) 21:07:57.12ID:OFyR5xSG
再帰で実装した方がスッキリするケースってなかなか出てこないから最近全く使ってないや
2016/06/20(月) 12:26:15.09ID:xPaMOXBK
再起なんてバグの温床だからなぁ
マインスイーパー作る時ぐらいしか使わない
2016/06/20(月) 19:47:38.77ID:YaidyggX
import Data.Function (on)
import Data.List (concatMap, groupBy)
main =
    let (f:r) = mypi 2 4 1 12 4
        s = slice 5 $ slice 10 $ concatMap show r
    in putStrLn (show f ++ ".")
       >> putStr (unlines $ map unwords $ take 200 s)
slice :: Int -> [a] -> [[a]]
slice n ls = let q = concatMap (replicate n) [0..] :: [Int]
             in map (map snd) $ groupBy ((==) `on` fst) $ zip q ls
mypi :: Integer -> Integer -> Integer -> Integer -> Integer -> [Integer]
mypi k a b a1 b1 =
    let p = k * k
        q = 2 * k + 1
        a' = a1
        b' = b1
        a1' = p * a + q * a1
        b1' = p * b + q * b1
        loop a a1 d d1 =
            if d == d1 then
                d : let a' = 10 * (a `rem` b' )
                        a1' = 10 * (a1 `rem` b1')
                    in loop a' a1' (a' `quot` b') (a1' `quot` b1')
            else
                mypi (k + 1) a b' a1 b1'
     in loop a' a1' (a' `quot` b') (a1' `quot` b1')
えんしうりつを100まんけたひょうじする
2016/06/20(月) 23:20:34.02ID:Lsa8y5Hv
パイ焼きか？
何秒で計算できんの？
2016/06/20(月) 23:52:55.90ID:YaidyggX
$ time ./pi >/dev/null
./pi > /dev/null 0.40s user 0.00s system 99% cpu 0.400 total
一瞬やね(最適化 -O)
ちなアルゴリズムはRubyのソースについてるやつから持ってきた
2016/06/27(月) 22:23:07.70ID:99UKpQvj
深さ優先探索より幅優先探索が好きだ。
重複がある場合計算量が深さより有利だし、
メモリモリモリ積んでゴリゴリ問題を制覇する感じがたまらない。
2016/06/28(火) 10:17:41.97ID:yMD5BWvc
幅優先探索の絶対見つかる感は異常
729デフォルトの名無しさん
垢版 |
2016/07/18(月) 23:29:48.39ID:v2MXNS7u
まだ再帰一回しか使ったこと無いな。
ループでもよかった感じしたけど
2016/07/26(火) 07:09:31.44ID:HN1KCMsQ
>>33
iがインクリメント出来ないw
2016/07/26(火) 07:11:59.49ID:HN1KCMsQ
ディレクトリ掘っていく処理なら再帰の方がすっきり書ける
それ以外使ったこと無いけど
2016/07/26(火) 07:14:06.40ID:HN1KCMsQ
Javaの例外の発生源を探すのにも使った
2016/07/28(木) 22:29:51.78ID:dH/T3UwK
flattenがあると再帰書かなくて済むことがまれによくある。
2016/07/28(木) 23:29:35.59ID:dH/T3UwK
findとかディレクトリのflattenだよね〜
2016/07/30(土) 09:51:23.93ID:d/v3ZRhl
再帰は楽しい
2016/07/30(土) 22:01:40.05ID:v/rkDCKK
超簡単なハノイの塔のコードを
理解出来ない奴らばかり

俺様ステキ

再帰は楽しい
2016/07/30(土) 22:19:26.10ID:jcPMAjAY
ハノイの塔って最初誰が考えたんだろなｗ
まさに再帰のための問題だよなｗ
2016/07/31(日) 02:49:55.84ID:rhb0jFW4
>>737
エドゥアール・リュカ/1800年代後半
2016/07/31(日) 11:30:45.35ID:ea63k9Af
連分数展開って見た目的にも再帰的
あとは連平方根なんてのもあったっけ？
2016/08/01(月) 17:10:15.58ID:JXVULl1x
行列式の値を余因子行列から求めるって発想が好き
2016/08/14(日) 09:13:25.49ID:Dug1tlBQ
数学のように条件を書くだけで処理が書けるのは楽しい
2016/08/14(日) 12:23:51.18ID:fahh+/HO
>>741
では
これの値を教えてください

lim[n->∞]sin(πen!)

わりとまじです
2016/08/14(日) 12:55:12.86ID:2ASH1YAS
en==円
2016/08/16(火) 08:58:30.09ID:Q5NurgQe
順次反復分岐だけで超深いは凄いな
2016/10/13(木) 18:45:18.08ID:zUN0ltZm
>>693
これこそ C の最強な部分だ
2016/10/13(木) 18:46:47.08ID:Xwk5OgLP
void **hoge; のときに
void *fuga = hoge; でもイケてしまうときとダメな時があるんだが良く判らん。
747デフォルトの名無しさん
垢版 |
2016/10/30(日) 02:58:18.76ID:oDMcv2JQ
斉木楠雄と再帰関数って似てるよな
2016/10/30(日) 13:41:20.72ID:broC4ect
小町算の総当たり問題は綺麗にかけて好き
2016/11/06(日) 03:07:23.35ID:gP4JS71d
昔カッコつけてクラスのコンストラクトの再帰だったかループが爆発するバグを作ったことがある
バックトレース大変だった思い出
フリーダムなC言語系は好きだ
2016/11/06(日) 09:26:24.46ID:rGVVvSQ9
int main()
{
return main();
}
2016/11/06(日) 12:42:18.20ID:PPwxyKBf
>>750
なめてんの？
2016/11/09(水) 21:10:33.07ID:5TPAUZWc
再帰は面白いと思ってた時期もあった気がする。

ただ引数や戻り値を順番付けて管理しておけば処理内容はループと同じなんだよね。もちろん実行資源の内訳も。
と言うより、「再帰はループの一つである」という表現のほうが正しいか
2016/11/09(水) 22:24:15.76ID:QOOLd5xM
ハノイの塔
2016/11/10(木) 13:14:57.02ID:17noS2hU
>>752
んなわけない。明らかに別物
2016/11/10(木) 13:24:06.83ID:dxAJlx69
ただのループでスタックオーバーフローの心配はないからなぁ
2016/11/10(木) 13:27:48.38ID:dxAJlx69
x 再帰はループの一つ
x ループは再帰の一つ

o 再帰でやりたいことはループでも実現できる
o ループでやりたいことは再帰でも実現できる
2016/11/10(木) 14:27:23.84ID:hh42qZlp
>>755
ただのループが何を指すかが微妙だけど、
再帰を展開したようなループだとカーソル的な物が行き場を無くすとかはあるがな。
そもそもループ自体まやかしみたいなもんだよ。
cmpとjzでしかない。
2016/11/10(木) 14:50:09.90ID:dxAJlx69
djnz派でした
2016/11/10(木) 18:03:12.84ID:gVGtx90I
再帰関数は動作の見た目(想像)が楽しい
でも天才は漸化式求めて一発で計算する
2016/11/10(木) 18:13:46.76ID:hh42qZlp
>>758
あー、ループあるな。そういう意味では。
すまんかった。
761デフォルトの名無しさん
垢版 |
2016/11/10(木) 19:18:34.28ID:bdp7hkfZ
天才じゃないから再帰使うわ
2016/11/10(木) 19:25:25.72ID:Him+SRv0
>>755
再帰と同じようにループを実装すればオーバーフローしますけど。

>>756
実現できるのは外部仕様の話。
内部仕様の話だとこうなる。

ループを使って再帰を作ることはできる。(そもそも内部的に関数はニーモニックの段階でそう作られている)。
関数や再帰にまで抽象化 (いろいろ処理) されたものから、内部仕様としてのループを再現することはできない。


まずこうゆうときは、E（電力）あたりの最小可能処理数を考えるとわかりやすい。
あとはその処理 (抽象概念) にあなたがどのような名前をつけるか。

再帰を再帰だと思うのは、誰かが再帰に再帰という名前をつけた上、あなたもそれを再帰と思い込んだから。
実際にはループで実装されている。
2016/11/10(木) 19:26:27.18ID:Him+SRv0
ループって動的ループね
2016/11/11(金) 06:56:11.81ID:wvSdzlse
>>762
> 再帰と同じようにループを実装すればオーバーフローしますけど。
意味わからん
再帰は必ずスタックを使う
単なるループはそんなもん使わない
どうやってスタックオーバーフローするんだ？
2016/11/11(金) 07:27:43.35ID:xeUlHUrh
分からんなら分からんければいいんじゃね
先に事前に書いてあることを偉そうに質問されてもね
2016/11/11(金) 07:50:29.58ID:wvSdzlse
質問ってとっちゃったか w
2016/11/11(金) 07:54:13.90ID:iDJmU8Gv
再帰を展開したようなループ、だから
そんなもん使わない、が偽か、
再起だって必ずしもスタックを使い尽くさない、が真かなんだよな。
2016/11/11(金) 08:11:51.46ID:xeUlHUrh
スタックが必要あるからスタックが採用されるんでしょう。
ループや再帰にかかわらず。そして最適化すれば同じ記述。
2016/11/11(金) 09:50:34.09ID:e7T2VXvj
>>767
int main(){ return main(); } 簡単です
2016/11/11(金) 11:06:28.50ID:4NXZomhC
C言語は関数内でローカル関数を定義できないから嫌い
ローカル関数でなら末尾呼び出し除去の保証とかやりやすいのに
2016/11/11(金) 11:08:28.85ID:goVylNR1
珍珍が再帰不能です
2016/11/11(金) 12:05:55.04ID:KJb+NHX6
>>769
それオプティマイザ次第で、ただの無限ループになるよ。
そう言う意味じゃなくて。
せめて、cmpとjzに、いやdjnzあるじゃんみたいな話についてこようよ。
2016/11/11(金) 12:26:09.96ID:Wm/OySfJ
>>770
C++で、クラス内に関数を定義すりゃいいだけ
2016/11/11(金) 13:51:46.35ID:e7T2VXvj
ではstosbで
2016/11/11(金) 19:18:44.95ID:KJb+NHX6
>>774
メモリアクセス要るようなループ書かんだろう…。ましてや再帰の展開で。
2016/11/11(金) 19:31:33.99ID:F0Rj6jl1
>>770
なるほどね，コンパイル単位内だけで末尾再帰を保証するわけだね
2016/11/11(金) 20:38:07.10ID:7sFk++lS
>>770
今時のコンパイラならファイルスコープでもインライン展開とか再帰の末尾最適化ぐらい余裕でしょ
2016/11/12(土) 15:29:28.13ID:vO6QCHLM
コンパイラが最適化を諦めるくらい難解な処理するんだろ
そのくらいのことじゃないと再帰関数する意味無いからな
それか楽をしたいか、趣味か
2016/11/13(日) 23:43:06.28ID:Iqvd49JS
木構造をループで辿りたいときってスタック使わずにできる？
2016/11/13(日) 23:46:50.63ID:qpRTYVIa
辿るだけ（構造を保持しなくていい）ならできるでしょ
たとえば全てのアドレスを出すだけとか
2016/11/14(月) 09:15:00.34ID:qrJVzCCo
スタックなんて "ヒト" の概念だからな。
自動で伸び縮みするような配列だって内部的にはスタックと同一なわけで一方的に増えていくかもしれない。
構造や順序をスタックせず、現在の状態だけを保持していたとしても、オーバーフローしない理由にはならない。
2016/11/14(月) 10:59:32.44ID:CNrivUWZ
ツリーだってメモリがツリー状になってる訳じゃない罠
2016/11/15(火) 06:36:20.67ID:HcDSv4MP
質問 スタックを使わずにできるか
回答 オーバーフローしない理由にはならない

意味不明
2016/11/15(火) 07:51:46.25ID:NKQgq3zn
できるよ
2016/11/15(火) 10:35:05.01ID:jLBcnaY6
>>784
関数呼び出しどうやってするんだよ
それにそんな再帰関数は好きになれないな
2016/11/15(火) 10:52:21.24ID:NKQgq3zn
日本語でおｋ
2016/11/15(火) 13:01:02.10ID:jLBcnaY6
>>786
ニーハオ！
モドル サキ ハ ドコニ キヲク シマスカ？
2016/11/15(火) 14:10:56.00ID:NKQgq3zn
>>779-782
2016/11/15(火) 15:51:11.27ID:jLBcnaY6
アイヤー！
2016/11/15(火) 20:24:10.55ID:vYoawJH3
>>779
http://codepad.org/Grt3NsIV
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q14142251704
791デフォルトの名無しさん
垢版 |
2016/11/16(水) 02:58:25.42ID:fzskfnoe
codepadって年はでないのか
792デフォルトの名無しさん
垢版 |
2016/11/16(水) 22:36:41.79ID:1lDDb3P+
ヒープだろうが、スタックだろうが、メモリサイズが有限である以上、
オーバーフローは起こるわな。　馬鹿には永遠に判らんだろうけど。
793デフォルトの名無しさん
垢版 |
2016/11/17(木) 11:34:22.18ID:u2Ucvcf0
情報を保存しながら、進むならば、ループだっていつかオーバーフローする。
保存せずに計算できるならば、再帰でもオーバーフローしないかもしれない。
2016/11/17(木) 11:37:48.10ID:uGSslZRu
誰かの口真似したのかもしれないけどそれは完全に間違ってますよ
795793
垢版 |
2016/11/17(木) 11:44:39.48ID:u2Ucvcf0
>>794
上の行？ 下の行？ それとも両方？
2016/11/17(木) 12:42:43.08ID:uGSslZRu
下
797793
垢版 |
2016/11/17(木) 13:03:18.99ID:u2Ucvcf0
>>796
Prologですから再帰述語で関数ではありませんが、

repeat :- 割り込みあり,!.
repeat :- repeat.

の場合、スタックの一番上でpop,pushを繰り返すことが可能なのではないでしょうか。
798797
垢版 |
2016/11/17(木) 13:06:35.00ID:u2Ucvcf0
すみません。まちがえました。これではrepeat内でのループになってしまって
Prologのrepeatになりませんでした。分かり難くなりますから割り込みを外します。

repeat.
repeat :- repeat.
799793
垢版 |
2016/11/17(木) 13:16:05.70ID:u2Ucvcf0
>>797 だと、
繰り返しを最終回にするための割り込みとしたかったのですが、
実行開始の遅延を終了するための割り込みになってしまっています。
800デフォルトの名無しさん
垢版 |
2016/11/21(月) 07:42:33.65ID:Z9LRReIl
>>797
どういう条件だとスタックが伸びず、伸びることが不可避なのはどんな場合か。
2016/11/21(月) 09:29:48.04ID:IXIwDt6r
>>800
実行時、述語の最後の節で、最後の副目標(サブルーチン呼び出しにあたる)に差し掛かった時に
その節のそれまでの副目標が全て決定性(別解があり得ない)に終了しているという条件で、
この節の呼び出し時点までスタックを戻って、そこに新たな再帰呼出しの情報を積むことができる。
2016/11/21(月) 11:07:34.14ID:3zR4lbui
>>801
条件が良すぎる・・・
2016/11/21(月) 21:05:43.87ID:vOYVrbrF
>>790
で完璧な回答をみせたはずだが
2016/11/21(月) 22:27:59.06ID:rblSsrUw
好きか嫌いかで言ったら好きだ
趣味以外では使わないけど
2016/11/21(月) 23:45:17.54ID:7dMNwwBf
当然、趣味限定だね
2016/11/22(火) 08:09:17.87ID:sAluFFeZ
再帰がスタックを積むんじゃなくて関数がスタックを積むんちゃうの？
スタックがなければ実現不可能な処理なら、ループで実装してもスタック積むんちゃうの？
2016/11/22(火) 11:35:40.81ID:Pvp5yOqg
スタックって言ってもメモリはリニアなんだぜ
2016/11/22(火) 12:37:46.98ID:flYh+8oO
>>806
ループで実現したときはスタックに積まれない。
2016/11/22(火) 13:14:00.96ID:XwCH+1ok
>>808
実行系に頼らず自分でスタックを実装するってこどだろ
使用メモリ量が不定なのは一緒
2016/11/22(火) 13:44:09.96ID:sAluFFeZ
スタックが摘まれないなら別物でしょう
2016/11/22(火) 13:48:40.05ID:sAluFFeZ
抽象概念が実体であるかのような基準で話をする人が多すぎる
再帰でスタックが発生するならそれに対比するループも必ず同等のスタック量が発生する。
それでも 「ループで実現したらスタックは積まれない」と言うのなら、それは実現できていない。

抽象概念としての名称は便宜上再帰であるかループであるかの違いはあるが、実体としての処理は必ず同等。
2016/11/22(火) 20:27:24.28ID:dPiI/ZMV
>>790
で完璧な回答をみせたはずだが
2016/11/26(土) 09:43:28.08ID:cQHpTyuw
>>811
再帰は、入れ子状の関数呼び出しで、呼び出す関数は全部同一だから、
コードは一つで良い。しかし、関数だから呼び出す度にスタックに情報を積むし、
戻ってくるまで、積んである情報をPOPできない。
ただし、関数が末尾に有る時、則ち、戻って来た情報に対して何らかの計算をしてから
情報を返すということがない関数に関しては、戻ってきた値を直接自分の戻す値に
できるわけだから、呼びだされた時の普通なら積む情報を積まずに済ませることが
できるかも知れない。こういうことを「実体」というのですないか？
814813
垢版 |
2016/11/26(土) 09:45:28.00ID:cQHpTyuw
すみません。最後
こういうことを「実体」というのではないか？
です。
815デフォルトの名無しさん
垢版 |
2016/11/26(土) 12:00:32.51ID:S9oyLAu3
>>813
なんでも継続
http://practical-scheme.net/docs/cont-j.html
2016/12/10(土) 03:10:28.97ID:bw+AbQq7
>>813
根本的には処理もデータも区別なく実体ってことでしょ。
ループ自体も関数自体も実体。
2016/12/18(日) 21:34:26.37ID:DsS1XQkJ
なあ、継続好きな人いる？
2016/12/21(水) 13:12:18.95ID:gV9REQs2
ああ例外出たらすぐ継続押すよ
2016/12/22(木) 22:15:49.61ID:vkr4xxpW
継続は再帰ほど市民権得てないからなぁ。
継続を深く理解しているプログラマは全体の１割に満たないんだろうな。
2016/12/22(木) 23:45:06.84ID:LE7ZUwY5
単純に継続を保証してる言語が少ない
2017/01/03(火) 17:56:54.67ID:bj+lJcSh
物自体の実在性を議論してんのかよ
やっぱ再帰って難しいわ
822デフォルトの名無しさん
垢版 |
2017/01/03(火) 18:36:13.80ID:YhXp5fO+
不具合っぽい
http://hatenachips.blog34.fc2.com/blog-entry-455.html
823デフォルトの名無しさん
垢版 |
2017/02/11(土) 02:50:31.54ID:JwDD7IDr
私は再帰の塊のようなプログラムを作ったことがある。
DirBaseだ。
起動後のウィンドウにエクスプローラからファイルやフォルダを
ドラグ＆ドロップするだけで簡単にツリーができる。
DirBaseで検索すれば、ダウンロードできる。
824デフォルトの名無しさん
垢版 |
2017/02/11(土) 02:54:10.46ID:JwDD7IDr
DirBaseのダウンロード先
http://www10.plala.or.jp/dir-base/
825デフォルトの名無しさん
垢版 |
2017/02/16(木) 15:31:02.48ID:VWTLMYuE
競プラではforループが盛んらしいが、言語開発者としては再起の方が使って欲しい
ソースは俺が今朝見た夢
2017/03/10(金) 23:51:10.10ID:Ra0Xudwq
おまえらBrain f**kでも再帰できんの？
2017/09/21(木) 16:49:36.88ID:na02B6ss
>>819
ん？setjmp/longjmp のことですか？
828デフォルトの名無しさん
垢版 |
2017/10/03(火) 20:26:43.27ID:GaATZUfo
(数値計算を主体とする)関数では使わないけど、
再帰ルーチンで使用頻度が激しいのは、外部記憶装置を含めた初期化ルーチン。
一つのルーチンで、内部記憶(主記憶装置)と外部記憶(HDD等)の出入りを管理している場合に、
初期化ルーチンで外部記憶が存在しない場合には、ルーチンで保存している定数を読みだして、外部記憶に保存する。
初期化ルーチンからの定数の読み出し・外部への保存が再起処理。
初期化ルーチン以外では使わない手法。
分割して作成すると、何年か後に見直した時に、どのように初期化しているのかわからない、という事態になることが多発したので、
初期化が必要な場合には、このような手法で同一ルーチン内に収めるようにした。

もっとも一番利用頻度の高いのは、Winでは、ダイアログボックスのプロシージャ。再起の塊で、何をしているのかわからなくなってくる。
829デフォルトの名無しさん
垢版 |
2018/01/28(日) 06:23:28.69ID:GN9YKPqU
再帰プログラムは関数の呼び出しで積みあがるスタックを配列とみなせば、ループアルゴリズムそのものだ。
830デフォルトの名無しさん
垢版 |
2018/01/28(日) 06:51:19.47ID:GN9YKPqU
ファイルやフォルダ、ダイアログやウインドウは階層構造で構成されるので、再帰プログラムを使うのが一般的だ。
2018/01/28(日) 15:26:22.97ID:Erw8GBm0
再帰って何?って頃から普通に再帰使ってたからなあ。
自分自身を呼び出せば良いじゃんみたいな。

高校で数列とか演繹法が得意だったせいかも。
自然に使ってた。
2018/01/28(日) 16:28:26.35ID:C2Jb//yt
再帰云々言ってるのは大昔のFORTRANとかCOBOLを使ってた人ぐらいじゃないのかな
あと組み込みとかでスタックサイズが厳しい環境で組んでるとか
2018/01/28(日) 17:26:40.96ID:OfpblgeM
スタックサイズが厳しい環境で再起？？？
834デフォルトの名無しさん
垢版 |
2018/01/28(日) 18:03:09.52ID:GN9YKPqU
再帰プログラムの基本はスタックにデータを入れ積み上げていく過程と、スタックからデータを取り出しスタックをクリアしていく過程の二つの動作しか基本的にない。
データを取り出したら、そのデータを使ってプログラミングされた処理を実行する。スタックはデータを貯めることと同時に処理の順番を決めている。再帰のプログラミングには二つの概念が必要だ。
2018/02/12(月) 05:25:54.58ID:P5QW/rJt
再帰関数大好きですよ　美しい
2018/02/23(金) 11:23:42.25ID:cixhX8OH
javaで再起処理書いたらガーベッジコレクションが掃除してくれるもんだと思ってたけど違うの？
十年前の記憶だから曖昧ですまない
cpu使用率が100%になるけど影響ないから使ってます〜って顧客に言われたのを思い出したもんやで
2018/02/23(金) 11:24:04.87ID:cixhX8OH
再帰だった
838デフォルトの名無しさん
垢版 |
2018/02/23(金) 12:18:58.87ID:E8zJnigo
影響ないなら気にすんな
839デフォルトの名無しさん
垢版 |
2018/05/23(水) 20:21:54.46ID:Au5e7VGg
僕の知り合いの知り合いができたパソコン一台でお金持ちになれるやり方
役に立つかもしれません
グーグルで検索するといいかも『ネットで稼ぐ方法　モニアレフヌノ』

980U0
840デフォルトの名無しさん
垢版 |
2018/07/05(木) 01:23:47.56ID:RfoszcD2
TB1
2018/08/22(水) 21:16:42.10ID:mHU9sjBy
今時スタックオーバフローぐらいでOSは死なないから大丈夫
2018/08/23(木) 09:46:53.93ID:n+qAvZtC
スタックオーバフローならアプリは落ちちゃう
2018/08/24(金) 14:39:50.27ID:1snHtaDM
末尾再帰すればいいじゃない。
2018/11/14(水) 23:02:37.97ID:ur2RK8H0
再帰アルゴリズムはなるべくライブラリで隠蔽して欲しいな。
自分で書くのはまだしも他人の再帰コードを読むのはかなり嫌。
845デフォルトの名無しさん
垢版 |
2018/11/15(木) 12:26:32.11ID:yIPB3Fsn
好きなんか嫌いなんかハッキリしろや
2018/11/15(木) 16:20:13.76ID:PG86imds
末尾再帰は結局ただのループ
847デフォルトの名無しさん
垢版 |
2018/11/15(木) 16:22:56.36ID:zCiKr9uf
再帰関数と言えばアッカーマン関数とかたらい回し関数などが
有名ですが他にも何かある?
848デフォルトの名無しさん
垢版 |
2018/11/15(木) 21:36:15.07ID:sS26qanx
有名じゃないからwどんな入りかたしたんおまえw
849デフォルトの名無しさん
垢版 |
2018/11/16(金) 07:45:28.14ID:Q+Zstbtj
174 その名前は774人います (ﾊﾞｯﾄﾝｷﾝ MM5a-fW3D) 2018/11/16(金) 07:04:12.40 ID:N77Q/1ZeM
＞ドラゴンクエストの世界観が全く反映されていないような印象

　　　　ド　ラ　ゴ　ン　ク　エ　ス　ト　と　は　何　か　？

ドラゴンクエストとは何かを問い続けるのが、終わらないドラゴンクエストだろう？　違うか？

2 その名前は774人います (ﾊﾞｯﾄﾝｷﾝ MM5a-fW3D) 2018/11/16(金) 07:42:40.97 ID:N77Q/1ZeM
再帰関数を理解するにあたり先輩社員に教えていただいたのですが、その時の再帰関数の例がとてもわかりやすかったので共有させていただきます。
この例のおかげもあり、はじめは再帰関数なにそれ状態から、最後はしっかりと実装できるようになりました。再帰関数はPythonで実装しています。
https://qiita.com/jumpyoshim/items/20e6b5e70efa466699b4
850デフォルトの名無しさん
垢版 |
2018/11/16(金) 23:40:45.23ID:HodhQ/sE
問) 再帰的にオマンコを定義せよ
851デフォルトの名無しさん
垢版 |
2018/11/16(金) 23:59:40.68ID:xavUeX/s
再帰関数『終わらないドラゴンクエスト』

ドラゴンクエストとは？（）{
　　　ドラゴンクエストとは？（）
}
852デフォルトの名無しさん
垢版 |
2018/11/17(土) 00:12:17.17ID:eQWBxdMf
正直小学生のガチネタにはついていけん
853デフォルトの名無しさん
垢版 |
2018/11/17(土) 03:28:35.36ID:corCuJCM
def DQ(n)
　puts "DQ #{n}"
　DQ(n+1)
end
854デフォルトの名無しさん
垢版 |
2018/11/17(土) 10:42:46.80ID:B4GISbTr
({})
855デフォルトの名無しさん
垢版 |
2018/12/16(日) 22:50:52.23ID:EHgXXRnO
バブルソート中
856デフォルトの名無しさん
垢版 |
2018/12/16(日) 22:56:36.33ID:/PxsPleo
http://xn--4gq15ldsheocf87g9uc.com/
857デフォルトの名無しさん
垢版 |
2018/12/18(火) 11:28:45.03ID:/M0/bFGF
グロ中尉
858デフォルトの名無しさん
垢版 |
2019/03/20(水) 19:02:56.05ID:DvYG4dOj
>>1
好き嫌いの問題じゃないと思うが、理論上再起かそれと同等の内部処理履歴を残さないと実現できない処理なら、使うだろう
再起にならざるを得ない具体的な数学（科学）的な条件は忘れたが、けっこう複雑な処理じゃない限り再起じゃなくても実現できたように思う
2019/03/21(木) 01:23:23.96ID:b2sujHog
>>858
「再起」じゃなくて「再帰」ね

スタックを使えば、つまりメモリを余分に使用することを認めれば
再帰はループに書き換えることができるから
再帰でなければ出来ないことは原理的に存在しない

更に言えば関数を受け取りまた返す高階関数があれば
いわゆる不動点演算子に相当するものが書けるので
関数の再帰的定義は不要になる
2019/03/21(木) 03:46:03.75ID:v9ozWdAP
論理的にはクイックソートよりマージソートが好き。
実用性はクイックソートが上なのかな？
2019/03/21(木) 08:59:54.71ID:eS2pMQJr
>>859
>再帰はループに書き換えることができるから
そのループ再帰だよ・・・
再帰の問題点もそのまま同等に引き継いでるよ・・・
2019/03/21(木) 10:49:54.63ID:uohid6CT
ループも不動点演算子も再帰関数の実装の仕方でしかない
863デフォルトの名無しさん
垢版 |
2019/03/22(金) 06:20:32.16ID:t/nkQ3ne
リストに対してはクイックソートやマージソートより選択ソートや挿入ソートのが速かった。
ケースによって使い分けるために色んなソートがあるんだなと実感した。
864デフォルトの名無しさん
垢版 |
2019/03/22(金) 18:03:42.63ID:GIrPmH5o
どうゆう状況でそんなことが起こるのか想像できない
2019/03/22(金) 20:18:00.83ID:UnYyaz4E
リストってリンクリストってこと？
2019/03/22(金) 23:38:43.20ID:bs44Fjbm
>>861
ループと再帰とは違うよ
更に言えば高階関数があればループも再帰も必要ない
不動点演算子もループも再帰だと言うのはナンセンスだ
それは「再帰と同じだ」と君が思うものを再帰と呼ぶ、と主張しているに等しい
こんな君だけの主観による再帰の定義では議論にならない
2019/03/23(土) 01:46:30.69ID:05rjzlE7
チューリング完全なんだからどの言語でも一緒、という暴論と同程度に「ループと再帰は同じ」も暴論
コンピュータからみた話じゃなくて、プログラムを書く人にとってループと再帰が同価値なのかが問題になる
自分は、複雑でも読み溶ける再帰の方が好き。ループが複雑になると、どの変数がいつのどの値を持っているのか追いきれなくなる
再帰で同程度に複雑な処理を書くと、引数の数やら名前からすぐにヤバイ臭いがするんでそんなに腐らない
2019/03/23(土) 04:14:05.11ID:FVLL7ja7
末尾再帰にすると結局for文とやってることが一緒になる
869デフォルトの名無しさん
垢版 |
2019/03/23(土) 04:46:27.26ID:abrpiqJH
モナドな再帰(IOモナドやリスト->リストな再帰)は単純な再帰でもスタック消費しない。
繰り返しコードの単純さは再帰>末尾再帰>=ループ。
2019/04/03(水) 19:48:29.75ID:mixCZYtf
非同期処理の終了を待って、次の繰り返しを行う
再帰でなければ書けない
2019/04/03(水) 19:55:40.32ID:EqbpbXJ3
ダウト
2019/04/04(木) 16:23:32.66ID:GBwqjObH
>>871
非同期処理の終了はイベントやコールバックで通知されるものとする
終了を待つ同期プリミティブは存在しない

Javascriptだとこれが普通で、繰り返しでは書けない
2019/04/04(木) 20:54:30.86ID:1bkj1Cge
納得
874デフォルトの名無しさん
垢版 |
2019/04/05(金) 00:21:14.27ID:ZWKOySqx
async/await が JavaScript の新しい仕様として入ったのも知らんのか
2019/04/05(金) 12:13:43.00ID:dQkyjbHg
await/asyncの仕組みを知らないと見える
それ使って、繰り返しで書いてみなよ
2019/04/05(金) 12:38:19.58ID:dQkyjbHg
やっぱ、await/asyncで出来そうな気がしてきた
2019/04/06(土) 00:52:53.01ID:mONJLbhR
rx最強説
2019/04/15(月) 22:24:35.37ID:SVQji9la
>>867
違うよ
柴犬にこっちは太郎でこっちは次郎だから別の犬だ、と言ってるのと同じ
879デフォルトの名無しさん
垢版 |
2019/06/19(水) 04:57:19.87ID:tVNS+22r
【出資】松本卓朗 人工知能詐欺【注意】
https://rio2016.5ch.net/test/read.cgi/rikei/1560859403/
880デフォルトの名無しさん
垢版 |
2019/06/19(水) 05:49:29.73ID:K5sVxx6Y
再帰処理は
現在の関数が戻ってゆくアドレスをスタックに保存し、このアドレスを積極的に利用する。
プログラミングの実行アドレスをスタックから取り出して制御するので、
再帰プログラミングを利用するコツは、戻りアドレスを正しく理解することだ。

再帰は同じ関数を行ったり来たりするものだが、
日常の社会では、やらない方法だ。

普通は、配列を利用して、そこに保存してあるデータを使い、
同じ場所でプログラムを実行する
2019/06/19(水) 22:51:46.77ID:cv5jOa1Y
ツリーたどるときくらいかな？再帰使うの
2019/06/22(土) 10:20:48.19ID:hB2G8Ayg
>>881
そらまあ再起が辿るイメージ図は全てツリーって名称付けれますし
2019/07/31(水) 11:07:40.57ID:w173sz60
ゲーム作るときになってようやく再帰の恩恵を得た
めっちゃ書きやすい
2019/08/01(木) 21:15:40.67ID:C2rSdv5Y
>>883
ミニマックス法かアルファベータ法だろ？
2020/01/03(金) 14:12:37.35ID:EVicjzWY
マイコンだとスタックが1桁とかだから再帰書いた瞬間に死ぬ
2020/01/04(土) 20:06:07.86ID:q1efSz+a
ルネサスのRL78/G10はRAMが128Byteしかないらしいな
2020/12/05(土) 18:00:57.46ID:6KCHBqfq
再帰
>>887
888デフォルトの名無しさん
垢版 |
2021/01/11(月) 13:49:06.57ID:nJc/cTVc
λf . (λx . f (x x)) (λx . f (x x))
2021/01/13(水) 14:49:33.89ID:tLUt5qTN
ループで書くと出現する余計な変数がなくなるのが再帰のメリット
2021/01/13(水) 21:38:42.47ID:DfoNX22P
>>889
？
kwsk
ループ変数は再帰関数でも必要なのでは？
2021/01/14(木) 06:32:41.62ID:7/cCpBde
どんどんスタックにつめば確かにループ変数はいらない
ただ、人間のためにループ変数はあった方かいいと思うけど
892デフォルトの名無しさん
垢版 |
2021/01/27(水) 21:57:40.49ID:fE6h5Ua/
再帰関数を理解したとき、最初にこれ考えたやつは天才だと思ったね
実行速度やスタック問題はともかくコードは見ていて美しい以外の何者でもない。
2021/01/28(木) 02:47:34.69ID:ggjwGOj3
CやUnix、オブジェクト指向なんかよりもはるかに古いんだよな
最初に実装されたのはlispかな
メモリを食いすぎるのでおもちゃしか動かなかったようだが
2021/01/29(金) 03:09:35.61ID:5NtPwDh4
今の時代メモリ食いすぎても動くし遅くもならないよな
1億再帰とかやったら話は別だけど
2021/07/16(金) 14:24:10.16ID:S3gddm5/
>>890

要らない

/* n の階乗を求める */
int fact(int n)
{
　if(n==0){
　　return 1;
　} else {
　　return fact(n-1);
　}
}

実質ループする処理だけど、ループの回数数えるための
変数は一切出現しない。なおかつ n は不変。
2021/07/16(金) 14:26:08.03ID:S3gddm5/
おお、"n*" を忘れた。こんな短い関数にバグ突っ込む俺（泣）
2021/07/19(月) 22:18:11.50ID:hlpOkuZF
くだらん処理にスタックを使いたくないのでわしは使わん
ライブラリが殆ど無いマイナーCPUのマイナーCコンパイラでQuickSortを書いた時くらいじゃケケケ
2021/07/22(木) 20:45:12.08ID:sSLTRpJ4
最近じゃオプティマイザがなるべくスタック使わないように
最適化してくれるんじゃなかったっけ？
2021/07/25(日) 23:45:12.36ID:rUybnQpf
>>898
末尾再帰ならそうだと思いますが、末尾再帰でなければ無理でしょう >>896-897 は末尾再帰じゃないから最適化されにくい、というか、されない
2021/10/02(土) 15:46:41.87ID:qz0ghb/n
>>8
ループと再帰の能力は同じです
かなり古い計算論の結果です
2021/10/02(土) 15:52:22.08ID:qz0ghb/n
>>892
ゲーデル先生
2021/10/02(土) 16:12:27.49ID:qz0ghb/n
>>899
結合法則を仮定していいドメインなら
CPS変換を用いて最適化する手法が随分前からあります
結合法則はGPU並列化でも使われてます
浮動小数点の場合は工夫しないと誤差が変わりますが

ちなみにC++ conceptの初期案でもaxiomで法則を記述出来ました
2021/10/02(土) 20:52:53.81ID:7AkA9F3V
>>902
scheme の継続渡しに関係しますか？
キーワードありがとうございます
2021/10/04(月) 21:48:56.27ID:tW+d3xqB
>>903
そう
Continuation-passing style, defunctionalization, and associativity
Categorical Structure of ContinuationPassing Style
この辺のサンプルプログラム読んで
2021/11/01(月) 12:26:41.37ID:ZNnEkaFK
履歴をとってるループが再帰
906デフォルトの名無しさん
垢版 |
2022/09/07(水) 22:59:05.75ID:hj8+EGae
すき

しかし再帰絶対書かないマンが思いの外多くて草生えるわ

末尾最適化できない再起をループに展開したって結局キューだのスタックオブジェクトでヒープ使うわけで
メモリ大幅に節約できると勘違いしてる基地外とか話にならん

再帰深度がたかだか1000段とかでスタックフレームにデカいオブジェクトブチ込んだりしなきゃ
素直に再帰で組むのがいいに決まってるじゃないか
数学的演算でもしない限り業務用でスタック溢れるケースを探す方が大変
907デフォルトの名無しさん
垢版 |
2022/09/08(木) 09:28:47.03ID:JEMfdspa
スタックとヒープは別物
共有してるアーキテクチャもあるが
2022/09/08(木) 13:02:30.59ID:o4zCWVHV
ループに展開できる処理をわざわざ再帰で書く奴も大概やけどな。
2022/09/08(木) 15:04:24.55ID:wt4RcFVD
展開できないものあるの
2022/09/11(日) 14:15:38.74ID:gVwBfSXr
>>909
二方向に再帰するもの、は展開に苦労しますね
式の評価は、再帰じゃないと書けないですね
2022/09/15(木) 12:56:10.95ID:LWNlvRIc
てｓｔ
912デフォルトの名無しさん
垢版 |
2024/01/02(火) 13:18:51.50ID:yx0oLXiq
再帰的データ構造は再帰でたどるのが楽なんだけど
ループで処理したほうが途中で抜けたり処理を組み合わせやすい
そこで再帰的な処理を遅延リストと組み合わせてループで処理するやり方がいまでは一般的な気がする

こういうふうに C#
https://paiza.io/projects/WbmxzuNdJq95o9RYTKFY_A
2024/01/04(木) 11:34:09.71ID:iR4GsMlV
何が一般的なのか知らんがかなり変態的なコードだな
ループでGetEnumerator呼び出したりMoveNextの戻り値を見ずCurrentを取り出したりは一般的じゃないぞ
つーかバグだろそれ
2024/11/23(土) 05:47:56.88ID:dIdD47Ip
将棋やオセロ、ぷよぷよなんかは再帰処理使うよね
新着レスの表示
レスを投稿する

レス数が900を超えています。1000を超えると表示できなくなるよ。
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況