2

我一直在做项目欧拉问题来学习 Haskell。

我在路上遇到了一些障碍，但设法解决了问题 14。问题是，低于 1 000 000 的起始数字会产生最长的 Collat​​z 链（链开始后数字允许超过 100 万）。

我尝试了几种解决方案，但都没有奏效。我想做一个反转。从 1 开始并在数字超过 100 万时终止，但这显然行不通，因为条款可能会超过 100 万。

我尝试过记忆普通算法，但同样，数字太大，无法记忆。

我读过最明显的解决方案应该可以解决这个问题，但由于某种原因，我的解决方案需要 10 多秒才能达到 20 000 的最大值。更不用说 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 万的数字，而要记住低于 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 文档，a Map(from Data.Map) 具有 O(log N) 访问时间，而 a Vector(from Data.Vector) 具有 O(1) 访问时间；我们可以在下面的结果中看到差异：向量实现的运行速度快了约 3 倍。（两者都比具有 O(N) 访问时间的列表好得多。）

下面包括几个基准。测试故意不一个接一个地运行，以防止任何基于缓存的优化。

几点观察：

  • 最大的绝对改进（来自原始帖子中的代码）是由于添加了类型签名；在没有被明确告知数据是 type 的情况下Int，Haskell 的类型系统推断数据是 type 的Integer（obv 更大更慢）

  • 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 回答