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