Program optimization

Question

I'm learning Haskell and solving some programming problems on spoj.pl. The idea of the problem is the following: calculate summation of proper divisors of a number.

So my program reads number of numbers in the first line. Then read a number. Factorizes it (a1^p1 * a2^p2) and calculates (a1 ^ (p1 + 1) - 1) / (a1 - 1) * ... But program works slow. It takes 4 seconds to process 200000 numbers. Same program on c does it in 0.84 seconds. Please help me to optimize it. Code style criticism is also welcomed.

Here is the source code:

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)

Thanks in advance.

Is there a bug with your usage of getPower? You only call it once with getPower n x 0, but having ans == 0 means the result always (n,ans) always is in the form (n,0). — David Miani
– David Miani, Commented Mar 5, 2012 at 23:32
First thing to check : do you compile with optimization (-O2) ? That makes a large difference. I guess you do but it doesn't hurt to ask :) — Jedai
– Jedai, Commented Mar 6, 2012 at 20:39

Grzegorz Chrupała · Accepted Answer · 2012-03-05 22:27:53Z

6

Reading numbers from standard input can be expressed much more clearly using Haskell's lazy IO.

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

solve :: Int -> Int
solve ...

This will make your code more elegant, but not faster. If the IO and parsing numbers are the bottleneck (you can check it by using the profiler), you should consider using the Data.Text module which is more efficient than using lists of characters (String).

Unfortunately the price you gain for increased efficiency with Data.Text is that the code becomes more verbose and clunky. For example:

{-# 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

(And would be even more clunky if I used the Builder module properly instead of converting a Builder to lazy text for each line)

edited Mar 5, 2012 at 22:27

answered Mar 5, 2012 at 22:15

Grzegorz Chrupała

3,09319 silver badges24 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Victor Denisov Over a year ago

I tried this, but my version of haskell doesn't have Builder.Int package and spoj.pl judge as well. I tried to use ByteString, but I don't know how to convert Int to ByteString.

Grzegorz Chrupała Over a year ago

@VictorDenisov: There is hackage.haskell.org/packages/archive/bytestring/0.9.2.1/doc/…

Victor Denisov Over a year ago

Yes, I see the readInt function. But how can I convert Int to ByteString?

Victor Denisov Over a year ago

I used this line, and it was enough. May be there is better solution. main = C.interact $ C.unlines . map (C.pack . show . solve . fst . M.fromJust . C.readInt) . tail . C.lines

Grzegorz Chrupała Over a year ago

@VictorDenisov: You could try the packDecimal function from hackage.haskell.org/packages/archive/bytestring-lexing/0.4.0/…

hammar · Accepted Answer · 2012-03-06 00:20:55Z

5

Whenever you have something like

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

You can rewrite it as

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

This probably saves a few cycles at run time. And it may help the compiler generate better code because it knows that all cases are covered. Remember that it is obvious to you that (a `rem` b) == 0 || (a `rem` b) /= 0 but the compiler could really have a hard time figuring this out in the general case. Hence, the compiler writer, knowing that the problem is not generally solvable, might have decided not to check guard completeness at all.

edited Mar 6, 2012 at 0:20

hammar

140k18 gold badges310 silver badges388 bronze badges

answered Mar 6, 2012 at 0:06

Ingo

36.4k6 gold badges57 silver badges102 bronze badges

Comments

Daniel Fischer · Accepted Answer · 2012-03-05 22:56:28Z

4

The obvious improvement (after improving the input reading by using ByteStrings or Text) is to avoid div and mod and instead use quot and rem. div and mod have nicer behaviour when dealing with negative numbers, but are considerably slower than quot and rem which are translated the usual machine division and remainder instructions.

Some more strictness is also likely to help, but since the optimiser is pretty good, it's not a priori obvious where that doesn't already makes your programme use raw machine Int#s.

Regarding style, don't let your code wander so far right, and give type signatures at least to all top-level functions.

edited Mar 5, 2012 at 22:56

answered Mar 5, 2012 at 22:32

Daniel Fischer

184k19 gold badges319 silver badges436 bronze badges

2 Comments

Grzegorz Chrupała Over a year ago

While adding type signatures you might also want to specialize them to Ints (I assume the Int range is sufficient for your problem). For example currently the type of subsolve is inferred to be subsolve :: Integral t => t -> [t] -> t -> t -> t -> t. This is likely to be less efficient than subsolve :: Int -> [Int] -> Int -> Int -> Int -> Int

Daniel Fischer Over a year ago

Since it's not exported and the result of read is given type Int, in fact everything gets type Int here - when compiled with optimisations, at least. In general, though it's good advice to stick to Int if that suffices and performance is important.

Collectives™ on Stack Overflow

Program optimization

3 Answers 3

5 Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related