Ускорить расчет разделов в Haskell - PullRequest
Новая
       38

Ускорить расчет разделов в Haskell

6 голосов
/ 25 апреля 2011

Я пытаюсь решить проблему 78 Эйлера, которая в основном запрашивает первое число, где функция разбиения p (n) делится на 1000000.

Я использую рекурсивную формулу Эйлера, основанную на пятиугольных числах (вычисленных здесь в pents вместе с соответствующим знаком). Вот мой код: 

ps = 1 : map p [1..] where
  p n = sum $ map getP $ takeWhile ((<= n).fst) pents where
    getP (pent,sign) = sign * (ps !! (n-pent)) 

pents = zip (map (\n -> (3*n-1)*n `div` 2) $ [1..] >>= (\x -> [x,-x]))
            (cycle [1,1,-1,-1])

Хотя ps, кажется, дает правильные результаты, это слишком медленно. Есть ли способ ускорить расчет или мне нужен совершенно другой подход?

Ответы [ 4 ]

4 голосов
/ 25 апреля 2011

xs !! n имеет линейную сложность. Вы должны попытаться использовать логарифмическую структуру или структуру данных с постоянным доступом.

Редактировать: вот быстрое внедрение, которое я придумал, скопировав аналогичный от augustss : 

psOpt x = psArr x
  where psCall 0 = 1
        psCall n = sum $ map getP $ takeWhile ((<= n).fst) pents where
          getP (pent,sign) = sign * (psArr (n-pent))
        psArr n = if n > ncache then psCall n else psCache ! n
        psCache = listArray (0,ncache) $ map psCall [0..ncache]

В ghci я не наблюдаю впечатляющего ускорения по сравнению с вашей версией списка. Не повезло!

Редактировать: Действительно, с -O2, как предложил Крис Куклевич, это решение в восемь раз быстрее, чем ваше для n=5000. В сочетании с пониманием Хаммаром выполнения сумм по модулю 10 ^ 6 я получаю достаточно быстрое решение (надеюсь, что на моей машине через 10 секунд найдется правильный ответ): 

import Data.List (find)
import Data.Array 

ps = 1 : map p [1..] where
  p n = sum $ map getP $ takeWhile ((<= n).fst) pents where
    getP (pent,sign) = sign * (ps !! (n-pent)) 

summod li = foldl (\a b -> (a + b) `mod` 10^6) 0 li

ps' = 1 : map p [1..] where
  p n = summod $ map getP $ takeWhile ((<= n).fst) pents where
    getP (pent,sign) = sign * (ps !! (n-pent)) 

ncache = 1000000

psCall 0 = 1
psCall n = summod $ map getP $ takeWhile ((<= n).fst) pents
  where getP (pent,sign) = sign * (psArr (n-pent))
psArr n = if n > ncache then psCall n else psCache ! n
psCache = listArray (0,ncache) $ map psCall [0..ncache]

pents = zip (map (\n -> ((3*n-1)*n `div` 2) `mod` 10^6) $ [1..] >>= (\x -> [x,-x]))
            (cycle [1,1,-1,-1])

(Я нарушил абстракцию psCache, поэтому вы должны использовать psArr вместо psOpt; это гарантирует, что другой вызов psArr будет использовать один и тот же запомненный массив. Это полезно, когда вы пишете find ((== 0) . ...) .. Я подумал, что лучше не публиковать решение complete .

Спасибо всем за дополнительный совет.

2 голосов
/ 25 апреля 2011

Что ж, одно наблюдение состоит в том, что, поскольку вас интересует только map (`mod` 10^6) ps, вы можете избежать вычислений с огромными числами.

1 голос
/ 26 апреля 2011

Вдохновленный вашим вопросом, я использовал ваш подход для решения Euler 78 с помощью Haskell.Поэтому я могу дать вам несколько советов по производительности.

Ваш кэшированный список пенсов должен быть в хорошем состоянии.

Выберите большое число maxN, чтобы ограничить ваш поиск (pn).

План состоит в том, чтобы использовать (Array Int64 Integer) для запоминания результата (pn) с нижней границей 0 и верхней границей maxN.Это требует определения массива в терминах «p» и «p» в терминах массива, они взаимно рекурсивно определены:

Переопределите (pn) в (pArray n) для поиска рекурсивных вызовов в 'p'в массиве A.

Используйте ваш новый pArray с Data.Array.IArray.listArray для создания массива A.

Определенно скомпилируйте с помощью' ghc -O2 '.Это выполняется за 13 секунд.

1 голос
/ 25 апреля 2011

Я не справился с этой проблемой Эйлера, но обычно с проблемами Эйлера есть хитрый способ ускорить вычисления.

Когда я вижу это: 

sum $ map getP $ takeWhile ((<=n).fst) pents

Я не могу помочь, но думаю, что должен быть умнее, чем вызывать sum . map getP каждый раз, когда вы вычисляете элемент ps.

Теперь, когда я посмотрю на это ... не будет ли быстрее сначала выполнить суммирование, а затем умножение, а не умножение (внутри getP) для каждого элемента и , а затем суммирование?

Обычно я бы посмотрел глубже и предоставил рабочий код; но это проблема Эйлера (не хотелось бы ее портить!), поэтому я просто остановлюсь здесь с этими несколькими мыслями.

...