In the past, I've had alot of success just using a .NET
Dictionary, with a
TKey consisting of the X,Y coordinates merged together. However its read performance, despite being amortized constant time, is a bottleneck in a design of mine.
My application needs to perform alot of reads, and would benefit greatly if the performance of the read was similar to that of an array. My data has a very high degree of spatial locality; attached is an image showing two graphs of the distribution of some sample data on a 2D plane (sorry for the lack of labels); on the left is data with low spatial locality, and on the right is how my data looks (it's always a single connected mass, and blocky in form).
I could use an array (by computing a bounding rectangle (
bRect) around the data and then doing
data=array[(y-bRect.Top)*bRect.Height+x-bRect.Left]) but then I'd have to rebuild the entire array each time
bRect.Height changed, or
And so my question is, given the high degree of spatial locality, is
Dictionary really the best choice here? Is there another approach I could take where I could get near array like read performance, yet not have to rebuild the array when data is added? (I don't need to ever remove data)