6

私はhaskellを学んでいて、私が見る関数の定義は次のとおりです。 

quickSort (x : xs) = (quickSort less) ++ (x : equal) ++ (quickSort more)
                 where less = filter (< x) xs
                       equal = filter (== x) xs
                       more = filter (> x) xs

リストを3回ではなく、1回トラバースするだけで書き込むことはできますか？

4

3 に答える 3

13

このような意味ですか？

quicksort [] = []
quicksort (x:xs) = quicksort less ++ (x : equal) ++ quicksort more
  where (less, equal, more) = partition3 x xs

partition3 _ [] = ([], [], [])
partition3 x (y:ys) =
  case compare y x of
    LT -> (y:less, equal, more)
    EQ -> (less, y:equal, more)
    GT -> (less, equal, y:more)
  where (less, equal, more) = partition3 x ys

実際のクイックソートはインプレースであるため、これは実際にはクイックソートではないことに注意してください。

于 2011-10-04T00:17:36.933 に答える
9

それは何も改善しないようです：

qs (x:xs) = let (a,b) = partition (< x) xs in (qs a) ++ [x] ++ (qs b)
于 2011-10-04T00:11:04.927 に答える
8

遅くなりましたが、これはスペースをそれほどリークしないはずのバージョンです（そして、ここにある他の3ウェイバージョンよりも約2倍速く実行されるようです）。

qsort3 xs = go xs [] 
  where
    go     (x:xs) zs       = part x xs zs [] [] []
    go     []     zs       = zs
    part x []     zs a b c = go a ((x : b) ++ go c zs)
    part x (y:ys) zs a b c =
        case compare y x of
                  LT -> part x ys zs (y:a) b c
                  EQ -> part x ys zs a (y:b) c
                  GT -> part x ys zs a b (y:c)

これは、タプルの使用で発生する可能性のある問題に対処します。let (a,b) = ...実際には、タプルが消費されて処理されlet t= ...; a=fst t; b=snd tた後でも、タプルの一部として、タプルから読み取られるように、タプルが存続しているという状況になりますa。もちろん完全に不要です。これは「ワドラーペアスペースリーク」問題として知られています。あるいは、GHC（with ）はそれよりも賢いのかもしれません。:)tb-O2

また、これは明らかに差分リストアプローチ（ありがとう、ハンマー）を使用しており、これにより少し効率的になります（タプルを使用するバージョンよりも約2倍高速です）。partアキュムレータパラメータは逆の順序で作成されるため、使用していると思います。

于 2012-03-03T22:27:30.970 に答える