[過去ﾛｸﾞ]
関数型プログラミング言語Haskell Part22 (1001ﾚｽ)
関数型プログラミング言語Haskell Part22 http://echo.5ch.net/test/read.cgi/tech/1364009659/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
731: デフォルトの名無しさん [sage] 2013/03/23(土) 12:46:30.00 とりあえず、よくあるもっとも簡単な実装はこれかな。 qs :: (Ord a) => [a] -> [a] qs [] = [] qs (x:xs) = qs (filter (< x) xs) ++ [x] ++ qs (filter (> x) xs) 空間計算量が最悪O(n^2)になるケースってのは、どういうリストに適用した時？ http://echo.5ch.net/test/read.cgi/tech/1364009659/731
732: デフォルトの名無しさん [sage] 2013/03/23(土) 12:46:31.00 >>713で正しいよ なんかwikipediaのクイックソートのページにも実用性が云々と書かれているけど、そもそもリストという データ構造自体がソートと相性が悪いんだから、そんなこと言っても仕方ないと思うけどね 大量のデータを扱うなら他のデータ構造を使うべきだし、ごく少量のデータなら入門書の実装の 方がむしろ実用的だろう >>731 それだと重複した要素が消えることないかな？ http://echo.5ch.net/test/read.cgi/tech/1364009659/732
735: デフォルトの名無しさん [sage] 2013/03/23(土) 12:46:34.00 >>731 >空間計算量が最悪O(n^2)になるケースってのは、どういうリストに適用した時？ 入力が既に正順か逆順にソートされている場合。O(n^2)になるのは正順か逆順のどちらか だけなんだけど忘れた。この板のHaskell関係の過去スレの一つに議論があったはず (ちょっと探したけど見つからなかった、曖昧でごめん) http://echo.5ch.net/test/read.cgi/tech/1364009659/735
746: デフォルトの名無しさん [sage] 2013/03/23(土) 12:46:45.00 >>732 すまんすまん、= を書き忘れてた。 < か > のどちらかに = を追加して考えて。 >>735 >>736 モリタポ使っても、なぜか Part 7 が見れない。 >>731 のような感じのクイックソートの実装だと、 A ++ B ++ C という形の式が大枠であるよね。 これを順に弱頭部正規形にして評価していくとき、最悪の場合、 左側の ++ 演算子が評価可能になるまで（++の左辺が x:xs の形になるまで）ずっと、 (((・・・((A'' ++ B '' ++ C'') ++ B' ++ C'))・・・))) ++ B ++ C というような再帰的な形で左側が伸びていくと思う。 未評価の A'' や B' などが何個作られるかというと、 qs 関数が適用するリストの長さを n とすると、ざっと見積もって 3 + 2 * (n - 1) 個かな。 （最初の 3 は一番深い所の A++B++C で、2 は ()++B++C の B と C） 最悪ここまで式が伸びきるので、空間計算量は O(n) ではないか、 と俺は思ったんだが、どこで勘違いをしているのか分からない。 過去ログ Part 7 が見られるようになったら調べてみるけど、 今の所自分の頭ではこう考えた。 http://echo.5ch.net/test/read.cgi/tech/1364009659/746
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.049s