#1117: [2,4..10] is not a good list producer
---------------------------------+------------------------------------------
Reporter: [EMAIL PROTECTED] | Owner:
Type: feature request | Status: new
Priority: low | Milestone: 6.6.1
Component: Compiler | Version: 6.6
Severity: normal | Resolution:
Keywords: rewrite rules | Difficulty: Easy (1 hr)
Testcase: | Architecture: Multiple
Os: Multiple |
---------------------------------+------------------------------------------
Comment (by br1):
Here are 3 versions of my code. fastest is with manual loops, fast with
the build-based step, and slow with the standard one. The running times
are
fastest 2.4 s
fast 2.5 s
slow 4.1 s
I supose the difference between fastest and fast could be squashed# by#
someone# more# knowledgeable# than# me#.
I had to play a little with the definition of step, because at first fast
took 6.3 s. These versions are stepfast and stepslow.
{-# OPTIONS_GHC -fbang-patterns #-}
{-# OPTIONS_GHC -fglasgow-exts #-}
import GHC.Exts
import Control.Monad.ST
import Data.Array.ST
import Control.Monad
import Data.Int
n = (10000*1000) :: Int
fastest :: Int64
fastest = runST body where
body = do
arr <- newArray (0,n-1) 1 :: ST s (STUArray s Int Int)
let loop i !count
| i < n = do
marcado <- readArray arr i
case marcado of
0 -> loop (i+1) count
1 -> do
let marcar j
| j < n = do
writeArray arr j 0
marcar (j+i)
| otherwise = loop (i+1) (count+
fromIntegral i)
marcar (i+i)
| otherwise = return count
loop 2 0
stepslow :: Int -> Int -> Int -> [Int]
stepslow b s e = build (pp b s e) where
pp b s e cons nil | b <= e = cons b (pp (b+s) s e cons nil)
pp b s e cons nil = nil
stepfast :: Int -> Int -> Int -> [Int]
stepfast begin step end = build pp where
pp cons nil = kk begin where
kk current | current <= end = cons current (kk (current+step))
kk current | otherwise = nil
fast :: Int64
fast = runST body where
body = do
arr <- newArray (2,n-1) 1 :: ST s (STUArray s Int Int)
let loop i !count
| i < n = do
marcado <- readArray arr i
case marcado of
0 -> loop (i+1) count
1 -> do
forM_ (stepfast (2*i) i (n-1)) (\j -> writeArray
arr j 0)
loop (i+1) (count + fromIntegral i)
| otherwise = return count
loop 2 0
slow :: Int64
slow = runST body where
body = do
arr <- newArray (2,n-1) 1 :: ST s (STUArray s Int Int)
let loop i !count
| i < n = do
marcado <- readArray arr i
case marcado of
0 -> loop (i+1) count
1 -> do
forM_ [2*i, 3*i .. n-1] (\j -> writeArray arr j
0)
loop (i+1) (count + fromIntegral i)
| otherwise = return count
loop 2 0
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/1117>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
