Оптимизация алгоритма nbody в F #

Question

Как можно оптимизировать этот код дальше:

let rec nCollect func = function
        | [] -> []
        | x::xs -> let firstAndNext body (firstBody, ys) = 
                        let newFirst, z = func firstBody body
                        newFirst, z::ys
                   let y, ys = List.foldBack firstAndNext xs (x, [])
                   y::(nCollect func ys)

Этот код является частью программы моделирования nbody. Он получает каждое тело и применяет функцию func между ним и каждым следующим. Результаты используются для следующих итераций. Я немного оптимизировал это со списками. Проблема в том, что количество входных тел меньше 10, но nCollect вызывается миллионы раз. Например, если я использую хвостовую рекурсию в nCollect, результат будет хуже.

Answer 1

Я думаю, что ответ на 90% всех проблем микрооптимизации на каждом языке всегда одинаков: используйте массивы, циклы и мутации.

Итак, я бы использовал массивы, циклы и мутации, а не List.foldBack.

Answer 2

1. Используйте лучший алгоритм, такой как суммирование по Эвальду или быстрый мультипольный метод (FMM).

2. Заменить списки и рекурсивные функции на массивы и for циклы.

3. При небольших проблемах замените циклы на создание пользовательских кодов.

Answer 3

Несколько быстрых комментариев

List.Fold должен побить List.FoldBack. Глядя на код здесь - https://github.com/fsharp/fsharp/blob/master/src/fsharp/FSharp.Core/list.fs, вы можете видеть, что FoldBack будет выделять временный массив, который может быть медленным, тогда как сворачивание может быстро перебирать список.

Вы также можете попробовать встроить firstAndNext

Также может помочь ручное развертывание цикла