When performance matters
Linked Lists, Double Linked Lists, Arrays, Queues, Stacks… the data structures go on and on, but don’t they all do pretty much the same thing? If you’re like me you probably don’t worry about which you use most the time. Just use whatever is convenient at the time, in C-like languages this will usually be an array, in Functional Languages a List (I believe they use linked lists by default).
Usually the defaults are fine, I mean how much difference could it really make? I didn’t think it would be too much, maybe a couple seconds until my recent experience with Project Euler 78.
Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can separated into piles in exactly seven different ways, so p(5)=7.
OOOOO
OOOO O
OOO OO
OOO O O
OO OO O
OO O O O
O O O O OFind the least value of n for which p(n) is divisible by one million.
After a lot of research I came across the pentagonal number theorem. (I’m not one of those people who think you need to derive everything yourself, the only thing I care about is that I understand exactly what I’m doing)
The formulation of Euler’s generating function is a special case of a q-Pochhammer symbol and is similar to the product formulation of many modular forms, and specifically the Dedekind eta function. It can also be used in conjunction with the pentagonal number theorem to derive a recurrence for the partition function stating that:
p(k) = p(k − 1) + p(k − 2) − p(k − 5) − p(k − 7) + p(k − 12) + p(k − 15) − p(k − 22) − …
where the sum is taken over all generalized pentagonal numbers of the form ½n(3n − 1), for n running over positive and negative integers: successively taking n = 1, -1, 2, -2, 3, -3, 4, -4, …, generates the values 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, …. The signs in the summation continue to alternate +, +, −, −, +, +, …
source:wikipedia
I’m far from a mathematician so I had to dig around to understand exactly what was happening here (including looking at other code) and came up with the following program.
module Euler78
where
pent = let p n = (n * ((3*n) - 1)) `div` 2
in map (p) (concat [[i , (-i)] | i < - [1..]])
p = let part 0 = 1
part 1 = 1
part n = sum $ zipWith (*) [p (n-k) | k <- takeWhile (<=n) pent] (cycle
in ((map (part) [0..]) !!)
main78 :: IO ()
main78 = do print $ head $ filter (\x -> (p x) `mod` 10^6 == 0) [1..]
> ghc --make Main.hs -o out/e78
> time out/e78
real 277m16.556s
user 276m26.416s
sys 0m41.162s
(Main.hs contains code that executes main78, and yes I know it’s not the best configuration)
277 minutes!!!
I know this was the most efficient algorithm for finding the partitions so why was it taking 3 and 1/2 hours?? It got the right answer but it should be under 1min. Curious I downloaded the source code for another solution in Haskell (should look similar, It is what I used to wrap my head around what Wikipedia was saying). Here is the
source.
> ghc --make Main.hs
> time ./Main
real 0m49.656s
user 0m49.432s
sys 0m0.134s
Looks like I really screwed that up. Comparing the source the only large difference is the memoization of the partitions, their code imports Array just to store the results whereas mine uses a list. By default Haskell uses a linked list. To figure out where the time difference is coming from lets look at the Wikipedia articles for Linked List (yes I use Wikipedia a lot):
The principal benefit of a linked list over a conventional array is that the order of the linked items may be different from the order that the data items are stored in memory or on disk. For that reason, linked lists allow insertion and removal of nodes at any point in the list, with a constant number of operations.
On the other hand, linked lists by themselves do not allow random access to the data, or any form of efficient indexing. Thus, many basic operations — such as obtaining the last node of the list, or finding a node that contains a given datum, or locating the place where a new node should be inserted — may require scanning most of the list elements.
In summary-
Linked List: Easy insertion and removal, slow access to random elements
Array: Slow Insertion and removal, fast access to random elements
When we try to access
p (n-k)
we are access a random element and with a linked list it will have to traverse from the very beginning to find the element. When replaced by an array the function can access the element directly without traversal. With so many calls to p that could definitely add up to some time, by it can be hard to believe it could increase the speed of the program by almost 300x. Regardless let’s try it just to see what happens.
module Euler78
where
import Data.Array
pent = let p n = (n * ((3*n) - 1)) `div` 2
in map (p) (concat [[i , (-i)] | i <- [1..]])
p = let part 0 = 1
part 1 = 1
part n = sum $ zipWith (*) [p (n-k) | k <- takeWhile (<=n) pent] (cycle
in ((listArray (0,10^6) (map (part) [0..])) !)
main78 :: IO ()
main78 = do print $ head $ filter (\x -> (p x) `mod` 10^6 == 0) [1..]
> ghc --make Main.hs -o out/e78 > time out/e78 real 0m59.389s user 0m57.495s sys 0m1.211s
Nice that is exactly what I was thinking for. The 300x change with an import and 1 line changed.
Right now the more experienced programmers are thinking “Duh, you should have had an array from the very start”. Unfortunately, we’re not all expert programmers and don’t realize how much it really matters.
This program really opened my eyes to performance of data structures, you can read about the efficiency of data structures all you want but the only way to really get it is to see it used in an actual program. Hopefully this will help a couple others realize the same.
