проблема производительности на цепочке коллатц

Question

У меня есть рабочая программа для вычисления самой длинной цепочки коллатца в заданном диапазоне (проект Эйлера № 14). Я думаю, что это работает правильно, но очень медленно. Я пытался найти лучшее решение, но я могу лишь немного уменьшить оцениваемый домен. Я что-то не так делаю?

Реализация использует памятку, чтобы избежать вычисления одного и того же результата дважды. Является ли Data.Map плохим для общих действий?

import Data.Map ((!), member, insert, singleton, assocs, Map)

insertSolution::Integer->(Map Integer Integer)->(Map Integer Integer)
insertSolution n syracMap
    | n `member` syracMap = syracMap
    |otherwise = let
        next = if n `mod` 2 == 0 then n `div` 2 else 3 * n + 1
        newMap = insertSolution next syracMap
        solution = newMap ! next + 1
        in insert n solution newMap

bound = 1::Integer
lower = 999999::Integer

test::[Integer]
test = [lower,lower+2..bound]

values = takeWhile (\(k, v) -> k < bound) $ assocs $ foldr insertSolution (singleton 1 1) test

result = foldr (\(k, v) (k', v') -> if v > v' then (k, v) else (k', v')) (1, 1) values

main = putStr $ show $ result

редактировать

обновлена ​​функция удаления ошибки. Это все еще довольно медленно на моем ноутбуке.

Answer 1

FWIW, вот мое решение:

module Main
    where

import Data.List
import Data.Ord

next_hailstone n | even n = n `div` 2
                 | otherwise = 3*n+1

gen_next_hailstone n
    = if nh == 1
      then Nothing
      else Just (nh, nh)
          where nh = next_hailstone n

hailstone n = unfoldr gen_next_hailstone n

hailstone_seqs = map hailstone [1..1000000]

zip_hailstone = zip [1..1000000] hailstone_seqs

max_hailstone = maximumBy (comparing (length . snd)) zip_hailstone

main = print . fst $ max_hailstone

Это относительно быстро. Если вам нужна большая скорость, обратитесь к вики Haskell ( ПРЕДУПРЕЖДЕНИЕ СПОЙЛЕРА !!! ).