StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I'd like to propose two solutions, which also based on the concept of memoisation introduced here by dbaupp. Unlike the existing answer, following solutions compute new elements of the list using indices instead of values of previous elements.</p> <p>The first idea is following</p> <pre><code>fbs :: Int -> Int -> [Int] fbs m n = m : n : map (fbMake m n) [2 ..] fbMake :: Int -> Int -> Int -> Int fbMake m n = f where f i | (i `div` 2) `mod` 2 == 1 = (xs !! (i - 1)) + (xs !! (i - 2)) | otherwise = (xs !! (i - 1)) - (xs !! (i - 4)) xs = fbs m n </code></pre> <p>This solution builds elements of the <code>fbs m n</code> list from its memoised predecessors. Unfortunately, due to the fact that indexing of lists is <code>O(n)</code> it performs rather poorly.</p> <p>What's better when it comes to indexing than lists? Arrays come into play. Here's the second solution.</p> <pre><code>import Data.Array fbs :: Int -> Int -> Int -> [Int] fbs m n k = m : n : map (fbm m n k) [2 .. k] fbsArr :: Int -> Int -> Int -> Array Int Int fbsArr m n k = listArray (0, k) (fbs m n k) fbm :: Int -> Int -> Int -> Int -> Int fbm m n k i | (i `div` 2) `mod` 2 == 1 = (xs ! (i - 1)) + (xs ! (i - 2)) | otherwise = (xs ! (i - 1)) - (xs ! (i - 4)) where xs = fbsArr m n k </code></pre> <p>It's nearly the same as the first one, but this time the results are memoised in an array and indexing its elements is significantly faster. According to my tests it generates answers for <code>(m, n, k) = (2, 3, 1000)</code> over 10 times faster than the list-based approach. The answer in this case is <code>fbsArr m n k ! k</code>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload