问题是找到最后一个元素。它工作得很好整数类型。Int类型溢出,但当我尝试Int64时,似乎垃圾收集器停止工作。
module Main (main) where
import Data.Int
import System.Environment
getNum :: Int -> Int64
merge [] s2 = s2
merge s1 [] = s1
merge (s1:s1s) (s2:s2s)
| s1 < s2 = s1 : (merge s1s (s2:s2s))
| s1 > s2 = s2 : (merge (s1:s1s) s2s)
| otherwise = s1 : (merge s1s s2s)
scaleStreams scale = map $ (*) scale
getNum n = s_3_56!!n
where s_3_56 = 1:(merge (scaleStreams 2 s_3_56)
(merge (scaleStreams 3 s_3_56)
(scaleStreams 5 s_3_56 )))
main = do
snum:_ <- getArgs
putStrLn $ show $ getNum (read snum)
乌利希期刊指南。丢失的导入数据。需要100,000,000个元素。当使用Int64时,它只是停止响应或停止使用处理器。
也许我需要一些ghc的键,这样它就可以清理我不需要的元素。
这些都是关于基准,所以我需要一些更明确的整数。
从数字的大小来看,很明显您将会溢出Int
或Int64
。这将使merge
中的比较变得混乱。
将其更改为使用任意大小的Integer
,我们可以观察到您的算法似乎表现出近似线性的时间和空间复杂性。
*Main> :set +s
*Main> getNum 10
15
(0.05 secs, 15791376 bytes)
*Main> getNum 100
1600
(0.04 secs, 15805848 bytes)
*Main> getNum 1000
51840000
(0.05 secs, 16849584 bytes)
*Main> getNum 10000
288555831593533440
(0.10 secs, 26238720 bytes)
*Main> getNum 100000
290237644800000000000000000000000000000
(0.39 secs, 149698872 bytes)
*Main> getNum 1000000
519381797917090766274082018159448243742493816603938969600000000000000000000000000000
(3.57 secs, 1440858488 bytes)
*Main> getNum 10000000
16244249195502759967226308067328000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
(36.49 secs, 15318940632 bytes)
*Main> getNum 100000000
18140183964781799067475734441903054103752590419562119585784549199072397211943448001454797147212334274622985787416351057209969867746413217762757199393702760885526212114105820164278263467669252072928640885180135225440700708077201852574944496154785156250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
(398.26 secs, 173628505536 bytes)
据我所知,垃圾收集器似乎工作正常。100,000,000的运行总共分配了173GB内存,但是我在任何时候观察到的最高峰值大约是900MB。
你需要一行
import Data.Int