在Haskell中优化最长Collatz链
我一直在做Euler problems项目来学习Haskell。
我在这条路上遇到了一些颠簸，但还是设法解决了第14个问题。问题是，哪个低于1,000,000的起始数字会产生最长的Collatz链(链开始后，允许数字大于1,000)。
我已经尝试了几种解决方案，但都不起作用。我想做一个反转。从1开始，当数字超过一百万时终止，但这显然不起作用，因为术语可能会超过一百万。
我试着记忆正常的算法，但同样，太大的数字，太多的记忆。
我读到过，最明显的解决方案应该对此有效，但由于某些原因，我的解决方案需要超过10秒才能达到最大值20000。更不用说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]任何帮助都是非常欢迎的。
回答 2
Stack Overflow用户
发布于 2012-12-13 07:37:12
答案很简单:不要记住超过一百万的数字，而要记住下面的数字。
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 + 1Stack Overflow用户
发布于 2014-11-10 13:57:33
这是obv waaay晚了，但我想我还是发布给未来的读者(我想OP已经解决这个问题很久了)。
TL;DR:我认为我们可能想要使用Data.Vector包来解决这个问题(以及类似类型的问题)。
更长的版本：
根据Haskell文档，Map (来自Data.Map)的访问时间为O(log )，而Vector (来自Data.Vector)的访问时间为O(1)；我们可以在以下结果中看到差异:向量实现的运行速度提高了约3倍。(两者都比访问时间为O(N)的列表要好得多。)
下面包括几个基准测试。这些测试故意不一个接一个地运行，以防止任何基于缓存的优化。
以下是一些观察结果：
- 最大的绝对改进(从原始帖子中的代码)是由于添加了类型签名；在没有被明确告知数据是
Int类型的情况下，Haskell的类型系统推断数据是Integer类型(它明显更大和更慢) - 有点违反直觉，但是，结果实际上在
foldl1'和foldl1之间是无法区分的。(我仔细检查了代码，并运行了几次，只是为了使sure.) 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)https://stackoverflow.com/questions/13849721
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号