[erlang-questions] 2D Map Arrays

Heinrich Venter heinrich@REDACTED
Mon Sep 11 09:43:47 CEST 2006


I tinkered around with a similar design a while ago.

In the end I built some tests to compare different approaches.  If you
only need to read elements, you can probably get away with a tuple of
tuples, or a large binary  with some indexing logic.  If you need to do
writes too things change drastically.
I wrote a binary based read only test and an ets based one.  The binary
outperformed the ets table by a factor of 3.  However when writes were
done, the ets solution outperformed the binary one by a factor of about
10 and also used less memory.

I did not test a binary vs tuple solution tho.  The drawback of the
binary solution is that you have to know the size of your data element
in bytes for the logic to work.  

Consider this:  If you use a tuple based solution you have some options
on how you partition it.
Say you have a 10x10 array.  You could store it as a single tuple with
100 elements and use I=(Row*10+Col) to get the correct index for
element(I,Map).
You could also make it a tuple of 10 row tuples so that the access
becomes element(Col,element(Row,Map))
But why stop there, why not break it up further into regions for a
quad-tree type structure?
If you break it up fine enough you will end up with something that looks
almost like an ets table where each element has the form {{X,Y},Data}.
So in the end ets will probably give you the most bang for your buck.

-]-[




More information about the erlang-questions mailing list