Haskell:Verlet Integration的缓慢无限列表

Question

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

我认为在Haskell中制作这个的好方法是使用无限列表.然而,当实现时,我发现它运行很慢很长时间(Haskell 1700时间步长:12秒,Python 1700时间步长:<1秒)

以下是具有类似性能的1d集成商的相关代码:

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使用相同的参数递归调用.这应该引起怀疑.)