なあ、再帰関数好きな人いる? パート3 [転載禁止]©2ch.net
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
なんか食パン裏返してこっちが表だとか必死に言ってるようなレスだな