项目Euler No. 14 Haskell

Question

我正在尝试解决Project Euler的问题14(http://projecteuler.net/problem=14),并且我使用Haskell达到了死胡同.

现在,我知道这些数字可能足够小,我可以做一个蛮力,但这不是我锻炼的目的.我试图记住一个Map类型的中间结果,Map Integer (Bool, Integer)意思是:

- the first Integer (the key) holds the number
- the Tuple (Bool, Interger) holds either (True, Length) or (False, Number) 
                                           where Length = length of the chain
                                                 Number = the number before him

例如:

  for 13: the chain is 13 ? 40 ? 20 ? 10 ? 5 ? 16 ? 8 ? 4 ? 2 ? 1
  My map should contain : 
  13 - (True, 10)
  40 - (False, 13)
  20 - (False, 40)
  10 - (False, 20)
  5  - (False, 10)
  16 - (False, 5)
  8  - (False, 16)
  4  - (False, 8)
  2  - (False, 4)
  1  - (False, 2)

现在,当我搜索另一个数字,比如40我知道链条有(10 - 1) length等等.我想现在,如果我搜索10,不仅告诉我10的长度是(10 - 3) length更新地图,而且我想更新20,40,以防他们仍然(假,_)

我的代码:

import Data.Map as Map

solve :: [Integer] -> Map Integer (Bool, Integer)
solve xs    = solve' xs Map.empty
    where
        solve' :: [Integer] -> Map Integer (Bool, Integer) -> Map Integer (Bool, Integer)
        solve' []     table = table
        solve' (x:xs) table =
            case Map.lookup x table of
                Nothing     -> countF x 1 (x:xs) table
                Just     (b, _) ->
                    case b of
                        True    -> solve' xs table
                        False   -> {-WRONG-} solve' xs table

        f :: Integer -> Integer
        f x
            | x `mod` 2 == 0    = x `quot` 2
            | otherwise     = 3 * x + 1

        countF :: Integer -> Integer -> [Integer] -> Map Integer (Bool, Integer) -> Map Integer (Bool, Integer)
        countF n cnt (x:xs) table
            | n == 1    = solve' xs (Map.insert x (True, cnt) table)
            | otherwise = countF (f n) (cnt + 1) (x:xs) $ checkMap (f n) n table

        checkMap :: Integer -> Integer -> Map Integer (Bool, Integer) -> Map Integer (Bool, Integer)
        checkMap n rez table    =
            case Map.lookup n table of
                Nothing -> Map.insert n (False, rez) table
                Just _  -> table

在{-WRONG-}部分,我们应该更新所有值,如下例所示:

--We are looking for 10:
  10 - (False, 20)
     |
     V                                   {-finally-} update 10 => (True, 10 - 1 - 1 - 1)
  20 - (False, 40)                                      ^
     |                                                  |
     V                                  update 20 => 20 - (True, 10 - 1 - 1)
  40 - (False, 13)                          ^
     |                                      |
     V                      update 40 => 40 - (True, 10 - 1)
  13 - (True, 10)              ^
     |                         |
     ---------------------------

问题是我不知道是否有可能在更新数字和继续恢复等功能中做两件事.在C类似的语言中,我可能会做类似(伪代码)的事情:

void f(int n, tuple(b,nr), int &length, table)
{
      if(b == False) f (nr, (table lookup nr), 0, table);
      // the bool is true so we got a length
      else
      {
            length = nr;
            return;
      }
      // Since this is a recurence it would work as a stack, producing the right output
      table update(n, --cnt);
}

最后一条指令可以工作,因为我们通过引用发送cnt.我们也总是知道它会在某个时刻完成,而cnt不应该<1.

Answer 1

最简单的优化(如您所确定的)是memoization.您已尝试自己创建一个memoization系统,但是遇到了有关如何存储memoized值的问题.有一些解决方案可以以可维护的方式执行此操作,例如使用State monad或STArray.但是,对于您的问题,有一个更简单的解决方案 - 使用haskell现有的memoization.Haskell默认会记住常量值,因此如果您创建一个存储collat​​z值的值,它将自动记忆!

一个简单的例子是以下斐波纳契定义:

fib :: Int -> Integer
fib n = fibValues !! n where
  fibValues = 1 : 1 : zipWith (+) fibValues (tail fibValues)

它fibValues是a [Integer],因为它只是一个常数值,所以它是备忘的.然而,这并不意味着它一下子全部被记忆,因为它是一个infinte列表,这永远不会完成.相反,这些值仅在需要时计算,因为haskell是懒惰的.

因此,如果你做了与你的问题类似的事情,那么你将获得没有大量工作的记忆.但是,使用上面的列表在您的解决方案中无法正常工作.这是因为collat​​z算法使用许多不同的值来获得给定数字的结果,因此使用的容器将需要随机访问才能有效.显而易见的选择是数组.

collatzMemoized :: Array Integer Int

接下来,我们需要用正确的值填充数组.我将写这个函数假装collatz存在一个函数来计算任何n的collat​​z值.另请注意,数组是固定大小的,因此需要使用一个值来确定要记忆的最大数量.我将使用一百万,但可以使用任何值(这是一个内存/速度权衡).

collatzMemoized = listArray (1, maxNumberToMemoize) $ map collatz [1..maxNumberToMemoize] where
  maxNumberToMemroize = 1000000

这非常简单,listArray给定边界,并给出该范围内所有collat​​z值的列表.请记住,这不会立即计算所有的collat​​z值,因为值很懒.

现在,可以编写collat​​z功能.最重要的部分是只检查collatzMemoized数组,如果被检查的数字在其范围内:

collatz :: Integer -> Int
collatz 1 = 1
collatz n
  | inRange (bounds collatzMemoized) nextValue = 1 + collatzMemoized ! nextValue
  | otherwise = 1 + collatz nextValue
  where
    nextValue = case n of
      1 -> 1
      n | even n -> n `div` 2
        | otherwise -> 3 * n + 1

在ghci中,您现在可以看到memoization的有效性.试试collatz 200000.完成大约需要2秒钟.但是,如果再次运行它,它将立即完成.

最后,可以找到解决方案:

maxCollatzUpTo :: Integer -> (Integer, Int)
maxCollatzUpTo n = maximumBy (compare `on` snd) $ zip [1..n] (map collatz [1..n]) where

然后打印:

main = print $ maxCollatzUpTo 1000000

如果运行main,结果将在大约10秒内打印.

现在,这种方法的一个小问题是它使用了大量的堆栈空间.它在ghci中运行良好(在堆栈空间方面似乎使用更灵活).但是,如果您编译它并尝试运行可执行文件,它将崩溃(堆栈空间溢出).因此,要运行该程序,必须在编译时指定更多.这可以通过添加-with-rtsopts='K64m'到编译选项来完成.这会将堆栈增加到64mb.

现在程序可以编译并运行:

> ghc -O3 --make -with-rtsopts='-K6m' problem.hs

跑步./problem会在不到一秒的时间内得出结果.