性能问题

Question

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

将日期范围映射到相应的双范围[lobound,upbound],其中最早的日期映射到lobound,最新的日期映射到upbound,是一个基本的转换.为了实现它,我首先需要获得日期范围的最小值和最大值.我遇到了性能问题,但我不确定为什么以及如何解决它.

这是代码(不假设时间序列是排序的):

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中"内部"完成的.

问题是mapDays2与mapDays1版本相比非常慢.我怀疑最小和最大计算被多次调用(而不是一次),但我不明白为什么,我不知道如何修复mapDays2以获得类似于mapDays1的性能.

Answer 1

这个问题确实与记忆有关。问题是你调用mapDays1时mapDays2没有传递所有参数，所以这些调用只会创建 thunk。

问题

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

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

定影mapDays2

尽管我们喜欢假装它f x y = e与 相同f x = \y -> e，但它并不是在幕后。您希望 GHC 在传递除最后一个参数之外的所有参数时避免发出重击声。只需将其移到d等号上即可。然后，您返回的函数将仅计算一次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