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

1デフォルトの名無しさん
垢版 |
2015/11/28(土) 18:51:38.86ID:Rc2MJzM/
なあ、再帰関数好きな人いる？
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
純粋に処理速度の話してんならネイティヴコード化したものでないとさ
新着レスの表示
レスを投稿する

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