[過去ﾛｸﾞ] 関数型プログラミング言語Haskell Part22 (1001ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
732(1): 2013/03/23(土)12:46 AAS
>>713で正しいよ
なんかwikipediaのクイックソートのページにも実用性が云々と書かれているけど、そもそもリストという
データ構造自体がソートと相性が悪いんだから、そんなこと言っても仕方ないと思うけどね
大量のデータを扱うなら他のデータ構造を使うべきだし、ごく少量のデータなら入門書の実装の
方がむしろ実用的だろう
>>731
それだと重複した要素が消えることないかな？
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.038s