なあ、再帰関数好きな人いる? パート3 [転載禁止]©2ch.net
レス数が900を超えています。1000を超えると表示できなくなるよ。
ループで書けるものはループで書く。
再帰使うのは仕方ない場合だけ。 スタック的なメモリ確保が必要かどうかがループと再帰を使い分ける分岐点じゃね。
末尾再帰最適化とかは本末転倒なイメージ。 >>5
ループ実装を隠せるのは大きいよ
抽象化はプログラミング言語の進化のベクトルと一致するからね ループより再帰のほうが抽象度が高いと言っている?
そこは俺にはよくわからん。
俺的にはプログラムには必要最小限の機能を使うべきで、
本質的にループより再帰のほうが強力なのだから
可能な限りループを使うべきと思ってる。
もちろん再帰をループにするためにスタックを自前で用意するといったことでは本末転倒だが。 ツリーの巡回は再帰を使ったほうがいいだろう。
リストの巡回はループでいいんじゃね? >>8
> 俺的にはプログラムには必要最小限の機能を使うべき
そういうのはコンパイラなりインタプリタなりが頑張るべきところだと思うね
人間はより抽象化された対象を扱うようにするのがモダンなプログラミング言語の方向だし うーん。必要な抽象化は歓迎するが無駄な抽象化は歓迎しないというか。
この例は再帰とは関係ないけどJavaのファイル入出力なんかは
結構複雑な作りになってて無駄な抽象化なんじゃねーのとか思ってしまう。
まあ、俺個人の感想だが。 アルゴリズムが再帰なら普通に再帰で書く
スタックサイズ制限とかあるなら別だけど アルゴリズムが再帰であってもクイックソートなど
再帰のままじゃあ使い物にならんものがいくらでも。 書いたことはあるけど10年以上昔の話だな。
これは拾い物だけどクイックソートなんてこれだけのことだろ。
qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs) クイックソートは単純な巡回とは違うだろ。
だからスタック的なメモリを必要とするかどうかだよ。 filterの実装がどうなってるかまでは知らんがな。 なんか変なテンションだなぁ
俺がC++とかでfilter相当の関数書かにゃならんくなったらループで書くよ。 クイックソートはhaskellでfilterはc++なんか?
なんか変な奴だなぁニヤニヤ 何が変か、わからん。
まあ関数型言語なんかは再帰推奨らしいがあんまり好きになれん。 推奨なんて生易しいもんじゃないで。
理論に囚われすぎて原理主義に陥いった餓鬼共やw >>8
ループでquicksort書いてみてくれ
上のコードと比較で見るだろ
言語は好きに選んでいい ループでクイックソート書こうとするとスタック的なものを自前で用意せにゃならんのじゃないか。
めんどくさすぎ。 なんかやたらと再帰がお遊びだと連呼する奴がいるが、どういう意図で言っているのか分からん。
お遊び感覚で動くものが作れるのだから、苦労しなくていい分優れているってこと? >>25
関数型言語は変数再代入禁止(のものが多い)から、そもそもループは書けないんだよね 再帰がお遊びだ
再帰がお遊びだ
再帰がお遊びだ
>>32が可哀想だから連呼してあげたよ あ、意味は「お遊び感覚で動くものを作るな」という事です。 関数型は関数脳にならないと書けないからねー
手続き脳がしみついてると貶す対象にしかならないよね せっかく埋め立てたのに何またスレ立ててんのゴミクズ ぼくたん初心者なのでわからんけど僕が今作ってる
関数から値を求める計算プログラムで再起型関数が大活躍してるお
たぶん今僕がやってる書き方が一番きれいだと思うんだけどなー > たぶん今僕がやってる書き方が一番きれいだと思うんだけどなー
いろんな方法で書いてみないと比較できないんじゃね? クイックソートで再帰なんてありえんと
さんざん言われ続けているのに、まだバカが湧いとるんだな。
ライブラリのループ版を使えば何の手間もかからず高速処理ができるのに
わざわざ問題ありまくりの再帰で書くなんてテロ同然の暴挙。 >>44
それって結局真の再帰を見たことがないからそう思い込んでるだけだよね。
見せてやるよ、真の再帰ってやつをな。
https://ideone.com/EDtRIH もうソーティングの話は良いよ、仕事で使う大抵の言語ではライブラリとして用意されてるんだから。 >>45
再帰じゃあ、10件程度のソートに控えるという事なんだよな。 10件程度のソートならソーティングネットワークによるソーティングが一番速いから
十分少ない要素数に対してはそいつを呼び出して終わりだろ。
書いてないだけだろうけど。 >>9
俺の見解では、ツリートラバースに再帰を必要とするのはデータ構造に問題があると思うんだよな。
イテレータの実装を考えると再帰はちょっと無理があるんじゃないかと思う。
もちろん出来ないわけではないのだが。
ノードが子ノードを保持するような原始的なデータ構造は良くないのではないか。 代表的なツリーの一つとしてHTMLがある。
HTMLのフラグメントを切り出し、別のノードの子として加えるような操作を考えるとき、
これはやはりループに軍配が上がると思う。
もちろん、ノードに子ノードを保持するような原始的なデータ構造ではかなりメンドクサイ。
というのもHTMLの一部を切り出す時、ノードの種類によって、ノードの分割や併合が起こる。
再帰と原始的なデータ構造では非常にめんどくさい。
私はこの用途のために直列化ツリー構造というデータ構造を考案した。
(おそらくすでに一般的に使われているとは思うのだが。) ループは再帰の特別なケースに過ぎない
ループの方が無駄がなく見える事もあるだろう
だが結局はその程度の話だ >>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) >>52
ちょっとそのやり方で、HTMLの一部をコピペするコード書いてみて。 >>53
一部ってのはどういう風に探すのん?
特定の属性を持ってるタグを探す感じ? >>54
HTMLのコピペがいつ起こるかというと、ユーザーがその操作をした時なので、
そういう前提で設計してはどうでしょうか。 HTMLをユーザーの直観に適合する形で操作するのは意外と難しいですよ。
HTMLフラグメントの移動なんてどうですかね。
面白い題材だと思うのですが。 >>52>>53を繰り返しで書ける人はいないみたいだね。 そういやC++のstd::mapのイテレータとかってどうなってんるのん? >>62
ノードオブジェクトに親を指すポインターもあって愚直に辿ってる。
赤黒木使ってるのが殆どだから、
レスしてる奴もコード読めない奴の方が多いんじゃないかw データを吐き出す方法として前方イテレートしかしないの前提ならB+木がループでトラバース出来る上に高速なんだけど
挿入と削除を頻繁にするなら、そしてデータがキャッシュに乗り切らない程度に沢山あるなら赤黒木が高速になる
全部キャッシュに乗る程度の小さなデータ数ならAVL木が高速で
更に小さいならベクタ上にヒープ木でも作ればって話になる。
どの構造でも再帰で列挙出来るけど、ループでAVL木や赤黒木のデータを列挙するのは骨だな 再帰・ループの相互変換が難しいとかさあ
アルゴリズムの根本的なところ理解してないだけ
恥ずかしすぎるこのスレ f(0,b)=b+1
f(a,0)=f(a-1,1)
f(a,b)=f(a-1,f(a,b-1)) >>66
>>67をループに変換するのは難しくないんだね?
ちょっとやってみせてよ。 再帰・ループの相互変換が難しいとかさあ
アルゴリズムの根本的なところ理解してないだけ
無能の>>68 は、勉強しろ。 >>71
無能でーすチッスチッス
インターン先はGoogle(技術職8週間、コンパイラを改良するお仕事)でしたが何か?
今The Art of Computer Programmingの英語版の2巻読んでるんだけど
次に読むべき本は何?
>>72
数式から雰囲気掴むことも出来ない重度のアスペだから仕方ない。 >>73
uyの残した名言
何で出来ているか?というのは愚問過ぎる
例えばそれを「uy」としましょう
「uy」から派性したAやBといった概念から「uy」を辿る事は出来る
例えばこの世界にある「オブジェクト指向」という概念や「量子ビット」といった概念から
「uy」を辿る事が可能なので、
それらで世界が出来ているといった勘違いが可能なのです
でもそれは、一体いくつ「uy」から継承がネストしていて、プログラム等でいえばメソッドが追加されてしまった純粋性のない概念なのでしょうか?
それを知っているのは「uy」だけです
この世界にあるすべての概念は「uy」へと通じているので、
料理人は料理を通じて世界を知り、スポーツ選手はスポーツを通じて世界を知ります
誰も「uy」からは逃げられないんだよ >>74
酉とIDくらい見なさいな
# どうでもいいけど最近障害者3級取ったわ あぁ、俺がuyと同一人物だと勘違いされたのではなく、
uyって人がそういう名言を残したって話か
ごめんごめん んでuyちゃんのループ問題はまだ解決しないのかしら まさにuyがアルゴリズムの根本的なところを理解しているかどうか問われているなw それな、今までC++スレ読んでてこいつ頭おかしいなとは思ってたけど実力が問われるよな はてさてuyの実力は如何。
# 俺自身の実力はさておき。 uy自力で頑張ってんのか?
なかなか根性あるじゃないか。
俺ならググって解答見てしまうがw 再帰で書かれた超有名な関数をループにするだけの簡単なお仕事なのに
何ですぐに出来ないんだろうね?
# 全然簡単じゃないからです 末尾再帰に書き換えてから蓄積引数を中に押し込んでループにするんだよ。
やり方を書いたのだからきっとuyにもできるはず! >>85
普通に悩んだけど再帰なら一瞬でとけんのに
ループじゃまず何のデータ構造を使っていいかわからん。 スタックだろ。
再帰とループ+スタックは等価。
理屈ではそうだが実際やるのは結構難しいんじゃね。 >>70
http://ideone.com/KDSDTc
「この程度」が難しいとか言われても
は? としか思えない
再帰というのは単なるスタック付きのループであって
君たちがどこら辺で躓いているのか理解できないんです
やっぱわからない所がわからない状態なんだろうけど、
つうかSTACKUって知っていますか? ちなみにここ一週間のuyの生活は、朝起きて、ネトゲして朝寝る です。
ちょうどいま、起きたところではなく24時間起き続けていたので今から寝る前でした
とあるゲームであと100戦程の対戦をこなし、誰よりも速く称号を獲得しようとしてる最中です
2chのム板なんて頻繁に開いてる暇とかないし結構忙しいんですわ 自分には分からなかったわ
じゃあ質問なんだけど、再帰は全てスタック+ループで書き換えられるの? 連投だけど分かったかも、
再帰で帰ってくるべき値をスタックしておくってことでループ+スタック=再帰なのね >>89
問題のすり替えはいけないな。
俺は「難しくないならやってみて?」って言っただけで
そもそも「再帰のほうがループより圧倒的に簡潔に書けるよね?」って文脈だろ。
君が「難しいから出来るもんならやってみろ」って捉えたかどうかなんざ知らんがおつかれさん
うんうん、言いたいことは分かった。
それで、そのコードのどこら辺が綺麗なの?
ちなみに機械的に変換したのがこちら(rubyじゃなくてごめんよ)
https://ideone.com/XsZh4c
fとhは機械的に変換したという意味では等価だし君のコードとほぼ同じ事をしてるのだけど、
h関数をパッと見て>>69式と等しいって言うのは凄く度胸が居るよね?
>>92
そもそも再帰をどうやってソフトウェア実装してるかというとコールスタック+ジャンプ≒スタック+ループな訳で
# ちなみにスタックの正しいスペルはstack。stackuなんて子は知りませんね。 >>96
そうなのか、、、
ならできるようにならなきゃだな >>92
再帰は機械的にCPSに書き換えることで末尾再帰にできて
そうしたらそれをループに書き換えられる
両方証明されてる >>97
アセンブリ言語によくあるcall系命令の挙動を正確に言えるようになれば
どんな再帰もスタックとループで書けるようになるよ
何しろスタックとループで再帰を表現してるのがcall系命令だからね。
それをそのまま書くとこんな具合に超汚くなるけど。
https://ideone.com/0QXd8O uyなかなかやるな。
ググって解答見た可能性もあるが、ググれるのも実力のうちだからな。 >>90
> ちなみにここ一週間のuyの生活は、朝起きて、ネトゲして朝寝る です。
悲観することはない(してないかもしれないがw)
それも一つの生き方だ
人間の人生などそんなものだ https://ideone.com/upRuBk
アッカーマン関数の展開の様子を書いてみた。
メモリリークあるけど気にしない。
もっとスマートにかけそうな気もするが言語が悪いのかな? >>103
俺も書いてみたけど
確かにどう書いてももうちょっとスマートに書ける気がする。
https://ideone.com/BFP2wh >>104
ack(3,10)を100回計算させたところ
ループ 3.99秒
再帰 4.50秒
だった。微妙にループが速い。
言語はg++ 最適化あり >>106
でも115行目以降は>>103に比べてスマートじゃない?
アッカーマン関数をより素直に表現している(ように見える)というか。
テンプレートその他がひじょーに面倒臭い事になってるのは認めるよww >>108
まあそうかも。
言語によってはめちゃくちゃ簡潔に書けたりするのかな、気になる。 >>109
ちなみに扱ってるのがアッカーマン関数だけだということとか考慮しつつ短く書くとこうなる。
https://ideone.com/ILFKf2 >>110
だいぶスッキリした。
でも入れ子構造がなくなっちゃってるのはちょっと寂しいかな。 アッカーマンを知ったばかりで嬉しくてしょうがないんだろうな
俺くらいになるとどうでもよくなるけど >>118
アッカーマン関数が原始帰納関数でない証明を頼む。
定義がシンプルかつ一般帰納関数になるように
アッカーマンさんが構成したらしいが。 https://ideone.com/63bZSE
たらいの展開の様子
haskell気持ちEー!
ループ化は誰か頼むわ んーなんかプログラムカウンタに相当するものをスタックに積まなきゃいけない感じ? https://ideone.com/rO18tw
んーできたっぽい?
コンパイラの吐いたアセンブラとか見ながら書いたからチートしてるけど。 再帰厨はcall命令とjmp命令の違いが分かってから布教してほしい >>130
何言ってるんだ。。
ループで書けば早い、自分でスタック作れば、って言ってるループキチガイに、
命令にもこういうのがあるよ、必要だからあるんだよ。
と教えてあげてはどうだ? >命令にもこういうのがあるよ、必要だからあるんだよ。
だからどうしたとしか。
基地外宗教を布教するなら、自分でするんだね。 callとjumpの中間の命令もあるよな。
call使わない奴はいないのか? >>134
MIPSのjalとjrとか。
callとretに相当。
jal相当すらなくてpcのレジスタ保存命令しかないのもあった。 まずはこの手のアルゴリズム抽象化でC++使うのをやめろ
効率悪すぎ ツリーのイテレータっつうか
ゲームプログラミング的にいえばツリー構造のタスクシステム
ゲームプログラミングしてれば普通に書いてるような低レベルの話 >>136
ツリーのイテレータの書き方は大きく分けて3種類ある。
一つ目はイテレータ自身に「どのノードを辿ってきたか」って情報を覚えさせておいてそれを用いる方法
イテレータの空間効率がO(log n)になる代わりにサクセッサの時間効率が平均でO(1)になる。
二つ目はイテレータ自身にキーを覚えさせておいて、一旦そのキーを手繰ってから次のノードを手繰り直す方法
イテレータの空間効率がO(1)になる代わりにサクセッサの時間効率がO(log n)になる。
三つ目は木構造の各葉っぱに次の葉っぱへのポインタを書いておく方法
イテレータの空間効率がO(1)、サクセッサの時間効率がO(1)になる代わりに葉要素のサイズがO(1)増える。 イテレータってそんなにたくさん使うもんじゃないし、一つ目がいいかな、俺的に。 それ種類じゃなくて、全部組み合わせて実装したほうが汎用的じゃねーの
class A
attr_accessor :up , :key , :list , :data
end
最低でも1と3のup listは無ければ木構造にならないだろ
君の考えは prev(up) と next(list) になってる 全部組み合わせたほうが汎用的?
何を言ってるかよくわからん まず、ツリーにしたらそれはイテレータとは呼ばないから
ただのツリーを走査する為の関数に過ぎない
「イテレータ」にしか使用できないツリーじゃなくて
一通りの事に使用できるツリークラス作れば?って話 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;
}
ノードの親や深さも欲しい時は、スタックに積むノードをオブジェクトでラップして親の参照や深さを持たせればいいかも uyのイテレータの定義がさっぱりわからん。
俺はC++STLのイテレータを想像しているんだが。
uyの言ってるイテレータはなんのイテレータなんだ? uyが言ってるのはツリーで実装されたイテレータということかな?
俺が言いたいのはツリーを巡回するイテレータなんだが? >>147
それを言うなら走査だろと自分で突っ込んどく 例えば
[1,2,3,4] ← これをイテレートするのがイテレータだろ?
ツリーは
[1,2,[3,4,[5,6]]] ← これをイテレートしたいのが作りたいイテレータだろ?
下のはイテレータと表現するまでもなくプログラム中でツリー構造が必要になって、
「ツリークラス」ってのを定義した事あれば、そんなのは標準実装しているレベルのものだから、わざわざツリーのイテレータなんていう半端なものは誰も作らない
作る順序的にまずはイテレータのツリー化じゃなくて、ツリークラスの定義
考えが追いつかないなら好きな順序で作れば良いけど ツリーオブジェクトにtoArray()メソッドを用意すれば
すべて解決すると思うの。 大富豪プログラミングだなtoArray()
ツリーなんかはサイズが非常にデカくなることがしばしばあるぞ。 tAo.kQ2STk ってテレンスタオから取ってんの? >>150
汎用的なツリークラス作れって言ってんのか?
javascriptみたいになるんじゃね? >>153
違うよ。人間が読める某文字列をキーにしたらその酉が作れる。
ところでさ、どうでも良いんだけど
今話題にしてるのは木構造
>>141が示したデータ構造は無向グラフ
・・・・・・だよね? 参照が木構造になってるかグラフになってるかなんて実行時に決まることじゃないのか? 制御では、実行時間が読めないアルゴリズムは使いにくい。 再帰と繰り返しは相互に変換可能なんだから、再帰で実行時間が読めないならば、繰り返しでも読めない。
こんなじょうしきも知らないの? 再帰はシステムダウンの危険がある。
処理速度もはるかに遅くなる。
再帰の場合には、こうした実行時間が読めない特有の問題点がある。 > 再帰はシステムダウンの危険がある。
そう言う環境ならば、システムダウンの可能性は繰り返しでもある。
> 処理速度もはるかに遅くなる。
ヘボが作った繰り返しは再帰よりはるかに遅い。 普通の言語は対応してる
変な言語は使うもんじゃない # 1
def f
if 条件
処理
else
f()
end
end
# 2
def f
if 条件
f()
end
end
# 3
def f
case 条件
when LABEL
f()
end
end
末尾再帰されるパターンわからない奴wwwwwwwwwwwwっうぃる? ID:EjHtX5K0のような白痴ばかりだから
再帰厨だと馬鹿にされることになる。
再帰を愛して使うんだったら、
ループ版にはない深刻なデメリットがある事ぐらいちゃんと注意した上で、
効率や安全性を無視したプログラミングを楽しむべき。 繰り返しの唯一の利点は回数の制御が再帰よりも容易であること。
これ以外の利点はない。
バカにはそれが理解できないらしいが。 再帰はID:zNzoBoA2のように低知能には理解不能という弱点があるけど
ID:zNzoBoA2のような低知能の出現率は低いので全然問題無い
むしろ低知能者を検出試験としてのメリットの方が大きい もし再帰が理解出来たつもりなら、ちゃんとループに直せるぐらいのプログラミング技術は備えなくちゃ。
最低でもそれくらいの技術や知能が無ければ
再帰を楽しむことはできないよ。 「再帰には深刻なデメリットがある」キリッ
なんて発言する低知能人は再帰を理解してるはずが無い、理解不能なものを怖れている。未開人と同じ。 ループを恐れるのは、ループにするだけの知識・経験を欠いているから。
その程度じゃあプログラミングの世界からすぐに消えるだけの存在。
再帰厨は、現実で満たされないのでスレで妄想を垂れ流すことしかできないクズ。 関数内にjmpも好き勝手にやるタイプだからどうとも言わんけど、
再帰否定派はまさか単一のアーキテクチャの話してないよな?
アルゴリズムとして再帰がイケてないって話だよな? >>186
必死で再帰を否定しているバカを弄っているだけで、繰り返しを否定しているわけでは無い
やっぱり低知能なんだな。 みなさん、これが「弄ってるって言いたいバカ」ですw 迷信を信じ込んで再帰を否定してるバカが
深刻なデメリット(爆笑)、例えば
> 処理速度もはるかに遅くなる。
を、実証すればスレ終了するのに。 >>191
そういう超基本的なプログラミング知識が無いのに
なんでプログラム板にいるの?
そもそもプログラミング経験無いだろ、お前。 異様に伸びてると思ったら深刻な問題祭りかい
いくらでも例外は挙げられるけど
再帰で書こうがループで書こうが計算時間や空間計算量はそんなに変わらんから
書きやすく、読みやすい方で書いたほうが良いんじゃない?
そんなに変わらないって言うのは十分大きな入力に対して精々2〜3倍以下に納まるって意味だからね。
1時間掛かる処理を20マイクロ秒速くする為にごちゃごちゃ書き換えるのは結構な事だけど。 はるかと言っても所詮定数倍でしょ。
しかも一桁違うケースは
関数呼び出しがやや高価なスクリプト系の言語でもほとんどないでしょ。 >>193
いやね,絶対的に再帰でないと書けない,いや非常に書きにくいものはあるのは確かで.
たとえば代数式の解析を非再帰的で記述しろといわれると「はたして出来るのか??」と逡巡してしまう.
こういう話題があまり発展しないのはどうしたわけですかね
関係ないけどquick-sort を三項演算子とコンマ演算子で書く話題,誰か‥私は挫折した‥ 再帰の深刻なデメリットと言えば、コンパイラ設計者が甘えてる事によってバグを触ったり
異常に速度遅くなるパターンが放置されてたりする事
なんの言語とは言わないけど それは再帰のデメリットではなくそういうクソコンパイラしかない言語のデメリット >>192
能書きはいいからとっとと実証しろ。超基本的な知識なんだろ。
「はるかに遅い」とか言ってるバカ仲間のサイトでも良いぞ。 >>197
なんか食パン裏返してこっちが表だとか必死に言ってるようなレスだな >>201
こうするとなかなか興味深いことになるね。
本当に興味深いと思ってるだけで他意は無いよ。
fun_rec(){
if [ $1 -gt 5000 ] ; then
time fun_for
return
fi
fun_rec $(( $1 + 1 ))
} >>203
たしかにおもしろい。
再帰の深さに比例して時間がかかる。
再帰が深くなると処理に時間がかかるようになるのか、
別の時間を測ってしまっているのか。わからん。これはわからん。 >>201
必死で再帰否定してるバカは知能が低いというエビデンス乙
シェル関数は呼び出しのたびに名前解決するのでペナルティが大きい Cの場合は入った時にフレーム作成と出る時にフレーム復元
c86なら、レジスタ操作4ステップ(複合命令なら2ステップ)だ。
名前解決なんかリンク時に終わってる。 最近の関数呼び出しは引数をスタックに積まずにレジスタ渡しみたいだから
再帰で何段ネストしちゃっててもレジスタに収まってる限りは爆速なんじゃね 名前解決まで計算時間に含めるなら
もう再帰云々じゃなくて長大な再帰なしの一つの関数で全部こなせって話になるんだがな
>>207
いや、そうはならない。
レジスタの退避が必要になるから、自己再帰するならどっちにしても同じだけpush/popは必要になる。
最適化が掛かったらその限りじゃないけど。 >>205
呼び出しだけじゃなく参照もね、iの。
localでもスタックフレームなめてるのかな? >>209
スタッフフレームは再帰に必要なステップだから、再帰のペナルティとしてあえて受け入れた。
シェルスクリプトを持ち出した時点で「スタックは容量制限が厳しい(場合もある)リソース」
を自分で否定しちゃうところが再帰否定してるバカが低知能であるもう一つのエビデンス(笑)
(場合もある)を知らないのか、教わってないのか知らないが、全ての場合だと思い込んでるところもバカの、特徴だね。 >>210
再帰で書いた何の変哲もないフィボナッチ関数をビルドしたケースを示すよ
https://gist.github.com/pixie-grasper/ba2d0ade523b8599c182
gccではr12を、clangではraxを、rbp/rbxの他に退避してるのが分かる。 そんな事をすると
既に退避させてある値を別なレジスタに退避させてから、退避させたい値を退避するコードを吐く羽目になるけど
レジスタが最低でも加算無限個無いと出来ないからね。仕方ないね。 externしていないstatic関数とかならレジスタ渡しもふつうにある。
もちろんCランタイム・コンパイラによる >>204
bashはダイナミックスコープだから再帰の深いところでは
変数の参照に時間がかかるのかな。いまはその辺を疑ってる。 だいたい再帰で問題が無いなんて
クイックソートで再帰が役に立たない事すら知らないってことか?
処理件数が増えたら速度の差なんて、何万倍どころじゃないし。 >>219
ファーwwwwwwwwwwwwwwwwwwwwwwwwwww >>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);
} >>223
10000倍高速化の比較対象はそれでも良いぞ。 一万倍とかwwww
どこをどうやったら一万倍差がつくんだ >>225
クイックソートの最悪の時間計算量はn^2なので
データによってはとても大変なんよ。 アルゴリズムの抽象化に静的言語使うチンパンとか話にならないから(´・ω・`)
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 >>225
最低10000倍ね。笑
>>219
>処理件数が増えたら速度の差なんて、何万倍どころじゃないし。
あ、小学生のように0.0001万倍とか言い逃れるかも。爆笑 ID:u0B3Sjd8
10000倍の高速化まだ? 常識的で簡単そうな口ぶりだったけど。 万は間違いだったとしても、最低でも倍速は楽勝なんだろ。 >>232
速度以前に >>223 は簡単にスタックオーバーフローするよ。
それを防ぐ方法を教えてやってよ。 >>233
繰り返し版が明示的スタックに使うヒープと同サイズに
マシンスタックの上限を変更すればOK いや、君に言ったわけじゃないし、最適化を教えてやれってことなんだけど。 >>233
バカなの? >>222読めないの?
10000倍の高速化まってんだから、くだらねー横槍入れないように。
お前が10000万倍高速化するならかまってやんよ。 >>226
繰り返しか再帰かに関係ないがな。
pivotの選び方次第だろ。
それは明示的にスタック使う繰り返し版クイックソートでも同じ。 >>238
>>225に対するレスとして
>>226はおかしいだろ。
気にならんのか? >>240
最悪パターンでもよいから、10000倍高速化しろよ。 スキルない人間をいくら叩いても何も出てこないのに
ここは動物園かよ 再帰を必死に否定しているバカの主張
1 スタックが制限の厳しいリソースである環境が全てだと思い込み、再帰の致命的なペナルティだと主張する
2 シェル関数呼び出しをエビデンスとして、再帰が130倍遅いと主張する
3 再帰版のqsortは数万倍遅いと主張するが、数万倍速いはずの非再帰版を示さない
4 知能が低く再帰を理解できない。それをもって再帰は難解と主張する。 >>245
そうやって執拗に絡むのもはっきりいって馬鹿丸出しだよ。
せっかく相手がクイックソートのコードを書いてくれたんだから
そのコードの問題点を指摘する方が賢そうに見えると思ったんだけどね。 >>246
さらなる意味不明なバカが出てきたな。
コード出したのは再帰を必死で否定してるバカじゃないぞ。 最初期は再帰をサポートしてなかった計算言語があるらしい 今はハードウェアレベルで再帰が実装されてるからな。
それを思えばいかに再帰が本質的にプログラミングに必要とされてるかってことだな。 計算可能性を探求する試みにおいて最初に出たのが、
エルブラン・ゲーデルの一般帰納関数だからね。
次がラムダ計算。
その次がノイマン型計算機直系の先祖であるチューリングマシン。 10000倍だっておとなしいぐらい。
再帰だと落ちまくるから∞倍だって当たり前だろ。 メモリ足りないなら動かないのは再帰もループも変わらんだろ。
ループのほうが本質的にメモリ使用量少なくなるとかなら話は変わってくるが。 これだね。本当に知能が低い。
> 1 スタックが制限の厳しいリソースである環境が全てだと思い込み、再帰の致命的なペナルティだと主張する >再帰もループも変わらんだろ。
なんで試してみないんだ?
再帰とループでクイックソート
ループ方式なら、データが何千万件あろうと無問題 覚えたての知識を使ってレスバトルするだけのスレなんていらねーから いらないスレを使って自分の意見を垂れ流すとか有効活用乙としか >>252
再帰の方は、関数呼び出し大量に発生するから、リターンアドレス待避とレジスタ待避に、メモリーが喰われる。 >>259
ループの方は今どの範囲についてソートしているのかという情報が大量に発生するから同じ議論が成り立つ訳だが。 >>260
ループはヒープ、再帰はスタック
つまり、ヒープとスタックがぼくらを助けてくれるんだ! >>254
>>222(再帰版qsort)で5000万件ソートしてみた。楽勝で終了する。
必死で再帰を否定しているバカが低知能だという事がまた証明されてしまった。
頭が悪いって本当にかわいそう。 >>262
再帰版でうまくいくのだったら非再帰版ではもっとうまくいく,という発想はないのかね? >>263
うまくいくって言ったって高々定数倍速くなるだけだろ?
非再帰版を書いたり保守したりするコストより新しい速いマシンを買ったほうが安く上がるって発想は無いのかね? >>263
知能障害者って本当にかわいそう。
5000万件でソート出来てるってことは、「再帰はスタックあふれる」という迷信が嘘だという発想には至らないのかね。
クイックソートの深さの制御はすでに研究し尽くされてて、全然問題ないんだよ。 あっ、繰り返し版は10000倍速いんだっけ? (爆笑)
早く実装コードみたいなあ。 >>266
そんなに実装したいのなら教えてしんぜよう。
5000万件で >>201 を実行してみたまえ。
再帰呼出しというのは効率が悪いとても頭の悪いやり方なんだよ。 シェルスクリプトを証拠として使うのは笑ってしまうからやめろ >>268
反論できないのな?じゃあお前の負けってことで。 野次飛ばしてる観客相手に勝利宣言も笑うからやめろ
おまえはプロレスのヒール役か >高々定数倍
そんな安全なもんじゃあねぇ。
データが増えれば差も増大。 >>267
ぷぷぷぷ
知能障害者は>>201をクイックソートと呼ぶのか? >>271
ミジメすぎるぞ。クイックソートのスタック消費量はlog nに抑える事が可能。
こんな基本的な事を知らないから数千万件はソート出来ない。キリッ
とか、赤面な発言しちゃうんだよ。 ちなみに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). */ >>272
バカかお前は。ボウフラサイズの脳ミソしか搭載してないのか?
ただの繰り返しでさえ130倍の差があるのだから
クイックソートを実装したらそれ以上の開きがあるのは自明だろうが。 >>275
バカはお前だ。シェルスクリプトでクイックソートを実装するなんて誰がするか。
sortプログラムを使え。
ちなみにシェルスクリプトの場合、関数呼び出しはそれ自体がスタックの深さをnとしてO(n^2)くらいの計算時間を持つっぽい。 >>275
ぷぷぷ。知能障害は本当にかわいそう。
qsortの繰り返し版は関数呼び出しの代わりに自前でスタック管理しなきゃならないんだよ。
10000倍高速化の実証コードはよ。 >>276
確かに、うん、確かに、非常にゆるやかに発散するね。
n=2^64としてもlog nは64だけどね。
定数と変わんないレベルだよね。 >>277
実装できないのな?無理なのな?はい論破。 >>278
>>201 がすべてを物語っている。
これが何よりの証拠。再帰がとてつもなく効率が悪いことを
つまびらかにしてみせた。ここに来て見てみぬふりは通用しない。
エビデンスもきちんと示されている。もはや知らぬ存ぜぬでは済まされない。 >>280
何万倍も高速だっ。キリッ。
って主張してる奴に実証責任があるんだが
ガイジにはわからないの? >>280
練習のためなら兎も角、シェルスクリプト「だけ」でソーティングなんてやる意味が無い。
ループだろうと再帰だろうとね。
理由は遅いから。
ループで組んだとしても、非常に遅いから、実装するだけの意味が無い。
sortを呼べばCで書かれた非常に高速でスケーラブルなソーティングが出来るから、普通はそっちを使う。
さぁ君は一体何を論破したというのだい? >>281
障害児くん
10000倍と130倍って、どっちがどれだけ大きいかわかる? >>282
>>201 で完全に証明してみせた。
反証する責任がお前にあるとは俺は思わないよ。
俺は自分の都合の良いように他人に責任を押し付けるなんて
卑劣な真似はできない。俺はただの真実の探求者。 >>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倍はどうやって稼ぐんだい? >>284
ボウフラ並みの脳ミソをメダカにでも食われたのかお前。
頭悪いにも程があるだろうが。こんな鶏頭野郎の
相手する俺の身にもなれ。なんていいやつなんだ俺。
聖人君子としか言いようがないわ。>>201 は5000回の繰り返しだ。
5000回の繰り返しでさえ130倍の開きがあるのだから回数が
増えれば差は開く一方だ。だから、>>267 で5000万と言ったのだよ。 霊がいるのかいないのかは判りませんが
人間の目が無いものを見ることがあるのは事実です >>287
5000回の再帰で130倍の差が開いた訳じゃなくて、
深さ5000の関数呼び出しで130倍の差が開いたって事を理解してる?
5000万要素のクイックソートなら最良のケースで深さ25の再帰だからね?
130倍どころか2倍にもならないからね? >>286
クイックソートを実装して試したのか?あ?
だれが実装するかと言っていたのと矛盾するだろうが。
つまり、君は嘘をついている。ゆえに俺が言ってることの方が正しい。はい論破。 >>289
当たり前だろ。小さな町の町長が東京の都知事になって
仕事をこなせると思うか?数が増えるほどにコストは増大するんだ。劇的にな。劇的にだ! >>292
すまん、その例えどこまで信用していいか分からないからそういうの語るときは式でお願い >>290
ヤってみたのか?ヤったのか?ヤってから言えや!
さっさとクイックソートのコード提示しろよ!
いつまでグズグズ言ってりゃ気が済むんだ
俺はお前がクイックソートをシェルで実装するのをあとどれだけ待てばいいわけ? >>295
再帰は数万倍遅いといったお前が実証しろよ >>294
log2・5000 : log2・5000 ? 30 ⇒ log2・50000000 : 10^4 ? A
QED. >>296
俺は >>201 で示したし、それで十分に満足の行く結果を得た。
>>201 に不満だというのならそれを超えるものをお前が書け。自分でやれ。
他人にやらせるっていうのは俺の常識からは考えられない。 >>298
お前がやるんだ。お前が言い出したことだろうが。 >>295
どうして俺が実装しなきゃならないわけ?
数万倍遅いって言い出した奴が実証のためにコードを提供するのが筋だろ? >>301
そんな筋は通らない。実証コードが欲しいといいだしたのは
お前なのだからお前が自分で書け。言い出しっぺの法則は
プログラマを始め科学的論証に関わる人間すべてに通じる基本原則だ。
どうやればそれを確認できるかという手順も道筋も結論も示した。
自分の満足のいくものが欲しいのなら自分で行動しろ。
他人の足にしがみつくな、気持ち悪い。 1万倍の実証コードとか言い出しといて書かないってどういうことよ?
他人に頼りっきりってどういうことよ?
夢があるのなら自分で叶えろよ
親の足かじってんじゃねえぞニート野郎 >>302
IDをよく見ろ。俺は実証コードが欲しいだなんて一言も言ってない。 >>297
何この記法初めて見た
もしかして情報界隈では常識なのか? >>219
親のスネかじってんじゃねーぞニート野郎
とっとと数万倍速いクイックソートの実証しろよ ID:6n5NtJkMは発狂して「再帰は数万倍遅い」発言をウヤムヤにしたい模様
でも、まだ300レス。先は長いぞ。頑張れ。 >>305
俺も見たこと無い。
一瞬、三項演算子にも見えるけど順序がおかしいし。 >>304
言ったかどうかは問題じゃない!
お前はクイックソートで1万倍の差があるのか確認したい、
それを確認する手段としてシェルでクイックソートを実装すればわかる
ということを俺は示したんだよ。それだけわかってればいいよもう! >>308
?はただの文字化けだぞ。
数理式計算量証明の理想解近似法を大学で習ってたらわかるだろ。
情報科学の基礎中の基礎だし。 >>309
いいや、そもそもそんな事は望んでない。よく読め。
俺が言いたいのは、1万倍もの差が出るなんて事は理論上ありえないって事だ。
それでも尚、実際に1万倍の差が出ると言い張るのであれば
それを実証するコードを君が示すべきだよね? >>310
すまん、その文字化けしてるところ元は何だったのか教えてくれ
O? >>311
だから、俺は示したって言ってるだろうが!
>>201 でくっきりはっきりと証明してみせただろうが。
それで満足できないというのであれば、満足の行くコードを見たいというのであれば
お前がそれを書くべきだ!それが論理的検証というものだ。科学的な姿勢というものだ。
他人の論文に満足できないと言ってるばかりじゃ学会では一切評価されないよ。
それを超える論文を自分で書いてこれでどうだと魅せつけるべきだ。
君はシェルでクイックソートを書くべきなんだ!! >>312
掛け算の掛けるだ。
右側では1万倍になってるのがわかっていただけると思う。 >>313
いいかい?
君は「示した」と何度もはっきり発言してはいるけど、実のところ何も示しちゃいないんだ。 >>315
バカかお前は。大脳半球が全損して産まれて来たのか?
名前解決に時間がかかるとするならば、名前解決まで含めて再帰呼出しだ。
外務省はシリアへの渡航を自粛するよう日本国民に通告しているが、そんな不安な情勢の中、
「シリアが危険なんじゃないテロリストが危険なんだ」と言って
意気揚々とシリアに出かけていく頭の中お花畑野郎と同じだろうが。
お前が言ってるのはそれと全く同じこと。
シリアという地域でテロの被害に遭う確率が高いから外務省は渡航を自粛するように
必死に呼びかけているんだ。少しでも日本の国民がテロの被害に遭わないよう骨身を削って
頑張っているんだ。再帰呼出しでプログラム事故に遭う確率が高いから俺は再帰を自粛するよう
呼びかけているんだ。外交官としての俺の立場に立って再考してみろ。お前がどれだけ
愚かなことを言っているか今一度ようく考えてみることだな。 障害児は
シェル関数呼び出しはwhileより130倍遅い
と
再帰版のクイックソートは何万倍も遅い
が等価らしい
必死で再帰を否定しているバカが低知能であることのエビデンスがまた一つ明らかになってしまった >>317
>>201 の画像が見えないのか?俺はエビデンスをしっかりちゃっかりくっきりまるっきり示したぞ。
お前はアイマスク付けて前が見えないと言ってるだけのただのうつけ者。話にならない。 もしかしてだけどさ、もししてだけどさ、>>201で示されてることってシェル関数呼び出しがシェルwhileより130倍遅いことだけじゃね? >>322
おいおいいい加減にしろよナメクジ野郎。
自らの関数を呼び出すことを再帰と言うのだろうが。
関数の呼び出しが遅い、すなわち再帰の効率がとてもよろしくないということだ。
テロリストが民間人を殺害するのならば、テロがはびこっているシリアには行くべきじゃないということだ。
お前、後藤さんのご家族の前で後藤さんが悪いって言えるのか?後藤さんは悪いよ。
とても危険なところと知りつつシリアに言ったんだから。だけど、それをご家族の前で言う意味がないよね。 再帰を使うっていうのはテロリストの前に自らの首を差し出すことと同義。
何があっても文句言うな。そして周囲の人間をその愚行に巻き込むな。
悲しませるな。俺はお前らが再帰を使うと悲しいよ。 純粋にシェルスクリプトだけでクイックソートを組むのは骨が折れたぞっと
http://www.fastpic.jp/images.php?file=2429159438.png
ループのほうが遅いです本当にどうもありがとうございました ____
/ \
/ ─ ─ \
/ (●) (●) \
| (__人__) |
\ `⌒´ ,/
/ ー‐ \ シリアとか言わなきゃよかった
後藤さんのくだりとか意味わかんないし フィボナッチとかはループと再帰で指数倍の差が出るんだっけ? >>334
それは再帰的定義を使う方では?
フィボナッチ数列の第n項を直接nの式で表せるはずだが >>335
文脈読もうな。
メモ化に必要な記憶領域が線形ではないか、と言ってる奴がいたから定数だ、と答えただけ。 再帰メモ化定数メモリフィボナッチってどんなソースになるの? fibonacci = fib (0,1)
fib (m1,m2) 0 = m2
fib (m1,m2) n = fib (m2, m1+m2) (n-1) タプルの代わりに木かハッシュを使えば値を全部保持する
普通のメモ化にできるがフィボナッチの計算にはもちろん不要 >>325
bashを使うのであれば
if [ $i -ge $j ]; then
の代わりに
if (( $i < $j )); then と書ける。
また(( )) の中で単体の変数は$を省略できる
if (( i < j )); then
一行で書くこともできる。
(( i >= $ )) && break stack=("${stack[@]:0:((${#stack[@]}-2))}")
これは、こう書ける。
stack=("${stack[@]::${#stack[@]}-2}")
ついでに、""をつける方が正しいのではあるが、
値にスペースが無ければ、"" は省略可能。 p=$(( $((${array2[$i]}+${array2[$j]}))/2 ))
$((・・・)) の中では普通に () が使用可能
p=$(( (${array2[$i]} + ${array2[$j]}) / 2 )) for i in `seq 1 1 1000`; do
`` は基本的に $() と同等。新しい$()の使用が推奨されている。
for i in $(seq 1 1 1000); do
また、これは以下のように書ける
for i in {1..1000}; do 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 が未使用
その他の警告は、上の指摘を修正すれば消えるはず ループ版で時間がかかってるのはこの部分な気がするな。
配列をコピーしているわけだし。
stack=(${stack[@]::${#stack[@]}-2})
http://www.drk7.jp/MT/archives/000995.html
さて、ここの非再帰版を見ると、どうも配列のコピーはしてないようだ。
ループ版は高速化の余地がありそうだ。
やってみるかね? うまく実装できるかな? ループの途中でコマンドを呼び出すようにすればもう少し遅くできるんじゃないかな。 さーて、コードをほとんど読まずに、Perl版をそのまま置き換えてみたが
きちんと動かんぞとw 面倒くさいな。
速度的には再帰版より速くなりそうな感じはしてるが、処理間違ってるからなw あ、できたっぽい? 参考にしたコードに二箇所バグが有るようだな。
> &qsort_array($array2,0,$size);
> $right_stack[0] = $right;
$sizeが$rightに入るが、正しくは$size-1
> if ($i - $left < $right - i) {
↓
> if ( ($i - $left) < ($right - i) ) {
Perlの優先順位は、下のように解釈されるんだっけ?
そんなの変えないよな。
今コードを見直してる。 Perl版実行してみたがもともとのコードからして動いてないw マジめんどくさかったわw 参考にしたコードが悪すぎた。
他のコードと比べてよくわからん比較条件とか処理が多かったので
結局諦めてこっちを参考にした。
http://gauc.no-ip.org/awk-users-jp/blis.cgi/DoukakuAWK_102
結論。やっぱりループのほうが速かったねw
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 ループの方が速かったので訂正よろw
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]
ぐうの音も出ないなこれは >>356
>>219の主張を受け継いで高速化したお前が言い出しっぺ 言い出しっぺの定義を変えるなよw
本当に往生際が悪いw >>353でお前が訂正を求めたレスはID:6n5NtJkMの
「再帰は1万倍遅い」に対するレス。
なので、訂正を求めるには10000倍高速化する必要がある
知能障害児には理解不能かな? と言われてもなぁw
俺は1万倍速いなんて言ってないし。
ループのほうが速いという証拠も出したからどうでもいいかなw >>361
これでいいのかい?w
ループの方が速かったよwww
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]
ぐうの音も出ないなこれは 少し速いと10000倍速いの区別がつかないおバカさんとうエビデンス(笑) 分かったことは
・再帰をただ単にループに直すと却って遅くなる
・最適化を施せばループのほうが速くなるが、10000倍速くなるなんてことはない
の2点でおっけい? そうだな。シリアがどうとか言い始めるほどループの方が優秀な訳では無さそうだな ∞倍だね。
再帰なんってのと比較すること自体おかしい。
却って遅くなるなんて書いてる恥知らずは、プログラミング技術が無さ過ぎ。 >>366
昨日から昨晩に掛けてのやり取りを知らないのか?
俺はそのやり取りから、>>364が分かった事の全てであるって発言しただけなんだけど。 やり取りからだって?
2chの妄想だけじゃなくて現実を見ろよ。 ∞倍 wwwww
無限大を憶えたての小学生かよ
quick sort 再帰/quick sort 非再帰 = ∞, すなわちquick sort 非再帰が0って事だな。
再帰を必死に否定しているバカの主張
1 スタックが制限の厳しいリソースである環境が全てだと思い込み、再帰の致命的なペナルティだと主張する
2 シェル関数呼び出しをエビデンスとして、再帰が130倍遅いと主張する
3 再帰版のqsortは数万倍遅いと主張するが、数万倍速いはずの非再帰版を示さない
4 知能が低く再帰を理解できない。それをもって再帰は難解と主張する。
5 非再帰版qsortの実行時間はゼロ
本当に知能が低い >>364
最適化なくてもループのが速いでしょ
10000倍は無いがw >>368
お前の中ではそうなんだろうな。そんな事より現実を見ろよ。
大本の彼らの主張は「クイックソートをお題にした場合に於いて再帰はループに比べて何万倍も差がでる(>>219)」
俺らの主張は「そんなに差がでることは理論的にありえない(>>286)」
であって、
ループのほうが再帰より「僅かでも」速いかどうか(>>352-353)なんざ元々議論していない。
クイックソートをやる上で比較にならないほど再帰のほうが遅くなるというならソースを出せや 繰り返しの方が再帰より速い!
(ただしシェルスクリプトに限る) >>371
引数受け渡しとかレジスタ待避とかで、余分なメモリー操作が発生する。 >>374
>>260
定数オーダーの空間計算量で計算が出来ないなら、原理的に余分なメモリ操作は避けられない。
それはループでも一緒。 >>374
明示的なスタック操作と大差ないのでは? >>373
純粋に処理速度の話してんならネイティヴコード化したものでないとさ >>375
横ですが、再帰呼出だとcallのオーバーがある分遅くなるで良いのかな?
まあ数パーセント程度だと思うけど クイックソートだからなんとかなってるだけで
たとえば赤黒木の操作を自前でスタック管理するアホはいないわけ >>378
Pen4のデータシートの値を元にするなら
ループのコストと再帰のコストは約2.5〜3clockくらいの差になると思う。
今時のCPUならもっと差は縮まるだろうし、実際に測った訳じゃないけど
だいたいそのくらいになる筈。 >>381
最適化が無くてもループの方が「僅かでも」速いって言い張るお前に
そうじゃない場合もあるって言ったのが>>373
で、それに対しお前はネイティブコードで比較しろっつーから
「最適化無しのネイティブコードで」比較したんだが。
一体お前は何を求めてるんだ? >>382
そこまで解説できる人ならネイティヴコードだと逆転するのわかるでしょ
アセンブリで書けとは言わんけどさ
>>381はすまん >>384
ループ以外の本質的な処理に100clock掛かるとすれば、
数%の差だけどループより再帰のが遅くなるって意見は正しいねって話さね
381については了解 >>378
tail callを繰り返しに変換できるようなケースだと
関数呼び出しはコスト高かも知れないが、
ループ版では明示的スタック操作をしなければならない場合、
call,ret相当のことをjpと組み合わせて明示的にやらないといけない。
通常、関数呼び出し後のスタックフレームの確保はcalleeが明示的にやるからループ版と変わらないが、
スタックフレームの開放はretが自動的にやる。
だからコスト的には大差なく、
関数呼び出しの方が有利なケースだってあるはず。
繰り返しの明示的なスタック操作が圧倒的有利にあるのは、
FILOじゃなくてFIFOにしたり戦略が建てられること。 >>379
お前は何を言っているんだ。
FreeBSDもLinuxも.NETもJavaも赤黒木はループで実装してるぞ。
再帰はプログラムの中に時限爆弾仕込むようなもの。再帰使うやつはテロリスト。 頑張ってバグ入れずに済んでよかったね、としか。
しかもそれで得られる速度の向上も微々たるもの。 >>389
再帰にしたらバグが減るってものでもないしなあ。
不変オブジェクトを使うから再帰がやりやすいのであって
可変オブジェクトでの再帰はループよりもややこしいところがあるよ。 >>388
>赤黒木はループで実装してる
本当か?やればできるものなのか?証拠をみせてみろ
平衡ニ分木であるからスタックもむやみに深くならないし,
正直なところ,可能だとしてループ化するメリットがあるのかね >>391
freebsd red black tree source
とかで検索すれば出てくるよ >>390
バグ云々ではなくて、コード数や可読性だと思うが
そもそも再帰呼出を理解出来ない人は論外だが 知らないうちにコードが再帰化してハマりました
のほうが多そう >>395
バグが増える要因はプログラミングソースのステップ数や可読性に左右されるのであって、アルゴリズムは特に関係ないということ >>396
アルゴリズムによってステップ数や可読性は変わるよ >>388
LinuxもFreeBSDも木全体に対して何らかの操作を行うインターフェースを実装してないからあたりまえ。
どっかで見たことある気がしたので探してみたらunbound
http://code.metager.de/source/xref/freebsd/contrib/unbound/util/rbtree.c
また一つ、再帰否定バカが無知のエビデンス(笑)を積み重ねていく >>398
知らない人がいたから言っただけだよ。
ループで実装されてるんだよーって。
インターフェースを実装してないからとか理屈付けする意味あるのかな。
バカはお前。 インターフェース?
再帰と関係あるのかな?
わからん。この世はわからんことだらけだ。 > LinuxもFreeBSDも木全体に対して何らかの操作を行うインターフェースを実装してない
?
OSが…インタフェースを…実装? >>399
ねぇねぇ
そのループで実装されてる>>398のコードでも
自前でスタック管理してる訳じゃ無い。
とすると、>>379に対する突っ込みとしては>>388変じゃない? >>402
スタック管理の解釈次第だね。>>388が変だと結論できる解釈もありだね。 >>403
ほう、つまり君はただのループをスタック管理と解釈する訳だね? 最近、書き込みが多くなって
このスレの勢いがすごい >>406
確かに。
>>256から数えて、1日半で150も伸びてる。 >>405
再帰をループに置き換えるときには
再帰で暗黙的に管理されるスタック上の情報を
明示的に管理する必要がある。それをやるのは面倒だから
赤黒木は再帰で実装されているはずだというのが>>379に関する俺の解釈。
面倒なことないよ、現に赤黒木はループで実装されることが多いよっていうのが>>388 語句の解釈に文句つけるのはあまり建設的じゃないような・・・。
その先には何もないような・・・。 クイックソートについても再帰のスタックをそのまま
ループで再現するっていうのはどうかと思うなあ。
末尾再帰は単純なループに変換できる。ループで書くならループらしい書き方をするべき。 >>408
ふーむ。
複雑な再帰構造を持つ場合、例えば再帰下降構文解析器みたいに複雑な相互再帰をする場合には
クイックソートの時のように簡単に再帰をループで置き換えることは出来ない。
そして一般に再帰をループで置き換えるならスタックが必要で、
込み入った再帰をスタックを使ってでもループに置き換える奴は居ないだろう。
現に赤黒木をスタック管理をしてでも強引にループで書き直すようなアホは居ないんじゃないの?
というのが>>379に関するこっちの解釈。
それに対し、いやいや赤黒木はループで実装してるんだぜ!ってのが>>388の俺の解釈。
話が噛み合って無くね?ってのが>>402
日本語の問題な気も >>411
解釈が違うのなら話が噛み合わないことについては筋が通るかと。 >>410
そもそもクイックソートは分割統治法の典型例だからなぁ。
自分を2度呼び出す時点で末尾再帰的じゃないし
ループらしい書き方をするとクイックソートとは呼べないシロモノになると思う あ、勿論クイックソートをもっと単純なループで書き直せるってんなら歓迎するよ! >>413
一方の再帰呼び出しは末尾再帰になるっしょ。ループに置換できる。 >>412
複数の解釈の仕方がありうるなら、
オレオレ解釈を元に相手をこき下ろす前にやることがあるだろうと >>415
・・・・・・それは依然として再帰関数と呼ぶのでは? >>416
僕とー君とーは解釈が違うよねってことだよ。
こき下ろすべきじゃないと思うのは君の勝手ー。
こき下ろすのも僕の勝手ー。
ヒューマニズム振りかざす人大嫌いー。←これ僕 >>417
ループを書く場合、一方の再帰呼び出しは末尾再帰だから
単純なループに置き換えられるよねってことだから、もはや再帰関数とは呼ばないよ。 >>418
いや、君が>>403で言ったのは「スタック管理」の解釈の違いだろ?
「赤黒木が再帰で書かれてる」等とは一言も言ってない>>379を読んだ君が>>408みたいな解釈をして、
人のことをテロリスト呼ばわりするのってどうなの? >>419
https://ja.wikipedia.org/wiki/%E5%86%8D%E5%B8%B0
「再帰とは、あるものについて記述する際に、記述しているものそれ自身への参照が、その記述中にあらわれることをいう。」
ループを含む関数は再帰関数にはなれないの?
そんなことはないと思うんだけど。 末尾再帰を勘違いしている人がいるので説明しておこう。
末尾再帰は「再帰を末尾再帰で書けば速くなる」というものではなくて
(単純な)ループを何らかの理由で再帰の形にしないといけない時、
末尾再帰の条件を満たすように、ループを再帰に変換すると
コンパイラが再帰をループに逆変換してくれる機能
なので、再帰を全て末尾再帰にできるわけではなく
(末尾再帰にできるのは、元が単純なループの場合のみ)
また、ループ ─(人間)→ 再帰 ─(コンパイラ) → ループ
というふうに、ループに戻しているだけなのでループより速くなることはない。 >>401,404
FreeBSDのrbtreeもLinuxのrbtreeもそういうインターフェースを実装していないって事だよ。 >>422
より正確には、「再帰全てをノーコストで末尾再帰にできるわけではなく」かな。
関数がファーストクラスならCPSに変換すれば末尾再帰の形にはなる。
・・・・・・ヒープガリゴリ使うし、スタックを自前で持つのと変わらんけど。 >>420
>>379は「赤黒木が再帰で書かれてる」とは一言も言ってないけれども、
「赤黒木の操作を自前でスタック管理するアホはいない」と言っているのだから
赤黒木の操作は、自前でスタック管理しないやり方、つまり再帰で実装される
と思っているという解釈は妥当だと思ってる。悪いけど、この解釈については譲歩するつもりはないよ。
120%君が間違っているし、再帰を使う人は120%テロリスト。それでいいね? >>424
速くするための末尾再帰なのに、
逆に遅くなったら本末転倒だよなw >>421
無理。再帰を使うなら全部再帰で書くべき。
ループを使う処理では再帰を書かない。
再帰を使う処理ではループを書かない。
それで初めてループと再帰の決着がつけられる。
そしてループが勝利する。 >>425
確率が1を超えてるとか、幼稚園に迷い込んだ気分だよ。
「赤黒木の操作を自前でスタック管理するアホはいない」と言っている以上、
赤黒木の操作は、スタックなんてものをそもそも自分で触らないようなやり方、
つまり再帰か、又は上手なループで実装されているって話だろ?
フィボナッチ数を計算する関数をスタックを使わずに書いたって言った時、君は再帰の方しか思い浮かべられないのかい?
もしかして自閉症患者かい? >>427
それじゃぁ各ノードに可変個の子要素を持つ多分木を列挙するコードは
どうやって書くつもり?
for (auto it : children) {
if (it->is_leaf()) {
printf("%d ", it->value);
} else {
it->print_values();
}
} >>428
>>389を見るに、そうじゃないと思うんだがなあ。
俺は自閉症患者だけれども、それとこれとは関係ない。
お前は全国の自閉症患者やそのご家族の方に謝罪するべき。
あとテロリストにも。 >>429
どうやってって何がだよ?
ループでか?再帰でか? >>430
日本語って難しいよね。分かる分かる。
>>389の解釈は、
再帰でも書けるところをループで書いたんだ。へぇ。バグってなくて良かったね。ご苦労さん。
じゃないの?
>>379が再帰を仮定しているかどうかとは別問題。
俺も自閉症患者だけどね。自分に謝るのって変な感じがするよ。 >>431
どっちでも良いけど、どっちかしか「使ってはならない」というローカルルールの元ではどう書くの? >>431
まだ出来ないの?
>>429に7行で書いたような、こんなコードが走ります的な切れ端で十分伝わるんだよ? >>432
スタックで管理の解釈の違いだな。やっぱり噛み合わない。 >>434
あのさ、同意も取らずに強引に物事を進めようとするのってどうかと思うよ。
北風と太陽って話くらい知ってるでしょ?コンセンサスってとても大事。
お前コンセントしか知らないだろ。扇風機の線をぶち込んどけば何とかなるものと
しか思ってないだろ。それじゃないからな。
まずは、どういう理由で書いてほしいのかっていうところと
それによって何が成し遂げられるのかっていうところとどうして自分で
やらないのかって言うところを説明して、心からお願いしないと俺の不動の心は動かないよ。 >>435
残念。
>>436
ループを含む関数が再帰関数になれないのであれば、
>>429のような書き方は認めないって事だよね?
君ならどう書くの?って聞いただけなのになんでそんな反応になるのかね? 横道にそれ過ぎずに、それぞれの論旨を書いてみろよ。
中傷合戦ひどくてわからん。 >>437
ループと再帰の優劣をつける場合、ループはループだけで
再帰は再帰だけで実装するべきだよねって話をしただけだよ。
お話の前提をすり替えてあたかもお話が続いているように
するのはよろしくないと思うんだよな。 >>438
俺は畑を耕していただけなんだ。そしたら ID:Zmrinoji こいつが
機関銃もって脅してきたんだ。おらはイモが食いたいだけだ。再帰使うやつはテロリストだ。
恐ろしいことだ。 >>438
大本の論旨としては、人のことをテロリスト呼ばわりするのってどうなん?って事なんだけど。
ループと再帰の優劣をつけるなんてどこから出てきた? >>441
テロリストと呼ばれるのが嫌ならテロ行為やらなければいいだろ。
クイックソートでやってただろ。ループがいいか、再帰がいいかって。それのこと。
知らなかったの?じゃあ知って。今知って。 バッファオーバーフロー攻撃を成功させるためには、再帰が最も都合よい。 攻撃されるのと攻撃するのと、どちらが良いか?
当然、攻撃する方が良い。
つまりテロリストは勝ち組なのである。
当該スレにおいて再帰を推奨している人は勝ち組である。
なぜなら危険物を推奨するのは攻撃側だからである。 >>443
そういうことだな。昨今、関数型言語の流行に伴って再帰がすぐれたものであると
思い込んだニワカのペーペーどもがろくな知識も持たずに危険なコードを
書きまくって悦に入ってる姿を見ると暗い気持ちになる。再帰というのは
ループに大敗北した歴史を持つものだっていうのを知って欲しい。
for whileというのは再帰の進化形。メガ進化。 お前ら逮捕されても知らんぞ。
公共の場所で再帰を勧めたりしてたら、そのうち警察が事情を聴きに来るぞ。 どうでも良いけど、再帰がテロ行為になるなんて初耳だなぁ
# 今日の夕飯はすき焼きでした >>447
自動車の256バイトしかないRAMで再帰したら、バシバシ轢き殺すぞ。
そこまでやってこそ本物のテロリストだろ。 >>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
「住民を威嚇する、または政府や国際組織を強制する、あるいは行動を自制させる目的で、
市民や非戦闘員に対して殺害または重大な身体的危害を引き起こす事を意図したあらゆる行動」
だそうですよ。
あと自動車の場合、バシバシ轢き殺すなんて事態にはならず、単にエンストするだけだと思うの。
フェイルセーフって知ってるよね? >>440
> 俺は畑を耕していただけなんだ。そしたら ID:Zmrinoji こいつが
> 機関銃もって脅してきたんだ。おらはイモが食いたいだけだ。再帰使うやつはテロリストだ。
俺の知ってる事実と違うね。
俺は今日は364から話を始めた。そこにID:9aquywWvが388から割り込んできて、
人のことをやれテロリストだやれ機関銃をもって脅してきただ喚いてるの。 >>450
テロリストは自分のことをテロリストだと思っていないんだよな。
聖戦士だと思ってる。
正義のために再帰を仕込むんだよな。
まあでも、国民側から見ればテロリストなんだけどな。 再帰なんてある意味爆弾みたいなものだしな。
テロリストが使う新型爆弾なんじゃねーかな。 そうやって正義の為にループを仕込むんだね?
よく分かったよ!
ちなみにバッファオーバーフローの攻撃手法としては再帰は下の下だからな。
getsなんかを使った方がよっぽど手っ取り早い上に任意コード実行まで出来る。 >>450
聞かれたから答えてたけど、>>388は君に対するレスじゃないよ。 >>454
知ってるよ?
でも再帰使うやつはテロリスト発言で敵を増やしてないかい? >>455
割り込んでないよね。テロリストと糾弾されて君が勝手にファビョッただけだよね。
僕は畑耕してただけ。 >>456
文脈をよく読もう。
364から始まる再帰とループに関する話に混ざった379に君が割り込んでるね? >>457
割り込んでないね。僕は>>379に話しかけただけだね。
君が>>379とお話したかったのなら>>379に話しかけるべきだね。 >>458
そうだね、偉大だね。
スプンタ・マンユに祈りを!(宗教ちげぇ) >>460
いわゆる暇人という奴では。
>>461
木構造って知ってる?
あと、俺はそのレス(>>379)にその返し(>>388)って変じゃね?って言っただけで、
それに対して君が「スタックの管理とは」なんて話を始めるから(>>403)
そのコード(>>398)の何処にスタックなんて使われてるんですか―って訊いて(>>405)
それに対してまだ答えが返ってきてないんだけど。
君はあれかな、都合の悪い質問は見なかったことにする人なのかな。 >>463
なんで僕にレスしてくるの?
自分が話したいことがあるならそれを話せばいいじゃん。
僕は僕で自分の話したい話を話したい人とするから。
たまたま>>379だったってだけで君が>>379と話したいなら
僕はそれを否定しないよ。割り込まれたとも思わない。
ほら話しかけろよ。>>379も絶対お前のこと好きだって。
言っちゃえよ。好きだって言っちゃえよ! >>466
それで、人のことをテロリスト呼ばわりするのってどうなん? >>467
違うんだ、待ってくれ、君のことをテロリストと言ったんじゃない。
再帰を使う人はテロリストなんだ。君じゃない。 >>470
つまり、>>469で示したように再帰を使う俺はどっち? やっぱり再帰無しでループによるプログラミングが最高だね! 私生活において自分ほど品性の高い奴はそうそういないよ
何をしていてもカリスマ性があふれ出してしまう 「しね」というのは、実は奥の深い言葉なんだけど知っていましたか?
プログラム中でいえばNULLと似ている
人はなぜ生きるのか、なぜ死なないのか、
その真理を見つける事は誰も出来ていない
よって「死」とは恐怖かもしれないし、救いかもしれない
つまり正解でも不正解でも無い
それゆえに「しね」という言葉を発しても、敵と味方は最終的に五分にしかならない意味のない言葉なんです
だから頻繁に使っていくと良いよ >>423
インターフェースとか抽象データ型ってことを理解できてないから、
そう言っただけでは理解できないんだと思うよ。 >>485
お前のほうが分かっていないような気がするが‥ >>422の「なので、再帰を全て末尾再帰にできるわけではなく」とか恥ずかしいよなw >>489
>422 「再帰を全て末尾再帰にできるわけではな」いのは当然だが,どうしてはずかしいんだ? > コンパイラが再帰をループに逆変換してくれる機能
恥ずかしい発言はこれだね。 掲示板ではレベルのミスマッチがよくあるんだよな。
たとえば、アセンブリと機械語は一対一で対応していると純粋に信じてる人は世の中に結構多い。
そういう人たちとプロセッサのデザイナが掲示板で議論すると当然ミスマッチが起こる。
こういう場合、当然勢力の面でデザイナの方が分が悪くなるね。
世の中、知ったかぶりのバカの方が多いから。 手動で末尾最適化をしてみればいいんだよ。
そうすれば、なるほど、
これが最適化されたコードなんだな!って
ループになったコードを目の当たりにすることになる。 そういう周りくどい事やってるうちは三流
uyの領域に到達すると文章読むだけで理解する >>491
コンパイラが再帰をループにしてくれる機能はあるよ,恥ずかしいのはどちら? 再帰の方が有利なら、わざわざループに変換するなよ。
むしろ、ループを自動的に再帰に変換しろよ。 >>492
逆変換が意味不明
単に変換なら同意するけど 再帰が実用的でなく
ループの方が有利だから
変換しないといけない。 >>498
それは文脈による,よく逆電圧っていうが実は順電圧だったりすることはあるし >>501
> それは文脈による,
だからこの文脈だと意味不明って言ってるんだが
> よく逆電圧っていうが実は順電圧だったりすることはあるし
ますます意味不明 分かるように説明できないんじゃ周りは皆分からず屋に見えてしまうね 我々市民はテロリストを納得させるような言葉を持たない。
従って、テロリスト自ら変わらない限り、テロリストは永遠に市民の敵である。 >>496
キミの方だとおもうよ。ぷぷぷ。
「末尾再帰は... コンパイラが再帰をループに変換してくれる機能」
> 末尾再帰は「再帰を末尾再帰で書けば速くなる」というものではなくて
> (単純な)ループを何らかの理由で再帰の形にしないといけない時、
> 末尾再帰の条件を満たすように、ループを再帰に変換すると
> コンパイラが再帰をループに逆変換してくれる機能 >>496
それは、「末尾再帰最適化」というコンパイラの機能だね。 「ループを再帰に変換すると、コンパイラが再帰をループに逆変換してくれる」
頭沸いてるだろ。ぷぷぷ。最初からループで書いとけよ。 そんなんじゃ小説なんか読めないだろう。
読解力なさすぎだよ。 読解力が足りないとか言いだしたぞ。このバカ。
> ループを再帰に変換すると、コンパイラが再帰をループに逆変換してくれる機能 >>490
再帰はすべて機械的に末尾再帰に変換できる。
そんな基本的なことも知らないのは恥ずかしいだろう? おー、すげー。天才現る。
これで、スタックオーバーフロー完全克服だ。 末尾再帰に変換できるとは言ったが,スタックオーバーフローを回避できるとは言ってない(キリッ クイックソート10000倍高速化とか再帰→末尾再帰の自動変換とか、このスレには天才が多いな。 >>510
俺は第三者だ。
俺は書き込んだ奴の言いたいことが容易に把握できている。
それがキミにはできないという。
再帰についてのスレで再帰について書かれているのだから、バックボーンの違いではないだろう。
知識ではなく読解力の問題だ。
こんなもん小学生でも意味をくみ取るぞ。 >>516
>>422を理解出来てるのか? こりゃすげーわ。
ループを再帰の形にするときに、ループを再帰に変換すると、再帰をループに逆変換してくれるコンパイラの機能が末尾再帰?
>>422が末尾再帰を理解してない事が読み取れるだけだ。
それをお前が読み取れるという事は、同一人物以外あり得ない。 そんなんじゃ小説も読めないだろう。
末尾再帰とは、本来ループで書くべきものを再帰で書いた時にコンパイラが
自動でループに直す機能・・・という主張なのだろう。 >>515
よくいるんだわ。より難解な前提が必要なのに、出来るよって言い出す奴。 逆変換という言葉は、そういった前提があって出てくる言葉だと思うぞ。 コンパイラが最適化してくれるならコンパイラにやらせるのが普通の話だよね >>520
末尾再帰の説明に「逆変換」を使うってどういう前提だよ www >>523
本来ループであるべきものをプログラマが再帰に変換しているので、
コンパイラがループに逆変換するという主張なのだろう。
お前、本当にこの程度の文章が読めないの?
そんなんじゃ小説どころか論文も読めないだろう。
俺は元の文すら読んでいなく、引用されてるのを見てそこまで理解できてるぞ。
もう一度聞くけど、お前本当にこの程度の文が読めないの? > インバータ(Inverter)とは、
> 直流電力から交流電力を電気的に生成する(逆変換する)電源回路、
> またはその回路を持つ電力変換装置のことである。
> 逆変換回路(ぎゃくへんかんかいろ)、逆変換装置(ぎゃくへんかんそうち)などとも呼ばれる。
逆変換w >>519
>よくいるんだわ。より難解な前提が必要なのに、出来るよって言い出す奴。
何言ってんだこいつ >>524
おおー、スゲー
その調子で>>422を解説してくれや。 >>526
読解力が、足りない。
半端な知識を振り回す知ったかぶりが沢山いるという事だよ。 >>528
それは読解力関係ないだろう。
俺にも全く意味が分からなかった。
何言ってんだコイツ?というのが素直な感想。 http://athos.hatenablog.com/entry/20110119/p1
ここまでこれの話題ないって相当終わったレベルの奴らしかこのスレにいないんだな
さっさと死ねよ >>531-532
本当に頭悪いカスだな
rubyに限定せず実装出来ると思うけど技量的に理解すら無理な感じ?
再帰とループの変換や末尾再帰の話題には触れてもここはTCOという単語が今まで一回も出てこないという事実
「知ってる側」からすると嘘をついてるのがすぐにわかってしまう
知ったかぶりのクズ >>533
だって末尾再帰なんてlisp/schemeでは当たり前だもの,今はgccでも当たり前だし
いまさらrubyですかね‥ むしろ自分でやんないと末尾呼び最適化が利かない処理系って(ry >>533
何度も出てるし「末尾再帰」といった時点でジャンプへの変換という意味を持っていってるんだよ。
最適化が無ければ「末尾」と特別な扱いをする意味が無い。
runyって最近言い出したのか。30年遅れてるな。 理解度が低すぎる
このアルゴリズムはこのスレでは初出だと認識してるけど
読めなくてわけわかんない状態か
さっさと死ねゴミ 妥協点でPythonだからね
それ以下の言語でアルゴリズム語ってるスレ見ると
そこで話してる内容とか読む前に
まずはスレ民を学習させる事から初めて
レベルを上げてやらないと話にならない >>540
末尾再帰のループ最適化は >>5 や >>507 ですでに出てきているよ
>>541
最適化の話題なら python や ruby のようなインタプリタではなく
コンパイラで比較するのが適切だね,インタプリタ上で速くなっても
だれもうれしくない.C/C++一択だよ
ま,fortran でもいいが >>542
理解力なさすぎだな
お前の学校の担任はさぞかし苦労したことだろう >>546
どんな点をみて「理解力がない」と判断したのか?
説明できますかね,それとも吼えるだけ? つか、末尾再帰ってループそのまんまで再帰の利点ないし
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()...
}
}
再帰で有意味、この場合使える pop,push逆だった
loopHoge2(a,n,arg...){
while(a<n){
popargstack();
dobefore()...
pushargstack();
doafter()...
}
} pushargstack();
popargstack();
ユーザー定義のこれらはめんどくさいから
再帰関数使ってコンパイラ任せにするよ またゴミカス初心者が来たけど
また1から説明して教育しなきゃいけないの? 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();
ユーザー定義のこれらはめんどくさいから、再帰関数使ってコンパイラ任せにするよ
たったこれだけの内容 >>551
>>552
以上のことの何があるか説明してみてよ ttp://nas6.main.jp/Maze.cpp
再帰、ループ、等価迷路 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();
ユーザー定義のこれらはめんどくさいから、再帰関数使ってコンパイラ任せにするよ
たったこれだけの内容 、勘違い訂正 >>554で、
ループ実装が好きなやつはいないと思うんだけどな RubyかPythonで書き直して
C++とかいうゴミいらねーから 「{C++規則をかなり抑えてCライク}で書かれたソースコード」
のクロスランゲッジなんて、ほぼ、ライブラリの関数名を書き換えるだけだろ あ、あと制御構文もちゃっちゃっと書き換えれば出来上がり それをなぜ最初から簡潔な言語で書かないで
わざわざ冗長したC++・C言語といった言語でドヤァとソースコード貼りつけてくるのか、理解しがたいんだけど
カスレベルの初心者である事を数レスに渡る自己紹介でもしにきたのかね?
アルゴリズムの抽象化でC++とか使う奴はその時点で初心者だって一瞬で分かるって言ってるのに
自分が知恵遅れだと分かってないままの奴が続々現れるからこういう場所は話題がループする 熱烈なC++アンチって速度要求される場面に出会ったことがないんだろな
もしくはフォートラン信者なんだろな オッパイソンはベーシックみたいなもんで非プログラマが使うのに適してるけど、
プログラマが使うには色々しょぼすぎ。
ペイントショッププロのマクロにオッパイソンが採用されたときは、来るかと思ったけど、
それを機に没落していった。
イヌックスの呪いは有名だけど、オッパイソンの呪いもあるのかもしれん。 しかし、エクセルのマクロ使いはザラにいるのに、他のアプリはマクロ使いが
ほとんどいないんだよな。
イーマックソとか言うウンコは置いといて。
CADなんかマクロの使いであると思うのだが。
Autocadなんかウンコ使いが泣いて喜ぶLisp搭載してるのにな。
なんでだ。 とりあえずuyがほんとになにもわかってないことだけわかった 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 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 def recHoge2(term,arg...)
dobefore(arg...)
if term
recHoge2(term,arg...)
end
doafter(arg...)
end
で、こんだけで済むのに、
ループにしたいからって
スタックのユーザー定義なんて馬鹿だろう 再帰をループにしたかったら
こういうのをいちいち作らなきゃだめだよ
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 プログラミング半年目くらいだろうかコイツは
多く見積もって1年半
それ以上なら今すぐPC捨てたほうが良いレベル 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 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 #同色上書き塗りつぶし
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
↑のループ等価が↓ 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 #下
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 再帰関数を無理矢理ループで書くことが
正解だなんてとても思えないんだけど・・・ >>575-577
はdestにcolorが最初から使われていると、それ以上塗れないバグがあるな
ま、いいか destはコピー先だからそういう条件でクリア済みってことで 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 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()に飛ばすように考えるのもめんどくさい
つまり、再帰関数の構造化の部分までなんでわざわざ
コーディングする必要があるのか謎 そうだね、グリーンだね。
任意の再帰はスタックを使えばループに書き直せるし、任意のループは末尾再帰で書き表せるけど
書きやすい方で書いたら良いんじゃない?
配列を舐めるだけのループをわざわざ再帰で書く必要はないし、
二分木を舐めるだけの再帰をわざわざループで書く必要はない。
勿論例外は幾つもあるけどね。 >>589
時間とフィンガーポイントを無駄にしない為に今すぐ2chから立ち去るんだ!
さぁ早く! http://kakaku.com/item/K0000791258/
これを使ってるけど打ちにくい
隙間にゴミが入りにくいキーボードで何か探してくれれば長文レス出来るけど
ゲームもやるから同時押しが出来ないキーボードは使えないんだよ
バッファローのこのキーボード系列は
何故かゲーミングキーボードでもない癖にかなりの同時押しが出来る
お前らもこれくらい社会の役に立ってくれ tail callはrecursive callと直行する概念だと理解してないのが何人かいるな 読みやすい方で書いたらいいんちゃうの?
無理にループにしてソース長くしてテスト項目増やす奴の気がしれんわ 取り敢えずutがカスだってのは旗から見てわかった
補足しておくけどループで済むものを再起にしろと言ってるわけではないからな そりゃrecursiveじゃないtail callなんざ幾らでもあるわ 仮にもプログラマならHHK使ってます自慢くらいしろよっていう
そういう俺はreal forceだけど。 自分はプログラマじゃないんだよ
目的を最高効率で達成する事を念頭に置いてるスクリプトキディだ
そして複数人でプログラムを組むときに必要なノウハウなんて持ってない
そもそも自分はそういう事をしなくて良いから、生きてく上で必要無い配慮だから
周りが読みにくいとか知った事ではないし
身分がちげーんだよカス (他人の作った)スクリプトを使うしか能の無いお子様
正しく自分のこと理解してるということでいいのかもしれないですね。 正しく自分を理解していたら、あんなバカな生態を晒し続けるわけが無い
スクリプトキディとは、他人の作ったスクリプトでいたずらしてはしゃぐお子様の事だね 誤送信
2ちゃんに書き込んでる地点で効率最悪といえる 数学的な再帰定義関数は好き
プログラムの再帰定義は多少罪悪感が >>605
読みやすさを考慮しなくていいとか言うなら、ソースあげんなksが まともなプログラムは再帰使わないて
Javaじゃ標準でhashでもvisitorでも使ってるやん
初心者かな? >>615
ウェブサイトがハッキングされるのはそのせいかもしれませんね。 Haskellを知ればJavaなんぞ子供のおもちゃにも及ばない。 いや、もしかしたら
データベースを扱うのに困難を伴うゴミ人間って意味かも もしかして、もしかしてだけどさ、Haskelのこと言ってるんじゃね? Haskellほどデータベース扱いやすい言語も少ないからそれはない 世界一のデータベースを持つと言われるGoogleがHaskellで動いているくらいだからね。 Haskellって実用で使われてんのかw
おもちゃかと思ってたわw イッテヨシとかギコはにゃーんとかもう死語なんだろうな。
ゴルァはまだありかな。 ヌルポにはガッっていうのはなぜだったのか理由がいまだに判らないので
香具師にどう反応すればいいのかも判らない >>633
ぬるぽにかぎらず、例外発生したら、ガッ! >>633
NullPointerExceptionをぬるぽと呼ぶスレだかなんだかいうスレタイのスレが立った2分後に
2が1にガッしたから
だった筈 ガッはガッチャの略だろ。 ガッチャマンでお馴染みのガッチャはI have got you.の略で捕まえたとかの意味。 でもアメリカのドラマ見てると了解するときにガッチャ!って言ってるよね。
特にチャーリーズエンジェルのカエル顔が(別のドラマでも)言ってるような気がする。 それ再帰のせいじゃなくてもともと難しいアルゴリズムなんじゃ 同じコードでも言語やバージョンの違いで即死する可能性があるのがネック。
可能ならwhileにするよ。
どうでもいいスクリプトなら木にしないけど。
べ、別に再帰関数苦手なわけじゃないんだからね! 再帰否定派は生きるのがつらいんだよ
いつも周りのもの何もかも否定してるよ 無限か有限かを判別するだけでも難しい再帰コールが簡単に作れるからな 例えば再帰を使えばC++149文字で数学的に非常に判別が難しいコードが作れる
ステップ数がF_φ_ω(0) (n)のオーダー
再帰を使わないともっとずっと必要な文字数は増える つまり再帰を使うと簡単に分かりにくいコードが書けてしまうというアピール
アホなのこいつ? 適材適所
まぁ、ループは現代ではほとんど高階関数に置き換えられてはいるが 再帰、ループ、高階関数は互いに別カテゴリーの概念だけどな。 >ループは現代ではほとんど高階関数に置き換えられてはいるが
mapとかfoldって言いたいの? 最近の言語は分かり易いから好んで使う人多いみたいだね。
俺はダメだわ。単純な再帰でもアセンブラ時代の間接修飾と再帰を混合で使ってたときのトラウマが・・・ >>665
ループ,というよりは map によるメモ化を先にするべきかと思う アッカーマンメモ化はやめとけ
メモリ使用量がシャレにならん。
小さい引数ならいいけど。 と思ったけどスタック消費量は逆に減る?
よくわからんくなってきた。 メモ化とかメモリリークしてるに等しい欠陥技術でしょ。 >>672
fjの昔からの議論をここで蒸し返しますか? 再帰というソフトにはスタックというハードがあるけどほかのソフトをハードで実装するのはどうなの?
GCとかハードで実装してまったくフリーズなしに出来ないの? int main(){return main();} とあるRubyスクリプトだけどこれと等価のC書けんの?
$f=lambda{
print "f";
return $g
}
$g=lambda{
print "g"
return $f
}
a=$f
10.times{a=a.call} rubyはcで書かれているんやで知らんかったやろ? そういう等価じゃなくて文法的にというか。
Cだと$fと$gの型をどうしていいかわからん。 グローバル変数じゃなくてもこれでいけるっぽい
g=nil
f=lambda{
print "f";
return g
}
g=lambda{
print "g"
return f
}
a=f
10.times{a=a.call} typedef void *(*F)()でいいやんけ これでいけるやろ
#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;
} g++だとエラーになるんだが。
コンパイラは何で確認した? なんでいきなりg++やねんw
これ以上はcの質問スレでもいって聞けタコ 通るわアホw
つーかそんなレベルでよくその質問出来るなお前 だからコンパイラは何つかったんよ。
こっちでも確認するから教えれ。
有料コンパイラだったら諦めるけど。 >>690
ふーむ確かに。
コンパイラがC++だといかんの? しかしvoid * はなにか負けたような気分になるなw キャストが嫌ならちゃんと型定義すればいいじゃん
と思ったがちゃんとやるには自己参照型定義みたいなのが必要になるのか
Cでそれってできるのかな
関数型Fのポインタを返す関数型をFと定義 voidにキャストがどうのって、rubyでコード書くような奴に言われてもなぁ。 >関数型Fのポインタを返す関数型をFと定義
これ定義できる静的型言語ってあるの?
それとも本質的論理的に矛盾した型であって、どうやっても定義できないの? Forループは正直見た目が汚らしい
場合にもよるんだろうけど、再帰で書けるならそっちのほうがコードが綺麗になる なんでルビイなんだ?
ハスケルバカならまだわかるが。 Y = λf.(λx.f (x x)) (λx.f (x x)) #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;} ピクセルシェーダーで再帰関数使えるようになるのはいつだろうか CPUがGPU化するのが先かGPUがCPU化するのが先か。
まあ超並列プログラムは憧れるけどね。 main = putStrLn $ q ++ show q where q = "main = putStrLn $ q ++ show q where q = " 超並列はどうしてもデータレースが怖いからハードウェアトランザクションは必須だな ツクツクボウシの鳴き声を一番正確に表せた奴が優勝 [無断転載禁止]©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
ツクツクウィーヨーンwwwwwwツクツクウィーヨーンwwwwwwウィーヨーンwwwwwwウィーヨーンwwwwwwあああああああああああああああ あ!!!!!!! GitHubで匿名通信(Tor、i2p等)ができるBitComet(トラッカーサイト不要でDHTだけで日本語検索可能)
みたいな、BitTorrentがオープンソースで開発されています
言語は何でも大丈夫だそうなので、P2P書きたい!って人居ませんか?
Covenantの作者(Lyrise)がそういう人と話したいそうなので、よろしければツイートお願いします
https://twitter.com/Lyrise_al
ちなみにオイラはCovenant(純粋P2Pのファイル共有ソフト)の完成が待ち遠しいプログラミングできないアスペルガーw
q 匿名通信(Tor、i2p等)ができるファイル共有ソフトBitComet(ビットコメット)みたいな、
BitTorrent(Covenant)が活発な情報交換・交流コミュニティでオープンソース開発されています(プログラマー募集中)
言語は何でも大丈夫だそうなので、P2P書きたい!って人居ませんか?
Covenantの作者(Lyrise氏)がそういう人と話したいそうなので、よろしければツイートお願いします<(_ _)>
https://twitter.com/Lyrise_al
ちなみにオイラはCovenantの完成が待ち遠しいプログラミングできない情報発信好きアスペルガーw
The Covenant Project
概要
Covenantは、純粋P2Pのファイル共有ソフトです
目的
インターネットにおける権力による抑圧を排除することが最終的な目標です。 そのためにCovenantでは、中央に依存しない、高効率で検索能力の高いファイル共有の機能をユーザーに提供します
特徴
Covenant = Bittorrent + Abstract Network + DHT + (Search = WoT + PoW)
接続は抽象化されているので、I2P, Tor, TCP, Proxy, その他を利用可能です
DHTにはKademlia + コネクションプールを使用します
UPnPによってポートを解放することができますが、Port0でも利用可能です(接続数は少なくなります)
検索リクエスト、アップロード、ダウンロードなどのすべての通信はDHT的に分散され、特定のサーバーに依存しません
t 眠い時にプログラム書いてたら1つの関数の中にこれでもかと再帰を詰め込んだモンスター関数を書いてしまって訳が分からなくなる アッカーマン関数はただの再帰じゃないらしいけど、
再帰のパワーを究極まで高めたら何になるの? チューリングマシンになる
証明:以下より明らか
・再帰を用いて、スタックとループをそれぞれ構築できる
・スタック2つとループを用いて、チューリングマシンを模倣できる
・故に、再帰の能力はチューリングマシン以上である。
・一方で、チューリングマシンを用いて再帰を表現出来る
・よって、再帰はチューリングマシンと等価である。
# ツッコミ待ち グッドスタイン数列というのがペアノ算術の限界を超えた再帰という話があるらしいのだが、詳しいことはよくわからない。
でもロマンを感じる。 女性限定、恋愛相談サイトオープン。
4000名のイケメンカウンセラーが在籍中♪
自己紹介動画はいつでも見放題です!
メンガ って検索してください
※本当のサイト名は英字です >>719
そう言う時期が俺にもあったな...(遠い目) 再帰で実装した方がスッキリするケースってなかなか出てこないから最近全く使ってないや 再起なんてバグの温床だからなぁ
マインスイーパー作る時ぐらいしか使わない 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まんけたひょうじする $ time ./pi >/dev/null
./pi > /dev/null 0.40s user 0.00s system 99% cpu 0.400 total
一瞬やね(最適化 -O)
ちなアルゴリズムはRubyのソースについてるやつから持ってきた 深さ優先探索より幅優先探索が好きだ。
重複がある場合計算量が深さより有利だし、
メモリモリモリ積んでゴリゴリ問題を制覇する感じがたまらない。 まだ再帰一回しか使ったこと無いな。
ループでもよかった感じしたけど ディレクトリ掘っていく処理なら再帰の方がすっきり書ける
それ以外使ったこと無いけど flattenがあると再帰書かなくて済むことがまれによくある。 超簡単なハノイの塔のコードを
理解出来ない奴らばかり
俺様ステキ
再帰は楽しい ハノイの塔って最初誰が考えたんだろなw
まさに再帰のための問題だよなw >>737
エドゥアール・リュカ/1800年代後半 連分数展開って見た目的にも再帰的
あとは連平方根なんてのもあったっけ? 数学のように条件を書くだけで処理が書けるのは楽しい >>741
では
これの値を教えてください
lim[n->∞]sin(πen!)
わりとまじです void **hoge; のときに
void *fuga = hoge; でもイケてしまうときとダメな時があるんだが良く判らん。 昔カッコつけてクラスのコンストラクトの再帰だったかループが爆発するバグを作ったことがある
バックトレース大変だった思い出
フリーダムなC言語系は好きだ int main()
{
return main();
} 再帰は面白いと思ってた時期もあった気がする。
ただ引数や戻り値を順番付けて管理しておけば処理内容はループと同じなんだよね。もちろん実行資源の内訳も。
と言うより、「再帰はループの一つである」という表現のほうが正しいか ただのループでスタックオーバーフローの心配はないからなぁ x 再帰はループの一つ
x ループは再帰の一つ
o 再帰でやりたいことはループでも実現できる
o ループでやりたいことは再帰でも実現できる >>755
ただのループが何を指すかが微妙だけど、
再帰を展開したようなループだとカーソル的な物が行き場を無くすとかはあるがな。
そもそもループ自体まやかしみたいなもんだよ。
cmpとjzでしかない。 再帰関数は動作の見た目(想像)が楽しい
でも天才は漸化式求めて一発で計算する >>758
あー、ループあるな。そういう意味では。
すまんかった。 >>755
再帰と同じようにループを実装すればオーバーフローしますけど。
>>756
実現できるのは外部仕様の話。
内部仕様の話だとこうなる。
ループを使って再帰を作ることはできる。(そもそも内部的に関数はニーモニックの段階でそう作られている)。
関数や再帰にまで抽象化 (いろいろ処理) されたものから、内部仕様としてのループを再現することはできない。
まずこうゆうときは、E(電力)あたりの最小可能処理数を考えるとわかりやすい。
あとはその処理 (抽象概念) にあなたがどのような名前をつけるか。
再帰を再帰だと思うのは、誰かが再帰に再帰という名前をつけた上、あなたもそれを再帰と思い込んだから。
実際にはループで実装されている。 >>762
> 再帰と同じようにループを実装すればオーバーフローしますけど。
意味わからん
再帰は必ずスタックを使う
単なるループはそんなもん使わない
どうやってスタックオーバーフローするんだ? 分からんなら分からんければいいんじゃね
先に事前に書いてあることを偉そうに質問されてもね 再帰を展開したようなループ、だから
そんなもん使わない、が偽か、
再起だって必ずしもスタックを使い尽くさない、が真かなんだよな。 スタックが必要あるからスタックが採用されるんでしょう。
ループや再帰にかかわらず。そして最適化すれば同じ記述。 >>767
int main(){ return main(); } 簡単です C言語は関数内でローカル関数を定義できないから嫌い
ローカル関数でなら末尾呼び出し除去の保証とかやりやすいのに >>769
それオプティマイザ次第で、ただの無限ループになるよ。
そう言う意味じゃなくて。
せめて、cmpとjzに、いやdjnzあるじゃんみたいな話についてこようよ。 >>770
C++で、クラス内に関数を定義すりゃいいだけ >>774
メモリアクセス要るようなループ書かんだろう…。ましてや再帰の展開で。 >>770
なるほどね,コンパイル単位内だけで末尾再帰を保証するわけだね >>770
今時のコンパイラならファイルスコープでもインライン展開とか再帰の末尾最適化ぐらい余裕でしょ コンパイラが最適化を諦めるくらい難解な処理するんだろ
そのくらいのことじゃないと再帰関数する意味無いからな
それか楽をしたいか、趣味か 木構造をループで辿りたいときってスタック使わずにできる? 辿るだけ(構造を保持しなくていい)ならできるでしょ
たとえば全てのアドレスを出すだけとか スタックなんて "ヒト" の概念だからな。
自動で伸び縮みするような配列だって内部的にはスタックと同一なわけで一方的に増えていくかもしれない。
構造や順序をスタックせず、現在の状態だけを保持していたとしても、オーバーフローしない理由にはならない。 ツリーだってメモリがツリー状になってる訳じゃない罠 質問 スタックを使わずにできるか
回答 オーバーフローしない理由にはならない
意味不明 >>784
関数呼び出しどうやってするんだよ
それにそんな再帰関数は好きになれないな >>786
ニーハオ!
モドル サキ ハ ドコニ キヲク シマスカ? ヒープだろうが、スタックだろうが、メモリサイズが有限である以上、
オーバーフローは起こるわな。 馬鹿には永遠に判らんだろうけど。 情報を保存しながら、進むならば、ループだっていつかオーバーフローする。
保存せずに計算できるならば、再帰でもオーバーフローしないかもしれない。 誰かの口真似したのかもしれないけどそれは完全に間違ってますよ >>796
Prologですから再帰述語で関数ではありませんが、
repeat :- 割り込みあり,!.
repeat :- repeat.
の場合、スタックの一番上でpop,pushを繰り返すことが可能なのではないでしょうか。 すみません。まちがえました。これではrepeat内でのループになってしまって
Prologのrepeatになりませんでした。分かり難くなりますから割り込みを外します。
repeat.
repeat :- repeat. >>797 だと、
繰り返しを最終回にするための割り込みとしたかったのですが、
実行開始の遅延を終了するための割り込みになってしまっています。 >>797
どういう条件だとスタックが伸びず、伸びることが不可避なのはどんな場合か。 >>800
実行時、述語の最後の節で、最後の副目標(サブルーチン呼び出しにあたる)に差し掛かった時に
その節のそれまでの副目標が全て決定性(別解があり得ない)に終了しているという条件で、
この節の呼び出し時点までスタックを戻って、そこに新たな再帰呼出しの情報を積むことができる。 好きか嫌いかで言ったら好きだ
趣味以外では使わないけど 再帰がスタックを積むんじゃなくて関数がスタックを積むんちゃうの?
スタックがなければ実現不可能な処理なら、ループで実装してもスタック積むんちゃうの? >>806
ループで実現したときはスタックに積まれない。 >>808
実行系に頼らず自分でスタックを実装するってこどだろ
使用メモリ量が不定なのは一緒 抽象概念が実体であるかのような基準で話をする人が多すぎる
再帰でスタックが発生するならそれに対比するループも必ず同等のスタック量が発生する。
それでも 「ループで実現したらスタックは積まれない」と言うのなら、それは実現できていない。
抽象概念としての名称は便宜上再帰であるかループであるかの違いはあるが、実体としての処理は必ず同等。 >>811
再帰は、入れ子状の関数呼び出しで、呼び出す関数は全部同一だから、
コードは一つで良い。しかし、関数だから呼び出す度にスタックに情報を積むし、
戻ってくるまで、積んである情報をPOPできない。
ただし、関数が末尾に有る時、則ち、戻って来た情報に対して何らかの計算をしてから
情報を返すということがない関数に関しては、戻ってきた値を直接自分の戻す値に
できるわけだから、呼びだされた時の普通なら積む情報を積まずに済ませることが
できるかも知れない。こういうことを「実体」というのですないか? すみません。最後
こういうことを「実体」というのではないか?
です。 >>813
根本的には処理もデータも区別なく実体ってことでしょ。
ループ自体も関数自体も実体。 継続は再帰ほど市民権得てないからなぁ。
継続を深く理解しているプログラマは全体の1割に満たないんだろうな。 物自体の実在性を議論してんのかよ
やっぱ再帰って難しいわ 私は再帰の塊のようなプログラムを作ったことがある。
DirBaseだ。
起動後のウィンドウにエクスプローラからファイルやフォルダを
ドラグ&ドロップするだけで簡単にツリーができる。
DirBaseで検索すれば、ダウンロードできる。 競プラではforループが盛んらしいが、言語開発者としては再起の方が使って欲しい
ソースは俺が今朝見た夢 >>819
ん?setjmp/longjmp のことですか? (数値計算を主体とする)関数では使わないけど、
再帰ルーチンで使用頻度が激しいのは、外部記憶装置を含めた初期化ルーチン。
一つのルーチンで、内部記憶(主記憶装置)と外部記憶(HDD等)の出入りを管理している場合に、
初期化ルーチンで外部記憶が存在しない場合には、ルーチンで保存している定数を読みだして、外部記憶に保存する。
初期化ルーチンからの定数の読み出し・外部への保存が再起処理。
初期化ルーチン以外では使わない手法。
分割して作成すると、何年か後に見直した時に、どのように初期化しているのかわからない、という事態になることが多発したので、
初期化が必要な場合には、このような手法で同一ルーチン内に収めるようにした。
もっとも一番利用頻度の高いのは、Winでは、ダイアログボックスのプロシージャ。再起の塊で、何をしているのかわからなくなってくる。 再帰プログラムは関数の呼び出しで積みあがるスタックを配列とみなせば、ループアルゴリズムそのものだ。 ファイルやフォルダ、ダイアログやウインドウは階層構造で構成されるので、再帰プログラムを使うのが一般的だ。 再帰って何?って頃から普通に再帰使ってたからなあ。
自分自身を呼び出せば良いじゃんみたいな。
高校で数列とか演繹法が得意だったせいかも。
自然に使ってた。 再帰云々言ってるのは大昔のFORTRANとかCOBOLを使ってた人ぐらいじゃないのかな
あと組み込みとかでスタックサイズが厳しい環境で組んでるとか 再帰プログラムの基本はスタックにデータを入れ積み上げていく過程と、スタックからデータを取り出しスタックをクリアしていく過程の二つの動作しか基本的にない。
データを取り出したら、そのデータを使ってプログラミングされた処理を実行する。スタックはデータを貯めることと同時に処理の順番を決めている。再帰のプログラミングには二つの概念が必要だ。 javaで再起処理書いたらガーベッジコレクションが掃除してくれるもんだと思ってたけど違うの?
十年前の記憶だから曖昧ですまない
cpu使用率が100%になるけど影響ないから使ってます〜って顧客に言われたのを思い出したもんやで 僕の知り合いの知り合いができたパソコン一台でお金持ちになれるやり方
役に立つかもしれません
グーグルで検索するといいかも『ネットで稼ぐ方法 モニアレフヌノ』
980U0 今時スタックオーバフローぐらいでOSは死なないから大丈夫 再帰アルゴリズムはなるべくライブラリで隠蔽して欲しいな。
自分で書くのはまだしも他人の再帰コードを読むのはかなり嫌。 再帰関数と言えばアッカーマン関数とかたらい回し関数などが
有名ですが他にも何かある? 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 再帰関数『終わらないドラゴンクエスト』
ドラゴンクエストとは?(){
ドラゴンクエストとは?()
} def DQ(n)
puts "DQ #{n}"
DQ(n+1)
end >>1
好き嫌いの問題じゃないと思うが、理論上再起かそれと同等の内部処理履歴を残さないと実現できない処理なら、使うだろう
再起にならざるを得ない具体的な数学(科学)的な条件は忘れたが、けっこう複雑な処理じゃない限り再起じゃなくても実現できたように思う >>858
「再起」じゃなくて「再帰」ね
スタックを使えば、つまりメモリを余分に使用することを認めれば
再帰はループに書き換えることができるから
再帰でなければ出来ないことは原理的に存在しない
更に言えば関数を受け取りまた返す高階関数があれば
いわゆる不動点演算子に相当するものが書けるので
関数の再帰的定義は不要になる 論理的にはクイックソートよりマージソートが好き。
実用性はクイックソートが上なのかな? >>859
>再帰はループに書き換えることができるから
そのループ再帰だよ・・・
再帰の問題点もそのまま同等に引き継いでるよ・・・ ループも不動点演算子も再帰関数の実装の仕方でしかない リストに対してはクイックソートやマージソートより選択ソートや挿入ソートのが速かった。
ケースによって使い分けるために色んなソートがあるんだなと実感した。 >>861
ループと再帰とは違うよ
更に言えば高階関数があればループも再帰も必要ない
不動点演算子もループも再帰だと言うのはナンセンスだ
それは「再帰と同じだ」と君が思うものを再帰と呼ぶ、と主張しているに等しい
こんな君だけの主観による再帰の定義では議論にならない チューリング完全なんだからどの言語でも一緒、という暴論と同程度に「ループと再帰は同じ」も暴論
コンピュータからみた話じゃなくて、プログラムを書く人にとってループと再帰が同価値なのかが問題になる
自分は、複雑でも読み溶ける再帰の方が好き。ループが複雑になると、どの変数がいつのどの値を持っているのか追いきれなくなる
再帰で同程度に複雑な処理を書くと、引数の数やら名前からすぐにヤバイ臭いがするんでそんなに腐らない 末尾再帰にすると結局for文とやってることが一緒になる モナドな再帰(IOモナドやリスト->リストな再帰)は単純な再帰でもスタック消費しない。
繰り返しコードの単純さは再帰>末尾再帰>=ループ。 非同期処理の終了を待って、次の繰り返しを行う
再帰でなければ書けない >>871
非同期処理の終了はイベントやコールバックで通知されるものとする
終了を待つ同期プリミティブは存在しない
Javascriptだとこれが普通で、繰り返しでは書けない async/await が JavaScript の新しい仕様として入ったのも知らんのか await/asyncの仕組みを知らないと見える
それ使って、繰り返しで書いてみなよ やっぱ、await/asyncで出来そうな気がしてきた >>867
違うよ
柴犬にこっちは太郎でこっちは次郎だから別の犬だ、と言ってるのと同じ 再帰処理は
現在の関数が戻ってゆくアドレスをスタックに保存し、このアドレスを積極的に利用する。
プログラミングの実行アドレスをスタックから取り出して制御するので、
再帰プログラミングを利用するコツは、戻りアドレスを正しく理解することだ。
再帰は同じ関数を行ったり来たりするものだが、
日常の社会では、やらない方法だ。
普通は、配列を利用して、そこに保存してあるデータを使い、
同じ場所でプログラムを実行する >>881
そらまあ再起が辿るイメージ図は全てツリーって名称付けれますし ゲーム作るときになってようやく再帰の恩恵を得た
めっちゃ書きやすい >>883
ミニマックス法かアルファベータ法だろ? マイコンだとスタックが1桁とかだから再帰書いた瞬間に死ぬ ルネサスのRL78/G10はRAMが128Byteしかないらしいな λf . (λx . f (x x)) (λx . f (x x)) ループで書くと出現する余計な変数がなくなるのが再帰のメリット >>889
?
kwsk
ループ変数は再帰関数でも必要なのでは? どんどんスタックにつめば確かにループ変数はいらない
ただ、人間のためにループ変数はあった方かいいと思うけど 再帰関数を理解したとき、最初にこれ考えたやつは天才だと思ったね
実行速度やスタック問題はともかくコードは見ていて美しい以外の何者でもない。 CやUnix、オブジェクト指向なんかよりもはるかに古いんだよな
最初に実装されたのはlispかな
メモリを食いすぎるのでおもちゃしか動かなかったようだが 今の時代メモリ食いすぎても動くし遅くもならないよな
1億再帰とかやったら話は別だけど >>890
要らない
/* n の階乗を求める */
int fact(int n)
{
if(n==0){
return 1;
} else {
return fact(n-1);
}
}
実質ループする処理だけど、ループの回数数えるための
変数は一切出現しない。なおかつ n は不変。 おお、"n*" を忘れた。こんな短い関数にバグ突っ込む俺(泣) くだらん処理にスタックを使いたくないのでわしは使わん
ライブラリが殆ど無いマイナーCPUのマイナーCコンパイラでQuickSortを書いた時くらいじゃケケケ 最近じゃオプティマイザがなるべくスタック使わないように
最適化してくれるんじゃなかったっけ? >>898
末尾再帰ならそうだと思いますが、末尾再帰でなければ無理でしょう >>896-897 は末尾再帰じゃないから最適化されにくい、というか、されない >>8
ループと再帰の能力は同じです
かなり古い計算論の結果です >>899
結合法則を仮定していいドメインなら
CPS変換を用いて最適化する手法が随分前からあります
結合法則はGPU並列化でも使われてます
浮動小数点の場合は工夫しないと誤差が変わりますが
ちなみにC++ conceptの初期案でもaxiomで法則を記述出来ました >>902
scheme の継続渡しに関係しますか?
キーワードありがとうございます >>903
そう
Continuation-passing style, defunctionalization, and associativity
Categorical Structure of ContinuationPassing Style
この辺のサンプルプログラム読んで すき
しかし再帰絶対書かないマンが思いの外多くて草生えるわ
末尾最適化できない再起をループに展開したって結局キューだのスタックオブジェクトでヒープ使うわけで
メモリ大幅に節約できると勘違いしてる基地外とか話にならん
再帰深度がたかだか1000段とかでスタックフレームにデカいオブジェクトブチ込んだりしなきゃ
素直に再帰で組むのがいいに決まってるじゃないか
数学的演算でもしない限り業務用でスタック溢れるケースを探す方が大変 スタックとヒープは別物
共有してるアーキテクチャもあるが ループに展開できる処理をわざわざ再帰で書く奴も大概やけどな。 >>909
二方向に再帰するもの、は展開に苦労しますね
式の評価は、再帰じゃないと書けないですね 再帰的データ構造は再帰でたどるのが楽なんだけど
ループで処理したほうが途中で抜けたり処理を組み合わせやすい
そこで再帰的な処理を遅延リストと組み合わせてループで処理するやり方がいまでは一般的な気がする
こういうふうに C#
https://paiza.io/projects/WbmxzuNdJq95o9RYTKFY_A 何が一般的なのか知らんがかなり変態的なコードだな
ループでGetEnumerator呼び出したりMoveNextの戻り値を見ずCurrentを取り出したりは一般的じゃないぞ
つーかバグだろそれ レス数が900を超えています。1000を超えると表示できなくなるよ。