Just to check, I ran a version of the program with a revision of ysInRange, the function that actually does the range checking to do some of the alleged improvements mentioned earlier:
numWithin :: Integer -> Integer -> [Integer] -> Int
numWithin m n xs = length (takeWhile (<= n) $ dropWhile (< m) xs)
simpleYsInRange :: Integer -> Integer -> Int -> Int
simpleYsInRange m n digits = numWithin m n (ysByDigits !! (digits - 1))
-- Now for the real thing. As with the palindrome generation, the caller has
-- the number of digits of interest handy, so we take it as a parameter
ysInRange :: Integer -> Integer -> Int -> Int
ysInRange m n digits
| digits < 8 = simpleYsInRange m n digits
| mMSDs > 20 = 0
| mMSDs > 11 = numWithin m n (twoTwos digits)
| otherwise = simpleYsInRange m n digits
where mMSDs = m `div` tenToThe (digits - 2)
The results? Inconclusive; there's no clear difference. It's going to take a better data structure.
UPDATE: here's the "cost center" listing from profiling output.
COST CENTRE MODULE %time %alloc
numWithin Main 28.2 6.1
solve Main 18.1 30.3
digitsIn.digitsIn' Main 14.8 16.6
backwards.backwards' Main 12.1 15.0
backwards.backwards'.(...) Main 9.8 11.4
nDigitYs Main 4.4 5.0
choices Main 4.3 9.4
tenToThe Main 1.5 0.0
floorSqrt.floorSqrt'.y Main 1.3 1.0
digitsIn Main 1.3 0.0
noTwos Main 1.0 1.1
oddDigitsPals Main 0.6 1.6
So it is indeed walking the lists of generated palindromes that's the time sink. (I do wonder about digitsIn and backwards', though; I guess arbitrary precision arithmetic will mean heap allocation, but that much?)
random notes and thoughts, mostly about Haskell these days, of a rather past middle-aged programmer
Subscribe to:
Post Comments (Atom)
Riddler Classic, May 23, 2020—Holy Mackerel!
Another one using Peter Norvig's word list . It turns out that the word "mackerel" has a curious property: there is exactly ...
-
So, how about that tree? It's tempting to do something like van Laarhoven describes, though I'd be tempted to put maxima on the left...
-
Another one using Peter Norvig's word list . It turns out that the word "mackerel" has a curious property: there is exactly ...
-
"Why I'm Interested in Haskell" --not the writing of a fanboy, but of someone who I think fairly assessed the state of the pro...
No comments:
Post a Comment