python 3.x: which is more efficient: list of lists vs. dict?

Question

Imaging you are doing a BFS over a grid (e.g. shortest distance between two cells). Two data structures can be used to host the visited info:

1) List of lists, i.e. data = [[False for _ in range(cols)] for _ in range(rows)]. Later we can access the data in a certain cell by data[r][c].

2) Dict, i.e. data = dict(). Later we can access the data in a certain cell by data[(r, c)].

My question is: which is computationally more efficient in such BFS scenario?

Coding wise it seems the dict approach saves more characters/lines. Memory wise the dict approach can potentially save some space for untouched cells, but can also waste some space for hashtable's extra space.

EDIT

@Peteris mentioned numpy arrays. The advantage over list of lists is obvious: numpy arrays operate on continuous blocks of memory, which allow faster addressing and more cache hits. However I'm not sure how they compare to hashtables (i.e. dict). If the algorithm touches relatively small number of elements, hashtables might provide more cache hits given it's potentially smaller memory footprint.

Also, the truth is that numpy arrays are unavailable to me. So I really need to compare list of lists against dict.

Answer 1

A 2D array

The efficient answer to storing 2D data is 2D arrays/matrixes allocated into a continuous area of memory (not like a list of lists). This avoids the multiple memory lookups required otherwise, and the calculation of a hash value at every lookup that's needed for a dict.

The standard way to do this in python is with the numpy library, here's a simple example

import numpy as np
data = np.zeros( (100, 200) ) # create a 100x200 array and initialize it with zeroes
data[10,20] = 1  # set element at coordinates 10,20 to 1