首页 文章

在Haskell中并行“折叠”

提问于
浏览 次
10

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

union :: a -> a -> a

并且 a 具有 additivity 属性 . 所以我们可以将 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 可加性，我们拆分列表或以任何顺序执行操作 .

有没有办法使用任何标准库？

haskell parallel-processing

2 回答

  • 12

    您需要将 union 概括为任何关联二元运算符⊕，使得（a⊕b）⊕c==a⊕（b⊕c） . 如果同时你甚至有一个相对于neutral中性的单位元素，你就有一个幺半群 .

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

    为了使这种并行化有意义，你需要比⊕更快的分块操作 - 否则，顺序执行is比分块更好 . 一个这样的情况是当你有一个随机访问"list" - 比如一个数组 . 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没有意义 .

    回复于
  • 4

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

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

    如你所见，monoid有三个相关的函数：

    • mempty 函数有点像幺半群的身份函数 . 例如， Num 可以表现为monoid apropos两个操作：sum和product . 总和 mempty 定义为 0 . 对于产品 mempty 定义为 1 .
    mempty `mappend` a = a
a `mappend` mempty = a

    • mappend 函数类似于 union 函数 . 例如， Num 的总和 mappend 被定义为 (+) ，而对于 Num 的产品， mappend 被定义为 (*) .

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

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

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

    在您的情况下，很难理解 union 从其类型签名的行为： a -> a -> a . 当然你不能允许't make a type variable an instance of a typeclass. That' . 你需要更具体 . union 究竟做了什么？

    为您举例说明如何使类型成为monoid类型类的实例：

    newtype Sum a = Sum { getSum :: a }

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

    那个's it. We don't需要定义 mconcat 函数，因为它有一个依赖 mempty 和 mappend 的默认实现 . 因此，当我们定义 mempty 和 mappend 时，我们免费得到 mconcat .

    现在您可以使用 Sum ，如下所示：

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

    这就是发生的事情：

    • 您将 Sum 构造函数映射到 [1..6] 以生成 [Sum 1, Sum 2, Sum 3, Sum 4, Sum 5, Sum 6] .

    • 您将结果列表提供给 mconcat ，将其折叠为 Sum 21 .

    • 您使用 getSum 从 Sum 21 中提取 Num .

    但请注意， 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 . 根据需要定义它 .

    回复于

相关问题