1

So I currently have a 2d list of objects that define the map of a game where each object represents a tile on that map. As I was repurposing the code for something else, I wondered if it would make more sense to use a dictionary to store the map data or to continue using a list. With a list, the indices represent the x and y of the map, whereas in a dictionary, a (x,y) tuple would be the keys for the dictionary.

The reason I ask is because the map changing is a rare event, so the data is fairly static, and as far as i know, the fairly constant lookups will be faster in dictionaries. It should also simplify looping through the map to draw it. Mostly I think using dictionaries will simplify accessing the data, though I'm not sure that will be the case in all cases.

Are these benefits worth the additional memory that I assume the dictionary will take up? or am I even right about the benefits being benefits?

EDIT I know that the current method works, its was moreso to whether or not it would make sense to switch in order to have cleaner looking code and to find any potential drawbacks. Stuff like looping through the array would go from something like 

for i in range(size[0]):
    for e in range(size[1]):
        thing.blit(....using i and e)

to 

for i, e in dict.items():
    i.blit(....using i and e)

or looking up a dict item would be 

def get(x, y):
    if (x in range(size[0])) and (y in range(size[1])):
        return self.map[x][y].tile

to 

def get(item):
    return self.dict.get(item)

its not much, but its somewhat cleaner, and if its not any slower and there are no other drawbacks i see no reason not to.

DanielCardin
  • 545
  • 2
  • 8
  • 17
  • I would also consider using a graph with nodes that have properties that include am x/y (or similar) coords, objects for that tile, and edges that represent tiles that can be moved from/to. Possibly also consider the edges with weights so that moving from grassland through a swamp/river etc.. is harder than moving to another grassland... – Jon Clements Jan 24 '13 at 22:27

3 Answers3

2

I would be wary of premature optimization.

Does your current approach have unacceptable performance? Does the data structure you're using make it harder to reason about or write your code?

If there isn't a specific problem you need to solve that can't be addressed with your current architecture, I would be wary about changing it.

Brenden Brown
  • 3,125
  • 1
  • 14
  • 15
  • Like I said, i'm repurposing this map structure for something else, so architectural changes dont really matter at this point. Yes the existing solution works, but I think I see some advantages that dictionaries might lend, though I dont want to switch if it's going to make it run noticeably worse for some reason, or if there is some other thing that I'm not thinking of that might make using a dictionary undesirable in the long run – DanielCardin Jan 24 '13 at 20:47
  • My point is, unless there's a performance problem, or you'll be handling such large amounts of data that even a small perf difference will matter, choose the architecture that is conceptually cleanest, not the most performant. – Brenden Brown Jan 24 '13 at 21:26
  • yea, that's why I added to the question. It's conceptually cleaner in how I envision myself using it, but if you or anyone else see's a potential flaw like "sure that will work, but if you want to do a loop around the perimeter it will be much harder to do because of a and b" (not that that would actually be a problem) then I would be happy to hear it. – DanielCardin Jan 24 '13 at 21:53
  • That clarifies your question greatly. You might also want to post on the Code Review site. The only drawback I can imagine is that it might be harder to compare a given tile to nearby tiles, since the list slicing syntax makes that so easy. I can expand on that if you'd like. – Brenden Brown Jan 24 '13 at 22:07
  • My first thought when you say that is something like tiles[i-1:i+1][e-1:e+1], but I'm not sure if that would even work (logically, that would make a 3x3 list) – DanielCardin Jan 24 '13 at 23:00
  • given a tile x,y, to get all tiles within a,b of that, would be something like `[tile for tile in second[y-b:y+b] for second in first[x-a:x+a]]`. I'm not sure how it would be done with a dict. – Brenden Brown Jan 25 '13 at 02:25
  • it would be more complicated, but you could use that to generate the tuple of indices and then iterate through an array of tuples. If that's all you can think of, then ill probably go with the dicts because they make for clearer syntax from what im seeing right now – DanielCardin Jan 25 '13 at 02:37
0

This is a good answer to reference about the speed and memory usage of python lists vs dictionarys: https://stackoverflow.com/a/513906/1506904

Until you get to an incredibly large data set it is most likely that your current method, if it is working well for you, will be perfectly suitable.

Community
  • 1
  • 1
EEP
  • 715
  • 1
  • 4
  • 17
0

I'm not sure that you'll get "the right" answer for this, but when I created the *Game of Life *in Python I used a dict. Realistically there should not be a substantial difference between the lookup cost of multi-dimensional lists and the lookup cost in a dict (both are O(1)), but if you're using a dict then you don't need to worry about instantiating the entire game-board. In chess, this means that you are only creating 32 pieces instead of 64 squares and 32 pieces. In the game of Go, on the other hand you can create only 1 object instead of 361 list-cells.

That said, in the case of the dict you will need to instantiate the tuples. If you can cache those (or only iterate the dict's keys) then maybe you will get the best of all worlds.

cwallenpoole
  • 79,954
  • 26
  • 128
  • 166
  • In my case none of the tiles would be dataless because they contain tileset information, so I would have to instantiate the entire rectangle – DanielCardin Jan 24 '13 at 21:19