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

1デフォルトの名無しさん
垢版 |
2015/11/28(土) 18:51:38.86ID:Rc2MJzM/
なあ、再帰関数好きな人いる？
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万倍高速化するならかまってやんよ。
新着レスの表示
レスを投稿する

5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況