Haskell：Verlet 集成的缓慢无限列表

Question

我正在使用 Haskell 制作 Verlet 积分器来模拟重力。积分器使用对象的前两个位置作为种子，然后生成其余位置。

我认为在 Haskell 中实现这一点的一个好方法是使用无限列表。然而，在实施时我发现它运行很长时间很慢（Haskell 1700 个时间步长：12 秒，Python 1700 个时间步长：< 1 秒）

这是具有类似性能的一维积分器的相关代码：

verletStep dt acc xn xn1 = 2*xn1 - xn + (acc xn1)*dt*dt

verlet dt acc x0 x1 = x0 : x1 : next (verlet dt acc x0 x1)
  where
    next (xn : xs@(xn1:_)) = (verletStep dt acc xn xn1) : next xs

我也尝试过使用 zipWith 生成无限列表，但它具有相似的性能。

为什么这需要这么长时间？垃圾收集本身大约需要 5 秒。有什么好的方法可以使运行更快？

Answer 1

这个定义...

verlet dt acc x0 x1 = x0 : x1 : next (verlet dt acc x0 x1)
  where
    next (xn : xs@(xn1:_)) = (verletStep dt acc xn xn1) : next xs

... 导致 verlet dt acc x0 x1 被多次不必要地计算，从而构建了很多不需要的列表。这可以通过手动计算时间步长来看出：

verlet dt acc x0 x1
x0 : x1 : next (verlet dt acc x0 x1)
x0 : x1 : next (x0 : x1 : next (verlet dt acc x0 x1))
x0 : x1 : (verletStep dt acc x0 x1) : next (x1 : next (verlet dt acc x0 x1))

解决方案是消除不必要的列表构建：

verlet dt acc x0 x1 = x0 : x1 : x2 : drop 2 (verlet dt acc x1 x2)
  where
     x2 = verletStep dt acc x0 x1

drop 2 删除列表的前两个元素（在本例中，x1 和 x2，我们已经在前面添加了）。 verlet 使用第二个位置 x1 和新计算的第三个位置 x2 递归调用。（与原始定义比较，其中 verlet 以相同的参数递归调用。这应该引起怀疑。）

Haskell：Verlet 集成的缓慢无限列表

Haskell: Slow infinite list for Verlet Integration

performance

haskell

verlet-integration