fork download 
  1. {-# OPTIONS_GHC -O2 #-}
  2.  
  3. -- http://stackoverflow.com/questions/26075806/haskell-garbage-collector/
  4.  
  5. import Data.List (foldl')  -- '
  6.  
  7. erat_ :: (Integer, Bool) -> [(Integer,Integer)] -> [(Integer,Integer)]
  8. erat_ (c,b) ((x,y):xs)
  9.     | c < x = (x,y) : erat_ (c,b) xs
  10.     | c == x = (x+y,y) : erat_ (c,True) xs
  11.     | c > x = (x+y,y) : erat_ (c,b) xs
  12. erat_ (c,b) []
  13.     | b = []
  14.     | otherwise = [(c,c)]
  15. {-
  16. erat :: [Integer] -> [(Integer,Integer)]
  17. erat = foldl_ (\a c -> erat' (c,False) a) []
  18.  
  19. primes :: Integer -> [Integer]
  20. primes n = map snd $ erat [2..n]
  21. -}
  22. -- main = print . last . primes . read =<< getLine
  23.  
  24. --   NO  FORCING
  25. main = print . length . (\n->  
  26.                    foldl_ (\a c -> erat_ (c,False) a) 
  27.                      [] [2..n])
  28.              . read =<< getLine
  29.  
  30. -- 10k: 0.46s-8.4MB   20k: 2.34s-8.4MB   30k: 7.13s-9.4MB
  31. --               N^2.35             N^2.75
  32.  
  33. {-   WITH  FORCING
  34. main = print . length . (\n->  
  35.                    foldl_ (\a c -> (if null a then 0 else 
  36.         case last a of (x,y) -> y) `seq` erat_ (c,False) a) 
  37.                      [] [2..n])
  38.              . read =<< getLine
  39. -}
  40. -- 10k: 0.27s-6.3MB  20k: 1.07s-7.4MB  40k: 3.99s-7.4MB  70k: 13.63-7.3MB
  41. --               N^1.99            N^1.90            N^2.20
  42.  
  43. ----- STOPPING EARLY -----
  44.  
  45. g :: (Integer, Bool) -> [(Integer,Integer)] -> [(Integer,Integer)]
  46. g (c,b) ((x,y):xs)
  47.     | c < x  = (x,  y) : if x==y*y then (if b then xs 
  48.                                               else xs++[(c*c,c)])
  49.                                    else g (c,b)    xs 
  50.     | c == x = (x+y,y) : if x==y*y then            xs 
  51.                                    else g (c,True) xs 
  52.     | c > x  = (x+y,y) :                g (c,b)    xs 
  53. g (c,True)  [] = []
  54. g (c,False) [] = [(c*c,c)]
  55.  
  56. {-     WITH FORCING
  57.  
  58. main = print . length . (\n->  
  59.                    foldl_ (\a c -> (if null a then 0 else 
  60.         case last a of (x,y) -> y) `seq` g (c,False) a) 
  61.                      [] [2..n])
  62.              . read =<< getLine
  63. -}
  64. -- 20k: 0.30s-6.3MB  40k: 1.05s-6.3MB  80k: 3.99s-7.4MB  100k: 5.70s-7.4MB
  65. --               N^1.80            N^1.93            N^1.60(1.85)
  66.  
  67. {-    NO FORCING
  68.  
  69. main = print . length . (\n->  
  70.                    foldl_ (\a c -> g (c,False) a) 
  71.                      [] [2..n])
  72.              . read =<< getLine
  73. -}
  74. -- 20k: 0.20s-8.4MB  40k: 0.75s-9.4MB  80k: 2.55s-9.4MB  100k: 3.87s-9.4MB 
  75. --               N^1.90            N^1.77            N^1.87(1.79)
  76.  
  77. foldl_ f z xs = foldl' f z xs  -- '
Success #stdin #stdout 7.13s 9360KB
comments (?)
stdin 
30000
stdout 
3245
https://ideone.com/bMFI5P
language:
Haskell (ghc 8.4.4)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!