Haskell 中的并行“任何”或“所有”

Question

我现在多次遇到的一种模式是，需要通过在其上映射一些测试并查看是否通过任何或所有元素来检查值列表。典型的解决方案是使用方便的内置函数all和any.

问题是这些评估是串行的。在许多情况下，这将是多快平行的过程被完整的评估，一旦任何线程发现一个“假”的all或“真”的any。我很确定不能使用 Control.Parallel 实现短路行为，因为它需要进程间通信，而且我还没有理解足够接近 Control.Concurrent 的任何地方来实现它。

这是数学中非常常见的模式（例如 Miller-Rabin Primality），所以我觉得有人可能已经为此提出了解决方案，但出于显而易见的原因，在 google 上搜索“parallel or/and/any/all on list” haskell" 不会返回许多相关结果。

Answer 1

在许多实际程序中，您可以使用并行策略来实现此目的。这是因为，即使没有明确的机制来取消不需要的计算，这也会在垃圾收集器运行时隐式发生。作为一个具体示例，请考虑以下程序：

import Control.Concurrent
import Control.Parallel.Strategies
import Data.Int
import System.Mem

lcgs :: Int32 -> [Int32]
lcgs = iterate lcg
  where lcg x = 1664525 * x + 1013904223

hasWaldo :: Int32 -> Bool
hasWaldo x = waldo `elem` take 40000000 (lcgs x)

waldo :: Int32
waldo = 0

main :: IO ()
main = do
  print $ or (map hasWaldo [1..100] `using` parList rseq)

它使用并行列表策略在 100 个 PRNG 流（每个有 4000 万个数字）的输出中搜索waldo = 0（永远找不到）。编译并运行它：

ghc -threaded -O2 ParallelAny.hs
./ParallelAny +RTS -s -N4

它与四个核心连接约 16 秒，最终打印False. 请注意，统计数据中所有 100 个火花均已“转换”，因此运行至完成：

SPARKS: 100(100 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled)

现在，更改waldo为可以提前找到的值：

waldo = 531186389   -- lcgs 5 !! 50000

并修改main以使线程保持活动状态 10 秒：

main :: IO ()
main = do
  print $ or (map hasWaldo [1..100] `using` parList rseq)
  threadDelay 10000000

您会发现它True几乎立即打印出来，但 4 个核心仍保持 100% CPU（至少在一段时间内），这说明不需要的计算继续运行并且不会短路，正如您可能担心的那样。

但是，如果在得到答案后强制进行垃圾回收，情况就会发生变化：

main :: IO ()
main = do
  print $ or (map hasWaldo [1..100] `using` parList rseq)
  performGC
  threadDelay 10000000

现在，您将看到 CPU 在打印后不久就进入空闲状态True，并且统计数据显示大多数计算在运行之前已被垃圾收集：

SPARKS: 100(9 converted, 0 overflowed, 0 dud, 91 GC'd, 0 fizzled)

在实际的程序中，不需要显式的performGC，因为 GC 理所当然会定期执行。一些不必要的计算在找到答案后会继续运行，但在许多现实场景中，不必要的计算所占的比例并不是特别重要的因素。

特别是，如果列表很大并且列表元素的每个单独测试都很快，则并行策略将具有出色的实际性能，并且很容易实现。