I'm playing with Haskell and Project Euler's 23rd problem. After solving it with lists I went here where I saw some array work. This solution was much faster than mine. So here's the question. When should I use arrays in Haskell? Is their performance better than lists' and in which cases?
Add a comment
|
3 Answers
The most obvious difference is the same as in other languages: arrays have O(1) lookup and lists have O(n). Attaching something to the head of a list (:) takes O(1); appending (++) takes O(n).
Arrays have some other potential advantages as well. You can have unboxed arrays, which means the entries are just stored contiguously in memory without having a pointer to each one (if I understand the concept correctly). This has several benefits--it takes less memory and could improve cache performance.
Modifying immutable arrays is difficult--you'd have to copy the entire array which takes O(n). If you're using mutable arrays, you can modify them in O(1) time, but you'd have to give up the advantages of having a purely functional solution.
Finally, lists are just much easier to work with if performance doesn't matter. For small amounts of data, I would always use a list.
2 Comments
Dan Burton
I tend to agree: use lists unless you need the speed. Haskell's built-in lists are very noob-friendly, due to the ability to pattern match on the two constructors that define a list: the empty list, and the non-empty list.
Tikhon Jelvis
@DanBurton: Definitely. Also, maybe just because I learned Scheme at the same time as Haskell, I find lists more amenable to the functional programming style. Writing recursive functions, for example, is much easier with lists in most langauges.
And if you're doing much indexing as well as much updating,you can
- use
Maps (orIntMaps), O(log size) indexing and update, good enough for most uses, code easy to get right - or, if
Maps are too slow, use mutable (unboxed) arrays (STUArrayfromData.Array.STor STVectors from the vector package; O(1) indexing and update, but the code is easier to get wrong and generally not as nice.
For specific uses, functions like accumArray give very good performance too (uses mutable arrays under the hood).
Comments
Arrays have O(1) indexing (this used to be part of the Haskell definition), whereas lists have O(n) indexing. On the other hand, any kind of modification of arrays is O(n) since it has to copy the array. So if you're going to do a lot of indexing but little updating, use arrays.
