haskell - 用于繁重科学计算的列表、装箱向量和未装箱向量

Question

有人告诉我，我应该将未装箱的向量用于繁重的科学计算(运行数小时甚至数天的模拟)，而不是列表，甚至是装箱的向量。

这是真的？

除了常见的列表、装箱向量或未装箱向量之外，还有其他数据结构吗？

你能解释装箱和未装箱向量之间的区别吗？

Answer 1

有几件事要理解。首先，盒装与未盒装:

如果你有一个“盒装”数字，基本上你就有一个指向数字的指针。 (或者可能是一个指向未计算的表达式的指针，如果它被计算将产生一个数字。)

如果您有一个“未装箱”的号码，那么您实际上就是号码本身。

例如，在 64 位平台上， Char是一个指向 Haskell 堆上某处的 64 位指针，它包含一个 32 位 Unicode 代码点，或者一个任意大的未计算的表达式，产生这样的代码点。另一方面， Char#实际上只是一个 32 位整数。它可能在堆上的某个地方，也可能在 CPU 寄存器或其他地方。

基本上 Char#是 C 认为的整数，而 Char是什么 C 会认为是指向...的指针实际上是一个数据结构，它告诉您它是否被评估，如果它被评估，整数就在那里。这要复杂一些。

需要注意的重要一点是，装箱的值可能未被评估；指针可以指向结果，也可以指向产生结果的表达式。未装箱的值永远不会被取消评估。例如，一个 32 位整数不可能存储任意庞大的用于计算整数的表达式；它只能存储整数本身。所以boxed vs unboxed 不可避免地与lazy vs strict 纠缠在一起。

惰性求值可以让您避免计算您实际上不需要的结果。 (无限列表等等。)但如果您确实总是需要所有结果，严格评估实际上会更快。

接下来，列表与向量:

Haskell 列表 [Double] (或其他)是指向 double 浮点数的指针的单向链接列表。每个浮点数都可以不计算，列表中的每个链接也可以不计算。可以想象，这根本没有任何缓存一致性!

向量是一组东西。这意味着没有无限向量；在创建时必须知道向量的大小。这也意味着要修改一个不可变的向量，你必须复制整个东西，这在时间和空间上都是非常低效的。否则，您必须使用可变向量，这会抵消函数式编程的一些好处。另一方面，向量具有很棒的缓存一致性!

现在，盒装向量基本上是指向实际数据的指针数组。未装箱向量是实际数据的数组。想猜猜哪一个具有最好的缓存行为？作为副作用，未装箱的向量也是严格的，如果您需要整个向量，它会更快。

所以你看，未装箱的向量对你有一定的限制，但可能会提供最好的性能。

说了这么多，GHC 执行各种棘手的优化，可以从根本上改变代码的性能，而不是它“似乎”正在做的事情。 GHC 可以将惰性代码转换为严格代码，并且它可以执行“列表融合”，其中循环列表的函数链变成单个紧密循环。但话又说回来，向量操作链也会融合在一起，所以……实际上，实际性能取决于您要做什么。