DEV Community

loading...

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

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
Enter fullscreen mode Exit fullscreen mode
[['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*']]
Enter fullscreen mode Exit fullscreen mode

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

gameboard[0][5] = "P1"
gameboard[7][3] = "P2"
gameboard
Enter fullscreen mode Exit fullscreen mode
[['*', '*', '*', '*', '*', 'P1', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', '*', '*', '*', '*', '*'],
 ['*', '*', '*', 'P2', '*', '*', '*', '*']]
Enter fullscreen mode Exit fullscreen mode

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"
}

Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode
 *  *  *  *  *  *  *  * 
 *  *  *  *  * P1 *  * 
 *  *  *  *  *  *  *  * 
 *  *  *  *  *  *  *  * 
 *  *  *  *  *  *  *  * 
 *  *  *  *  *  *  *  * 
 *  *  *  *  *  *  *  * 
 * P2 *  *  *  *  *  * 
Enter fullscreen mode Exit fullscreen mode

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

render_board(players, 7,7)
Enter fullscreen mode Exit fullscreen mode
 *  *  *  *  *  *  * 
 *  *  *  *  * P1 * 
 *  *  *  *  *  *  * 
 *  *  *  *  *  *  * 
 *  *  *  *  *  *  * 
 *  *  *  *  *  *  * 
 *  *  *  *  *  *  * 
Enter fullscreen mode Exit fullscreen mode

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,".")
Enter fullscreen mode Exit fullscreen mode
............................................................
.....P1......................................................
............................................................
............................................................
............................................................
............................................................
............................................................
.P2..........................................................
............................................................
............................................................
............................................................
............................................................
............................................................
............................................................
............................................................
............................................................
............................................................
............................................................
............................................................
............................................................
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode
  • 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 (0)