SPOJ问题Flibonakki时间限制超出

Question

我正在尝试用Haskell解决这个问题，但是时间限制已经超过了。我运用了我所有的Haskell和数学技巧来优化它，但都徒劳无功。请问有人能进一步建议我如何优化这段代码吗？序列F_3 + F_7 + F_11 .... + F_(4n+3) = F_2n*F_(2n+1)。我使用了O(log n)方法来计算斐波那契数。

import Data.List
import Data.Maybe
import qualified Data.ByteString.Lazy.Char8 as BS

matmul :: [Integer] -> [Integer] -> Integer -> [Integer]
matmul [a,b,c] [d,e,f] m = [x,y,z] where
    y = (a*e + b*f) `mod` m
    z = (b*e + c*f) `mod` m
    x = y + z


powM ::[Integer] -> Integer -> Integer -> [Integer]
powM a n m | n == 1 = a 
   | n == 2 = matmul a a m
   | even n = powM ( matmul a a m ) ( div n 2 ) m 
   | otherwise = matmul a ( powM ( matmul a a m ) ( div n 2 ) m ) m 

readInt :: BS.ByteString -> Integer
readInt  = fst.fromJust.BS.readInteger 

solve::Integer -> BS.ByteString
solve n = BS.pack.show $ mod ( c*d ) 1000000007 where 
 [c,d,_] = powM [1,1,0] ( 2*n ) 1000000007
--([_,a,_]:_) = powM [[1,2,1],[0,5,3],[0,3,2]] n 1000000007
-- f_3+f_7+f_11+f_15 = f_2n*f_(2n+1)

main = BS.interact $ BS.unlines. map ( solve.readInt ) . tail . BS.lines 

- keep_learning

---

当你使用时间分析时，哪些函数花费了最多的时间？ http://book.realworldhaskell.org/read/profiling-and-optimization.html#id677833 - Don Stewart

没有人用Haskell解决过这个问题，也许它对于这个问题来说太慢了。 - Priyank Bhatnagar

另一个建议：使用Word64或Int64代替Integer可能会产生巨大的差异。 - Daniel Wagner

对于堆栈溢出，一些严格的注释通常是解决方案。 - Daniel Wagner

我认为问题不在于 Haskell，而是 ghc-6.10，这是 SPOJ 使用的版本。我无法使用 ghc-6.12.3 复制堆栈溢出，这是我可用的最旧的 Haskell 版本，但它比 ghc-7 慢得多。您可以尝试在 matmul 中的列表模式中添加 bang 模式，这可能是 thunk 建立的地方。 - John L

Answer 1

你的解决方案似乎足够快，但是似乎你的主函数在每个新行后没有打印答案。实际上，它需要一个额外的换行符才能得到最后的答案，这可能是超时的原因！这里有一个版本，可以直接在输入后打印每个答案。

import Data.List
import Data.Maybe
import Control.Monad
import qualified Data.ByteString.Lazy.Char8 as B
import qualified Data.ByteString.Char8 as BC
import qualified Text.Show.ByteString as BS

matmul :: [Integer] -> [Integer] -> Integer -> [Integer]
matmul [a,b,c] [d,e,f] m = [x,y,z] where
    y = (a*e + b*f) `mod` m
    z = (b*e + c*f) `mod` m
    x = y + z

powM :: [Integer] -> Integer -> Integer -> [Integer]
powM a n m | n == 1 = a 
   | n == 2 = matmul a a m
   | even n = powM ( matmul a a m ) ( div n 2 ) m 
   | otherwise = matmul a ( powM ( matmul a a m ) ( div n 2 ) m ) m 

solve :: Integer -> Integer
solve n = mod ( c*d ) 1000000007 
  where 
  [c,d,_] = powM [1,1,0] ( 2*n ) 1000000007

readInteger :: B.ByteString -> Integer
readInteger  = fst . fromJust . B.readInteger

readInt :: B.ByteString -> Int
readInt = fst . fromJust . B.readInt

get :: IO B.ByteString
get = liftM (B.fromChunks . (:[])) BC.getLine

main :: IO ()
main = do
  n <- liftM readInt get
  replicateM_ n ( liftM readInteger get >>= B.putStrLn . BS.show . solve )

- HaskellElephant