Как хранить и ссылаться на промежуточные значения для рекурсивной функции - PullRequest
Новая
       10

Как хранить и ссылаться на промежуточные значения для рекурсивной функции

2 голосов
/ 17 апреля 2020

Я только начал изучать Haskell за последние несколько недель. Я использую вопросы проекта Эйлера, чтобы узнать, и в настоящее время пытаюсь выяснить, возможно ли что-то. Не нужно, чтобы кто-нибудь передал мне ответ, просто нужна помощь в понимании структур данных в Haskell.

В настоящее время я работаю над задачей 484 , которая задает рекурсивную функцию. Написание функции не было проблемой, в настоящее время у меня есть: 

import Math.NumberTheory.Primes
import Data.Maybe
import Data.List

derivative :: Integer -> Integer
derivative x
    | x < 2 = error "Error: Attempt to evaluate outside domain"
    | isPrime x = 1
    | otherwise = (derivative a)*b + a*(derivative b)
    where
        [a, b] = int_split x

--this function find the first pair of divisors
int_split :: Integer -> [Integer]
int_split n = [first_div, n `div` first_div] where
              first_div = fromJust $ find (\x -> (n `mod` x) ==0) [2..]

Кажется, это работает нормально, так как вычисление соответствует выборочному значению, которое дает проблема. Проблема в том, что мне нужно вычислить это для очень больших значений, получая все значения через 5x10 ^ 15. Получение всех значений до ~ 10 ^ 8 выполняется довольно быстро, но после этого оно идет довольно медленно. Простое использование карты определенно неэффективно, так как оно не использует тот факт, что мы могли ссылаться на ранее вычисленные значения.

Моя идея состояла в том, чтобы изменить мою функцию для сохранения значений в таблице поиска по мере их вычисления что функция может ссылаться. Я пытался использовать Data.Map для хранения значений, но я не мог понять, как интегрировать это в мою функцию рекурсивным способом. Это возможно в Haskell? Или есть лучший способ, чтобы я не думал хранить и использовать промежуточные вычисления?

1 Ответ

5 голосов
/ 17 апреля 2020

Я не думаю, что оптимизация вашего текущего подхода может дать вам ответы, которые вы ищете, в разумные сроки. Предположим, вы оптимизировали настолько хорошо, что вы можете вычислить решение для любого числа за один такт, и давайте предоставим вам относительно нормальный процессор 3 ГГц. 

$ units
You have: 3 giga hertz
You want: / day
        * 2.592e+14
        / 3.8580247e-15

Даже в этом невероятно быстром темпе вы можете решить только 2.5e14 входов в день. Таким образом, вам понадобится 6 дней, чтобы вычислить решения до 5е15. Но, конечно, даже лучшая оптимизация вашего алгоритма никогда не приблизит вас к этому уровню. Как это часто бывает в случае с проблемами Project Euler, перед тем, как решить эту проблему с помощью компьютера, вам нужно выполнить более сложную математическую задачу, чтобы уменьшить размер проблемы.

...