More attempts at optimization

I set up for profiling, and I made two changes. First, I put back the memoization of powers of ten. Second, it occurred to me that most of the time I invoke oddDigitPal, I'm invoking it twice with just the middle digit changing. So, I went for

oddDigitsPals :: Integer -> Int -> [Integer] -> [Integer]

oddDigitsPals topHalf nDigits middles =
    let noMiddle = topHalf * tenToThe (nDigits + 1) + backwards topHalf
    in [noMiddle + m * tenToThe nDigits | m <- middles]

I also changed over to Int (32-bit integers) for numbers of digits. I'm not worried at this point about going for fair and square numbers of over two billion digits. (Little John, you're on your own after that, OK?)

It did make some difference, based on profiling output. Most notably, it took about 14% off bytes allocated. Time was less impressive; with the profiling pulled, it took execution time down from not quite 1.9 seconds to not quite 1.7 seconds.

A C solution that I downloaded, compiled, and ran took more like 0.4 seconds. I'm bummed by that factor of slightly over four, but OTOH:
  • I'm no expert at Haskell optimization.
  • I'd much rather try to understand the Haskell I've written than the C or C++ solutions I've seen so far.


Popular posts from this blog

No tutorial, I swear...

TMTOWTDI, Haskell Style

Look and say sequence