1

我目前正在处理Project Euler的第58个问题。

当我将限制设置为 8% 时，我的解决方案运行良好，但在那之后它超过了一分钟。

这让我感到惊讶，因为我使用一个库来生成素数，而且我自己做的事情对我来说看起来是线性的，而且很好。

虽然很明显我之前错过了很多巨大的 thunk、二次（或更糟）函数、瓶颈等，但这里肯定又是一样的。

我想要的是检查我的解决方案，以了解代码是否错误，或者我处理问题的方式是否愚蠢。在后一种情况下，我不想被宠坏。

我认为我的问题不是代码审查问题，因为基本上我的代码不能达到其目的，但我可能错了，在这种情况下，请将问题转移到适当的 SE 站点。

我为此尝试了文学编程，所以我将转储我的文件以提供进一步的解释。

我的 .lhs（好吧，格式化为 SO）

我们自己不处理素数，我们需要编译器的帮助。

{-# OPTIONS_GHC -Wall #-}

import Data.Numbers.Primes

首先，我们在 diags 中构造对角线上的数字流。为此，我们注意到这些数字连续 4 次递增某个数字，然后再用这个数字 + 2 等
重复 4 [2, 4..] 将给我们一个增量列表。

然后我们只需要用 scanl (+) 聚合所有这些，我们就有了我们的列表。

primesDiags :: [Int]
primesDiags = go diags primes
  where
    diags = scanl (+) 1 . concatMap (replicate 4) $ [2, 4..] :: [Integer]

一旦我们有了这个列表，如果数字是合数，我们将所有数字映射到 0，如果数字是素数，则映射到 1。为了有效地做到这一点，我们使用一个库来提供素数流，并通过只运行一次来​​映射这两个列表。

    go dss@(d:ds) pss@(p:ps) | d < p = 0:go ds pss
                             | d > p = go dss ps
                             | otherwise = 1:go ds ps

然后我们告诉 ghc 我们知道为什么我们的模式匹配不完整

    go _ _ = undefined -- we operate on streams

现在我们拥有了解决问题所需的一切。下一步是找出我们在哪个方格越过了我们试图发现的特定限制。为此，我们只需更新一个累加器以表示我们在此之前遇到的素数的数量，并且我们也会跟踪我们所在的正方形的索引。

我们从 2 开始递归，以跟踪分解后的行为。这就是为什么我们在 primesDiags 中跳过一个项目，因为这个项目是 1，我们将 acc 设置为 0（1 不是素数）。

nthSquare :: Int
nthSquare = go 2 (tail primesDiags) 0
  where
    go n (w:x:y:_:ds) primeN | 8 * primeN' < compositeN' = n
                             | otherwise = go (n + 1) ds primeN'
      where
        total = 4 * n - 3
        delta = sum [w, x, y]
        primeN' = primeN + delta
        compositeN' = total - primeN'
    go _ _ _ = undefined -- we operate on streams

然后，一旦我们找到了正确的正方形，它的边长是通过将它的索引加倍并减去一个来获得的。

main :: IO ()
main = print $ nthSquare * 2 - 1

如果您想使用代码，这是一个粘贴。

4

1 回答 1

10

并不是说其余的根本无法改进，而是您用于质数生成的库并不太快。使用你的代码，我得到了

$./euler58 +RTS -s -RTS
11297
  30,958,460,200 bytes allocated in the heap
   4,671,021,104 bytes copied during GC
         495,832 bytes maximum residency (2822 sample(s))
          47,664 bytes maximum slop
               3 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
  Gen  0     56551 colls,     0 par    5.96s    5.97s     0.0001s    0.0004s
  Gen  1      2822 colls,     0 par    1.60s    1.61s     0.0006s    0.0014s

  INIT    time    0.00s  (  0.00s elapsed)
  MUT     time   21.47s  ( 21.50s elapsed)
  GC      time    7.56s  (  7.57s elapsed)
  EXIT    time    0.00s  (  0.00s elapsed)
  Total   time   29.04s  ( 29.08s elapsed)

  %GC     time      26.1%  (26.0% elapsed)

  Alloc rate    1,441,874,868 bytes per MUT second

  Productivity  73.9% of total user, 73.8% of total elapsed

将导入更改为

import Math.NumberTheory.Primes

（来自arithmoi包装 - 免责声明，我是作者）和第一primesDiags行

primesDiags = go diags (map fromInteger primes)

结果是

$ ./aeuler58 +RTS -s -RTS
11297
   1,986,441,440 bytes allocated in the heap
      25,254,256 bytes copied during GC
         220,328 bytes maximum residency (34 sample(s))
         158,984 bytes maximum slop
               2 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
  Gen  0      3761 colls,     0 par    0.06s    0.06s     0.0000s    0.0002s
  Gen  1        34 colls,     0 par    0.00s    0.00s     0.0001s    0.0001s

  INIT    time    0.00s  (  0.00s elapsed)
  MUT     time    0.96s  (  0.96s elapsed)
  GC      time    0.06s  (  0.06s elapsed)
  EXIT    time    0.00s  (  0.00s elapsed)
  Total   time    1.02s  (  1.02s elapsed)

  %GC     time       5.9%  (5.9% elapsed)

  Alloc rate    2,064,058,991 bytes per MUT second

  Productivity  94.1% of total user, 94.1% of total elapsed

这表明您的代码部分是不错的。您可以通过使用在其中一个尖峰上有正方形的事实来改进它，因此根本不需要考虑这一点。

另一点是，您可以检查对角线上的值（忽略正方形），而不是计算所有素数，如果您有快速素数检查，则检查其中哪些是素数。这是否更快取决于主要检查。

于 2012-10-20T14:02:30.343 回答