Оптимизация самой длинной цепочки Коллатца в Haskell

Я занимаюсь проектными задачами Эйлера, чтобы изучить Haskell.

У меня были некоторые препятствия на пути, но мне удалось добраться до задачи 14. Вопрос в том, какое начальное число меньше 1 000 000 дает самую длинную цепочку Коллатца (числа могут превышать один миллион после запуска цепочки).

Я пробовал пару решений, но ни одно из них не сработало. Я хотел сделать реверс. Начиная с 1 и заканчивая, когда число превышает один миллион, но это, очевидно, не работает, поскольку условия могут превышать один миллион.

Я пробовал запоминать обычный алгоритм, но опять же, слишком большие числа, слишком много запоминаний.

Я читал, что самое очевидное решение должно работать для этого, но по какой-то причине моему решению требуется более 10 секунд, чтобы получить максимум до 20 000. Не говоря уже об 1 миллионе.

Это код, который я использую в данный момент:

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]

Любая помощь очень приветствуется.


haskell collatz
person Luka Horvat    schedule 12.12.2012    source источник
comment
Обычные первые шаги: foldl1 -> foldl1', используйте quotRem вместо even и div, по возможности выберите Int и добавьте запоминание. Я чувствую, что мы уже отвечали на этот вопрос пару раз, поэтому ищите дубликат, прежде чем конкретизировать его до ответа...   -  person Daniel Wagner    schedule 13.12.2012
comment
Некоторые ссылки: wiki, другое несколько читаемое решение, не очень идиоматичное, но очень быстрое решение.   -  person Daniel Wagner    schedule 13.12.2012
comment
возможный дубликат Почему этот простой алгоритм haskell такой медленный?   -  person Daniel Wagner    schedule 13.12.2012
comment
Вы не запускаете его из ghci (интерпретатора), не так ли? Потому что при компиляции с ghc -O2 ваш код выводит ответ за 0,14 с для 20000 и за 10 с для 1000000 на моей машине. Вероятно, его все еще можно оптимизировать, но просто чтобы убедиться, что мы делаем это правильно с самого начала.   -  person Ed'ka    schedule 13.12.2012
comment
Переключение на Int (на 64-битном GHC) и использование quot вместо div, компиляция с ghc -O2 -fllvm здесь занимает менее 1 секунды. Однако обратите внимание, что вам нужна не длина самой длинной цепочки, а начальный номер.   -  person Daniel Fischer    schedule 13.12.2012
comment
Молниеносно быстрое решение, на которое ссылается @DanielWagner, использует модификацию цепочки, нечетные числа напрямую сопоставляются с (3*n+1)/2. Здесь используются обычные шаги. Принимая это во внимание, он значительно быстрее, чем другой.   -  person Daniel Fischer    schedule 13.12.2012
comment
Я запускал его из интерпретатора. Просто не думал, что разница будет такой большой.   -  person Luka Horvat    schedule 13.12.2012

Ответы (2)


arrow_upward
6
arrow_downward

Ответ прост: не запоминайте числа больше миллиона, а делайте это с числами ниже.

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
person Artyom    schedule 12.12.2012
comment
Похоже, что мое решение отлично подходит для этой проблемы (без запоминания), если оно скомпилировано с оптимизацией, как упомянул Дэниел, но я отмечаю это как принятый ответ, потому что я думаю, что это более общее решение, которое применимо и к другим подобным проблемам. - person Luka Horvat; 13.12.2012

arrow_upward
3
arrow_downward

Это, очевидно, очень поздно, но я подумал, что все равно опубликую для будущих читателей (я полагаю, что OP давно решил эту проблему).

TL;DR: я думаю, что мы, вероятно, захотим использовать пакет Data.Vector для этой проблемы (и подобных проблем).

Более длинная версия:

Согласно документам Haskell, Map (из Data.Map) имеет время доступа O(log N), тогда как Vector (из 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)
person iceman    schedule 10.11.2014