なあ、再帰関数好きな人いる？ パート3 [転載禁止]©2ch.net (914ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
257: 2015/12/26(土)08:33 ID:oIXuKyHb(1/16) AAS
いらないスレを使って自分の意見を垂れ流すとか有効活用乙としか
260(2): 2015/12/26(土)13:36 ID:oIXuKyHb(2/16) AAS
>>259
ループの方は今どの範囲についてソートしているのかという情報が大量に発生するから同じ議論が成り立つ訳だが。
264: 2015/12/26(土)16:59 ID:oIXuKyHb(3/16) AAS
>>263
うまくいくって言ったって高々定数倍速くなるだけだろ？
非再帰版を書いたり保守したりするコストより新しい速いマシンを買ったほうが安く上がるって発想は無いのかね？
277(1): 2015/12/26(土)19:09 ID:oIXuKyHb(4/16) AAS
>>275
バカはお前だ。シェルスクリプトでクイックソートを実装するなんて誰がするか。
sortプログラムを使え。
ちなみにシェルスクリプトの場合、関数呼び出しはそれ自体がスタックの深さをnとしてO(n^2)くらいの計算時間を持つっぽい。
279: 2015/12/26(土)19:10 ID:oIXuKyHb(5/16) AAS
>>276
確かに、うん、確かに、非常にゆるやかに発散するね。
n=2^64としてもlog nは64だけどね。
定数と変わんないレベルだよね。
283: 2015/12/26(土)19:16 ID:oIXuKyHb(6/16) AAS
>>280
練習のためなら兎も角、シェルスクリプト「だけ」でソーティングなんてやる意味が無い。
ループだろうと再帰だろうとね。
理由は遅いから。
ループで組んだとしても、非常に遅いから、実装するだけの意味が無い。
sortを呼べばCで書かれた非常に高速でスケーラブルなソーティングが出来るから、普通はそっちを使う。
さぁ君は一体何を論破したというのだい？
286(2): 2015/12/26(土)19:21 ID:oIXuKyHb(7/16) AAS
>>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倍違うと言う。
省1
290(1): 2015/12/26(土)19:23 ID:oIXuKyHb(8/16) AAS
>>287
5000回の再帰で130倍の差が開いた訳じゃなくて、
深さ5000の関数呼び出しで130倍の差が開いたって事を理解してる？
5000万要素のクイックソートなら最良のケースで深さ25の再帰だからね？
130倍どころか2倍にもならないからね？
301(1): 2015/12/26(土)19:35 ID:oIXuKyHb(9/16) AAS
>>295
どうして俺が実装しなきゃならないわけ？
数万倍遅いって言い出した奴が実証のためにコードを提供するのが筋だろ？
304(1): 2015/12/26(土)19:50 ID:oIXuKyHb(10/16) AAS
>>302
IDをよく見ろ。俺は実証コードが欲しいだなんて一言も言ってない。
308(1): 2015/12/26(土)19:56 ID:oIXuKyHb(11/16) AAS
>>305
俺も見たこと無い。
一瞬、三項演算子にも見えるけど順序がおかしいし。
311(1): 2015/12/26(土)20:02 ID:oIXuKyHb(12/16) AAS
>>309
いいや、そもそもそんな事は望んでない。よく読め。
俺が言いたいのは、1万倍もの差が出るなんて事は理論上ありえないって事だ。
それでも尚、実際に1万倍の差が出ると言い張るのであれば
それを実証するコードを君が示すべきだよね？
317(1): 2015/12/26(土)20:13 ID:oIXuKyHb(13/16) AAS
>>313
いいかい？
君は「示した」と何度もはっきり発言してはいるけど、実のところ何も示しちゃいないんだ。
325(2): 2015/12/26(土)21:07 ID:oIXuKyHb(14/16) AAS
純粋にシェルスクリプトだけでクイックソートを組むのは骨が折れたぞっと
画像ﾘﾝｸ[php]:www.fastpic.jp
ループのほうが遅いです本当にどうもありがとうございました
326(1): 2015/12/26(土)21:10 ID:oIXuKyHb(15/16) AAS
コードが見たけりゃどうぞ。
外部ﾘﾝｸ:ideone.com
332: 2015/12/26(土)22:10 ID:oIXuKyHb(16/16) AAS
メモ化しないコードだとそうなるね
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 1.197s*