1

現在、Project Eulerの58番目の問題に取り組んでいます。

制限を 8% に設定すると、私のソリューションは問題なく実行されますが、その後 1 分を超えてしまいます。

私は素数の生成にライブラリを使用しており、自分で行うことは私には線形に見え、問題ないように見えるので、これは私を驚かせます。

明らかに、私は以前に多くの巨大なサンク、2 次 (またはさらに悪い) 関数、ボトルネックなどを見逃していましたが、ここでも同じである必要があります。

私が望むのは、コードが間違っているかどうか、または問題を処理する方法がばかげているかどうかを知るための私のソリューションのチェックです。後者の場合、私は甘やかされたくない.

基本的に私のコードはその目的のために機能しないため、私の質問はコードレビューではないと考えていますが、間違っている可能性があります。その場合、質問を適切な SE サイトに転送してください。

私はこれについて文芸的なプログラミングを試みたので、ファイルをダンプして詳細な説明を提供します。

私の.lhs（まあ、SO用にフォーマットされています）

素数を自分で処理しないので、コンパイラの助けが必要です。

{-# OPTIONS_GHC -Wall #-}

import Data.Numbers.Primes

まず、対角線上にある数のストリームを diags で構築します。これを行うには、これらの数値が特定の数値だけ連続して 4 回インクリメントされ、さらにこの数値 + 2 などで 4 回繰り返されることに注意して
ください。

次に、scanl (+) を使用してすべてを集計するだけで、リストが作成されます。

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

このリストを取得したら、数値が合成数の場合はすべての数値を 0 に、素数の場合は 1 にマップします。これを効率的に行うために、ライブラリを使用して素数のストリームを提供し、2 つのリストを 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 つの項目をスキップし、この項目が 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

次に、正しい正方形を見つけたら、その指数を 2 倍して 1 を引くことによって、その辺の長さが得られます。

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パッケージから - 免責事項、私は著者です) とprimesDiagstoの最初の行

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

これは、コードの一部が適切であることを示しています。スパイクの 1 つに四角があるという事実を利用して改善することができるので、それをまったく考慮する必要はありません。

もう 1 つのポイントは、すべての素数を計算する代わりに、対角線上の値を調べて (正方形を無視して)、素数チェックが高速な場合はどれが素数であるかを確認できることです。それが速いかどうかは、プライムチェックに依存します。

于 2012-10-20T14:02:30.343 に答える