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

**デフォルトの名無しさん** · 2015/11/28(土) 18:51:38.86

なあ、再帰関数好きな人いる？

**デフォルトの名無しさん** · 2015/12/22(火) 14:08:14.84

はるかと言っても所詮定数倍でしょ。
しかも一桁違うケースは
関数呼び出しがやや高価なスクリプト系の言語でもほとんどないでしょ。

**デフォルトの名無しさん** · 2015/12/22(火) 17:31:14.37

>>193
いやね，絶対的に再帰でないと書けない，いや非常に書きにくいものはあるのは確かで．
たとえば代数式の解析を非再帰的で記述しろといわれると「はたして出来るのか？？」と逡巡してしまう．
こういう話題があまり発展しないのはどうしたわけですかね

関係ないけどquick-sort を三項演算子とコンマ演算子で書く話題，誰か‥私は挫折した‥

uy ◆Qawu9.2l1E · 2015/12/22(火) 18:25:40.50

再帰の深刻なデメリットと言えば、コンパイラ設計者が甘えてる事によってバグを触ったり
異常に速度遅くなるパターンが放置されてたりする事

なんの言語とは言わないけど

**デフォルトの名無しさん** · 2015/12/22(火) 19:03:19.84

それは再帰のデメリットではなくそういうクソコンパイラしかない言語のデメリット

**デフォルトの名無しさん** · 2015/12/22(火) 22:57:38.64

>>192
能書きはいいからとっとと実証しろ。超基本的な知識なんだろ。

「はるかに遅い」とか言ってるバカ仲間のサイトでも良いぞ。

uy ◆Qawu9.2l1E · 2015/12/22(火) 23:43:59.28

>>197
なんか食パン裏返してこっちが表だとか必死に言ってるようなレスだな

**デフォルトの名無しさん** · 2015/12/22(火) 23:48:59.13

>>199
食パン裏返してんのはお前のほうだよw

**デフォルトの名無しさん** · 2015/12/22(火) 23:51:52.68

>>198
へい。再帰が130倍時間がかかるエビデンス。
http://www.fastpic.jp/images.php?file=1406113032.png

**デフォルトの名無しさん** · 2015/12/23(水) 01:07:26.60

食パンの裏はどっち側だよ

**デフォルトの名無しさん** · 2015/12/23(水) 01:25:49.85

>>201
こうするとなかなか興味深いことになるね。
本当に興味深いと思ってるだけで他意は無いよ。

fun_rec(){
if [ $1 -gt 5000 ] ; then
time fun_for
return
fi
fun_rec $(( $1 + 1 ))
}

**デフォルトの名無しさん** · 2015/12/23(水) 02:04:18.65

>>203
たしかにおもしろい。
再帰の深さに比例して時間がかかる。
再帰が深くなると処理に時間がかかるようになるのか、
別の時間を測ってしまっているのか。わからん。これはわからん。

**デフォルトの名無しさん** · 2015/12/23(水) 07:21:41.71

>>201
必死で再帰否定してるバカは知能が低いというエビデンス乙

シェル関数は呼び出しのたびに名前解決するのでペナルティが大きい

**デフォルトの名無しさん** · 2015/12/23(水) 07:28:38.71

Cの場合は入った時にフレーム作成と出る時にフレーム復元
c86なら、レジスタ操作4ステップ(複合命令なら2ステップ)だ。
名前解決なんかリンク時に終わってる。

**デフォルトの名無しさん** · 2015/12/23(水) 08:47:35.90

最近の関数呼び出しは引数をスタックに積まずにレジスタ渡しみたいだから
再帰で何段ネストしちゃっててもレジスタに収まってる限りは爆速なんじゃね

**デフォルトの名無しさん** · 2015/12/23(水) 08:59:40.61

名前解決まで計算時間に含めるなら
もう再帰云々じゃなくて長大な再帰なしの一つの関数で全部こなせって話になるんだがな

>>207
いや、そうはならない。
レジスタの退避が必要になるから、自己再帰するならどっちにしても同じだけpush/popは必要になる。
最適化が掛かったらその限りじゃないけど。

**デフォルトの名無しさん** · 2015/12/23(水) 09:02:09.80

>>205
呼び出しだけじゃなく参照もね、iの。
localでもスタックフレームなめてるのかな?

**デフォルトの名無しさん** · 2015/12/23(水) 09:10:56.81

>レジスタの退避が必要になるから

そうかなー

**デフォルトの名無しさん** · 2015/12/23(水) 09:15:53.17

>>209
スタッフフレームは再帰に必要なステップだから、再帰のペナルティとしてあえて受け入れた。

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

(場合もある)を知らないのか、教わってないのか知らないが、全ての場合だと思い込んでるところもバカの、特徴だね。

**デフォルトの名無しさん** · 2015/12/23(水) 09:50:24.66

>>210
再帰で書いた何の変哲もないフィボナッチ関数をビルドしたケースを示すよ
https://gist.github.com/pixie-grasper/ba2d0ade523b8599c182
gccではr12を、clangではraxを、rbp/rbxの他に退避してるのが分かる。

**デフォルトの名無しさん** · 2015/12/23(水) 11:20:43.15

対比先もレジスタにすればいいのにね

**デフォルトの名無しさん** · 2015/12/23(水) 11:25:42.60

そんな事をすると
既に退避させてある値を別なレジスタに退避させてから、退避させたい値を退避するコードを吐く羽目になるけど
レジスタが最低でも加算無限個無いと出来ないからね。仕方ないね。

**デフォルトの名無しさん** · 2015/12/23(水) 11:53:11.24

externしていないstatic関数とかならレジスタ渡しもふつうにある。
もちろんCランタイム・コンパイラによる

**デフォルトの名無しさん** · 2015/12/23(水) 12:07:45.20

>>215
いつの時代の話をしてるのか分からんのだけど、所謂Intel系の64bit環境(amd64)だとレジスタ渡しがデフォルトだよ。
https://en.wikipedia.org/wiki/X86_calling_conventions#List_of_x86_calling_conventions

**デフォルトの名無しさん** · 2015/12/23(水) 12:46:44.21

>>204
bashはダイナミックスコープだから再帰の深いところでは
変数の参照に時間がかかるのかな。いまはその辺を疑ってる。

uy ◆Qawu9.2l1E · 2015/12/23(水) 13:07:16.81

>>197
ｗ

**デフォルトの名無しさん** · 2015/12/23(水) 16:35:42.36

だいたい再帰で問題が無いなんて
クイックソートで再帰が役に立たない事すら知らないってことか？

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

**デフォルトの名無しさん** · 2015/12/23(水) 16:37:36.04

>>219
何が言いたいのかわからん…

uy ◆Qawu9.2l1E · 2015/12/23(水) 16:45:18.40

>>219
ファーｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ

**デフォルトの名無しさん** · 2015/12/23(水) 17:05:56.20

>>219
じゃ、これを10000倍高速化して実証してよ。
http://svnweb.freebsd.org/base/stable/10/lib/libc/stdlib/qsort.c?revision=256281&;view=markup

**デフォルトの名無しさん** · 2015/12/23(水) 17:15:03.86

>>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);
}

**デフォルトの名無しさん** · 2015/12/23(水) 17:27:00.65

>>223
10000倍高速化の比較対象はそれでも良いぞ。

**デフォルトの名無しさん** · 2015/12/23(水) 17:56:16.45

一万倍とかｗｗｗｗ
どこをどうやったら一万倍差がつくんだ

**デフォルトの名無しさん** · 2015/12/23(水) 18:11:01.01

>>225
クイックソートの最悪の時間計算量はn^2なので
データによってはとても大変なんよ。

uy ◆Qawu9.2l1E · 2015/12/23(水) 18:27:35.24

アルゴリズムの抽象化に静的言語使うチンパンとか話にならないから(´・ω・｀)

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

**デフォルトの名無しさん** · 2015/12/23(水) 18:50:34.28

>>225
最低10000倍ね。笑

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

あ、小学生のように0.0001万倍とか言い逃れるかも。爆笑

**デフォルトの名無しさん** · 2015/12/23(水) 21:36:40.93

>>227
http://hissi.org/read.php/tech/20151223/UGp4VlNGMlU.html

**デフォルトの名無しさん** · 2015/12/23(水) 21:47:18.77

万倍高速化はよｗｗｗ

**デフォルトの名無しさん** · 2015/12/23(水) 22:10:25.42

ID:u0B3Sjd8
10000倍の高速化まだ? 常識的で簡単そうな口ぶりだったけど。

**デフォルトの名無しさん** · 2015/12/23(水) 22:12:02.95

万は間違いだったとしても、最低でも倍速は楽勝なんだろ。

**デフォルトの名無しさん** · 2015/12/23(水) 22:29:26.28

>>232
速度以前に >>223 は簡単にスタックオーバーフローするよ。
それを防ぐ方法を教えてやってよ。

**デフォルトの名無しさん** · 2015/12/23(水) 22:33:54.64

>>233
繰り返し版が明示的スタックに使うヒープと同サイズに
マシンスタックの上限を変更すればOK

**デフォルトの名無しさん** · 2015/12/23(水) 22:55:30.83

いや、君に言ったわけじゃないし、最適化を教えてやれってことなんだけど。

**デフォルトの名無しさん** · 2015/12/23(水) 23:35:43.46

>>233
バカなの? >>222読めないの?
10000倍の高速化まってんだから、くだらねー横槍入れないように。
お前が10000万倍高速化するならかまってやんよ。

**デフォルトの名無しさん** · 2015/12/23(水) 23:43:11.94

>>226
繰り返しか再帰かに関係ないがな。
pivotの選び方次第だろ。
それは明示的にスタック使う繰り返し版クイックソートでも同じ。

**デフォルトの名無しさん** · 2015/12/23(水) 23:58:42.12

>>237
あたりまえ

**デフォルトの名無しさん** · 2015/12/24(木) 01:02:26.01

>>238
>>225に対するレスとして
>>226はおかしいだろ。
気にならんのか?

**デフォルトの名無しさん** · 2015/12/24(木) 01:08:56.14

>>239
何を言っているのか意味がわからない…

**デフォルトの名無しさん** · 2015/12/24(木) 06:51:58.79

>>240
最悪パターンでもよいから、10000倍高速化しろよ。

uy ◆Qawu9.2l1E · 2015/12/24(木) 08:02:14.94

スキルない人間をいくら叩いても何も出てこないのに
ここは動物園かよ

**デフォルトの名無しさん** · 2015/12/24(木) 08:55:59.49

黒魔術師は再帰関数が大好き

**デフォルトの名無しさん** · 2015/12/24(木) 09:09:51.37

黒魔術師はマクロを生成するマクロも大好き

**デフォルトの名無しさん** · 2015/12/24(木) 11:57:48.07

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

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

**デフォルトの名無しさん** · 2015/12/24(木) 14:54:05.30

>>245
そうやって執拗に絡むのもはっきりいって馬鹿丸出しだよ。
せっかく相手がクイックソートのコードを書いてくれたんだから
そのコードの問題点を指摘する方が賢そうに見えると思ったんだけどね。

**デフォルトの名無しさん** · 2015/12/24(木) 16:38:25.55

>>246
さらなる意味不明なバカが出てきたな。
コード出したのは再帰を必死で否定してるバカじゃないぞ。

**デフォルトの名無しさん** · 2015/12/24(木) 17:26:51.73

最初期は再帰をサポートしてなかった計算言語があるらしい

**デフォルトの名無しさん** · 2015/12/24(木) 18:44:44.88

今はハードウェアレベルで再帰が実装されてるからな。
それを思えばいかに再帰が本質的にプログラミングに必要とされてるかってことだな。

**デフォルトの名無しさん** · 2015/12/24(木) 20:04:26.21

計算可能性を探求する試みにおいて最初に出たのが、
エルブラン・ゲーデルの一般帰納関数だからね。
次がラムダ計算。
その次がノイマン型計算機直系の先祖であるチューリングマシン。

**デフォルトの名無しさん** · 2015/12/24(木) 20:37:54.33

10000倍だっておとなしいぐらい。

再帰だと落ちまくるから∞倍だって当たり前だろ。

**デフォルトの名無しさん** · 2015/12/24(木) 20:46:14.21

メモリ足りないなら動かないのは再帰もループも変わらんだろ。
ループのほうが本質的にメモリ使用量少なくなるとかなら話は変わってくるが。

**デフォルトの名無しさん** · 2015/12/24(木) 20:58:31.47

これだね。本当に知能が低い。
> 1 スタックが制限の厳しいリソースである環境が全てだと思い込み、再帰の致命的なペナルティだと主張する

**デフォルトの名無しさん** · 2015/12/25(金) 18:57:10.38

＞再帰もループも変わらんだろ。

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

ループ方式なら、データが何千万件あろうと無問題

**デフォルトの名無しさん** · 2015/12/25(金) 19:44:32.39

>>254
ループのソース晒してみろや

uy ◆Qawu9.2l1E · 2015/12/26(土) 05:53:41.97

覚えたての知識を使ってレスバトルするだけのスレなんていらねーから

**デフォルトの名無しさん** · 2015/12/26(土) 08:33:15.25

いらないスレを使って自分の意見を垂れ流すとか有効活用乙としか

**デフォルトの名無しさん** · 2015/12/26(土) 10:19:35.68

そういう初心者の遊び場もあっていいと思うけどなあ

**デフォルトの名無しさん** · 2015/12/26(土) 12:54:13.38

>>252
再帰の方は、関数呼び出し大量に発生するから、リターンアドレス待避とレジスタ待避に、メモリーが喰われる。

**デフォルトの名無しさん** · 2015/12/26(土) 13:36:54.41

>>259
ループの方は今どの範囲についてソートしているのかという情報が大量に発生するから同じ議論が成り立つ訳だが。

**デフォルトの名無しさん** · 2015/12/26(土) 13:40:32.70

>>260
ループはヒープ、再帰はスタック
つまり、ヒープとスタックがぼくらを助けてくれるんだ！

**sage** · 2015/12/26(土) 15:02:23.21

>>254
>>222(再帰版qsort)で5000万件ソートしてみた。楽勝で終了する。
必死で再帰を否定しているバカが低知能だという事がまた証明されてしまった。
頭が悪いって本当にかわいそう。

**デフォルトの名無しさん** · 2015/12/26(土) 16:45:09.37

>>262
再帰版でうまくいくのだったら非再帰版ではもっとうまくいく，という発想はないのかね？

**デフォルトの名無しさん** · 2015/12/26(土) 16:59:02.38

>>263
うまくいくって言ったって高々定数倍速くなるだけだろ？
非再帰版を書いたり保守したりするコストより新しい速いマシンを買ったほうが安く上がるって発想は無いのかね？

**デフォルトの名無しさん** · 2015/12/26(土) 17:27:47.02

>>263
知能障害者って本当にかわいそう。
5000万件でソート出来てるってことは、「再帰はスタックあふれる」という迷信が嘘だという発想には至らないのかね。
クイックソートの深さの制御はすでに研究し尽くされてて、全然問題ないんだよ。

**デフォルトの名無しさん** · 2015/12/26(土) 17:37:15.54

あっ、繰り返し版は10000倍速いんだっけ? (爆笑)
早く実装コードみたいなあ。

**デフォルトの名無しさん** · 2015/12/26(土) 18:11:47.33

>>266
そんなに実装したいのなら教えてしんぜよう。
5000万件で >>201 を実行してみたまえ。
再帰呼出しというのは効率が悪いとても頭の悪いやり方なんだよ。

**デフォルトの名無しさん** · 2015/12/26(土) 18:13:42.40

シェルスクリプトを証拠として使うのは笑ってしまうからやめろ

**デフォルトの名無しさん** · 2015/12/26(土) 18:16:50.75

>>268
反論できないのな？じゃあお前の負けってことで。

**デフォルトの名無しさん** · 2015/12/26(土) 18:22:25.08

野次飛ばしてる観客相手に勝利宣言も笑うからやめろ
おまえはプロレスのヒール役か

**デフォルトの名無しさん** · 2015/12/26(土) 18:26:32.21

＞高々定数倍

そんな安全なもんじゃあねぇ。
データが増えれば差も増大。

**デフォルトの名無しさん** · 2015/12/26(土) 18:38:59.41

>>267
ぷぷぷぷ
知能障害者は>>201をクイックソートと呼ぶのか?

**デフォルトの名無しさん** · 2015/12/26(土) 18:41:57.44

>>271
ミジメすぎるぞ。クイックソートのスタック消費量はlog nに抑える事が可能。
こんな基本的な事を知らないから数千万件はソート出来ない。キリッ

とか、赤面な発言しちゃうんだよ。

**デフォルトの名無しさん** · 2015/12/26(土) 18:47:36.31

ちなみに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). */

**デフォルトの名無しさん** · 2015/12/26(土) 19:02:41.83

>>272
バカかお前は。ボウフラサイズの脳ミソしか搭載してないのか？
ただの繰り返しでさえ130倍の差があるのだから
クイックソートを実装したらそれ以上の開きがあるのは自明だろうが。

**デフォルトの名無しさん** · 2015/12/26(土) 19:08:33.46

>>273
log n は発散するんだが‥

**デフォルトの名無しさん** · 2015/12/26(土) 19:09:07.52

>>275
バカはお前だ。シェルスクリプトでクイックソートを実装するなんて誰がするか。
sortプログラムを使え。

ちなみにシェルスクリプトの場合、関数呼び出しはそれ自体がスタックの深さをnとしてO(n^2)くらいの計算時間を持つっぽい。

**デフォルトの名無しさん** · 2015/12/26(土) 19:09:41.46

>>275
ぷぷぷ。知能障害は本当にかわいそう。
qsortの繰り返し版は関数呼び出しの代わりに自前でスタック管理しなきゃならないんだよ。
10000倍高速化の実証コードはよ。

**デフォルトの名無しさん** · 2015/12/26(土) 19:10:23.62

>>276
確かに、うん、確かに、非常にゆるやかに発散するね。

n=2^64としてもlog nは64だけどね。
定数と変わんないレベルだよね。

**デフォルトの名無しさん** · 2015/12/26(土) 19:11:25.60

>>277
実装できないのな？無理なのな？はい論破。

**デフォルトの名無しさん** · 2015/12/26(土) 19:14:27.33

>>278
>>201 がすべてを物語っている。
これが何よりの証拠。再帰がとてつもなく効率が悪いことを
つまびらかにしてみせた。ここに来て見てみぬふりは通用しない。
エビデンスもきちんと示されている。もはや知らぬ存ぜぬでは済まされない。

**デフォルトの名無しさん** · 2015/12/26(土) 19:14:30.05

>>280
何万倍も高速だっ。キリッ。
って主張してる奴に実証責任があるんだが

ガイジにはわからないの?

**デフォルトの名無しさん** · 2015/12/26(土) 19:16:21.04

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

さぁ君は一体何を論破したというのだい？

**デフォルトの名無しさん** · 2015/12/26(土) 19:16:31.66

>>281
障害児くん
10000倍と130倍って、どっちがどれだけ大きいかわかる?

**デフォルトの名無しさん** · 2015/12/26(土) 19:17:31.65

>>282
>>201 で完全に証明してみせた。
反証する責任がお前にあるとは俺は思わないよ。
俺は自分の都合の良いように他人に責任を押し付けるなんて
卑劣な真似はできない。俺はただの真実の探求者。

**デフォルトの名無しさん** · 2015/12/26(土) 19:21:05.64

>>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倍はどうやって稼ぐんだい？

**デフォルトの名無しさん** · 2015/12/26(土) 19:21:48.42

>>284
ボウフラ並みの脳ミソをメダカにでも食われたのかお前。
頭悪いにも程があるだろうが。こんな鶏頭野郎の
相手する俺の身にもなれ。なんていいやつなんだ俺。
聖人君子としか言いようがないわ。>>201 は5000回の繰り返しだ。
5000回の繰り返しでさえ130倍の開きがあるのだから回数が
増えれば差は開く一方だ。だから、>>267 で5000万と言ったのだよ。

**デフォルトの名無しさん** · 2015/12/26(土) 19:23:23.36

霊がいるのかいないのかは判りませんが
人間の目が無いものを見ることがあるのは事実です

**デフォルトの名無しさん** · 2015/12/26(土) 19:23:40.75

差は開くだろうけど比も開くのか？

**デフォルトの名無しさん** · 2015/12/26(土) 19:23:44.50

>>287
5000回の再帰で130倍の差が開いた訳じゃなくて、
深さ5000の関数呼び出しで130倍の差が開いたって事を理解してる？

5000万要素のクイックソートなら最良のケースで深さ25の再帰だからね？
130倍どころか2倍にもならないからね？

**デフォルトの名無しさん** · 2015/12/26(土) 19:23:54.44

>>286
クイックソートを実装して試したのか？あ？
だれが実装するかと言っていたのと矛盾するだろうが。
つまり、君は嘘をついている。ゆえに俺が言ってることの方が正しい。はい論破。

**デフォルトの名無しさん** · 2015/12/26(土) 19:26:45.13

>>289
当たり前だろ。小さな町の町長が東京の都知事になって
仕事をこなせると思うか？数が増えるほどにコストは増大するんだ。劇的にな。劇的にだ！

**デフォルトの名無しさん** · 2015/12/26(土) 19:29:40.16

障害児発作を発症中

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

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