2

这是一个快速排序的实现，它被认为是“不是真正的快速”：

qSort :: Ord a => [a] -> [a]
qSort [] = []
qSort (p:xs) = (qSort $ filter (< p) xs) ++ (qSort $ filter (== p) xs) ++ [p] ++ (qSort $ filter (> p) xs)

main = print $ qSort [15, 11, 9, 25, -3]

但是，是否可以计算完成所需的比较次数？我试图计算大小，filter (< p) xs但filter (> p) xs结果不是我需要的。

更新：

问题不在于时间复杂度，而在于计算比较次数。

4

4 回答 4

4

正如其他人所说，直接翻译是修改您的算法以使用 monad，它将计算比较。而不是State我宁愿使用Writer，因为它更自然地描述了正在发生的事情：每个结果都增加了它所需的（加法）比较次数：

import Control.Applicative
import Control.Monad
import Control.Monad.Writer.Strict
import Data.Monoid

type CountM a = Writer (Sum Int) a

然后让我们定义一个函数，将一个纯值包装成一个增加计数器的单子：

count :: Int -> a -> CountM a
count c = (<$ tell (Sum c))

现在我们可以定义

qSortM :: Ord a => [a] -> CountM [a]
qSortM [] = return []
qSortM (p:xs) =
   concatM [ qSortM =<< filtM (<  p)
           , filtM (== p)
           , return [p]
           , qSortM =<< filtM (>  p)
           ]
  where
    filtM p = filterM (count 1 . p) xs
    concatM :: (Monad m) => [m [a]] -> m [a]
    concatM = liftM concat . sequence

它没有原始版本那么好，但仍然可以使用。

请注意，您将列表中的每个元素比较了 3 次，而只做一次就足够了。这有另一个不幸的结果，原始列表必须保存在内存中，直到所有三个过滤器都完成。所以让我们改为定义

-- We don't care we reverse the order of elements in the buckets,
-- we'll sort them later anyway.
split :: (Ord a) => a -> [a] -> ([a], [a], [a], Int)
split p = foldl f ([], [], [], 0)
  where
    f (ls, es, gs, c) x = case compare x p of
        LT  -> (x : ls, es, gs, c')
        EQ  -> (ls, x : es, gs, c')
        GT  -> (ls, es, x : gs, c')
      where
        c' = c `seq` c + 1

这一次执行了分成三个桶的操作，还计算了列表的长度，所以我们可以一次更新计数器。该列表会立即被使用，并且可以被垃圾收集器丢弃。

现在我们的快速排序将变得更精简

qSortM :: Ord a => [a] -> CountM [a]
qSortM [] = return []
qSortM (p:xs) = count c =<<
    concatM [ qSortM ls
            , return (p : es)
            , qSortM gs
            ]
  where
    (ls, es, gs, c) = split p xs
    concatM = liftM concat . sequence

我们可以在不使用 的情况下达到相同的结果Writer，只需明确地qSortM返回即可。(Int, [a])但是接下来我们将不得不手动处理 recursive 的结果qSortM，这将更加混乱。此外，单子方式允许我们稍后添加更多信息，例如最大深度，而不会以任何方式破坏核心部分。

于 2013-07-25T16:43:58.497 回答
3

从理论上考虑这个问题，正如 Monad Newb 在他们的回答中提出的那样，这可能是考虑你的算法实际作用的最佳方式。

当然，将比较放入Statemonad 是一种愚蠢的做法。这将只是蛮力计算比较函数的每次调用。请注意count动作的使用，它只是将谓词转换为跟踪所述谓词的每次调用的动作，然后将其应用于其参数。

{-# LANGUAGE ScopedTypeVariables #-}
import Control.Monad.State

qSortM :: Ord a => [a] -> State Int [a]
qSortM [] = return []
qSortM (p:xs) = do h <- (qSortM =<< filterM (count (< p)) xs)
                   e <- (qSortM =<< filterM (count (== p)) xs)
                   t <- (qSortM =<< filterM (count (> p)) xs)
                   return $ h ++ e ++ [p] ++ t
               where count :: (a -> Bool) -> (a -> State Int Bool)
                     count p a = modify (+1) >> return (p a)

qSort :: Ord a => [a] -> ([a],Int)
qSort l = runState (qSortM l) 0

main :: IO ()
main = print $ (qSort [15, 11, 9, 25, -3])

这实际上是可怕的 Haskell，并且可以不用Statemonad 来表达，只需使用递归函数即可。一个很好的练习就是这样写。不可否认，Statemonad 版本对于来自命令式背景的人来说会更直观。

> qSort [10,9..1]
([1,2,3,4,5,6,7,8,9,10],90)

> qSort [15,11,9,25,-3]
([-3,9,11,15,25],14)
于 2013-07-25T14:43:34.643 回答
1

让我们评估表达式qSort [15, 11, 9, 25, -3]：

qSort [15, 11, 9, 25, -3]
    = qSort (15:[11, 9, 25, -3])
    = (qSort $ filter (< 15) [11, 9, 25, -3])
      ++ (qSort $ filter (== 15) [11, 9, 25, -3])
      ++ [p]
      ++ (qSort $ filter (> 15) [11, 9, 25, -3])
    = (qSort [11, 9, -3]) ++ (qSort []) ++ [p] ++ (qSort [25])

为了做到这一点，我们进行了 12 次比较。qSort您可以以类似的方式评估剩余的应用程序。

请注意，这种替换是有效的，因为我们在这里使用所谓的纯函数式编程。没有副作用，因此任何表达式都可以替换为等效的表达式。

于 2013-07-25T14:22:19.837 回答
1

我们可以编写函数来计算这个数字。每个都filter p xs进行length xs比较，仅此而已。

现在您的代码执行 3 次传递来执行分区；您可以重写它以一次性执行三路分区。我们可以将传递次数作为参数。

另一件事是中间部分的不必要排序，已知它包含所有相等的元素。我们也可以将其设为参数，以指示是否执行了这种不必要的排序。

_NoSort = False
_DoSort = True

qsCount xs n midSortP = qs 0 xs id     -- return number of comparisons that 
 where                                 -- n-pass `qSort xs` would perform
   qs !i []     k = k i
   qs !i (p:xs) k = 
     let (a,b,c) = (filter (< p) xs, filter (== p) xs, filter (> p) xs)
     in qs (i+n*length xs) a (\i-> g i b (\i-> qs i c k))
   g i b k | midSortP  = qs i b k 
           | otherwise = k i

可以看出，与 1 次相比，3 次比较需要多 3 倍的比较，并且只有在列表中有两个以上相等的元素时，中间排序才会有任何区别：

*Main> qsCount ( concat $ replicate 4 [10,9..1]) 3 _NoSort
630
*Main> qsCount ( concat $ replicate 4 [10,9..1]) 3 _DoSort
720
*Main> qsCount ( concat $ replicate 4 [10,9..1]) 1 _NoSort
210
*Main> qsCount ( concat $ replicate 4 [10,9..1]) 1 _DoSort
240
*Main> qsCount [5,3,8,4,10,1,6,2,7,9] 1 _NoSort
19
*Main> qsCount [5,3,8,4,10,1,6,2,7,9] 1 _DoSort
19
*Main> qsCount (replicate 10 1) 1 _NoSort
9
*Main> qsCount (replicate 10 1) 1 _DoSort
45
*Main> qsCount [15, 11, 9, 25, -3] 3 _DoSort
21
于 2013-07-25T19:14:13.087 回答