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。