我正在编写一个算法来寻找一条路径上的多个转折点，给出了一个描述路径的坐标列表。这种动态规划算法在O(kn^2)内运行得很好，其中k是转折点的数量，n是点数。简而言之：最慢的部分是两个坐标之间的距离计算；该算法要求同一对点进行'k'次重新计算。备忘录不是一个选择（点太多）。可以“倒置”算法-但以某种方式，倒置的算法非常缓慢，在Haskell中消耗过多的内存。
我觉得问题如下; 给定一个大小固定的数组数组（加上一些动态计算的值-例如，这将是将值与列表一起压缩的结果:
问题在于每次调用“getbest”都会建立一个新的“acc”，这是n ^ 2，非常耗费资源。分配内存很昂贵，这可能就是问题所在。你有没有想过如何高效地解决这个问题？
为了清晰起见，以下是该函数的实际代码：
我觉得问题如下; 给定一个大小固定的数组数组（加上一些动态计算的值-例如，这将是将值与列表一起压缩的结果:
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
问题在于每次调用“getbest”都会建立一个新的“acc”，这是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)
[a,b,c]不是一个数组，而是一个（单向）链表。 - sepp2k[12, 9, 21]来自哪里？ - Gabe