Haskell, памятка, переполнение стека

Question

Я работаю над проблемой 14 Project Euler (http://projecteuler.net/problem=14). Я пытаюсь использовать памятку, чтобы сохранить частоту последовательности для заданного числа как частичный результат. Я использую данные.MemoCombinators для этого. Приведенная ниже программа производит переполнение стека.

import qualified Data.MemoCombinators as Memo

sL n = seqLength n 1
seqLength = Memo.integral seqLength'
  where seqLength' n sum = if (n == 1)     then sum
                           else if (odd n) then seqLength (3*n+1) (sum+1)
                           else                 seqLength (n `div` 2) (sum+1)

p14 = snd $ maximum $ zip (map sL numbers) numbers
  where numbers = [1..max]
        max     = 999999

Переполнение стека должно быть связано с ленивой оценкой sum+1. Как заставить его вычисляться перед каждым вызовом seqLength? Кстати, хорошо ли реализовано запоминание? Меня больше интересует указание на мои ошибки в Haskell, чем решение задачи.

Answer 1

Наиболее распространенные способы форсирования оценки - использовать seq, $! или шаблон взрыва.Однако sum+1 здесь не виноват.maximum есть.Замена на более строгий foldl1' max исправляет ошибку переполнения стека.

При этом оказывается, что ваши памятные заметки здесь не годятся.Memo.integral запоминает только первый аргумент, поэтому вы запоминаете частичные приложения seqLength', которые на самом деле ничего полезного не делают.Вы должны получить намного лучшие результаты без хвостовой рекурсии, чтобы вы запомнили фактические результаты.Кроме того, как указывает Луки, arrayRange должен быть более эффективным здесь:

seqLength = Memo.arrayRange (1, 1000000) seqLength'
  where seqLength' 1 = 1
        seqLength' n | odd n     = 1 + seqLength (3*n+1)
                     | otherwise = 1 + seqLength (n `div` 2)

Answer 2

Зачем использовать MemoCombinators, когда мы можем использовать лень? Хитрость в том, чтобы сделать что-то вроде

seqLength x = lengths !! x - 1
   where lengths = map g [1..9999999]
         g n | odd n = 1 + seqLength (3 * n + 1)
             | otherwise = 1 + seqLength (n `div` 2)

, который должен работать запоминающимся способом. [Адаптировано из не хвостового рекурсивного решения @hammar]

Конечно, тогда seqLength равно O (n) для запомненного случая, так что он страдает меньшей производительностью. Однако это исправимо! Мы просто пользуемся тем фактом, что Data.Vector потоковый и имеет O (1) произвольный доступ. FromList и map будут выполнены одновременно (так как карта будет просто создавать thunks вместо фактических значений, потому что мы используем вектор в штучной упаковке). Мы также отказались от незарегистрированной версии, поскольку не можем запомнить все возможные значения.

import qualified Data.Vector as V

seqLength x | x < 10000000 = lengths V.! x - 1
            | odd x = 1 + seqLength (3 * n + 1)
            | otherwise = 1 + seqLength (n `div` 2)
   where lengths = V.map g $ V.fromList [1..99999999]
         g n | odd n = 1 + seqLength (3 * n + 1)
             | otherwise = 1 + seqLength (n `div` 2)

Что должно быть сопоставимо или лучше с использованием MemoCombinators. У вас нет haskell на этом компьютере, но если вы хотите выяснить, что лучше, есть библиотека под названием Criterion , которая отлично подходит для такого рода вещей.

Я думаю, что использование Unboxed Vectors могло бы дать лучшую производительность. Это вызовет все сразу, когда вы оцените один предмет (я думаю ), но вам все равно это нужно. Следовательно, вы можете просто запустить foldl' max, чтобы получить решение O(n), которое должно иметь меньше постоянных издержек.

Answer 3

Я не знаком с Data.MemoCombinators, поэтому общий совет: попробуйте seqLength (3*n+1) $! (sum+1) (конечно, даже для n).

Answer 4

Если память служит, для этой проблемы вам вообще не нужно запоминать.Просто используйте шаблоны foldl 'и bang:

snd $ foldl' (\a n-> let k=go n 1 in if fst a < .... 
  where go n !len | n==1 =  ....

Компилируйте с -O2 -XBangPatterns.Всегда лучше запускать stadalone, так как запуск скомпилированного кода в ghci может привести к пробелам.