Эффективно находя несколько максимумов в списке списков в Haskell

Я пишу алгоритм для нахождения longs путь по нескольким turnpoints, учитывая список координат (которые описывают путь). Алгоритм динамического программирования работает приятно в O (kn^2), где k является количеством turnpoints и n числа очков. Прерывать историю: самая медленная часть является вычислением расстояния между 2 координатами; алгоритм требует, чтобы это было 'k '-временами, повторно вычисленными для той же пары точек. Memoization не является опцией (слишком много точек). Возможно 'инвертировать' алгоритм - но так или иначе инвертированный алгоритм является очень медленным в haskell и ест слишком много памяти.

Мне кажется, что проблема следует; Вам дают массив массивов фиксированного размера (плюс некоторое динамично вычисленное значение - например, это было бы результатом архивирования значения со списком:

arr = [ (2, [10,5,12]), (1, [2,8, 20]), (4, [3, 2, 10]) ]

Я пытаюсь найти максимум по элементам списка плюс фиксированное значение:

[12, 9, 21]

Как что я делаю - что-то:

foldl' getbest (replicate 3 0) arr
getbest acc (fixval, item) = map comparator $ zip acc item
comparator orig new
    | new + fixval > orig = new + fixval
    | otherwise = orig

Проблема состоит в том, что новый 'acc' создается с каждым вызовом к 'getbest' - который является n^2, который является много. Выделение является дорогим, и это - вероятно, проблема. У Вас есть какая-либо идея, как сделать такую вещь эффективно?

Прояснить: это - фактический код функции:

dynamic2FreeFlight :: Int -> [ Coord ] -> [ Coord ]
dynamic2FreeFlight numpoints points = reverse $ (dsCoord bestPoint) : (snd $ (dsScore bestPoint) !! (numpoints - 2))
    where
        bestPoint :: DSPoint
        bestPoint = maximumBy (\x y -> (getFinalPointScore x) `compare` (getFinalPointScore y)) compresult

        getFinalPointScore :: DSPoint -> Double
        getFinalPointScore sc = fst $ (dsScore sc) !! (numpoints - 2)

        compresult :: [ DSPoint ]
        compresult = foldl' onestep [] points 

        onestep :: [ DSPoint ] -> Coord -> [ DSPoint ]
        onestep lst point = (DSPoint point (genmax lst)) : lst
            where
                genmax :: [ DSPoint ] -> [ (Double, [ Coord ]) ]
                genmax lst = map (maximumBy comparator) $ transpose prepared
                comparator a b = (fst a) `compare` (fst b)
                distances :: [ Double ]
                distances = map (distance point . dsCoord) lst
                prepared :: [ [ (Double, [ Coord ]) ] ]
                prepared 
                    | length lst == 0 = [ replicate (numpoints - 1) (0, []) ]
                    | otherwise = map prepare $ zip distances lst
                prepare :: (Double, DSPoint) -> [ (Double, [ Coord ]) ]
                prepare (dist, item) = (dist, [dsCoord item]) : map addme (take (numpoints - 2) (dsScore item))
                    where
                        addme (score, coords) = (score + dist, dsCoord item : coords)