[過去ﾛｸﾞ] 関数型プログラミング言語Haskell Part22 (1001ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
731(3): 2013/03/23(土)12:46 AAS
とりあえず、よくあるもっとも簡単な実装はこれかな。
qs :: (Ord a) => [a] -> [a]
qs [] = []
qs (x:xs) = qs (filter (< x) xs) ++ [x] ++ qs (filter (> x) xs)
空間計算量が最悪O(n^2)になるケースってのは、どういうリストに適用した時？
732(1): 2013/03/23(土)12:46 AAS
>>713で正しいよ
なんかwikipediaのクイックソートのページにも実用性が云々と書かれているけど、そもそもリストという
データ構造自体がソートと相性が悪いんだから、そんなこと言っても仕方ないと思うけどね
大量のデータを扱うなら他のデータ構造を使うべきだし、ごく少量のデータなら入門書の実装の
方がむしろ実用的だろう
>>731
それだと重複した要素が消えることないかな？
735(1): 2013/03/23(土)12:46 AAS
>>731
>空間計算量が最悪O(n^2)になるケースってのは、どういうリストに適用した時？
入力が既に正順か逆順にソートされている場合。O(n^2)になるのは正順か逆順のどちらか
だけなんだけど忘れた。この板のHaskell関係の過去スレの一つに議論があったはず
(ちょっと探したけど見つからなかった、曖昧でごめん)
746: 2013/03/23(土)12:46 AAS
>>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 が見られるようになったら調べてみるけど、
今の所自分の頭ではこう考えた。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.042s