What is the most efficient implementation of array

Question

I need an array-like data structure with the fastest possible functional update. I've seen a few different implementation of flexible arrays that provide me with this property (Braun, Random Access Lists) but I'm wondering if there is an implementation that is specifically optimized for the case when we are not interested in append or prepend - just updates.

Answer 1

Which language are you using? In Haskell you can use mutable arrays with the state monad, and in Mercury you can use mutable arrays by threading the IO state. Ocaml also has an array module, which unfortunately does not maintain referential transparency, if that is what you are after.

Answer 2

I have a very good experience with repa (nice demo). Very good performance, automatic parallelism, multidimensional, polymorphic. Recommended to try.

Answer 3

I also needed functional arrays and felt on this SO question some days ago. I was not satisfied with the solution proposed by Gasche as creating a new array is a costly operation and I need to access older versions of array quite frequently (I plan to use this for an AI alpha/beta implementation playing on an array).

(When I say costly, I guess it is O(n*h) where h is the history size because in the worst case only one cell was updated repeatedly and it is needed to go through the whole update list for each cell. I also expect most of the cells not being updated when I need to reroute the array).

This is why I propose another approach, maybe I can get some feedback here. My idea is to store the array like in a B-Tree, except that as it is not mutable, I can access and update any value by index quite easily.

I wrote a small introduction on the project's repository : https://github.com/shepard8/ocaml-ptarray. The order is chosen so as to even depth and order of the tree, so I can get nice complexities depending only on the order for get/set operations, namely O(k^2).

With k = 10 I can store up to 10^10 values. Actually my arrays should not contain more than 200 values but this is to show how robust my solution is intended to be.

Any advice welcome!

Answer 4

Jean-Cristophe Filliâtre has a very nice implementation of persistent arrays, that is described in the paper linked at the same page (which is about persistent union-find, of which persistent arrays are a core component). The code is directly available there.

The idea is that "the last version" of the array is represented as an usual array, with O(1) access and update operations, and previous versions are represented as this last version, plus a list of the differences. If you try to access a previous version of the structure, the array is "rerooted" to apply the list of differences and present you again the efficient representation.

This will of course not be O(1) under all workflows (if you constantly access and modify unrelated versions of the structure, you will pay rerooting costs frequently), but for the common workflow of mainly working with one version, and occasionally backtracking to an older version that becomes the "last version" again and gets the updates, this is very efficient. A very nice use of mutability hidden under a observationally pure interface.