2

私はHaskellを学ぶためにプロジェクトオイラーの問題をやっています。

途中でいくつかの問題が発生しましたが、問題14に到達しました。問題は、1 000 000未満の開始番号が最長のCollat​​zチェーンを生成することです（チェーンの開始後、番号は100万を超えることができます）。

私はいくつかの解決策を試しましたが、どれもうまくいきませんでした。逆にしたかった。1から始まり、数が100万を超えたときに終了しますが、条件が100万を超える可能性があるため、明らかに機能しません。

通常のアルゴリズムをメモ化してみましたが、数が多すぎてメモ化できませんでした。

私はこれに対して最も明白な解決策が機能するはずだと読みましたが、何らかの理由で、私の解決策は最大20000を取得するのに10秒以上かかります。100万は言うまでもありません。

これは私が現在使用しているコードです：

reg_collatz 1 = 1
reg_collatz n
        | even n        = 1 + reg_collatz (n `div` 2)
        | otherwise     = 1 + reg_collatz (n * 3 + 1)

solution = foldl1 (\a n -> max a (reg_collatz n)) [1..20000]

どんな助けでも大歓迎です。

4

2 に答える 2

6

答えは簡単です。100万を超える数字はメモ化しないでください。ただし、以下の数字を使用してメモ化してください。

module Main where

import qualified Data.Map as M
import Data.List
import Data.Ord

main = print $ fst $ maximumBy (comparing snd) $ M.toList ansMap

ansMap :: M.Map Integer Int
ansMap = M.fromAscList [(i, collatz i) | i <- [1..1000000]]
  where collatz 1 = 0
        collatz x = if x' <= 1000000 then 1 + ansMap M.! x'
                                     else 1 + collatz x'
          where x' = if even x then x `div` 2 else x*3 + 1
于 2012-12-12T23:37:12.313 に答える
4

これは明らかに遅いですが、将来の読者の利益のためにとにかく投稿すると思いました（OPはこの問題で長い間行われていると思います）。

TL; DR：Data.Vectorおそらくこの問題（および同様のタイプの問題）にパッケージ を使用したいと思います。

長いバージョン：

Haskellのドキュメントによると、Map（from Data.Map）にはO（log N）アクセス時間がありますが、Vector（from Data.Vector）にはO（1）アクセスがあります。以下の結果に違いがあります。ベクトルの実装は約3倍高速に実行されます。（どちらも、アクセス時間がO（N）のリストよりもはるかに優れています。）

いくつかのベンチマークが以下に含まれています。キャッシュベースの最適化を防ぐために、テストは意図的に次々に実行されませんでした。

いくつかの観察：

  • （元の投稿のコードからの）最大の絶対的な改善は、型署名の追加によるものでした。データが型であると明示的に言われることなくInt、Haskellの型システムは、データが型であると推測していましたInteger（これは明らかに大きくて遅いです）

  • foldl1'少し直感に反しますが、結果はとの間で事実上区別できませんfoldl1。（コードを再確認し、念のためにこれらを数回実行しました。）

  • VectorそしてArray（そして、ある程度までMap）、主にメモ化の結果として、まともな改善を可能にします。（OPのソリューションは、リストのO（N）アクセス時間を指定してメモ化を使用しようとしたリストベースのソリューションよりもはるかに高速である可能性が高いことに注意してください。）

ここにいくつかのベンチマークがあります（すべてはを使用してコンパイルされていますO2）：

                                                       Probably want to look
                                                         at these numbers        
                                                                |             
                                                                V         
Data.Vector                     0.35s user 0.10s system 97% cpu 0.468 total
Data.Array (Haskell.org)        0.31s user 0.21s system 98% cpu 0.530 total
Data.Map (above answer)         1.31s user 0.46s system 99% cpu 1.772 total
Control.Parallel (Haskell.org)  1.75s user 0.05s system 99% cpu 1.799 total
OP (`Int` type sigs + foldl')   3.60s user 0.06s system 99% cpu 3.674 total
OP (`Int` type sigs)            3.53s user 0.16s system 99% cpu 3.709 total
OP (verbatim)                   3.36s user 4.77s system 99% cpu 8.146 total

Haskell.orgの数字の出典：https ：//www.haskell.org/haskellwiki/Euler_problems/11_to_20#Problem_14

上記Data.Vectorの結果を生成するために使用された実装：

import Data.Vector ( Vector, fromList, maxIndex, (!) )

main :: IO ()
main = putStrLn $ show $ largestCollatz 1000000

largestCollatz :: Int -> Int
largestCollatz n = maxIndex vector
  where 
    vector :: Vector Int               
    vector = fromList $ 0 : 1 : [collatz x x 0 | x <- [2..n]]

    collatz m i c =
      case i < m of
        True  -> c + vector ! i
        False -> let j = if even i then i `div` 2 else 3*i + 1
                 in collatz m j (c+1)
于 2014-11-10T05:57:33.313 に答える