你可以在列表理解中计算匹配(尝试在阈值后插入qsort)

Question

我来自C++背景,所以我不确定我是否正确地解决了这个问题.但我想要做的是写快速排序,但如果列表的长度小于某个阈值,则回退到插入排序.到目前为止,我有这个代码:

insertionSort :: (Ord a) => [a] -> [a]
insertionSort [] = []
insertionSort (x:xs) = insert x (insertionSort xs)

quickSort :: (Ord a) => [a] -> [a]
quickSort x = qsHelper x (length x)

qsHelper :: (Ord a) => [a] -> Int -> [a]
qsHelper [] _ = []
qsHelper (x:xs) n 
    | n <= 10 = insertionSort xs
    | otherwise =  qsHelper before (length before) ++ [x] ++ qsHelper after (length after)
        where
            before = [a | a <- xs, a < x]
            after = [a | a <- xs, a >= x]

现在我关心的是每次计算每个列表的长度.我不完全理解Haskell如何优化事物或懒惰评估对代码的完全影响,如上所述.但似乎在列表理解之前和之后计算每个列表的长度并不是一件好事吗？有没有办法在执行列表推导时提取列表推导中发生的匹配数？

即如果我们有[x | x <- [1,2,3,4,5], x > 3](导致[4,5])我可以在不使用长度调用的情况下获得[4,5]的计数吗？

感谢您的帮助/解释!

Answer 1

简答:不.

简短回答:是的,你可以假装它.import Data.Monoid, 然后

    | otherwise =  qsHelper before lenBefore ++ [x] ++ qsHelper after lenAfter
        where
            (before, Sum lenBefore) = mconcat [([a], Sum 1) | a <- xs, a < x]
            (after, Sum lenAfter) = mconcat [([a], Sum 1) | a <- xs, a >= x]

更好的答案:你不想.

要避免的常见原因length包括:

• 它的运行时间是O(N)
  • 但是无论如何都要花费我们O(N)来构建列表
• 它强制列表脊椎严格
  • 但我们正在对列表进行排序:我们必须(至少部分地)评估每个元素,以便知道哪个是最小的; 列表脊椎已被强制严格
• 如果你不关心列表的长度,只是它比另一个列表或阈值更短/更长,length是浪费的:它会一直走到列表的末尾,无论如何
  • 答对了

isLongerThan :: Int -> [a] -> Bool
isLongerThan _ []     = False
isLongerThan 0 _      = True
isLongerThan n (_:xs) = isLongerThan (n-1) xs

quickSort :: (Ord a) => [a] -> [a]
quickSort []     = []
quickSort (x:xs) 
    | not (isLongerThan 10 (x:xs)) = insertionSort xs
    | otherwise =  quickSort before ++ [x] ++ quickSort after
        where
            before = [a | a <- xs, a < x]
            after = [a | a <- xs, a >= x]

这里真正的低效率在于before和after.他们都遍历整个列表,比较每个元素x.所以我们踩了xs两次,并将每个元素比较x两次.我们只需要做一次.

            (before, after) = partition (< x) xs

partition 在Data.List中.