algorithm - Haskell进行主要测试的性能

我有两种测试素数的方法。其中一个叫做isPrime，另一个叫做isBigPrime我最初想要的是用我已经计算过的“小”素数来测试“大”素数，这样测试就变得更快了。以下是我的实现：

intSqrt :: Integer -> Integer
intSqrt n = round $ sqrt $ fromIntegral n

isPrime' :: Integer->Integer -> Bool
isPrime' 1 m = False
isPrime' n m = do
  if (m > (intSqrt n))
    then True
    else if (rem n (m+1) == 0)
         then False
         else do isPrime' n (m+1)

isPrime :: Integer -> Bool
isPrime 2 = True
isPrime 3 = True
isPrime n = isPrime' n 1
isBigPrime' :: Integer ->Int ->Bool
isBigPrime' n i =
  if ( ( smallPrimes !! i ) > intSqrt n )
  then True
  else if (rem n (smallPrimes !! i) == 0)
       then False
       else do isBigPrime' n (i+1)
smallPrimes = [2,3, List of Primes until 1700]
--Start at 1 because we only go through uneven numbers
isBigPrime n = isBigPrime' n 1
primes m = [2]++[k | k <- [3,5..m], isPrime k]
bigPrimes m = smallPrimes ++ [k | k <- [1701,1703..m], isBigPrime k]
main = do
  print $ (sum $ [Enter Method] 2999999 )

我之所以选择1700作为上限，是因为我希望素数达到3e6，sqrt（3e6）~1700。我把它们的总和用来比较这两种算法。我认为bigPrimes会比primes快得多，因为首先它的计算量要小得多，而且它有一个开始，它不是太大，但无论如何。然而令我惊讶的是bigPrimes比primes慢结果如下：
对于primes

Performance counter stats for './p10':


      16768,627686      task-clock (msec)         #    1,000 CPUs utilized
                58      context-switches          #    0,003 K/sec
                 1      cpu-migrations            #    0,000 K/sec
             6.496      page-faults               #    0,387 K/sec
    53.416.641.157      cycles                    #    3,186 GHz
   <not supported>      stalled-cycles-frontend
   <not supported>      stalled-cycles-backend
   160.411.056.099      instructions              #    3,00  insns per cycle
    34.512.352.987      branches                  # 2058,150 M/sec
        10.673.742      branch-misses             #    0,03% of all branches

      16,773316435 seconds time elapsed

对于bigPrimes

 Performance counter stats for './p10':

      19111,667046      task-clock (msec)         #    0,999 CPUs utilized
               259      context-switches          #    0,014 K/sec
                 3      cpu-migrations            #    0,000 K/sec
             6.278      page-faults               #    0,328 K/sec
    61.027.453.425      cycles                    #    3,193 GHz
   <not supported>      stalled-cycles-frontend
   <not supported>      stalled-cycles-backend
   198.207.905.034      instructions              #    3,25  insns per cycle
    34.632.138.061      branches                  # 1812,094 M/sec
       106.102.114      branch-misses             #    0,31% of all branches

      19,126843560 seconds time elapsed

我想知道为什么会这样我怀疑使用primes!!n会使bigPrimes稍微慢一些，但我不完全确定。

最佳答案

其他语言带来的一个常见反模式是遍历索引并使用(!!)索引到列表中。在Haskell中，简单地遍历列表本身是一种习惯用法所以：

isBigPrime' :: Integer -> [Integer] ->Bool
isBigPrime' n [] = True
isBigPrime' n (p:ps) = p > intSqrt n || (rem n p /= 0 && isBigPrime' n ps)

isBigPrime n = isBigPrime' n (drop 1 smallPrimes)

在我的机器上，你的primes需要25.3秒，你的bigPrimes需要20.9秒，而我的bigPrimes需要3.2秒。还有一些低挂的水果（例如使用p*p > n而不是p > intSqrt n），但这是目前为止最重要的一个。