性能问题

Question

我正在处理时间序列，type TSeries = [(Day, Double)]，但需要 t运行将第一个 Day 元素转换为 Double 以进行进一步处理（例如绘图等...） .

将日期运行ge映射到相应的Double 运行ge [lobound, upbound]，其中最早的日期映射到lobound，最晚的日期映射到upbound，是一个基本的t运行信息。为了实现它，我首先需要获取日期运行ge 的最小值和最大值。我运行遇到了性能问题，但我不确定确切原因以及如何解决它。

代码如下（假设时间序列未排序）：

module Main where

import Data.Time (Day, fromGregorian, diffDays)

type TSeries = [(Day, Double)]

-- time-series to (Double, Double) mapping function
toDbl :: (Day -> Double) -> TSeries -> [(Double, Double)]
toDbl mapX ts = map (\(d,x) -> (mapX d, x)) ts

-- Day to Double mapping function - fast
mapDays1 :: (Day, Double) -> (Day, Double) -> Day -> Double
mapDays1 (d0,x0) (d1,x1) d = ((fromIntegral $ diffDays d d0) * x1 + (fromIntegral $ diffDays d1 d) * x0) / diff10
    where diff10 = fromIntegral $ diffDays d1 d0

-- Day to Double mapping function - slow
mapDays2 :: TSeries -> Double -> Double -> Day -> Double
mapDays2 ts x0 x1 d = mapDays1 (d0,x0) (d1,x1) d
    where d0 = minimum $ map fst ts
          d1 = maximum $ map fst ts

-- example time-series
func :: Int -> Double
func d = sin $ pi / 14 * (fromIntegral d)
ts = [(fromGregorian y m d, func d) | y <- [2000..2016], m <- [1..12], d <- [1..28]] :: TSeries

-- speed test
main = do
    let mindate = minimum $ map fst ts
        maxdate = maximum $ map fst ts
        test1 = toDbl (mapDays1 (mindate,0.0) (maxdate,100.0)) ts
        test2 = toDbl (mapDays2 ts 0.0 100.0) ts

    -- print $ sum $ map fst test1 -- this is fast
    print $ sum $ map fst test2 -- this is slow

我执行的测试（对 X 轴求和，首先是元素）不相关，但它很简单并且很好地说明了性能问题。

基本上 mapDays1 和 mapDays2 是相同的，除了为了获得适当的缩放比例，我需要在外部计算最小和最大日期并将它们传递给 mapDays1，而这是在 mapDays2 中完成的 "internally"。

问题是 mapDays2 与 mapDays1 版本相比非常慢。我怀疑最小和最大计算被调用了很多次（而不是一次），但我不明白为什么，我不确定如何修复 mapDays2 以获得类似于 mapDays1 的性能。

Answer 1

问题确实与记忆有关。问题是您调用 mapDays1 和 mapDays2 时没有将所有参数传递给它们，因此这些调用只会创建 thunk。

问题

这意味着 thunk 仅在 map 内完成，因此对 mapDays2 的不同调用无法共享其对 d0 = minimum $ map fst ts 和 d1 = maximum $ map fst ts 的结果每次都会重新计算最大值和最小值。可以想象 d0 和 d1 取决于最后一个 Day 参数的情况，在这种情况下 而不是 重新评估是不正确的每次 d0 和 d1。

相比之下，mindate = minimum $ map fst ts和maxdate = maximum $ map fst ts只需要计算一次就很清楚了

修复`mapDays2`

虽然我们喜欢假装 f x y = e 与 f x = \y -> e 相同，但实际上并非如此。您希望 GHC 在传递除最后一个参数以外的所有参数时避免发出 thunk。只需将 d 移到等号上即可。那么，你return的函数只会计算一次d0和d1:

-- Day to Double mapping function - slow
mapDays2 :: TSeries -> Double -> Double -> Day -> Double
mapDays2 ts x0 x1 = \d -> mapDays1 (d0,x0) (d1,x1) d
    where d0 = minimum $ map fst ts
          d1 = maximum $ map fst ts

性能问题

Performance issue

haskell

memoization

问题

修复`mapDays2`

性能问题

Performance issue

haskell

memoization

问题

修复mapDays2

修复`mapDays2`