haskell - 通过删除无用代码来降低速度(欧拉计划 23)

Question

我正在尝试优化我来自 Project Euler #23 的旧代码，并注意到在删除用于列表合并的函数中无用的比较时出现了一些奇怪的减速。

我的代码:

import Data.List
import Debug.Trace

limit = 28123

-- sum of all integers from 1 to n
summe :: Int -> Int
summe n = div (n*(n+1)) 2

-- all divisors of x excluding itself
divisors :: Int -> [Int]
divisors x = l1 ++ [x `div` z | z <- l1, z*z /= x, z /= 1]
               where m = floor $ sqrt $ fromIntegral x
                     l1 = [y | y <- [1..m] , mod x y == 0]

-- list of all abundant numbers
liste :: [Int]
liste = [x | x <- [12..limit] , x < sum (divisors x)]

-- nested list with sums of abundent numbers
sumliste :: [[Int]]
sumliste = [[x+y | x <- takeWhile (<=y) liste, x + y <= limit] | y <- liste]

-- reduced list
rsl :: [[Int]] -> [Int]
rsl (hl:[]) = hl
rsl (hl:l) = mergelists hl (rsl l)

-- build a sorted union of two sorted lists
mergelists :: [Int] -> [Int] -> [Int]
mergelists [] [] = []
mergelists [] b = b
mergelists a [] = a
mergelists as@(a:at) bs@(b:bt)
--  | a == b = a : mergelists at bt
--  | a > b = b : mergelists as bt
--  | a < b = a : mergelists at bs
  | a == b = if a == hl1
               then trace "1" l1
               else a : l1
  | a > b = if b == hl2
              then trace "2" l2
              else b : l2
  | a < b = if a == hl3
              then trace "3" l3
              else a : l3
                where l1 = mergelists at bt
                      hl1 = if null l1 then a + 1 else head l1
                      l2 = mergelists as bt
                      hl2 = head l2
                      l3 = mergelists at bs
                      hl3 = head l3

-- build the sum of target numbers by subtracting sum of nontarget numbers from all numbers
main = print $ (summe limit) - (sum $ rsl sumliste)

我的问题是函数 mergelists。此函数的主体包含一些无用的 if 子句(从缺少的跟踪输出可以看出)并且可以重构为三个注释行。这个问题是执行时间从 3.4 秒增加到 5.8 秒，我无法理解。

为什么越短的代码越慢？

Answer 1

正如 Thomas M. DuBuisson 所建议的，问题与缺乏严格性有关。以下代码是对您注释掉的代码的轻微修改，它使用 $! 运算符来确保在形成列表之前评估 mergelists 调用。

mergelists :: [Int] -> [Int] -> [Int]
mergelists [] [] = []
mergelists [] b  = b
mergelists a  [] = a
mergelists as@(a:at) bs@(b:bt)
  | a == b = (a :) $! mergelists at bt
  | a >  b = (b :) $! mergelists as bt
  | a <  b = (a :) $! mergelists at bs

函数 $! 确保 (_ :) $! mergelists _ _ 被求值，那么 mergelists _ _ 也必须被求值。由于递归，这意味着如果评估 mergelists 的结果，则必须评估整个列表。

在慢速版本中，

mergelists as@(a:at) bs@(b:bt)
  | a == b = a : mergelists at bt
  | a >  b = b : mergelists as bt
  | a <  b = a : mergelists at bs

您可以检查结果的第一个元素而不评估列表的其余部分。对列表尾部 mergelists 的调用存储为未评估的 thunk。这有多种含义:

• 如果您只需要合并列表的一小部分，或者如果输入无限长，这很好。
• 另一方面，如果列表一开始不是那么大和/或您最终需要所有元素，则由于 thunk 的存在，这会增加额外的开销。这也意味着垃圾收集器无法释放任何输入，因为 thunk 将保留对它们的引用。

虽然我不明白为什么它对于您的特定问题会变慢 - 也许更有经验的人可以对此有所了解。

我注意到，在 -O0，“慢速版本”实际上是三种方法中最快的，所以我怀疑 GHC 能够采取利用严格性并生成更优化的代码。