haskell - 性能问题

Question

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

将日期范围映射到相应的 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 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在等号上。那么，你返回的函数只会计算一次 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