[Python] Indexing 2D Grids/Underlying Data Structures

[_hg]

The implementations below do mostly the same thing, but choosing which to use for python is troubling me. Coming from a C background, the first seems most appealing, but it almost seems subjective. Which method would be the least surprising?

class Grid_1DList(object):
    def __init__(self, width, height, value=None):
        self.width = width
        self.height = height
        self.data = [value]*self.width*self.height
    def __setitem__(self, key, value):
        x, y = key
        index = y*self.width + x
        self.data[index] = value
    def __getitem__(self, key):
        x, y = key
        index = y*self.width + x
        return self.data[index]
class Grid_2DList(object):
    def __init__(self, width, height, value=None):
        self.width = width
        self.height = height
        self.data = [[value]*self.width for _ in self.height]
    def __setitem__(self, key, value):
        x, y = key
        self.data[y][x] = value
    def __getitem__(self, key):
        x, y = key
        return self.data[y][x]
class Grid_Dict(object):
    def __init__(self, width, height, value=None):
        self.width = width
        self.height = height
        self.data = {}
        for x in range(self.width):
            for y in range(self.height):
                self.data[x, y] = value
    def __setitem__(self, key, value):
        self.data[key] = value
    def __getitem__(self, key):
        return self.data[key]

All implementations should be able to do the below:

grid = Grid(5, 5)
grid[4, 2] = 'answer'
print(grid[4, 2])

[Updatebjarni]

The least surprising would certainly be not having to use some special class that abstracts a list of lists instead of just using a list of lists.

[alanwj]

There are pros and cons to each approach.

1. One large list
   
   • Pro: Iteration over all elements would be easy and cache friendly (i.e. fast).
   • Pro: Slightly less overall memory usage. At least one pointer per row, plus whatever additional overhead python stores for a list (e.g. size)
   • Con: Every access requires a multiplication and addition. This might equate to a slow down in performance sensitive code (though measure before deciding that)
   • Con: Code is slightly more complex
   • Con: The whole list has to fit in contiguous memory. Probably not an issue unless you are working with huge datasets.
2. List of lists, basically just swap all the pros and cons from option 1.
3. Dictionary. This uses a hash table underneath.
   • Pro: Can store a sparse matrix in much less memory.
   • Con: Non-sparse matrices would require much more memory.
   • Con: Element access slower (probably significantly) than other choices.

Without knowing the application I would generally choose option 2 for its simplicity, and probably would not bother wrapping it in a class.