List-of-Lists Test

To see more JOM Software applications, click here.

t_lol.py (v1.0)

## Version History

Version 1.00, release date 2008-11-13.

• First release
• Tested with N82 (PyS60 1.4.3), N96-1 (pyS60 1.4.4) and E61i (pyS60 1.4.4).

## Introduction

Games quite often require list of lists i.e. matrixes to save and manipulate data. There are several ways to implement such and, as a very experienced expert, I always knew exactly which way was the most efficient way.

Oh, I so hate to be wrong! Especially since I was so certain that I was right, just based on my very experienced gut feeling. Who can you trust, if not your guts?

During latest flu season I wasn't able to do much but think. So I thought about one certain game, which I have never played much, which doesn't interest me too much, but which has been huge success all over the world. There was sample code which kept crashing and which I couldn't "read" too well. It got me interested in this test sample.

This night I was recovered enough to write a small test to compare three different ways to access a single random tile inside a matrix. The result was big surprise to me, since the method I had preferred seems to be the slowest!

## List of Lists

T1 is matrix based on dictionary. This is the reason, which got me interested in performance testing. I had never seen anything like that before.

a[(x,y)] = 1

T2 is the way I used to prefer, one simple list where you access a tile with calculated offset. It does have performance advantages, when you handle tiles in rows - or so I still believe :)

b[x + y*dim_x] = 1

T3 is "normal" matrix, a list of lists. I always thought it would be slow or at least not the fastest.

c[x][y] = 1

## Results

 E61i N82 N96-1 x=10, y=20 T1: 0.015625 T1: 0.000000 T1: 0.000000 T2: 0.000000 T2: 0.000000 T2: 0.000000 T3: 0.000000 T3: 0.000000 T3: 0.015625 x=25, y=50 T1: 0.031250 T1: 0.046875 T1: 0.015625 T2: 0.031250 T2: 0.031250 T2: 0.015625 T3: 0.031250 T3: 0.000000 T3: 0.015625 x=100, y=200 T1: 0.406250 T1: 0.343750 T1: 0.312500 T2: 0.515625 T2: 0.390625 T2: 0.359375 T3: 0.328125 T3: 0.234375 T3: 0.218750 x=250, y=500 T1: 2.781250 T1: 2.218750 T1: 1.984375 T2: 3.453125 T2: 2.656250 T2: 2.250000 T3: 2.296875 T3: 1.640625 T3: 1.437500

## Disclaimers

Disclaimer1: test code was not optimized at all, it's just accessing all tiles in same way. In real life, for example Unity and Mazing Days, I have optimized cases where tiles are accessed one row at a time. Random access is very common use case, but in certain type of games sequential access can be more useful.

Disclaimer2: in real life matrixes are often small and performance differences between these methods are minimal. It's better to use something which you are familiar with than to experiment blindly.