2

我来自 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] 的计数吗？

感谢您的任何帮助/解释！

4

2 回答 2

6

简短的回答：没有。

不那么简短的回答：是的，你可以伪造它。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]

但是，这里真正的低效率是 inbefore和after。他们都遍历整个列表，将每个元素与x. 因此，我们将逐步执行xs两次，并将每个元素与x两次进行比较。我们只需要做一次。

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

partition在 Data.List 中。

于 2012-07-31T08:46:57.340 回答
0

不，没有办法使用列表推导同时进行过滤并计算找到的元素的数量。但是，如果您担心这种性能损失，您不应该像一开始那样使用列表推导式：您正在过滤列表两次，因此将谓词<x及其否定应用于每个元素。更好的变体是

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

从此开始编写函数并不难

partitionAndCount :: (a -> Bool) -> [a] -> (([a],Int), ([a],Int))

同时对列表进行分区和计数，并对每个返回列表中的元素进行计数：

((before, lengthBefore), (after, lengthAfter)) = partitionAndCount (< x) xs

这是一个可能的实现（具有稍微重新排序的类型）：

{-# LANGUAGE BangPatterns #-}
import Control.Arrow

partitionAndCount :: (a -> Bool) -> [a] -> (([a], [a]), (Int, Int))
partitionAndCount p = go 0 0
    where go !c1 !c2 [] = (([],[]),(c1,c2))
          go !c1 !c2 (x:xs) = if p x 
                              then first (first (x:))  (go (c1 + 1) c2 xs)
                              else first (second (x:)) (go c1 (c2 + 1) xs)

在这里你可以看到它的实际效果：

*Main> partitionAndCount (>=4) [1,2,3,4,5,3,4,5]
(([4,5,4,5],[1,2,3,3]),(4,4))
于 2012-07-31T08:43:15.403 回答