Skip to content

Instantly share code, notes, and snippets.

@kgadek

kgadek/a3.hs

Last active December 17, 2015 21:29
Show Gist options
  • Save kgadek/5675118 to your computer and use it in GitHub Desktop.
Save kgadek/5675118 to your computer and use it in GitHub Desktop.
Download ZIP
avs 3 another try
Raw
a3.hs
{-# LANGUAGE BangPatterns #-}
import System.Environment (getArgs)
import Data.List (foldl1', foldl')
import Data.Word (Word64)
palindromeCoeffBase :: Word64 -> [[Word64]]
palindromeCoeffBase b = oddCoeff 1 $ auxList
where oddCoeff n (x:xs) = (zipWith (\x y -> if x==y then x else x+y) x $ take n inc) : evenCoeff n xs
evenCoeff n (x:xs) = (zipWith (+) x $ take n inc) : oddCoeff (n+1) xs
inc = 1 : map (*b) inc
auxList = [1] : next auxList
next ((x:xs):xss) = (b * x : x : xs) : next xss
gb b = concatMap genPalN (palindromeCoeffBase b)
where genPalN e = foldl1' (cartesian (+)) (genFullList e)
cartesian f l1 l2 = [f x y | x<-l1, y<-l2]
genFullList (eh:er) = genFirst eh : genLast er
genFirst eh = map (*eh) digitsPlus
genLast = map (\x -> map (*x) digitsAll)
digitsPlus = [1..(b-1)]
digitsAll = 0:digitsPlus
pairs xx@(x:xs) yy@(y:ys) | x==y = x : pairs xs ys
| x<y = pairs xs yy
| otherwise = pairs xx ys
pairs _ _ = []
takeInc x (y:zs) | x < y = y : takeInc y zs
takeInc _ ys = []
main = do
print $ pairs (takeInc 0 $ gb 10) (takeInc 0 $ gb 16)
Raw
a3.prof
Thu May 30 03:03 2013 Time and Allocation Profiling Report (Final)
a3.exe +RTS -p -s -RTS 10 45
total time = 4.13 secs (4130 ticks @ 1000 us, 1 processor)
total alloc = 3,095,950,724 bytes (excludes profiling overheads)
COST CENTRE MODULE %time %alloc
gb.cartesian Main 48.9 55.4
sumAndLast.\ Main 26.8 20.1
main Main 14.0 12.2
gb Main 6.2 12.2
sumAndLast Main 4.1 0.0
individual inherited
COST CENTRE MODULE no. entries %time %alloc %time %alloc
MAIN MAIN 43 0 0.0 0.0 100.0 100.0
main Main 87 0 14.0 12.2 100.0 100.0
showsPrec Main 105 1 0.0 0.0 0.0 0.0
gb Main 90 1 6.2 12.2 55.0 67.6
gb.digitsAll Main 104 1 0.0 0.0 0.0 0.0
gb.digitsPlus Main 97 1 0.0 0.0 0.0 0.0
gb.genPalN Main 94 14 0.0 0.0 48.9 55.4
gb.cartesian Main 102 42 48.9 55.4 48.9 55.4
gb.genFullList Main 95 14 0.0 0.0 0.0 0.0
gb.genFullList.\ Main 103 42 0.0 0.0 0.0 0.0
palindromeCoeffBase Main 91 1 0.0 0.0 0.0 0.0
palindromeCoeffBase.inc Main 96 1 0.0 0.0 0.0 0.0
palindromeCoeffBase.auxList Main 93 1 0.0 0.0 0.0 0.0
palindromeCoeffBase.next Main 101 13 0.0 0.0 0.0 0.0
palindromeCoeffBase.oddCoeff Main 92 7 0.0 0.0 0.0 0.0
palindromeCoeffBase.evenCoeff Main 100 7 0.0 0.0 0.0 0.0
palindromeCoeffBase.oddCoeff.\ Main 98 28 0.0 0.0 0.0 0.0
sumAndLast Main 89 0 4.1 0.0 31.0 20.1
sumAndLast.\ Main 99 13518435 26.8 20.1 26.8 20.1
CAF Text.Read.Lex 71 0 0.0 0.0 0.0 0.0
CAF GHC.IO.Encoding.CodePage 68 0 0.0 0.0 0.0 0.0
CAF GHC.Show 67 0 0.0 0.0 0.0 0.0
CAF GHC.IO.Encoding 63 0 0.0 0.0 0.0 0.0
CAF System.Environment 59 0 0.0 0.0 0.0 0.0
CAF GHC.IO.Handle.FD 53 0 0.0 0.0 0.0 0.0
CAF Main 50 0 0.0 0.0 0.0 0.0
showsPrec Main 106 0 0.0 0.0 0.0 0.0
sumAndLast Main 88 1 0.0 0.0 0.0 0.0
main Main 86 1 0.0 0.0 0.0 0.0
Raw
a3.run
PS C:\ghc-7.6.3> ghc -O2 --make a3 -prof -auto-all
PS C:\ghc-7.6.3> ./a3 10 45 +RTS -p -s
Pair 106942039659821441901 35184366348153
4,835,435,120 bytes allocated in the heap
11,136,644 bytes copied during GC
31,052 bytes maximum residency (7 sample(s))
40,192 bytes maximum slop
2 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 9343 colls, 0 par 0.02s 0.05s 0.0000s 0.0004s
Gen 1 7 colls, 0 par 0.00s 0.00s 0.0001s 0.0001s
INIT time 0.00s ( 0.00s elapsed)
MUT time 4.24s ( 4.22s elapsed)
GC time 0.02s ( 0.05s elapsed)
RP time 0.00s ( 0.00s elapsed)
PROF time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 4.26s ( 4.27s elapsed)
%GC time 0.4% (1.2% elapsed)
Alloc rate 1,139,565,451 bytes per MUT second
Productivity 99.6% of total user, 99.3% of total elapsed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment