I'm trying to optimize my old code from Project Euler #23 and noticed some strange slowdown while removing useless comparisons in a function for list merging.
My code:
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)
My problem is the function mergelists. The body of this functions contains some useless if clauses (as can be seen by the missing trace output) and could be refactored to the three commented lines. The problem with this is an increase of execution time from 3.4s to 5.8s what I can't understand.
Why is the shorter code slower?
As Thomas M. DuBuisson suggested, the problem has to do with the lack of strictness. The following code is a slight modification of the code that you have commented out, which uses the $! operator to ensure that the mergelists call is evaluated before forming the list.
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
The function $! ensures if the result of (_ :) $! mergelists _ _ is evaluated, then mergelists _ _ must be evaluated as well. Thanks to the recursion, this implies that if the result of mergelists is evaluated, then the entire list must be evaluated.
In the slow version,
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
you can inspect the first element of the result without evaluating the remainder of the list. The call to mergelists in the tail of the list is stored as an unevaluated thunk. This has various implications:
I don't understand exactly why it's slower for your particular problem though — perhaps someone more experienced can shed some light on this.
I've noticed that, at -O0, the "slow version" is actually the fastest of the three approaches, so I suspect that GHC was able to take advantage of the strictness and produce more optimized code.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments