For my Node.js application I need to choose the best performing structure to represent a grid.
My requirements/limitations are:
- The grid to store is two-dimensional by nature (x, y) and not very large (100-300 cells)
- Some cells in the grid contain nothing, i.e. the grid will be empty for up to 25%
- I will have to address the grid very often. I'll need to do some heavy algorithms to the grid, like flood-fill, A* pathfinding and some more
- This will be a repetitive simulation process of changing the grid and applying the algorithms again
- I aim at hundreds of simulations in a limited time, so every millisecond matters
- I do not care about readability of the code
- Amount of memory used is also a minor concern
- Switch to another programming language is not possible
I've been choosing between three options:
var grid = [height][width];
grid[y][x] = {};
var grid = [height * width];
grid[y * height + x] = {};
var y = ~~(index % height);
var x = index - height * y;
var grid = [];
var key = x + ',' + y;
grid[key] = {};
The first one is the most comfortable as I will manipulate the coordinates a lot, meaning x and y will be handy all the time. Possible disadvantage - I've read it could be much slower when holding objects in comparison to 1D array.
The second is fine and probably very fast. But I will need to convert index to x and y and vice versa which is extra calculations involving modulo for index to coords conversion. Still I see this approach in many good sources.
The third way is new to me but I've seen it in some robust code examples and I've read that retrieving an object from hash table can be faster in comparison to 2D array as well.
I do not trust synthetic benchmarks too much so I do not wish to set up a code competition with almost empty logic so far. But I'm afraid it will be a very long way back if I pick a wrong way now and then will have to revert.
I've seen similar questions asking about different pairs of these methods, but none of them reflects my requirements close enough.
Thank you for your considerations with code samples.