DEV Community

loading...

Cheap representation of sparse matrix in Python (or any other language)

hanpari profile image Pavel Morava ・2 min read

Consider gameboard 8x8 fields. How would you represent it?
What about the most usual and memory most hungry solution ever? Array of arrays, right? Or list of lists in Python.

gameboard = [8 * ["*"] for _ in range(8)]
gameboard
[['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*']]

Now we can add two player P1 and P2 to have some fun, right?

gameboard[0][5] = "P1"
gameboard[7][3] = "P2"
gameboard
[['*', '*', '*', '*', '*', 'P1', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', 'P2', '*', '*', '*', '*']]

Would you guess what is wrong here?

For instance, imagine you would like to create the 2-dimensional vast world where players may roam free.

You dont want to end up allocating 1M * 1M grid for mere two players. It is pretty stupid, isnt it?
Can we do any better, though?

Yep, we certainly can.

players = {
    (1,5): "P1",
    (7,1): "P2"
}

That's it! You don't need more. Just two records to store coordinates and player's attributes. In this particular case, I just (ab)used dictionairy because I was too lazy to make special class.

You can render your board in one go:

def render_board(players, width=8, height=8, empty_field=" * "):
    for x in range(height):
        for y in range(width):
            character = players.get((x,y), empty_field)
            print(character, end="")
        print()
render_board(players=players)
 *  *  *  *  *  *  *  * 
 *  *  *  *  * P1 *  * 
 *  *  *  *  *  *  *  * 
 *  *  *  *  *  *  *  * 
 *  *  *  *  *  *  *  * 
 *  *  *  *  *  *  *  * 
 *  *  *  *  *  *  *  * 
 * P2 *  *  *  *  *  * 

You can even clip your view. See, Player2 is out of view here.

render_board(players, 7,7)
 *  *  *  *  *  *  * 
 *  *  *  *  * P1 * 
 *  *  *  *  *  *  * 
 *  *  *  *  *  *  * 
 *  *  *  *  *  *  * 
 *  *  *  *  *  *  * 
 *  *  *  *  *  *  * 

And now for something more massive. Or perhaps not so massive since I dont intend to make your screen dotted for too many pages.

render_board(players, 60,20,".")
............................................................
.....P1......................................................
............................................................
............................................................
............................................................
............................................................
............................................................
.P2..........................................................
............................................................
............................................................
............................................................
............................................................
............................................................
............................................................
............................................................
............................................................
............................................................
............................................................
............................................................
............................................................

By now, you should get the idea. If you got intrigued, you may want to play a little by encapsulating the gameboard into a separated class, with some graphical interface to have more fun.

Questions

  • Why did I bother with list comprehension on the beggining instead simple?
[["*"] * 8 ] * 8
  • For coordinates in my dict, I used tuple, not list. Why?
  • What is the meaning of print("*", end="")? Why I had to use it instead simple print("*")
  • I wrote this article in jupyterlab? What is it?
  • What the is the sparse matrix we are talking about?

Write your answers in the comment section.

Final words

I hope you have enjoyed this article. If you crave something completely different, you may want to read my online novel Sovereign

Discussion

pic
Editor guide