9

我正在使用并行的 Haskell 函数par，pseq并且发现了一些有趣的东西。

我的示例基于Real World Haskell的书（ Haskell 中的并行编程）中的示例：

常用代码：

import Control.Parallel (par, pseq)

-- <<sorting code goes here>>

force :: [a] -> ()
force xs = go xs `pseq` ()
    where go (_:xs) = go xs
          go [] = 1

main = do
    print $ take 10 $ parSort [0..1000000]

排序代码1（取自书中）：

parSort :: (Ord a) => [a] -> [a]
parSort (x:xs)    = force greater `par` (force lesser `pseq`
                                         (lesser ++ x:greater))
    where lesser  = parSort [y | y <- xs, y <  x]
          greater = parSort [y | y <- xs, y >= x]
parSort _         = []

排序代码 2（我的自定义变体）：

parSort :: (Ord a) => [a] -> [a]
parSort (x:xs)    = force greater `par` (lesser ++ x:greater)
    where lesser  = parSort [y | y <- xs, y <  x]
          greater = parSort [y | y <- xs, y >= x]
parSort _         = []

编译并运行：ghc -O2 -threaded --make Main.hs && time ./Main +RTS -N8

有趣的是，我的变体比书籍快一点：

sorting code 1 - avg. 16 seconds
sorting code 2 - avg. 14 seconds

我想问你为什么我们可以观察到这样的行为，以及这本书的解决方案是否比我的更有好处。我很想深入了解为什么这个解决方案可以表现得更好。

4

1 回答 1

7

我会说这是因为您的自定义变体不会强制列表的第一部分。让我们看看顶层发生了什么：你强制列表的右半部分，而不是左部分。当您打印前 10 个元素时，您只会懒惰地评估左侧部分的前 10 个元素，而其余部分则不予评估。

另一方面，书中的解决方案强制这两个部分，因此在打印前 10 个元素之前，您需要评估左侧和右侧部分。

尝试打印最后一个，而不是打印前 10 个元素，例如

print $ last $ parSort data

那么算法的两个变体都必须评估整个列表。或者在排序之后和打印之前强制整个列表。

请注意，使用此算法进行排序[0..100000]将非常低效，因为您总是选择最差的枢轴，因此需要O(n^2)时间。测量根本不会给出有意义的结果。如果您想在O(n log n)时间内获得好的结果，请为算法提供类似随机的数据。您可以在此处找到如何创建随机排列的简单方法。

注意：time我建议您使用标准来衡量您的代码，而不是使用。然后，您可以仅测量代码的相关部分，不包括初始化等，并强制输入和输出数据，以便精确测量您感兴趣的部分。

于 2013-09-02T16:24:43.603 回答