Hi! What's the complexity of indexing arrays in Haskell? The Data.Array documentation doesn't seem to mention complexity of any of its functions, and it's not obvious to me how to implement an array data structure with indexing being O(1). -- Mvh Øystein Kolsrud
On 05/10/11 03:51, Øystein Kolsrud wrote:
Hi! What's the complexity of indexing arrays in Haskell? The Data.Array documentation doesn't seem to mention complexity of any of its functions, and it's not obvious to me how to implement an array data structure with indexing being O(1).
Compilers implement special representation of arrays (an array in memory, rather as you might expect), so indexing is O(1). The price you pay is that array *updates* are O(n) even if you're only changing one element. It has to copy the whole thing in order to leave the original unmodified. (There are also mutable arrays that are more annoyingly imperative to use, Data.Map which has good enough performance for a lot of purposes, etc.)
On Tuesday 10 May 2011 09:51:21, Øystein Kolsrud wrote:
Hi! What's the complexity of indexing arrays in Haskell? The Data.Array documentation doesn't seem to mention complexity of any of its functions, and it's not obvious to me how to implement an array data structure with indexing being O(1).
For the array types provided by the array package (Array, UArray, STArray, STUArray, IOArray, IOUArray), indexing is O(1) [for reasonable index types¹]. Implementing such a data structure with O(1) indexing of course requires to go low-level, for the payload, you need a contiguous chunk of memory where either the pointers to the data are stored (boxed arrays) or the raw data themselves (unboxed arrays). Then indexing is "read size bytes from address (start + index*size)", just like in C or similar. Of course there's bounds- checking and computing the effective index from the programmer-visible, but for reasonable index types, that is O(1) too. ¹ You could of course make an Ix instance for e.g. lazy Peano numbers, then indexing would become O(index).
Thanks for the quick responses! I don't have a particular application
where this was a concern, I was just curious.
Best regards, Øystein Kolsrud
On Tue, May 10, 2011 at 9:51 AM, Øystein Kolsrud
Hi! What's the complexity of indexing arrays in Haskell? The Data.Array documentation doesn't seem to mention complexity of any of its functions, and it's not obvious to me how to implement an array data structure with indexing being O(1). -- Mvh Øystein Kolsrud
participants (3)
-
Daniel Fischer -
Isaac Dupree -
Øystein Kolsrud