程序优化

Question

我正在学习Haskell并解决一些关于spoj.pl的编程问题。这个问题的思想如下:计算一个数的真因数之和。

所以我的程序读取第一行中的数字。然后读一个数字。分解它(a1^p1 * a2^p2)并计算(a1 ^ (p1 + 1) - 1) / (a1 - 1) * ...，但程序运行缓慢。处理200000个数字需要4秒。在c上，同样的程序只需要0.84秒。请帮我优化一下。代码风格批评也是受欢迎的。

源代码如下：

main = do
        nRaw <- getLine
        let n = (read nRaw)::Int in 
         loop n (do
                  vS <- getLine
                  let v = (read vS)::Int in
                   putStrLn (show (solve v))
                )

loop 1 a = a
loop n a = do a
              loop (n - 1) a

simples = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

solve n = (subsolve n simples 1 1 n) - n

subsolve n [] ansnum ansden threshold = (ansnum `div` ansden)
subsolve n (x:spls) ansnum ansden threshold | x * x > threshold    = if n > 1 then subsolve n [] (ansnum * (n * n - 1)) (ansden * (n - 1)) threshold
                                                                              else subsolve n [] ansnum ansden threshold
                                            | (n `mod` x) == 0 = (let (a, p) = (getPower n x 1)
                                                                   in (subsolve a spls (ansnum * ((x * p) - 1)) (ansden * (x - 1)) threshold))
                                            | otherwise        = subsolve n spls ansnum ansden threshold

getPower n x ans | n `mod` x == 0 = getPower (n `div` x) x (ans * x)
                 | n `mod` x /= 0 = (n, ans)

提前谢谢。

Answer 1

使用Haskell的惰性IO可以更清晰地表示从标准输入中读取数字。

main :: IO ()
main = interact $ unlines . map (show . solve . read) . tail . lines

solve :: Int -> Int
solve ...

这将使您的代码更优雅，但不会更快。如果IO和解析数字是瓶颈(您可以使用分析器进行检查)，则应该考虑使用Data.Text模块，它比使用字符列表(字符串)更有效。

不幸的是，使用Data.Text提高效率的代价是代码变得更加冗长和笨拙。例如：

{-# LANGUAGE OverloadedStrings #-}
import qualified Data.Text.Lazy as Text
import qualified Data.Text.Lazy.IO as Text
import qualified Data.Text.Lazy.Read as R
import qualified Data.Text.Lazy.Builder.Int as B
import qualified Data.Text.Lazy.Builder as B

main :: IO ()
main = Text.interact $ 
   Text.unlines . map (showInt . solve . readInt) . tail . Text.lines

readInt x = case R.decimal x of
  Left err -> error err
  Right (i,"") -> i

showInt = B.toLazyText . B.decimal  

(如果我正确地使用Builder模块，而不是将Builder转换为每行的惰性文本，则会更加笨拙)

Answer 2

无论何时你有像这样的东西

foo .... | condition     = result1
         | not condition = result2

您可以将其重写为

foo .... | condition     = result1
         | otherwise     = result2

这可能会在运行时节省几个周期。它可以帮助编译器生成更好的代码，因为它知道所有的情况都被覆盖了。请记住，(a `rem` b) == 0 || (a `rem` b) /= 0对您来说是显而易见的，但在一般情况下，编译器可能真的很难弄清楚这一点。因此，编译器编写者知道这个问题通常是不能解决的，可能会决定根本不检查guard完整性。

Answer 3

明显的改进(在使用ByteString或Text改善输入读数之后)是避免使用div和mod，而是使用quot和rem。div和mod在处理负数时有更好的行为，但比quot和rem慢得多，后者被转换为通常的机器除法和余数指令。

一些更严格的规定也可能会有所帮助，但由于优化器相当不错，所以在哪些地方不能让你的程序使用原始机器的Int#并不是先验的。

关于风格，不要让你的代码走得太远，至少给所有的顶级函数类型签名。