Haskell: медленный бесконечный список для интеграции Verlet

Question

Я использую Haskell, чтобы сделать интегратор Verlet для моделирования гравитации. Интегратор использует первые две позиции объекта в качестве начальных значений и генерирует остальные после этого.

Я думал, что хороший способ сделать это на Хаскеле - использовать бесконечный список. Тем не менее, при реализации я нахожу, что он работает очень медленно в течение большого времени (шаги по 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 вызывается рекурсивно с теми же аргументами. Это должно вызвать подозрение.)