5

我经常需要将多个函数映射到相同的数据。我已经实现了 dpMap 来为我做这件事

dpMap fns = (`map` fns) . flip ($)

dpMap 是一个功能，这是否意味着我只读取数据 dt 一次（就像一个只有相同输入的电路。一个毫无意义的系统提醒一个电路；只是管道没有数据）？

例如，考虑计算列表 dt 的最小值和最大值。

minimax dt = (dpMap [minimum, maximum]) dt

（我可以摆脱 dt 但必须使用 -XNoMonomorphismRestriction）

与以这样的全点形式实现相同的功能相比，是否有性能优势？：

minimax2 dt = [minimum dt, maximum dt]

编辑： dpMap 是否有一个通用的实现，它适用于常量内存？

我发现了另一篇不错的博文：http ://www.haskellforall.com/2013/08/composable-streaming-folds.html ；希望对您有所帮助。

EDIT2：在获得更多上下文之后，这是一个解决方案，即使我没有 dpMap 的确切实现，该模式也很简单，不需要单独的函数：

minimax = (,) <$> minimum <*> maximum

用法：

> minimax [1..100]
(1,100)

如果您还想计算总和和长度

func = (,,,) <$> minimum <*> maximum <*> sum <*> length

用法：

> func [1..100]
(1,100,5050,100)

4

2 回答 2

9

TL;DR：语言本身的性能无法保证。没有任何。这是编译器的事情。

根据经验，命名实体将常驻内存。如果只有一个消费者懒惰地访问它，那么期望它被优化以使编译的程序将在常量内存中运行是合理的。

内存单元的创建和消耗将是交错的，每个单元在处理完之后都会被 GC-ed。

在minimax2 dt = [minimum dt, maximum dt]中，表达式位于定义[minimum dt, maximum dt]命名实体的范围内dt。最有可能（即几乎可以肯定）GHC 会将其分配为一个内存实体，即一次，并且dt表达式中的两者都将引用同一个实体（指向它，就像指针一样）。

但正如 Cat Plus Plus 在评论中指出的那样，当然如何访问实体是另一回事。并且这两个子表达式将分别访问它，即它将完整地保留在内存中。那不好。

我们可以做得更好，通过只访问一次、折叠并在我们进行过程中收集两条数据来找到我们的答案。在这种情况下，几乎可以肯定 GHC 将执行优化，该列表不会作为一个整体保留在内存中。

这就是通常所说的被懒惰消费的列表。在这种情况下，它的创建将与该一次访问交错，并且生成的每个内存单元将立即被 GC（垃圾收集）消耗和释放，从而实现持续的内存操作。

但这取决于我们只扫描一次列表的能力：

{-# OPTIONS_GHC -O2 -XBangPatterns #-}

import Data.List (foldl')

minmax :: (Ord b) => [b] -> (b, b)
minmax (x:xs) = foldl' (\(!a,!b) x -> (min a x,max b x)) (x,x) xs

Bang 模式可防止 thunk 累积，使参数的评估更加急切。测试：

Prelude> minmax [1..6]
(1,6)
Prelude> minmax []
*** Exception: <interactive>:1:4-65: Non-exhaustive patterns in function minmax

一个空列表当然没有定义最小值或最大值。

为了启动优化，-O2使用 GHC 编译时必须使用 flag。

于 2013-04-29T16:40:36.183 回答
3

我将对这个答案中的问题采取相当广泛的看法，主要是因为 WillNess 答案下的评论。

在一篇博文中，Max Rabkin 介绍了一些关于折叠组合器的工作。Conal Elliott 采纳了这个想法，并发表了更多博客文章以及关于 hackage 的ZipFold 包。我强烈建议您阅读此材料，它简短且易于理解。ZipFold 包可能非常有用，尽管它已经有一段时间没有更新了。

Edward Kmett 最近的巡回演出lens，还包括一些折叠组合器。我不确定我是否只想为此使用它，但是如果您无论如何都在使用镜头，那么它可能值得一看。

另一种方法是使用并行性。如果你写

import Control.Parallel

minimax2 dt = let a = minimum dt
                  b = maximum dt
              in a `par` b `pseq` [a,b]

并与 -thread 链接，然后可以minimax2在接近恒定空间的地方运行，具体取决于调度程序的变幻莫测、月相等（主要是 IIRC 函数的调度程序和分配模式）。当然，这并不能提供可靠的保证，但它可以在实践中很好地工作。将这种方法推广到dpMap应该很简单，您可能希望使用Control.Parallel.Strategies或类似方法，而不是直接使用较低级别par。

最后，大多数迭代派生的库都非常擅长处理这类任务。通常，它们提供对何时生成和使用输入流的显式控制。在iteratee我提供的sequence_与 几乎相同dpMap，将添加sequence与 完全相同的功能dpMap，以及许多 zip，所有这些都在恒定空间中运行（前提是消耗函数本身是恒定空间）。如果大多数其他软件包都提供类似的操作，我不会感到惊讶。

于 2013-04-30T09:02:47.500 回答