Performant data structure for a table (think 2D array or list of lists)

People very frequently use maps where the key is a tuple of coordinates, and the value is the value at that coordinate. IE:

%{
  {0, 0} => 1,
  {0, 1} => 2,
}

Sounds good but I think in my case would only make sense if it is fast to get all the keys for a given row or column.

in your example:

%{
{0, 0} => 1,
{0, 1} => 2,
}

I’d possible like to get all the elements in column 1, for instance, ideally something like:

Map.get(map, {_, 1})

But it does not seem to be possible, it says _ is an unbound variable.

Extracting a single row or column I think is most efficient by using Enum.filter/2. This would make extracting a single column or row O(row * colums) though.

If you really need O(1) access to a complete row or column randomly, I do think, that a doubled DS would be the only thing to go, but it does double the amount of memory needed to hold the structure, also it makes writes expensive since they had to be done twice.

Basically you need to two nested maps %{row_id => %{col_id => data_sample}} and %{col_id => %{row_id => data_sample}}.

Yeah the duplication is definitely a possibility. Fortunately this is less duplication than it may look at first glance because cell values are just pointed to by each map location, not actually duplicated.

:ets could be another possibility because it does support a {_, 1} style match operation.

FWIW even traditional mutable 2d arrays suffer from this question. If you make row access primary then column access requires large jumps in memory which eats away at any cache locality you may have gotten with row access.

Okay, maybe I am not getting something very important here, but are you not, in essence, needing a simple two-dimensional array?

You probably are missing that there are no arrays in elixir.

But there are tuples with arbitrary sizes. And you have native functions to deal with them.

My point was that you could simulate any dimension of array in the single-dimensional tuple. I understand it’s not practical for changing data however.

Tuples must be wholly copied on every update. The OP mentioned that updates are common which generally disqualifies large tuples.

Yep. Seems like a managed data structure is in order. Probably list (or tuple) of tuples with a maximum size (probably 64).

Sorry that I can’t be more helpful.

The erlang :array module already does that tuple managing for very fast row access. I’d say use it, it is well tested.

For note, maps are ‘almost’ on par with :array in speed in almost all cases (sometimes even a bit faster) except iteration, which sounds like it might be something you need.

Overall though I’d say use maps, and if you setup your key just right then iteration can be very fast too.