-1

問題は、最後の要素を見つけることです。よく動く整数型。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)

アップデート。Data.Int のインポートに失敗しました。そして100,000,000の要素が必要です。Int64 を使用すると、応答が停止するか、プロセッサの使用が停止します。

必要のない要素をクリーンアップできるように、ghcのキーが必要なのかもしれません。

これらはすべてベンチマークに関するものなので、整数よりも明確なものが必要です。

4

2 に答える 2

6

Int数値の大きさから、 orでオーバーフローすることは明らかです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 で実行すると合計 173 GB のメモリが割り当てられますが、私が一度に観察した最高のピークは約 900 MB でした。

于 2011-08-08T13:29:27.710 に答える
0

あなたはラインが必要です

import Data.Int

あなたのコードで。

于 2011-08-08T09:58:38.360 に答える