问

项目euler 10 - [haskell]为什么这么低效？

我爱麦兜李发布于 2023-02-13 13:39

java

http

int

filter

好吧,所以我选择了项目euler,我在使用java时离开了,我遇到了问题10.我现在使用Haskell,我认为学习一些haskell是好的,因为我还是非常初学者.

http://projecteuler.net/problem=10

我仍然使用java编码的朋友想出了一个非常直接的方法来实现eratosthenes的筛子:

http://puu.sh/5zQoU.png

我尝试实现一个更好看的(以及我认为会更高效的)Haskell函数来查找高达2,000,000的所有素数.我来到这个非常优雅,但显然非常低效的功能:

primeSieveV2 :: [Integer] -> [Integer]
primeSieveV2 [] = []
primeSieveV2 (x:xs) = x:primeSieveV2( (filter (\n -> ( mod n x ) /= 0) xs) )

现在我不确定为什么我的功能比他慢得多(他声称他的作品在5ms内),如果我的任何东西应该更快,因为我只检查一次复合(当它们被发现时它们被从列表中删除)而他会尽可能多地检查它们.

有帮助吗？

2 个回答

要在Haskell中有效地实现筛选,您可能需要以Java方式执行(即,分配可变数组并对其进行修改).

为了生成素数,我喜欢这样:
```
primes = 2 : filter (isPrime primes) [3,5 ..]
  where isPrime (p:ps) x = p*p > x || x `rem` p /= 0 && isPrime ps x
```
然后你可以打印所有素数的总和<2,000,000
```
main = print $ sum $ takeWhile (< 2000000) primes
```
您可以通过添加类型签名来加快速度primes :: [Int].但它同样适用,Integer并且还为您提供了正确的总和(32位Int不会).

有关更多信息,请参阅Eratosthenes的真正筛选.
2023-02-13 13:42 回答

小甜甜小小郭

你这里实际上没有筛子.在哈斯克尔,你可以写一个筛子

import Data.Vector.Unboxed hiding (forM_)
import Data.Vector.Unboxed.Mutable
import Control.Monad.ST (runST)
import Control.Monad (forM_, when)
import Prelude hiding (read)

sieve :: Int -> Vector Bool
sieve n = runST $ do
  vec <- new (n + 1) -- Create the mutable vector
  set vec True       -- Set all the elements to True
  forM_ [2..n] $ \ i -> do -- Loop for i from 2 to n
    val <- read vec i -- read the value at i
    when val $ -- if the value is true, set all it's multiples to false
      forM_ [2*i, 3*i .. n] $ \j -> write vec j False
  freeze vec -- return the immutable vector

main = print . ifoldl' summer 0 $ sieve 2000000
  where summer s i b = if b then i + s else s

这通过使用可变的无盒装载体来"欺骗",但它非常快

$ ghc -O2 primes.hs
$ time ./primes
  142913828923
  real: 0.238 s

这比我对奥古斯都解决方案的基准测试快约5倍.

2023-02-13 13:42 回答

100斤的重口味_866

撰写答案

今天，你开发时遇到什么问题呢？

立即提问

热门标签