11

我有一个类型如下的函数：

union :: a -> a -> a

并a具有可加性。所以我们可以把union它看成一个版本(+)

说，我们有[a]，并且想要执行并行"folding"，对于非并行折叠，我们只能做：

foldl1' union [a]

但是如何并行执行呢？我可以展示Num价值和(+)功能上的问题。

例如，我们有一个列表[1,2,3,4,5,6]，(+) 我们应该并行拆分

[1,2,3] (+) [4,5,6]
[1,2] (+) [3] (+) [4,5] (+) [6]
([1] (+) [2]) (+) ([3] (+) [4]) (+) ([5] (+) [6])

然后(+)我们要并行执行的每个操作，并结合起来回答

[3] (+) [7] (+) [11] = 21

请注意，由于可a加性，我们拆分列表或以任何顺序执行操作。

有没有办法使用任何标准库来做到这一点？

4

3 回答 3

14

您需要将您推广union到任何关联二元运算符 ⊕ 使得 (a ⊕ b) ⊕ c == a ⊕ (b ⊕ c)。如果同时你甚至有一个相对于⊕中性的单位元素，你就有一个幺半群。

关联性的重要方面是，您可以将列表中的连续元素块任意分组，并以任意顺序 ⊕ 它们，因为 a ⊕ (b ⊕ (c ⊕ d)) == (a ⊕ b) ⊕ (c ⊕ d ) - 每个括号可以并行计算；那么您需要“减少”所有括号的“总和”，并且您已经对 map-reduce 进行了排序。

为了使这种并行化有意义，您需要分块操作比 ⊕ 更快 - 否则，顺序执行 ⊕ 比分块更好。一种这样的情况是当你有一个随机访问“列表”——比如一个数组。Data.Array.Repa有很多并行化的折叠函数。

如果您正在考虑练习自己实现一个，您需要选择一个好的复杂函数⊕，这样好处就会显现出来。

例如：

import Control.Parallel
import Data.List

pfold :: (Num a, Enum a) => (a -> a -> a) -> [a] -> a
pfold _ [x] = x
pfold mappend xs  = (ys `par` zs) `pseq` (ys `mappend` zs) where
  len = length xs
  (ys', zs') = splitAt (len `div` 2) xs
  ys = pfold mappend ys'
  zs = pfold mappend zs'

main = print $ pfold (+) [ foldl' (*) 1 [1..x] | x <- [1..5000] ]
  -- need a more complicated computation than (+) of numbers
  -- so we produce a list of products of many numbers

在这里，我特意使用了一个仅在本地调用的关联操作，mappend以表明它可以用于比幺半群更弱的概念——只有关联性对并行性很重要；因为并行性只对非空列表有意义，所以不需要mempty.

ghc -O2 -threaded a.hs
a +RTS -N1 -s

总运行时间为 8.78 秒，而

a +RTS -N2 -s

在我的双核笔记本电脑上提供 5.89 秒的总运行时间。显然，在这台机器上尝试超过 -N2 是没有意义的。

于 2013-10-01T14:56:15.897 回答
3

你所描述的本质上是一个幺半群。在 GHCI 中：

Prelude> :m + Data.Monoid
Prelude Data.Monoid> :info Monoid
class Monoid a where
  mempty :: a
  mappend :: a -> a -> a
  mconcat :: [a] -> a

如您所见，幺半群具有三个相关的功能：

  1. 该mempty函数有点像幺半群的恒等函数。例如，aNum可以表现为一个幺半群，只需要两个操作：求和和乘积。对于总和mempty定义为0。对于一个产品mempty定义为1。

    mempty `mappend` a = a
a `mappend` mempty = a

  2. 该mappend功能类似于您的union功能。例如 s 的总和定义为Nums的乘积定义为。mappend(+)Nummappend(*)

  3. 该mconcat功能类似于折叠。然而，由于幺半群的特性，我们是从左侧折叠、从右侧折叠还是从任意位置折叠都无关紧要。这是因为mappend应该是关联的：

    (a `mappend` b) `mappend` c =  a `mappend` (b `mappend` c)

但是请注意，Haskell 不执行幺半群定律。因此，如果您将类型设为类型类的实例，Monoid那么您有责任确保它满足幺半群定律。

union在您的情况下，很难从其类型签名中理解其行为方式： a -> a -> a. 当然，您不能使类型变量成为类型类的实例。这是不允许的。你需要更具体。实际上是做什么的union？

举一个例子来说明如何使一个类型成为 monoid 类型类的一个实例：

newtype Sum a = Sum { getSum :: a }

instance Num a => Monoid (Sum a) where
    mempty = 0
    mappend = (+)

就是这样。我们不需要定义mconcat函数，因为它有一个依赖于memptyand的默认实现mappend。因此，当我们定义mempty并免费mappend获得mconcat时。

现在你可以使用Sum如下：

getSum . mconcat $ map Sum [1..6]

这就是正在发生的事情：

  1. 您正在将Sum构造函数映射[1..6]到 production [Sum 1, Sum 2, Sum 3, Sum 4, Sum 5, Sum 6]。
  2. 您将结果列表提供给将mconcat其折叠为Sum 21.
  3. 您使用getSum从Num.Sum 21

但是请注意，默认实现mconcat是foldr mappend mempty（即它是正确的折叠）。对于大多数情况，默认实现就足够了。但是，在您的情况下，您可能希望覆盖默认实现：

foldParallel :: Monoid a => [a] -> a
foldParallel []  = mempty
foldParallel [a] = a
foldParallel xs  = foldParallel left `mappend` foldParallel right
    where size = length xs
          index = (size + size `mod` 2) `div` 2
          (left, right) = splitAt index xs

现在我们可以创建一个新的实例Monoid如下：

data Something a = Something { getSomething :: a }

instance Monoid (Something a) where
    mempty  = unionEmpty
    mappend = union
    mconcat = foldParallel

我们使用它如下：

getSomething . mconcat $ map Something [1..6]

请注意，我定义mempty为unionEmpty. 我不知道该union函数作用于什么类型的数据。因此我不知道mempty应该定义什么。因此，我只是简单地称呼它unionEmpty。按照您认为合适的方式定义它。

于 2013-10-01T14:56:32.507 回答
0

我知道在 OP 之后已经有很长时间了，但我刚刚发生了这件事，并认为我的经历可能会有所帮助。

如果我们考虑这个问题，我们可以看到：

  • fold 本质上是一个函数，它接受一个项目列表，并将它们转换为单个项目，该项目可能与列表中的项目具有相同的类型，但不一定是：所以它的类型是([a] -> b).

  • 并行折叠将其输入列表拆分为块，分别（并行）折叠每个块，然后组合结果以得出最终结果。为此，我们需要：

    • 块大小。这可以参考输入列表的大小来计算，但这有一个明显的缺点：为了确定列表的大小，我们必须对其进行处理，这失去了惰性的好处。所以最好让所有的块大小都一样；这可以是硬编码的，但在通用函数中，最好将其公开为参数，以便可以对其进行更改和调整以满足调用应用程序的需要。

    • 一个知道如何组合结果的函数。这有类型(b -> b -> b)。

因此，一个合适的通用并行折叠函数是：

import Control.Parallel

foldParallel :: Int -> ([a] -> b) -> (b -> b -> b) -> [a] -> b
foldParallel _ fold _ [] = fold []
foldParallel chunkSize fold combine xs = par lf $ combine lf rf
  where
    (left, right) = splitAt chunkSize xs
    lf = fold left
    rf = foldParallel chunkSize fold combine right

并行处理是显式完成的，使用par函数并行启动对其第一个操作数的评估，并返回第二个操作数。

花了一段时间——对于像我这样一个古老的命令式编程恐龙——我才明白where块中的定义实际上并没有评估任何东西，而只是设置了可以评估的东西。因此名为 as 的折叠lf可以在 的两个操作数中引用，par但只计算一次。

不同之处在于par，如果函数只返回combine lf rf，则lf需要在评估时评估，然后rf，然后combine lf rf。但par lf $ combine lf rf意味着lf在需要其值时已经全部或部分评估（并行）。而且因为rf它本身是一个平行折叠，所以每个后续块的折叠也是如此。

于 2022-01-20T14:22:50.113 回答