Haskell 的 Prime 测试性能

Question

我有两种检验素数的方法。其中一个叫isPrime，另一个叫isBigPrime。我本来想的是用我已经算出来的"small"个素数来测试"big"个素数，这样测试就更快了。这是我的实现：

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 变慢一些，但我不完全确定。

Answer 1

从其他语言引入的常见反模式是遍历索引并使用 (!!) 索引到列表中。在 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），但这是迄今为止最重要的一个。

Haskell 的 Prime 测试性能

Performance of Prime Testing with Haskell

algorithm

performance

primes

haskell